On the Development of a Multi-Layered Agent-Based Heurisitc System for Vehicle Routing Problem under Random Vehicle Breakdown
Abstract
With the recent technological advancement, the Dynamic Vehicle Routing Problem (DVRP) is becoming more applicable but almost all of the research in this field limited the source of dynamism from the order side rather from the vehicle, in addition to the adoption of inflexible tools that are mainly designed for the static problem. Considering multiple random vehicle breakdowns complicates the problem of how to adapt and distribute the workload to other functioning vehicles. In this ongoing PhD research, a proposed multi-layered Agent-Based Model (ABM) along with a modelling framework on how to deal with such disruptive events in a reactive continuous manner. The model is partially constructed and experimented, with a developed clustering rule, on two randomly generated scenario for the purpose of validation. The rule achieved good order allocation to vehicles and reacted to different problem sizes by rejecting orders that are over the model capacity. This shows a promising path in fully adopting the ABM model in this dynamic problem.
Downloads
References
M. G. Speranza. Trends in transportation and logistics. European Journal of Operational Research, vol. 264, no. 3, pp. 830-836, 2018.
H. Lasi, P. Fettke, H. G. Kemper, T. Feld and M. Hoffmann. Industry 4.0. Business and Information Systems Engineering, vol. 6, no. 4, pp. 239-242, 2014.
J. Gubbi, R. Buyya, S. Marusic and M. Palaniswami. Internet of things (IoT): A vision, architectural elements, and future directions. Future Generation Computer Systems, vol. 29, no. 7, pp. 1645-1660, 2013.
G. B. Dantzig and J. H. Ramser. The truck dispatching problem. Management Science, vol. 6, no. 1, pp. 80-91, 1959.
G. Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, vol. 59, pp. 345-358, 1992.
J. K. Lenstra and A. H. G. Kan. Complexity of vehicle routing and scheduling problems. Networks, vol. 11, no. 2, pp. 221-227, 1981.
M. M. Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operational Research, vol. 35, no. 2, pp. 254-265, 1987.
M. Schneider. The vehicle-routing problem with time windows and driver-specific times. European Journal of Operational Research, vol. 250, no. 1, pp. 101-119, 2016.
V. Pillac, M. Gendreau, C. Guéret and A. L. Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, vol. 225, no. 1, pp. 1-11, 2013.
P. C. Guedes and D. Borenstein. Real-time multi-depot vehicle type rescheduling problem. Transportation Research Part B: Methodological, vol. 108, pp. 217-234, 2018.
M. Gendreau, F. Guertin, J. Y. Potvin and É. D. Taillard. Parallel tabu search for real-time vehicle routing and dispatching. Transportation, vol. 33, no. 4, pp. 381-390, 1999.
J. Q. Li, D. Borenstein and P. B. Mirchandani. A decision support system for the single-depot vehicle rescheduling problem. Comput. Oper. Res., vol. 34, no. 4, pp. 1008-1032, 2007.
J. Q. Li, P. B. Mirchandani and D. Borenstein. The vehicle rescheduling problem: Model and algorithms. Networks, vol. 50, no. 3, pp. 211-229, 2007.
J. Q. Li, P. B. Mirchandani and D. Borenstein. A Lagrangian heuristic for the real-time vehicle rescheduling problem. Transportation Research Part E: Logistics and Transportation, vol. 45, no. 3, pp. 419-433, 2009.
J. Q. Li, P. B. Mirchandani and D. Borenstein. Real-time vehicle re-routing problems with time windows. European Journal of Operational Research, vol. 194, no. 3, pp. 711-727, 2009.
R. R. Pandi, S. G. Ho, S. C. Nagavarapu, T. Tripathy and J. Dauwels. Disruption management for dial-a-ride systems. IEEE Intelligent Transportation Systems Magazine, vol. 12, no. 4, pp. 219-234, 2020.
Q. Mu, Z. Fu, J. Lysgaard and R. Eglese. Disruption management of the vehicle routing problem with vehicle breakdown. Journal of the Operational Research Society, vol. 62, no. 4, pp. 742-749, 2011.
I. Minis, K. Mamasis and V. Zeimpekis. Real-time management of vehicle breakdowns in urban freight distribution. The Journal of Heuristics, vol. 18, no. 3, pp. 375-400, 2012.
K. Mamasis, I. Minis and G. Dikas. Managing vehicle breakdown incidents during the urban distribution of a common product. Journal of the Operational Research Society, vol. 64, no. 6, pp. 925-937, 2013.
M. Van der Merwe, M. Ozlen, J. W. Hearne and J. P. Minas. Dynamic re-routing of vehicles during cooperative wildfire response operations. Annals of Operations Research, vol. 254, no. 1-2, pp. 467-480, 2017.
H. Seyyedhasani and J. S. Dvorak. Dynamic re-routing of a fleet of vehicles in agricultural operations through a dynamic multiple depot vehicle routing problem representation. Biosystems Engineering, vol. 171, pp. 63-77, 2018.
G. Clarke and J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operational Research, vol. 12, no. 4, pp. 568-581, 1964.
L. Bodin and B. Golden. Classification in vehicle routing and scheduling. Networks, vol. 11, no. 2, pp. 97-108, 1981.
R. Van Lieshout, J. Mulder and D. Huisman. The vehicle rescheduling problem with retiming. Operations Research and Computers, vol. 96, pp. 131-140, 2018.
B. Dávid and M. Krész. The dynamic vehicle rescheduling problem. Central European Journal of Operations Research, vol. 25, no. 4, pp. 809-830, 2017.
G. Laporte. Fifty years of vehicle routing. Transportation Science, vol. 43, no. 4, pp. 408-416, 2009.
K. Fischer, J. Müller and M. Pischel. Cooperative transportation scheduling: An application domain for DAI. Applied Artificial Intelligence, vol. 10, no. 1, pp. 1-34, 1996.
M. Mes, M. van der Heijden and A. van Harten. Comparison of agent-based scheduling to look-ahead heuristics for realtime transportation problems. European Journal of Operational Research, vol. 181, no. 1, pp. 59-75, 2007.
M. Wooldridge and N. R. Jennings. Agent theories, Architectures, and languages: A survey. In: M. J. Wooldridge and N. R. Jennings, (Eds.), Intelligent Agents. Vol. 890. Berlin, Heidelberg: Springer, pp. 1-39, 1995.
N. Kuhn, J. P. Müller and J. Müller. Simulating cooperative transportation companies. In: J. Biethahn, W. Hummeltenberg, B. Schmidt and T. Witte, (Eds.), Simulation als Betriebliche Entscheidungshilfe, Wiesbaden: Vieweg+Teubner Verlag, pp. 263- 274, 1994.
R. Kohout and K. Erol. In-time Agent-based Vehicle Routing with a Stochastic Improvement Heuristic. Menlo Park, California: American Association for Artificial Intelligence, pp. 864-869, 1999.
B. Zeddini, M. Temani, A. Yassine and K. Ghedira. An Agent-Oriented Approach for the Dynamic Vehicle Routing Problem. In: 2008 International Workshop on Advanced Information Systems for Enterprises, pp. 70-76, 2008.
D. Barbucha and P. Jedrzejowicz. An agent-based approach to vehicle routing problem. International Journal of Computer and Information Technology, vol. 1, no. 2, p. 6, 2007.
D. Barbucha and P. Jȩdrzejowicz. Agent-Based Approach to the Dynamic Vehicle Routing Problem. Berlin, Heidelberg: 7th International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS 2009), pp. 169-178, 2009.
D. Barbucha. Agent-based guided local search. Expert Systems with Applications, vol. 39, no. 15, pp. 12032-12045, 2012.
D. Barbucha. Experimental Study of the Population Parameters Settings in Cooperative Multi-agent System Solving Instances of the VRP. In: N. T. Nguyen, (Ed.), Transactions on Computational Collective Intelligence I × . Vol. 7770. Berlin, Heidelberg: Springer. Berlin Heidelberg, pp. 1-28, 2013.
D. Barbucha. Multi-agent Approach to the DVRP with GLS Improvement Procedure. Singapore: Intelligent Decision Technologies, pp. 117-126, 2020.
J. Vokřínek, A. Komenda and M. Echouček. Agents towards Vehicle Routing Problems. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pp. 773-780, 2010.
P. Kalina and J. Vokřínek. Parallel Solver for Vehicle Routing and Pickup and Delivery Problems with Time Windows Based Abu-Monshar, et al.: Vehicle Breakdown in DVRP 10 http://journals.cihanuniversity.edu.iq/index.php/cuesj CUESJ 2021, 5 (1): 1-10 on Agent Negotiation. 2012 IEEE International Conference on Systems Man and Cybernetics, pp. 1558-1563, 2012.
M. Maciejewski and K. Nagel. Towards Multi-Agent Simulation of the Dynamic Vehicle Routing Problem in MATSim. In: R. Wyrzykowski, J. Dongarra, K. Karczewski and J. Waśniewski, (Eds.), Parallel Processing and Applied Mathematics. Vol. 7204. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 551-560, 2012.
M. Gath, S. Edelkamp and O. Herzog. Agent-based Dispatching in Groupage Traffic. Singapore, Singapore: 2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS), pp. 54-60, 2013.
S. K. Nambiar and S. M. Idicula. A Multi-agent Vehicle Routing System for Garbage Collection. In: 2013 5th International Conference on Advanced Computing (ICoAC), Dec, pp. 72-76, 2013.
A. Pan, S. Y. S. Leung, K. L. Moon and K. W. Yeung. Optimal reorder decision-making in the agent-based apparel supply chain. Expert Systems with Applications, vol. 36, no. 4, pp. 8571-8581, 2009.
Copyright (c) 2021 Anees M. Abu- Monshar, Ammar F. Al-Bazi, Qusay H. Alsalami
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License [CC BY-NC-ND 4.0] that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
