Agent - based dispatching enables autonomous groupage traffic

• Autorzy: Gath M. , Edelkamp S. , Herzog O.

Identyfikatory

DOI

10.2478/jaiscr-2014-0003

• Języki publikacji: EN

Abstrakty

EN

The complexity and dynamics in groupage traffic require flexible, efficient, and adaptive planning and control processes. The general problem of allocating orders to vehicles can be mapped into the Vehicle Routing Problem (VRP). However, in practical applications additional requirements complicate the dispatching processes and require a proactive and reactive system behavior. To enable automated dispatching processes, this article presents a multiagent system where the decision making is shifted to autonomous, interacting, intelligent agents. Beside the communication protocols and the agent architecture, the focus is on the individual decision making of the agents which meets the specific requirements in groupage traffic. To evaluate the approach we apply multiagent-based simulation and model several scenarios of real world infrastructures with orders provided by our industrial partner. Moreover, a case study is conducted which covers the autonomous groupage traffic in the current processes of our industrial parter. The results reveal that agent-based dispatching meets the sophisticated requirements of groupage traffic. Furthermore, the decision making supports the combination of pickup and delivery tours efficiently while satisfying logistic request priorities, time windows, and capacity constraints.

Słowa kluczowe

EN

groupage traffic; vehicle routing problem; VRP; multi-agent system; decision making; intelligent agent; multiagent simulation

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2013
• Tom: Vol. 3, No. 1
• Strony: 27--40
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Gath M.

• Institute for Artificial Intelligence, Center for Computing and Communication Technologies, Am Fallturm 1, 28359 Bremen, Germany

autor

Edelkamp S.

• Institute for Artificial Intelligence, Center for Computing and Communication Technologies, Am Fallturm 1, 28359 Bremen, Germany

autor

Herzog O.

• Institute for Artificial Intelligence, Center for Computing and Communication Technologies, Am Fallturm 1, 28359 Bremen, Germany

Bibliografia

• [1] M. Gendreau, “Vehicle Routing Problem with TimeWindows, Part I: Route Construction and Local Search Algorithms,” Transportation Science, vol. 39, no. 1, pp. 104–118, 2005.
• [2] M. Gendreau and O. Brysy, “Vehicle Routing Problem with Time Windows, Part II: Metaheuristics,” Transportation Science, vol. 39, pp. 119–139, 2005.
• [3] O. Brysy, W. Dullaert, and M. Gendreau, “Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows,” J. Heuristics, vol. 10, pp. 587–611, 2004.
• [4] J. Homberger and H. Gehring, “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with TimeWindows,” European Journal of Operational Research, vol. 162, pp. 220–238, 2005.
• [5] B. Golden, S. Raghavan, and E. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges. Springer Verlag, 2008.
• [6] M. Dorigo and L. Gambardella, “Ant colonies for the traveling salesman problem,” 1996.
• [7] B. Scholz-Reiter, K. Windt, J. Kolditz, F. B¨ose, T. Hildebrandt, T. Philipp, and H. H¨ohns, “New Concepts of Modelling and Evaluating Autonomous Logistic Processes,” in IFAC Manufacturing, Modelling, Management and Control, G. Chryssolouris and M. D, Eds. Athens, Greece: Elsevier, 2004.
• [8] T. Warden, R. Porzel, J. D. Gehrke, O. Herzog, H. Langer, and R. Malaka, “Towards Ontologybased Multiagent Simulations: The PlaSMA Approach,” in European Conference on Modelling and Simulation (ECMS), A. Bargiela, S. Azam Ali, D. Crowley, and E. J. Kerckhoffs, Eds., 2010, pp. 50 – 56.
• [9] M.Wooldridge, “Intelligent Agents,” in Multiagent Systems. A Modern Approach to Distributed Artificial Intelligence, G. Weiss, Ed. MIT Press, 1999, pp. 27 – 77.
• [10] K. Dorer and M. Calisti, “An Adaptive Solution to Dynamic Transport Optimization,” in International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), ACM. ACM Press, 2005, pp. 45–51.
• [11] J. Himoff, G. Rzevski, and P. Skobelev, “Multi-Agent Logistics i-Scheduler for Road Transportation,” in International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2006, pp. 1514–1521.
• [12] A. Schuldt, Multiagent Coordination Enabling Autonomous Logistics. Springer Verlag, 2011.
• [13] J. O. Berndt and O. Herzog, “Distributed Learning of Equilibrium Strategies in Concurrent Iterated Many-issue Negotiations,” in Multiagent System Technologies (MATES). Berlin: Springer, 2012.
• [14] K. Fischer, J. P. M¨uller, and M. Pischel, “Cooperative Transportation Scheduling: An Application Domain for DAI,” Journal of Applied Artificial Intelligence, vol. 10, pp. 1–33, 1995.
• [15] H.-J. B¨urckert, K. Fischer, and G. Vierke, “Applied Artificial Intelligence : An Holonic Transport Scheduling with Teletruck,” Applied Artificial Intelligence, vol. 14, no. 7, pp. 697 – 725, 2000.
• [16] P. Skobelev, “Multi-agent systems for real time resource allocation, scheduling, optimization and controlling: Industrial applications,” in Holonic and Multi-Agent Systems for Manufacturing (HOLOMAS), 2011, pp. 1–14.
• [17] M. H¨ulsmann, B. Scholz-Reiter, and K. Windt, Eds., Autonomous Cooperation and Control in Logistics:Contributions and Limitations – Theoretical and Practical Perspectives. Berlin: Springer-Verlag, 2011.
• [18] J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” 5th Berkeley Symp. Math. Statist. Prob., vol. 1, pp. 281 – 297, 1967.
• [19] N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Graduate School of Industrial Administration, Carnegie-Mellon University, Tech. Rep. 388, 1976.
• [20] R. Baldacci, A. Mingozzi, and R. Roberti, “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints,” European Journal of Operational Research, vol. 218, no. 1, pp. 1–6, 2012.
• [21] Foundation for Intelligent Physical Agents, “FIPA Contract Net Interaction Protocol Specification,” Geneva, Switzerland, Standard No. SC00029H, 2002.
• [22] N. R. Jenninges, “An Agent-Based Approach for Building Complex Software Systems,” Communication of the ACM, vol. 44, no. 4, pp. 35 – 41, 2001.
• 40 M. Gath, S. Edelkamp and O. Herzog [23] F. Bellifemine, G. Caire, and D. Greenwood, Developing Multi-Agent Systems with JADE. Chichester, UK: John Wiley & Sons, 2007.
• [24] J. D. Gehrke, A. Schuldt, and S. Werner, “Quality Criteria for Multiagent-Based Simulations with Conservative Synchronisation,” in 13th ASIM Dedicated Conference on Simulation in Production and Logistics, M. Rabe, Ed., Citeseer. Stuttgart: Fraunhofer IRB Verlag, 2008, pp. 545–554.
• [25] E.W. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, vol. 1, pp. 269–271, 1959.
• [26] R. K. Ahuja, K. Mehlhorn, J. Orlin, and R. Tarjan, “Faster Algorithms for the Shortest Path Problem,” Journal of the ACM, vol. 37, no. 2, pp. 213–223, Apr. 1990.
• [27] M. a. Krajewska, H. Kopfer, G. Laporte, S. Ropke, and G. Zaccour, “Horizontal Cooperation among Freight Carriers: Request Allocation and Profit Sharing,” Journal of the Operational Research Society, vol. 59, no. 11, pp. 1483–1491, Sep. 2007.