An Agent-Based Approach to Vehicle Routing Problem

The paper proposes and validates a new method of solving instances of the vehicle routing problem (VRP). The approach is based on a multiple agent system paradigm. The paper contains the VRP formulation, an overview of the multiple agent environment used and a description of the proposed implementation. The approach is validated experimentally. The experiment plan and the discussion of experiment results follow.

• Dariusz Barbucha
• Piotr Jedrzejowicz

• multi-agent systems
• population-based methods
• vehiclerouting problem.

<p>[1] M.E. Aydin and T.C. Fogarty, &quot;Teams of autonomous agents for job-shop scheduling problems: An Experimental Study&quot;, Journal of Intelligent Manufacturing, 15(4), pp. 455-462, 2004.
[2] D. Barbucha, I. Czarnowski, P. Je┬&copy;drzejowicz, E. Ratajczak, and I. Wierzbowska, &quot;JADE-based A-Team as a tool for implementing population-based algorithms&quot;, in Proc. of 6th IEEE International Conference on Intelligent System Design and Applications (ISDA 2006), Jinan, 2006, IEEE Press, vol. III, pp. 155-160.
[3] D. Barbucha, I. Czarnowski, P. Jedrzejowicz, E. Ratajczak, and I. Wierzbowska, &quot;JABAT - An implementation of the A-Team concept&quot;, in Proc. International Multiconference on Computer Science and Information Technology, Wisa, 2006, PTI, vol. 1, pp. 235-241.
[4] K. Burckert, H.J. Fischer, and G. Vierke, &quot;Holonic transport scheduling with TeleTruck&quot;, Journal of Applied Artificial Intelligence, 14, pp. 697- 725, 2000.
[5] G. Clarke and J.W. Wright, &quot;Scheduling of vehicles from central depot to a numbes of delivery points&quot;, Operations Research 12, 1964, pp. 568- 581.
[6] P. Davidson, L. Henesey, L. Ramstedt, J. Tornquist, and F. Wernstedt, &quot;An analysis of agent-based approaches to transport logistics&quot;, Transportation Research Part C, 13, pp. 255-271, 2005
[7] B.E. Gillett, L.R. Miller, &quot;A heuristic algorithm for the vehicle dispatch problem&quot;, Operations Research 22, pp. 240-349, 1974.
[8] B. Golden and W. Stewart, &quot;Empirical analysis of heuristics&quot;, in Traveling Salesman Problem, E. Lawler, J. Lenstra, A. Rinnooy, and D. Shmoys, Eds. New York: Wiley-Interscience, 1985, pp. 207-249.
[9] J. Kozlak, J.C. Creput, V. Hilaire, and A. Koukam, &quot;Multi-agent environment for dynamic transport planning and scheduling&quot;, in Computational Science - ICCS-2004, Bubak M. Albada, G.D.V., Sloot, P.M.A., Dongarra, J. (Eds.), Lecture Notes in Computer Science 3038, 2004, pp. 638-645.
[10] G. Laporte, M. Gendreau, J. Potvin, and F. Semet, &quot;Classical and modern heuristics for the vehicle routing problem&quot;, International Transactions in Operational Research, 7, pp. 285-300, 2000.
[11] I.H. Osman, &quot;Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem&quot;, Annals of Operations Research, vol. 41, pp. 421-451, 1993.
[12] H.V.D. Parunak, &quot;Agents in overalls: Experiences and issues in the development and deployment of industrial agent-based systems&quot;, International Journal of Cooperative Information Systems, 9(3), pp. 209-228, 2000.
[13] Ch. Prins, &quot;A simple and effective evolutionary algorithm for the vehicle routing problem&quot;, Computers &amp; Operations Research, 31, pp. 1985- 2002, 2004.
[14] S. Talukdar, L. Baeretzen, A. Gove, and P. de Souza, &quot;Asynchronous teams: Cooperation schemes for autonomous agents&quot;, Journal of Heuristics, 4, pp. 295-321, 1998.
[15] S.R. Thangiah, O. Shmygelska, and W. Mennell, &quot;An agent architecture for vehicle routing problem&quot;, in Proc. of the ACM Symposium on Applied Computing (SAC-2001), Las Vegas, 2001, pp. 517-521.
[16] P. Toth, and D. Vigo, Ed. The Vehicle Routing Problem, SIAM Monographs Discrete Mathematics and Applications, SIAM:Philadelphia, 2002.
[17] ORLibrary, http://people.brunel.ac.uk/mastjjb/jeb/orlib/vrpinfo.html</p>