Abstract
The requirements of transport processes have become increasingly complex due to shorter transit times, the individual qualities of shipments, and higher amounts of small sized orders. Especially in courier and express services providing same day deliveries, the high degree of dynamics even increases this complexity. To ensure reliable and flexible planning and control of transport processes, we present a reactive and proactive agent-based system to support the dispatching of logistic transport service providers. Beside the application in simulated real-world processes of our industrial partners, this paper focuses on the impact and relevance of shortest-path queries in the system. We compare the application of state-of-the-art algorithms and investigate the effects of high speed shortest-path computations in agent-based negotiations. The results prove that efficient shortest-path algorithms are an essential key component in agent-based control of dynamic transport processes.
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
Abraham I, Delling D, Goldberg AV, Werneck RF (2011) A hub-based labeling algorithm for shortest paths in road networks. In: Experimental algorithms. 10th international symposium SEA 2011. Lecture notes in computer science, vol 6630. Springer, Berlin, pp 230–241
Abraham I, Delling D, Goldberg AV, Werneck RF (2012) Hierarchical hub labelings for shortest paths. In: Algorithms—ESA 2012. 20th Annual European symposium, Ljubljana, September 2012. Lecture notes in computer science, vol 7501. Springer, Berlin, pp 24–35
Batz GV, Delling D, Sanders P, Vetter C (2008) Time-dependent contraction hierarchies. In: Proceedings of the 11th workshop on algorithm engineering and experiments, New York
Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. In: Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University
Dijkstra EW (1959) A note on two problems in connexion with graphs. Num Math 1:269–271
Dorer K, Calisti M (2005) An adaptive solution to dynamic transport optimization. In: Proceedings of the 4th international conference on autonomous agents and multiagent systems, ACM Press, pp 45–51
Edelkamp S, Gath M (2013) Optimal decision making in agent-based autonomous groupage traffic. In: Proceedings of the 5th international conference on agents and artificial intelligence, vol 1, pp 248–254
Edelkamp S, Gath M, Cazenave T, Teytaud F (2013) Algorithm and knowledge engineering for the TSPTW problem. In: IEEE symposium on computer intelligence in scheduling, Singapore
Fischer K, Müller JP, Pischel M (1995) Cooperative transportation scheduling: an application domain for dai. J Appl Artif Intell 10:1–33
Gath M, Herzog O, Edelkamp S (2013a) Agent-based dispatching in groupage traffic. In: IEEE symposium on computer intelligence in production and logistics systems, Singapore
Gath M, Herzog O, Edelkamp S (2013b) Agent-based planning and control for groupage traffic. In: Proceedings of the 10th international conference and expo of emerging technologies (to appear)
Geisberger R, Sanders P, Schultes D, Vetter C (2012) Exact routing in large road networks using contraction hierarchies. Transp Sci 46:388–404
Gendreau M, Bräysy O (2005) Vehicle routing problem with time windows, part I: route construction and local search algorithms. Transp Sci 39:104–118
Golden B, Raghavan S, Wasil E (eds) (2008) The vehicle routing problem: latest advances and new challenges. Springer, New York
Greulich C (2013) Enhanced shortest path computation for multiagent-based intermodal transport planning in dynamic environments, In: Proceedings of the 5th international conference on agents and artificial intelligence, vol 2, pp 324–329
Harjes F, Scholz-Reiter B (2013) Agent-based disposition in event logistics. Res Logistics Prod 2:137–150
Lewandowski M, Werthmann D, Gath M, Lawo M (2013) Agent-based control for material handling systems in in-house logistics. In: European conference on smart objects, systems and technologies
Mac Queen J (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley symposium on mathematical statistics and probability, vol 1, pp 281–297
Parragh SN, Doerner KF, Hartl RF (2008a) A survey on pickup and delivery problems, part I: transportation between customers and depot. J für Betriebswirtschaft 58(1):21–51
Parragh SN, Doerner KF, Hartl RF (2008b) A survey on pickup and delivery problems part II: transport between pickup and delivery locations. J für Betriebswirtschaft 58(2):81–117
Scholz-Reiter B, Windt K, Freitag M (2004) Autonomous logistic processes: new demands and first approaches. In: Proceedings of the 37th CIRP international seminar on manufacturing systems, pp 357–362
Schuldt A (2011) Multiagent coordination enabling autonomous logistics. Springer, Berlin
Skobelev P (2011) Multi-agent systems for real time resource allocation, scheduling, optimization and controlling: industrial applications. In: Mařík V, Vrba P, Leitão P (eds) Holonic and multi-agent systems for manufacturing. Springer, Berlin, pp 1–14
Wooldridge M (2013) Intelligent agents. In: Weiss G (ed) Multiagent systems. A modern approach to distributed artificial intelligence. MIT Press, Cambridge, pp 3–50
Acknowledgments
The presented research was partially funded by the German Research Foundation (DFG) within the project Autonomous Courier and Express Services (HE 989/14-1) at the University Bremen, Germany. We thank our industrial partners for great cooperation and Stefan Edelkamp for great discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Gath, M., Herzog, O., Vaske, M. (2016). The Impact of Shortest-Path Searches on Dynamic Autonomous Transport Scheduling. In: Kotzab, H., Pannek, J., Thoben, KD. (eds) Dynamics in Logistics. Lecture Notes in Logistics. Springer, Cham. https://doi.org/10.1007/978-3-319-23512-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-23512-7_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23511-0
Online ISBN: 978-3-319-23512-7
eBook Packages: EngineeringEngineering (R0)