Abstract
We present an efficient route minimization algorithm for the vehicle routing problem with time windows. The algorithm uses a generic agent decomposition of the problem featuring a clear separation between the local planning performed by the individual vehicles and the abstract global coordination achieved by negotiation — differentiating the presented algorithm from the traditional centralized algorithms. Novel negotiation semantics is introduced on the global coordination planning level allowing customers to be temporarily ejected from the emerging solution being constructed. This allows the algorithm to efficiently backtrack in situations when the currently processed customer cannot be feasibly allocated to the emerging solution. Over the relevant widely-used benchmarks the algorithm equals the best known solutions achieved by the centralized algorithms in 90.7% of the cases with an overall relative error of 0.3%, outperforming the previous comparable agent-based algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bachem, A., Hochstättler, W., Malich, M.: The simulated trading heuristic for solving vehicle routing problems. Technical report, Discrete Applied Mathenatics (1996)
Brafman, R.I., Domshlak, C.: From one to many: Planning for loosely coupled multi-agent systems. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 28–35 (2008)
Bräysy, O., Gendreau, M.: Vehicle routing problem with time windows, part I route construction and local search algorithms. Transportation Science 39(1), 104–118 (2005)
Bräysy, O., Gendreau, M.: Vehicle routing problem with time windows, part II metaheuristics. Transportation Science 39(1), 119–139 (2005)
Campbell, A.M., Savelsbergh, M.: Efficient insertion heuristics for vehicle routing and scheduling problems. Transportation Science 38, 369–378 (2004)
Dan, Z., Cai, L., Zheng, L.: Improved multi-agent system for the vehicle routing problem with time windows. Tsinghua Science Technology 14(3), 407–412 (2009)
Davidsson, P., Henesey, L., Ramstedt, L., Törnquist, J., Wernstedt, F.: An analysis of agent-based approaches to transport logistics. Transportation Research Part C: Emerging Technologies 13(4), 255–271 (2005)
Davis, R., Smith, R.G.: Negotiation as a metaphor for distributed problem solving. Artificial Intelligence 20, 63–109 (1983)
Desaulniers, G., Lessard, F., Hadjar, A.: Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Science 42(3), 387–404 (2008)
Fischer, K., Müller, J.P., Pischel, M.: Cooperative transportation scheduling: an application domain for dai. Journal of Applied Artificial Intelligence 10, 1–33 (1995)
Gehring, H., Homberger, J.: A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research 162(1), 220–238 (2005)
Kalina, P., Vokřínek, J.: Parallel solver for vehicle routing and pickup and delivery problems with time windows based on agent negotiation. In: 2012 IEEE Conference on Systems, Man, and Cybernetics (SMC), pp. 1558–1563 (2012)
Kalina, P., Vokřínek, J., Mařík, V.: The art of negotiation: Developing efficient agent-based algorithms for solving vehicle routing problem with time windows. In: Mařík, V., Lastra, J.L.M., Skobelev, P. (eds.) HoloMAS 2013. LNCS, vol. 8062, pp. 187–198. Springer, Heidelberg (2013)
Kohout, R., Erol, K.: In-time agent-based vehicle routing with a stochastic improvement heuristic. In: 11th Conference on Innovative Applications of Artificial Intelligence. AAAI/MIT Press (1999)
Komenda, A., Novák, P., Pěchouček, M.: Domain-independent multi-agent plan repair. Journal of Network and Computer Applications (in print, 2013)
Komenda, A., Vokrinek, J., Cap, M., Pechoucek, M.: Developing multiagent algorithms for tactical missions using simulation. IEEE Intelligent Systems 28(1), 42–49 (2013)
Komenda, A., Vokřínek, J., Pěchouček, M.: Plan representation and execution in multi-actor scenarios by means of social commitments. Web Intelligence and Agent Systems 9(2), 123–133 (2011)
Leong, H.W., Liu, M.: A multi-agent algorithm for vehicle routing problem with time window. In: Proceedings of the 2006 ACM Symposium on Applied Computing, SAC 2006, pp. 106–111. ACM, New York (2006)
Lim, A., Zhang, X.: A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. INFORMS Journal on Computing 19(3), 443–457 (2007)
Liu, F.-H., Shen, S.-Y.: The fleet size and mix vehicle routing problem with time windows. Operational Research Society 50, 721–732 (1999)
Lu, Q., Dessouky, M.M.: A new insertion-based construction heuristic for solving the pickup and delivery problem with hard time windows. European Journal of Operational Research 175, 672–687 (2005)
Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical Report C3P Report 826, California Institute of Technology (1989)
Nagata, Y.: Edge assembly crossover for the capacitated vehicle routing problem. In: Cotta, C., van Hemert, J. (eds.) EvoCOP 2007. LNCS, vol. 4446, pp. 142–153. Springer, Heidelberg (2007)
Nagata, Y., Bräysy, O., Dullaert, W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res. 37(4), 724–737 (2010)
Prescott-Gagnon, E., Desaulniers, G., Rousseau, L.-M.: A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows. Netw. 54(4), 190–204 (2009)
Ren, Y., Dessouky, M., Ordóñez, F.: The multi-shift vehicle routing problem with overtime. Comput. Oper. Res. 37(11), 1987–1998 (2010)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35, 254–265 (1987)
Vokřínek, J., Komenda, A., Pěchouček, M.: Abstract architecture for task-oriented multi-agent problem solving. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 41(1), 31–40 (2011)
Wang, F., Tao, Y., Shi, N.: A survey on vehicle routing problem with loading constraints. In: Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization, CSO 2009, vol. 2, pp. 602–606. IEEE Computer Society, Washington, DC (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kalina, P., Vokřínek, J., Mařík, V. (2013). An Efficient Route Minimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Agent Negotiation. In: Boella, G., Elkind, E., Savarimuthu, B.T.R., Dignum, F., Purvis, M.K. (eds) PRIMA 2013: Principles and Practice of Multi-Agent Systems. PRIMA 2013. Lecture Notes in Computer Science(), vol 8291. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-44927-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-44927-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-44926-0
Online ISBN: 978-3-642-44927-7
eBook Packages: Computer ScienceComputer Science (R0)