A genetic algorithm for vehicle routing in logistic networks with practical constraints

Grzegorz Koloch; Michał Lewandowski; Marcin Zientara; Grzegorz Grodecki; Piotr Matuszak; Igor Kantorski; Adam Nowacki

doi:10.5604/01.3001.0015.5584

Grzegorz Koloch SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0001-5506-2864 , Michał Lewandowski SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0002-6003-1859 , Marcin Zientara SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0002-3984-2665 , Grzegorz Grodecki SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0001-6558-3217 , Piotr Matuszak SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0002-5312-9698 , Igor Kantorski SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0001-9870-0803 , Adam Nowacki SGH Warsaw School of Economics, Institute of Econometrics, Decision Analysis and Support Unit, ul. Madalińskiego 6/8, 02-513 Warszawa ORCID:https://orcid.org/0000-0003-4635-6347 Przegląd Statystyczny. Statistical Review, vol. 68, 2021, 3, pages: 16-40 Published online: 30 December 2021 DOI 10.5604/01.3001.0015.5584

1238 Views 51 Downloads

ARTICLE

(English) PDF

ABSTRACT

We optimise a postal delivery problem with time and capacity constraints imposed on vehicles and nodes of the logistic network. Time constraints relate to the duration of routes, whereas capacity constraints concern technical characteristics of vehicles and postal operation outlets. We consider a method which can be applied to a brownfield scenario, in which capacities of outlets can be relaxed and prospective hubs identified. As a solution, we apply a genetic algorithm and test its properties both in small case studies and in a simulated problem instance of a larger (i.e. comparable with real-world instances) size. We show that the genetic operators we employ are capable of switching between solutions based on direct origin-to-destination routes and solutions based on transfer connections, depending on what is more beneficial in a given problem instance. Moreover, the algorithm correctly identifies cases in which volumes should be shipped directly, and those in which it is optimal to use transfer connections within a single problem instance, if an instance in question requires such a selection for optimality. The algorithm is thus suitable for determining hubs and satellite locations. All considerations presented in this paper are motivated by real-life problem instances experienced by the Polish Post, the largest postal service provider in Poland, in its daily plans of delivering postal packages, letters and pallets.

KEYWORDS

rich vehicle routing problem, brownfield, hubs and satellites, genetic algorithm

JEL

C60, C61, L87

REFERENCES

Archetti, C., & Speranza, M. G. (2012). Vehicle routing problems with split deliveries. International Transactions in Operational Research, 19(1–2), 3–22. https://doi.org/10.1111 /j.1475-3995.2011.00811.x.

Arnold, F., & Sörensen, K. (2019). What makes a VRP solution good? The generation of problemspecific knowledge for heuristics. Computers & Operations Research, 106, 280–288. https://doi.org/10.1016/j.cor.2018.02.007.

Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787–800. https://doi.org/10.1016/S0305-0548 (02)00051-5.

Bäck, T., Fogel, D. B., & Michalewicz, Z. (Eds.). (2018). Evolutionary Computation 1: Basic Algorithms and Operators. CRC Press. https://doi.org/10.1201/9781482268713.

Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1–6. https://doi.org/10.1016/j.ejor.2011.07.037.

Baldacci, R., Toth, P., & Vigo, D. (2010). Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research, 175(1), 213–245. https://doi.org/10.1007 /s10479-009-0650-0.

Baumung, M. N., Gündüz, H. I., Müller, T., & Sebastian, H.-J. (2015). Strategic Planning of Optimal Networks for Parcel and Letter Mail. In H.-J. Sebastian, P. Kaminsky & T. Müller (Eds.), Quantitative Approaches in Logistics and Supply Chain Management (pp. 81–103). Springer. https://doi.org/10.1007/978-3-319-12856-6_4.

Benjamin, A. M., & Beasley, J. E. (2013). Metaheuristics with disposal facility positioning for the waste collection VRP with time windows. Optimization Letters, 7(7), 1433–1449. https://doi.org /10.1007/s11590-012-0549-6.

Boland, N., Hewitt, M., Marshall, L., & Savelsbergh, M. (2017). The Continuous Time Service Network Design Problem. Operations Research, 65(5), 1303–1321. https://doi.org/10.1287 /opre.2017.1624.

Borčinová, Z. (2017). Two models of the capacitated vehicle routing problem. Croatian Operational Research Review, 8(2), 463–469. https://doi.org/10.17535/crorr.2017.0029.

Boussaid, I., Lepagnot, J., & Siarry, P. (2013). A survey on optimization metaheuristics. Information Sciences, 237, 82–117. https://doi.org/10.1016/j.ins.2013.02.041.

Bräysy, O., & Gendreau, M. (2005). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, 39(1), 104–118. https://doi.org/10.1287/trsc.1030.0056.

Casazza, M., Ceselli, A., & Calvo, R. W. (2018). A branch and price approach for the Split Pickup and Split Delivery VRP. Electronic Notes in Discrete Mathematics, 69, 189–196. https://doi.org /10.1016/j.endm.2018.07.025.

