A multi-agent algorithm for vehicle routing problem with time window

ABSTRACT

Many existing algorithms for solving the vehicle routing problem with time windows (VRPTW) first construct initial tours and then apply a tour optimization algorithm to refine the solution. In this two-stage approach, the tour optimization stage is often hampered by the tour construction phase that produce initial solutions that are skewed, namely, the initial tours are very good, but the later tours are often very poor. This often leads to difficulties in the tour-optimization stage that often get trapped in local optimal quickly. In this paper, we propose a new multi-agent algorithm for solving the VRPTW that involves the uses a distributed, multi agent approach for the tour-optimization phase. Our approach can be considered as a combination of multi-agent system and heuristic local search. A prototype system has been developed and extensive experimentation on the Solomon benchmarks show that our multi-agent approach is effective and has comparable performance to the best results in the literature.

REFERENCES

• 1: Chiang, W. C. and Russel, R. A. (1996), "Simulated Annealing Metaheurstics for the Vehicle Routing Problem with Time Windows", Annals of Operations Research, Vol. 63, 1996, pp. 3--27.
• 2: Stan Franklin , Art Graesser, Is it an Agent, or Just a Program?: A Taxonomy for Autonomous Agents, Proceedings of the Workshop on Intelligent Agents III, Agent Theories, Architectures, and Languages, p.21-35, August 12-13, 1996
• 3: L. M. Gambardella , E. Taillard , G. Agazzi, MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, 1999
• 4: Yizhi Lao , Hon-Wai Leong, A Multi-agent Based Approach to the Inventory Routing Problem, Proceedings of the 7th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, p.345-354, August 18-22, 2002
• 5: Potvin, J. Y. and Rousseau, J. M. (1995), "An Exchange Heuristic for Routing Problems with Time Windows", Journal of the Operational Research Society, Vol. 46, 1995, pp. 1433--1446.
• 6: Michael Schumacher, Objective coordination in multi-agent system engineering: design and implementation, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 7: M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, v.35 n.2, p.254-265, March-April 1987
• 8: Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J. Y. (1997), "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows", Transportation Science, Vol. 31, No. 2, 1997, pp. 170--186.
• 9: Thangiah, S. R. (1993) Vehicle Routing with Time Windows Using Genetic Algortithms. "Applications Handbook of Genetic Algortihms: New Frontiers", 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Keywords:
multi-agent algorithm, vehicle routing problem (VRPTW)