Improved Multi-Agent System for the Vehicle Routing Problem with Time Windows

被引：8

作者：

但正刚 ^{[1
]}

蔡临宁 ^{[1
]}

郑力 ^{[1
]}

机构：

[1] Department of Industrial Engineering, Tsinghua University,Beijing 100084, China

来源：

Tsinghua Science and Technology | 2009年 / 14卷 / 03期

关键词：

vehicle routing problem with time window; multi-agent system; improved contract-net protocol;

D O I：

暂无

中图分类号：

U116.2 [运输线路优选];

学科分类号：

08 ; 0823 ;

摘要：

The vehicle routing problem with time windows (VRPTW) involves assigning a fleet of limited capacity vehicles to serve a set of customers without violating the capacity and time constraints. This paper presents a multi-agent model system for the VRPTW based on the internal behavior of agents and coordination among the agents. The system presents a formal view of coordination using the traditional contract-net protocol (CNP) that relies on the basic loop of agent behavior for order receiving, order announcement, bid calculation, and order scheduling followed by order execution. An improved CNP method based on a vehicle selection strategy is used to reduce the number of negotiations and the negotiation time. The model is validated using Solomon’s benchmarks, with the results showing that the improved CNP uses only 30% as many negotiations and only 70% of the negotiation time of the traditional CNP.

引用

页码：407 / 412

页数：6

共 6 条

[1] Multi-objective genetic algorithms for vehicle routing problem with time windows [J].

Ombuki, B ;

Ross, BJ ;

Hanshar, F .

APPLIED INTELLIGENCE, 2006, 24 (01) :17-30

[2]

Decentralized Probabilistic Algorithm Using a Multi-Agent System for Vehicle Routing Problems[J] . Ichiro Shigaki,Masami Konishi.International Journal of Smart Engineering System . 2003 (4)

[3]

Local search in routing problems with time windows[J] . M. W. P. Savelsbergh.Annals of Operations Research . 1985 (1)

[4]

Vehicle routing problem with time windows.PartⅡ:Metaheuristics .2 Braysy O,Gendreau M. Transportation Science . 2005

[5]

Negotiation as a metaphor for distributed problem solving .2 Davis R,Smith RG. Artificial Intelligence . 1983

[6]

Algorithms for the vehicle routing and scheduling problems with time window constraints .2 Solomon M M. Operations Research . 1987

← 1 →