Çetiner, S., Sepil, C., & Süral, H. (2010). Hubbing and routing in postal delivery systems. Annals of Operations Research, 181(1), 109–124. https://doi.org/10.1007/s10479-010-0705-2.

Crevier, B., Cordeau, J. F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756–773. https://doi.org /10.1016/j.ejor.2005.08.015.

Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53(5), 512–522. https://doi.org /10.1057/palgrave.jors.2601319.

de Camargo, R. S., de Miranda, G., & Lokketangen, A. (2013). A new formulation and an exact approach for the many-to-many hub location-routing problem. Applied Mathematical Modelling, 37(12-13), 7465–7480. https://doi.org/10.1016/j.apm.2013.02.035.

Dréo, J., Pétrowski, A., Siarry, P., & Taillard, E. (2006). Metaheuristics for Hard Optimization: Methods and Case Studies. Springer-Verlag. https://doi.org/10.1007/3-540-30966-7.

Granada-Echeverri, M., Toro, E. M., & Santa, J. J. (2019). A mixed integer linear programming formulation for the vehicle routing problem with backhauls. International Journal of Industrial Engineering Computations, 10(2), 295–308. https://doi.org/10.5267/j.ijiec.2018.6.003.

Kadri, R. L., & Boctor, F. F. (2018). An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case. European Journal of Operational Research, 265(2), 454–462. https://doi.org/10.1016/j.ejor.2017.07.027.

Karimi, H., & Setak, M. (2018). A bi-objective incomplete hub location-routing problem with flow shipment scheduling. Applied Mathematical Modelling, 57, 406–431. https://doi.org/10.1016 /j.apm.2018.01.012.

Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80(5), 8091–8126. https://doi.org/10.1007/s11042 -020-10139-6.

Kerivin, H. L. M., Lacroix, M., Mahjoub, A. R., & Quilliot, A. (2008). The splittable pickup and delivery problem with reloads. European Journal of Industrial Engineering, 2(2), 112–133. https://doi.org/10.1504/EJIE.2008.017347.

Keskin, M., Laporte, G., & Çatay, B. (2019). Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers & Operations Research, 107, 77–94. https://doi.org/10.1016/j.cor.2019.02.014.

Kora, P., & Yadlapalli, P. (2017). Crossover Operators in Genetic Algorithms: A Review. International Journal of Computer Applications, 162(10), 34–36. https://doi.org/10.5120 /ijca2017913370.

Laporte, G., Gendreau, M., Potvin, J.-Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4-5), 285– 300. https://doi.org/10.1111/j.1475-3995.2000.tb00200.x.

Leung, J. M. Y., Magnanti, T. L., & Singhal, V. (1990). Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics. Transportation Science, 24(4), 245–260. https://doi.org /10.1287/trsc.24.4.245.

Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and Mutation Operators of Genetic Algorithms. International Journal of Machine Learning and Computing, 7(1), 9–12. http://doi.org/10.18178/IJMLC.

Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126– 141. https://doi.org/10.1016/j.ejor.2002.11.003.

Prins, C. (2002). Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case. Journal of Mathematical Modelling and Algorithms, 1(2), 135–150. https://doi.org/10.1023/A:1016516326823.

Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the Capacitated Vehicle Routing Problem. Mathematical Programming, 94(2–3), 343–359. https://doi.org/10.1007 /s10107-002-0323-0.

Rieck, J., & Zimmermann, J. (2010). A new mixed integer linear model for a rich vehicle routing problem with docking constraints. Annals of Operations Research, 181(1), 337–358. https://doi.org/10.1007/s10479-010-0748-4.

Spliet, R., & Gabor, A. F. (2015). The Time Window Assignment Vehicle Routing Problem. Transportation Science, 49(4), 721–731. https://doi.org/10.1287/trsc.2013.0510.

Squillero, G., & Tonda, A. (2016). Divergence of character and premature convergence: A survey of methodologies for promoting diversity in evolutionary optimization. Information Sciences, 329, 782–799. https://doi.org/10.1016/j.ins.2015.09.056.

Theurich, F., Fischer, A., & Scheithauer, G. (2021). A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs. EURO Journal on Computational Optimization, 9, 1–11. https://doi.org/10.1016/j.ejco.2020.100003.

Toth, P., & Vigo, D. (Eds.). (2002). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718515.

Umbarkar, A. J., & Sheth, P. D. (2015). Crossover operators in genetic algorithms: a review. ICTACT Journal on Soft Computing, 6(1), 1083–1092. http://doi.org/10.21917/ijsc.2015.0150.

Vajda, P., Eiben, A. E., & Hordijk, W. (2008). Parameter Control Methods for Selection Operators in Genetic Algorithms. In G. Rudolph, T. Jansen, N. Beume, S. Lucas & C. Poloni (Eds.), Parallel Problem Solving from Nature – PPSN X (pp. 620–630). Springer. https://doi.org/10.1007/978-3 -540-87700-4_62.

Wassan, N. A., & Nagy, G. (2014). Vehicle Routing Problem with Deliveries and Pickups: Modelling Issues and Meta-heuristics Solution Approaches. International Journal of Transportation, 2(1), 95–110. http://dx.doi.org/10.14257/ijt.2014.2.1.06.