A multi agent based system to enable dynamic vehicle routing

Authors

  • Dmontier Pinheiro Aragão, Jr. Universidade Federal de Santa Catarina
  • Antônio Galvão Novaes Universidade Federal de Santa Catarina
  • Mônica Maria Mendes Luna Universidade Federal de Santa Catarina

DOI:

https://doi.org/10.14295/transportes.v23i1.765

Keywords:

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

Download data is not yet available.

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

2015-05-12

How to Cite

Aragão, D. P., Novaes, A. G., & Mendes Luna, M. M. (2015). A multi agent based system to enable dynamic vehicle routing. TRANSPORTES, 23(1), 69–77. https://doi.org/10.14295/transportes.v23i1.765

Issue

Vol. 23 No. 1 (2015)

Section

Artigos

License

Authors who submit papers for publication by TRANSPORTES agree to the following terms:

  1. Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.

  3. Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.

  4. Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.

  5. Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.