An Agent-Based Approach to Vehicle Routing Problem

Authors: Dariusz Barbucha, Piotr Jedrzejowicz

Abstract:

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.

Keywords: multi-agent systems, population-based methods, vehiclerouting problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076620

References:

[1] M.E. Aydin and T.C. Fogarty, "Teams of autonomous agents for job-shop scheduling problems: An Experimental Study", Journal of Intelligent Manufacturing, 15(4), pp. 455-462, 2004.
[2] D. Barbucha, I. Czarnowski, P. Je┬©drzejowicz, E. Ratajczak, and I. Wierzbowska, "JADE-based A-Team as a tool for implementing population-based algorithms", 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, "JABAT - An implementation of the A-Team concept", 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, "Holonic transport scheduling with TeleTruck", Journal of Applied Artificial Intelligence, 14, pp. 697- 725, 2000.
[5] G. Clarke and J.W. Wright, "Scheduling of vehicles from central depot to a numbes of delivery points", Operations Research 12, 1964, pp. 568- 581.
[6] P. Davidson, L. Henesey, L. Ramstedt, J. Tornquist, and F. Wernstedt, "An analysis of agent-based approaches to transport logistics", Transportation Research Part C, 13, pp. 255-271, 2005
[7] B.E. Gillett, L.R. Miller, "A heuristic algorithm for the vehicle dispatch problem", Operations Research 22, pp. 240-349, 1974.
[8] B. Golden and W. Stewart, "Empirical analysis of heuristics", 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, "Multi-agent environment for dynamic transport planning and scheduling", 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, "Classical and modern heuristics for the vehicle routing problem", International Transactions in Operational Research, 7, pp. 285-300, 2000.
[11] I.H. Osman, "Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem", Annals of Operations Research, vol. 41, pp. 421-451, 1993.
[12] H.V.D. Parunak, "Agents in overalls: Experiences and issues in the development and deployment of industrial agent-based systems", International Journal of Cooperative Information Systems, 9(3), pp. 209-228, 2000.
[13] Ch. Prins, "A simple and effective evolutionary algorithm for the vehicle routing problem", Computers & Operations Research, 31, pp. 1985- 2002, 2004.
[14] S. Talukdar, L. Baeretzen, A. Gove, and P. de Souza, "Asynchronous teams: Cooperation schemes for autonomous agents", Journal of Heuristics, 4, pp. 295-321, 1998.
[15] S.R. Thangiah, O. Shmygelska, and W. Mennell, "An agent architecture for vehicle routing problem", 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