Abstract
Online vehicle routing problems are highly complex problems for which several techniques have been successfully proposed. Traditionally, the solutions concern the optimization of conventional criteria (such as the number of mobilized vehicles and the total traveled distance). However, in online systems, the optimization of the response time to the connected users becomes at least as important as the optimization of the traditional criteria. Multi-agent systems and greedy insertion heuristics are the most promising approaches to optimize this criteria. To this end, we propose a multi-agent system and we focus on the clients dispatching strategy. The strategy decides which agents perform the computation to answer the clients requests. We propose three dispatching strategies: centralized, decentralized and hybrid. We compare these three approaches based on their response time to online users. We consider two experiments configuration, a centralized configuration and a network configuration. The results show the superiority of the centralized approach in the first configuration and the superiority of the hybrid approach in the second configuration.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Solomon, M.: Algorithms for the vehicle routing and scheduling with time window constraints. Oper. Res. 15, 254–265 (1987)
Wooldridge, M., Jennings, N.R.: Intelligent agents: theory and practice. Knowl. Eng. Rev. 10(2), 115–152 (1995)
Bessghaier, N., Zargayouna, M., Balbo, F.: Management of urban parking: an agent-based approach. In: International Conference on Artificial Intelligence: Methodology, Systems, and Applications, pp. 276–285. Springer, Heidelberg (2012)
Diana, M.: The importance of information flows temporal attributes for the efficient scheduling of dynamic demand responsive transport services. J. Adv. Transp. 40(1), 23–46 (2006)
Thangiah, S.R., Shmygelska, O., Mennell, W.: An agent architecture for vehicle routing problems. In: Proceedings of the 2001 ACM Symposium on Applied Computing, SAC 2001, pp. 517–521. ACM Press, New York (2001)
Kohout, R., Erol, K.: In-Time agent-based vehicle routing with a stochastic improvement heuristic. In: Proceedings of the Sixteenth National Conference on Artificial Intelligence and the Eleventh Innovative Applications of Artificial Intelligence (AAAI 1999/IAAI 1999), pp. 864–869. AAAI Press, Menlo Park (1999)
Zeddini, B., Temani, M., Yassine, A., Ghedira, K.: An agent-oriented approach for the dynamic vehicle routing problem. In: IWAISE 2008, pp. 70–76. IEEE (2008)
Zargayouna, M., Balbo, F., Scemama, G.: A multi-agent approach for the dynamic VRPTW. In: ESAW 2008 (2008)
Zargayouna, M., Zeddini, B.: Fleet organization models for online vehicle routing problems. In: Transactions on Computational Collective Intelligence VII, pp. 82–102. Springer, Heidelberg (2012)
Grootenboers, F., de Weerdt, M., Zargayouna, M.: Impact of competition on quality of service in demand responsive transit. In: Dix, J., Witteveen, C. (eds.) MATES 2010. LNCS, vol. 6251, pp. 113–124. Springer, Heidelberg (2010)
Gendreau, M., Guertin, F., Potvin, J.Y., Taillard, E.D.: Parallel tabu search for real-time vehicle routing and dispatching. Transp. Sci. 33(4), 381–390 (1999)
North, M.J., Howe, T.R., Collier, N.T., Vos, R.J.: The repast simphony runtime system. In: Agent 2005 Conference on Generative Social Processes, Models, and Mechanisms (2005)
Zargayouna, M., Zeddini, B., Scemama, G., Othman, A.: Simulating the impact of future internet on multimodal mobility. In: AICCSA 2014. IEEE Computer Society (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Zeddini, B., Zargayouna, M. (2019). Dispatching Strategies for Dynamic Vehicle Routing Problems. In: Jezic, G., Chen-Burger, YH., Howlett, R., Jain, L., Vlacic, L., Šperka, R. (eds) Agents and Multi-Agent Systems: Technologies and Applications 2018. KES-AMSTA-18 2018. Smart Innovation, Systems and Technologies, vol 96. Springer, Cham. https://doi.org/10.1007/978-3-319-92031-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-92031-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92030-6
Online ISBN: 978-3-319-92031-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)