A multi agent based system to enable dynamic vehicle routing
DOI:
https://doi.org/10.14295/transportes.v23i1.765Keywords:
agents, dynamic vehicle routing, vickrey auction, negotiation.Abstract
The transport activities usually involves several actors and vehicles spread out on a network of streets. This complex system intricate the techniques to deal with dynamic events usually present in transport operations. In this context, as could be noted in the literature review, the use of multi-agent systems (MAS) seems suitable to support the autonomous decision-making. This work presents an agent based system to deal with a dynamic vehicle routing problem, more precisely, in a pick-up problem, where some tasks assigned to vehicles at the beginning of the operation could be transferred to others vehicles. The task transfer happens when the vehicle agents perceive that the cycle time can exceed the daily limit of working hours, and is done through a negotiation protocol called Vickrey. The proposed system allows a collaborative decision-making among the agents, which makes possible adjustments during the course of the planned route.Downloads
References
Anosike, A. I.; Zhang, D. Z. (2009) An agent-based approach for integrating manufacturing operations. International Journal of Production Economics, v. 121, n. 2, p. 333-352. ISSN 0925-5273.
Aragão Junior, D.P. (2014) Colaboração em sistemas multiagentes na roteirização dinâmica de veículos : Um método para avaliação de estratégias em empresas OEM. Florianópolis, SC.
Ausubel, L. M. and Milgrom, P. (2006) The lovely but lonely Vickrey auction. Combinatorial Auctions. MIT Press.
Basseville, M. and Nikiforov, I. (1993) Detection of abrupt changes: theory and application. New Jersey.
Chen, Z.-L. (2010) Integrated Production and Outbound Distribution Scheduling: Review and Extensions. Operations Research, 58, 130-148.
Chow, H. K. H., Choy, K. L. and Lee, W. B. (2007) A dynamic logistics process knowledge-based system - An RFID multi-agent approach. Knowledge-Based Systems, 20, p. 357-372.
Dai, B. and Chen, H. (2011). A multi-agent and auction-based framework and approach for carrier collaboration. Logistics Research, 3(2), 101–120. DOI: 10.1007/s12159-011-0046-9
Davidsson, P., Henesey, L., Ramstedt, L., Törnquist, J. and Wernstedt, F. (2005) An analysis of agent-based approaches to transport logistics. Transportation Research Part C: Emerging Technologies, 13, p. 255-271.
Fox, M. S., Barbuceanu, M. and Teigen, R. (2000) Agent-oriented supply-chain management. International Journal of Flexible Manufacturing Systems, 12, p. 165-188.
Goel, A. (2008) Fleet Telematics: Real-time management and planning of commercial vehicle operations. New York, Springer.
Isermann, R. (1997) Supervision, fault-detection and fault-diagnosis methods - An introduction. Control Engineering Practice, 5, p. 639-652.
Isermann, R. (2005) Model-based fault-detection and diagnosis-status and applications. Annual Reviews in Control, 29, p. 71-85.
Jiang, T. and Tianfield, H. (2006) Literature Review Upon Multi-Agent
Supply Chain Management. International Conference on Machine Learning and Cybernetics, ICMLC, p. 89-94.
Jiao, J. X., You, X. and Kumar, A. (2006) An agent-based framework for collaborative negotiation in the global manufacturing supply chain network.
Robotics and Computer-Integrated Manufacturing, 22, p. 239-255.
Julka, N., Karimi, I. & Srinivasan, R., 2002. Agent-based supply chain management—2: a refinery application. Computers & Chemical Engineering, 26(12), pp.1771–1781.
Karageorgos, A. et al., 2003. Agent-based optimisation of logistics and production planning. Engineering Applications of Artificial Intelligence, 16(4), pp.335–348.
Larsen, A. (2001) The Dynamic Vehicle Routing Problem. Doctoral thesis, Technical University of Denmark.
Lau, J. S. K., Huang, G. Q., Mak, K. L., and Liang, L. (2006). Agent-based modeling of supply chains for distributed scheduling. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 36(5), 847–861. DOI: 10.1109/TSMCA.2005.854231
Maciejewski, M. & Nagel, K., 2012. Towards Multi-Agent Simulation of the Dynamic Vehicle Routing Problem in MATSim. In R. Wyrzykowski et al., eds. Parallel Processing and Applied Mathematics. Lecture Notes in Computer Science. Berlin Heidelberg: Springer, pp. 551–560.
Mes, M., Van Der Heijden, M. and Van Harten, A. (2007) Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems. European Journal of Operational Research, 181, p. 59-75.
Monostori, L., Vancza, J. and Kumara, S. R. T. (2006) Agent-based systems for manufacturing. International Academy for Production Engineering, Cirp Annals-Manufacturing Technology, 55, p. 697-720.
Novaes, A. G. N., Bez, E. T. and Burin, P. J. (2012) Fault detection in dynamic vehicle routing operations. International Conference on Dynamics in Logistics, LDIC. Bremen, Alemanha.
Novaes, A. G. N., Scholz-Reiter, B., Bez, E. T. and Burin, P. J. (2011) An agent-based approach to improve urban vehicle rounting operations. XXV Congresso de Pesquisa e Ensino em Transportes, ANPET. Belo Horizonte, Brazil.
Parunak, H. V. D. (2000). Agents in overalls: Experiences and issues in the development and deployment of industrial agent-based systems. International Journal of Cooperative Information Systems, 9(03), 209–227.
Roorda, M.J. et al., 2010. A conceptual framework for agent-based modelling of logistics services. Transportation Research Part E: Logistics and Transportation Review, 46(1), pp.18–31.
Russel, S. and Norvig, P. (2003) Artificial Intelligence: A Modern Approach. New Jersey, NJ, USA, Prentice Hall.
Schuh, G. (2006). Sm@rt Logistics: Intelligent networked systems. {CIRP}
Annals - Manufacturing Technology, 55(1), 505–508. DOI: 10.1016/S0007-8506(07)60469-7
Simani, S., Fantuzzi, C. and Patton, R. (2003) Model-based fault diagnosis in dynamic systems using identification techniques. Springer.
Vokrinek, J., Komenda, A. & Pechoucek, M., 2010. Agents Towards Vehicle Routing Problems. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. AAMAS ’10. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, pp. 773–780.
W3C (2010) Web Services Glossary. Visited in 20/06/2013. Url: http://www.w3.org/TR/ws-gloss/.
Wellman, M. P., Walsh, W. E., Wurman, P. R. and Mackie-Mason, J. K. (2001) Auction Protocols for Decentralized Scheduling. Games and Economic Behavior, 35, p. 271-303.
Wooldridge, M. (2002). An introduction to multiagent systems. John Wiley & Sons. Chichester, England.
Downloads
Published
How to Cite
Issue
Section
License
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- The authors retain the copyright and grant Transportes the right of first publication of the manuscript, without any financial charge, and waive any other remuneration for its publication by ANPET.
- Upon publication by Transportes, the manuscript is automatically licensed under the Creative Commons License CC BY 4.0 license. This license permits the work to be shared with proper attribution to the authors and its original publication in this journal.
- Authors are authorized to enter into additional separate contracts for the non-exclusive distribution of the version of the manuscript published in this journal (e.g., publishing in an institutional repository or as a book chapter), with recognition of the initial publication in this journal, provided that such a contract does not imply an endorsement of the content of the manuscript or the new medium by ANPET.
- Authors are permitted and encouraged to publish and distribute their work online (e.g., in institutional repositories or on their personal websites) after the editorial process is complete. As Transportes provides open access to all published issues, authors are encouraged to use links to the DOI of their article in these cases.
- Authors guarantee that they have obtained the necessary authorization from their employers for the transfer of rights under this agreement, if these employers hold any copyright over the manuscript. Additionally, authors assume all responsibility for any copyright infringements by these employers, releasing ANPET and Transportes from any responsibility in this regard.
- Authors assume full responsibility for the content of the manuscript, including the necessary and appropriate authorizations for the disclosure of collected data and obtained results, releasing ANPET and Transportes from any responsibility in this regard.
