Abstract
Vehicle Routing Problem (VRP) class refers to a wide range of transportation problems where a set of vehicles have to deliver (or pickup) goods or persons to (from) locations situated in a given area. The Dynamic Vehicle Routing Problem (DVRP) class generalizes the VRP by assuming that information about customers is not given a priori to the decision-maker and it may change during over the time. It means that at any moment of time, there may exist customers already under servicing and new customers which need to be serviced. As a consequence, each newly arriving request needs to be incorporated into the existing vehicles tours, which means that the current solution may need to be reconfigured to minimize the goal functions. The paper presents a multi-agent approach to the DVRP, where Guided Local Search (GLS) procedure has been applied to periodic re-optimization of static subproblems, including requests, which have already arrived to the system. Computational experiment has been carried out to confirm the efficiency of the proposed approach.
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
Alsheddy, A., Voudouris, C., Tsang, E.P.K., Alhindi, A.: Guided local search. In: Marti, R., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Heuristics, pp. 261–298. Springer, Cham (2018)
Backer, B.D., Furnon, V., Prosser, P., Kilby, P., Shaw, P.: Solving vehicle routing problems using constraint programming and metaheuristics. J. Heuristics 6(4), 501–523 (2000)
Barbucha, D., Jȩdrzejowicz, P.: Agent-Based approach to the dynamic vehicle routing problem. In: Demazeau, Y., Pavon, J., Corchado, J.M., Bajo, J. (eds.) 7th International Conference on Practical Applications of Agents and Multi-agent Systems (PAAMS 2009). Advances in Intelligent and Soft Computing, vol. 55, pp. 169–178. Springer, Berlin, Heidelberg (2009)
Barbucha, D.: Agent-based guided local search. Expert Syst. Appl. 39(15), 12032–12045 (2012)
Barbucha, D.: A Multi-agent approach to the dynamic vehicle routing problem with time windows. In: Badica, C., Nguyen, N.T., Brezovan, M. (eds.) Computational Collective Intelligence. Technologies and Applications—5th International Conference, ICCCI 2013. LNCS, vol. 8083, pp. 467–476. Springer, Berlin, Heidelberg (2013)
Barbucha, D.: Solving DVRPTW by a Multi-agent system with vertical and horizontal cooperation. In: Nguyen, N.T., Pimenidis, E., Khan, Z., Trawinski, B. (eds) Computational Collective Intelligence. ICCCI 2018. LNCS, vol. 11056, pp. 181–190. Springer, Cham (2018)
Barbucha, D.: VNS-based Multi-agent approach to the dynamic vehicle routing problem. In: Nguyen, N.T., Chbeir, R., Exposito, E., Aniorte, P., Trawinski, B.: Computational Collective Intelligence—11th International Conference, ICCCI 2019, Proceedings, Part I. LNCS, vol. 11683, pp. 556-565. Springer, Cham (2019)
Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds.): Combinatorial Optimization. Wiley, Chichester (1979)
Egeblad, J., Nielsen, B., Odgaard, A.: Fast neighbourhood search for two- and three-dimensional nesting problems. Eur. J. Oper. Res. 183(3), 1249–1266 (2007)
Hani, Y., Amodeo, L., Yalaoui, F., Chen, H.: Ant colony optimization for solving an industrial layout problem. Eur. J. Oper. Res. 183(2), 633–642 (2007)
Khouadjia, M.R.: Solving Dynamic Vehicle Routing Problems: From Single-Solution Based Metaheuristics to Parallel Population Based Metaheuristics. Ph.D. Thesis, Lille University, France (2011)
Kilby, P., Prosser, P., Shaw, P.: Dynamic VRPs: a study of scenarios. Technical Report APES-06-1998, University of Strathclyde, Glasgow, Scotland (1998)
Kilby, P., Prosser, P., Shaw, P.: Guided local search for the vehicle routing problem. In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 473–486. Kluwer Academic Publishers (1999)
Mills, P., Tsang, E.P.K.: Guided local search for solving SAT and weighted MAXSAT problems. J. Autom. Reason. 24, 205–223 (2000)
Pillac, V., Gendreau, M., Gueret, C., Medaglia, A.L.: A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225, 1–11 (2013)
Psaraftis, H.N., Wen, M., Kontovas, C.A.: Dynamic vehicle routing problems: three decades and counting. Networks 67(1), 3–31 (2016)
Tarantilis, C.D., Zachariadis, E.E., Kiranoudis, C.T.: A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. INFORMS J Comput. 20(1), 154–168 (2008)
Voudouris, C., Tsang, E.: Partial constraint satisfaction problems and guided local search. In: Proceedigns of 2nd International Conference on Practical Application of Constraint Technology (PACT’96), London, pp. 337–356 (1996)
Voudouris, C., Tsang, E.: Guided local search and its application to the traveling salesman problem. Eur. J. Oper. Res. 113, 469–499 (1999)
Voudouris, C., Tsang, E.P.K., Alsheddy, A.: Guided local search. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, pp. 321–361. Springer, Berling, Heidelberg (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Barbucha, D. (2020). Multi-agent Approach to the DVRP with GLS Improvement Procedure. In: Czarnowski, I., Howlett, R., Jain, L. (eds) Intelligent Decision Technologies. IDT 2020. Smart Innovation, Systems and Technologies, vol 193. Springer, Singapore. https://doi.org/10.1007/978-981-15-5925-9_10
Download citation
DOI: https://doi.org/10.1007/978-981-15-5925-9_10
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-5924-2
Online ISBN: 978-981-15-5925-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)