Multiobjective Memetic GRASP to Solve Vehicle Routing Problems with Time Windows Size

Carlos Molano, Manuel Lagos, Carlos Alberto Cobos

Abstract


The Vehicle Routing Problem with Time Windows is a complete NP combinatorial problem in which product deliveries to customers must be made under certain time constraints. This problem can be solved from a single objective approach, well studied in the state of the art, in which the objective of the total travel distance or the size of the fleet (number of vehicles) is generally minimized. However, recent studies have used a multiobjective approach (Multiobjective Vehicle Routing Problem with Time Windows, MOVRPTW) that solves the problem from a viewpoint closer to reality. This work presents a new multiobjective memetic algorithm based on the GRASP (Greedy Randomized Adaptive Search Procedures) algorithm called MOMGRASP for the minimization of three objectives in MOVRPTW (total travel time, waiting time of customers to be attended, and balance of total travel time between routes). The results of the experimentation carried out with 56 problems proposed by Solomon and 45 problems proposed by Castro-Gutiérrez show that the proposed algorithm finds better solutions in these three objectives and competitive solutions than those reported by Zhou (compared to LSMOVRPTW algorithm and optimizing 5 objectives: number of vehicles, total travel distance, travel time of the longest route, total waiting time due to early arrivals, and total delay time due to late arrivals) and by Baños (versus the MMOEASA algorithm in two scenarios; case 1: total travel distance and balance of distance and case 2: total travel distance and balance of workload).

Keywords


Vehicle routing problem; grasp; metaheuristic algorithm; combinatorial optimization; multiobjective; memetic.

Full Text:

PDF

References


J. Caceres-Cruz, P. Arias, D. Guimarans, D. Riera, and A. A. Juan, “Rich vehicle routing problem: Survey,†ACM Comput. Surv., vol. 47, no. 2, pp. 1–28, 2014, doi: 10.1145/2666003.

A. Dixit, A. Mishra, and A. Shukla, “Vehicle routing problem with time windows using meta-heuristic algorithms: A survey,†in Advances in Intelligent Systems and Computing, 2019, vol. 741, pp. 539–546, doi: 10.1007/978-981-13-0761-4_52.

S. Ben Hamida, R. Gorsane, and K. Gorsan Mestiri, “Towards a better understanding of genetic operators for ordering optimization: Application to the capacitated vehicle routing problem,†in 15th International Conference on Software Technologies, ICSOFT 2020, 2020, pp. 461–469.

R. S. Kumar, K. Kondapaneni, V. Dixit, A. Goswami, L. S. Thakur, and M. K. Tiwari, “Multi-objective modeling of production and pollution routing problem with time window: A self-learning particle swarm optimization approach,†Comput. Ind. Eng., vol. 99, pp. 29–40, 2016, doi: 10.1016/j.cie.2015.07.003.

Y. Zhou and J. Wang, “A Local Search-Based Multiobjective Optimization Algorithm for Multiobjective Vehicle Routing Problem with Time Windows,†IEEE Syst. J., vol. 9, no. 3, pp. 1100–1113, 2015, doi: 10.1109/JSYST.2014.2300201.

H. Yousefi, R. Tavakkoli-Moghaddam, M. Taheri Bavil Oliaei, M. Mohammadi, and A. Mozaffari, “Solving a bi-objective vehicle routing problem under uncertainty by a revised multichoice goal programming approach,†Int. J. Ind. Eng. Comput., vol. 8, no. 3, pp. 283–302, 2017, doi: 10.5267/j.ijiec.2017.1.003.

E. T. Yassen, M. Ayob, M. Z. A. Nazri, and N. R. Sabar, “An adaptive hybrid algorithm for vehicle routing problems with time windows,†Comput. Ind. Eng., vol. 113, pp. 382–391, 2017, doi: 10.1016/j.cie.2017.09.034.

V. F. Yu, T. Iswari, N. M. E. Normasari, A. M. S. Asih, and H. Ting, “Simulated annealing with restart strategy for the blood pickup routing problem,†in IOP Conference Series: Materials Science and Engineering, 2018, vol. 337, no. 1, doi: 10.1088/1757-899X/337/1/012007.

J. Wang, W. Ren, Z. Zhang, H. Huang, and Y. Zhou, “A Hybrid Multiobjective Memetic Algorithm for Multiobjective Periodic Vehicle Routing Problem with Time Windows,†IEEE Trans. Syst. Man, Cybern. Syst., vol. 50, no. 11, pp. 4732–4745, 2020, doi: 10.1109/TSMC.2018.2861879.

A. Agárdi, L. Kovács, and T. Bányai, “Optimization of multi-depot periodic vehicle routing problem with time window,†Acad. J. Manuf. Eng., vol. 17, no. 4, pp. 96–108, 2019.

M. Gmira, M. Gendreau, A. Lodi, and J.-Y. Potvin, “Tabu search for the time-dependent vehicle routing problem with time windows on a road network,†Eur. J. Oper. Res., vol. 288, no. 1, pp. 129–140, 2021, doi: https://doi.org/10.1016/j.ejor.2020.05.041.

R. Baños, J. Ortega, C. Gil, A. L. Márquez, and F. De Toro, “A hybrid meta-heuristic for multi-objective Vehicle Routing Problems with Time Windows,†Comput. Ind. Eng., vol. 65, no. 2, pp. 286–296, 2013, doi: 10.1016/j.cie.2013.01.007.

A. B. Pratiwi, A. Pratama, I. Sa’diyah, and H. Suprajitno, “Vehicle routing problem with time windows using natural inspired algorithms,†in Journal of Physics: Conference Series, 2018, vol. 974, no. 1, doi: 10.1088/1742-6596/974/1/012025.

J. Chen and J. Shi, “A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms,†Comput. Ind. Eng., vol. 133, pp. 95–106, 2019, doi: 10.1016/j.cie.2019.05.008.

N. Rezaei, S. Ebrahimnejad, A. Moosavi, and A. Nikfarjam, “A green vehicle routing problem with time windows considering the heterogeneous fleet of vehicles: Two metaheuristic algorithms,†Eur. J. Ind. Eng., vol. 13, no. 4, pp. 507–535, 2019, doi: 10.1504/EJIE.2019.100919.

L. Deng and J. Zhang, “A Hybrid Ant Colony Optimization for Bi-Objective VRP with Time Windows,†Complex Syst. Complex. Sci., vol. 17, no. 4, pp. 73–84, 2020, doi: 10.13306/j.1672-3813.2020.04.009.

M. Song, J. Li, Y. Han, Y. Han, L. Liu, and Q. Sun, “Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics,†Appl. Soft Comput., vol. 95, p. 106561, 2020, doi: https://doi.org/10.1016/j.asoc.2020.106561.

G. Srivastava, A. Singh, and R. Mallipeddi, “NSGA-II with objective-specific variation operators for multiobjective vehicle routing problem with time windows,†Expert Syst. Appl., vol. 176, p. 114779, 2021, doi: https://doi.org/10.1016/j.eswa.2021.114779.

T. S. Khoo and B. B. Mohammad, “The parallelization of a two-phase distributed hybrid ruin-and-recreate genetic algorithm for solving multi-objective vehicle routing problem with time windows,†Expert Syst. Appl., vol. 168, p. 114408, 2021, doi: https://doi.org/10.1016/j.eswa.2020.114408.

H. Zhang, Q. Zhang, L. Ma, Z. Zhang, and Y. Liu, “A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows,†Inf. Sci. (Ny)., vol. 490, pp. 166–190, 2019, doi: https://doi.org/10.1016/j.ins.2019.03.070.

J. C. Molina, J. L. Salmeron, and I. Eguia, “An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows,†Expert Syst. Appl., vol. 157, p. 113379, 2020, doi: https://doi.org/10.1016/j.eswa.2020.113379.

A. K. Ariyani, W. F. Mahmudy, and Y. P. Anggodo, “Hybrid genetic algorithms and simulated annealing for multi-trip vehicle routing problem with time windows,†Int. J. Electr. Comput. Eng., vol. 8, no. 6, pp. 4713–4723, 2018, doi: 10.11591/ijece.v8i6.pp.4713-4723.

J. Euchi, S. Zidi, and L. Laouamer, “A Hybrid Approach to Solve the Vehicle Routing Problem with Time Windows and Synchronized Visits In-Home Health Care,†Arab. J. Sci. Eng., vol. 45, no. 12, pp. 10637–10652, 2020, doi: 10.1007/s13369-020-04828-5.

P. Jiang, J. Men, H. Xu, S. Zheng, Y. Kong, and L. Zhang, “A Variable Neighborhood Search-Based Hybrid Multiobjective Evolutionary Algorithm for HazMat Heterogeneous Vehicle Routing Problem with Time Windows,†IEEE Syst. J., vol. 14, no. 3, pp. 4344–4355, 2020, doi: 10.1109/JSYST.2020.2966788.

M. Liu, Y. Shen, Q. Zhao, and Y. Shi, “A Hybrid BSO-ACS Algorithm for Vehicle Routing Problem with Time Windows on Road Networks,†in 2020 IEEE Congress on Evolutionary Computation (CEC), 2020, pp. 1–8, doi: 10.1109/CEC48606.2020.9185868.

Y. Shen, M. Liu, J. Yang, Y. Shi, and M. Middendorf, “A hybrid swarm intelligence algorithm for vehicle routing problem with time windows,†IEEE Access, vol. 8, pp. 93882–93893, 2020, doi: 10.1109/ACCESS.2020.2984660.

A. Pessoa, R. Sadykov, and E. Uchoa, “Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems,†Eur. J. Oper. Res., vol. 270, no. 2, pp. 530–543, 2018, doi: https://doi.org/10.1016/j.ejor.2018.04.009.

R. F. Fachini and V. A. Armentano, “Logic-based Benders decomposition for the heterogeneous fixed fleet vehicle routing problem with time windows,†Comput. Ind. Eng., vol. 148, p. 106641, 2020, doi: https://doi.org/10.1016/j.cie.2020.106641.

J. Castro-Gutierrez, D. Landa-Silva, and J. Moreno Pérez, “Nature of real-world multi-objective vehicle routing with evolutionary algorithms,†in Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics, 2011, pp. 257–264, doi: 10.1109/ICSMC.2011.6083675.

M. M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,†Oper. Res., vol. 35, no. 2, pp. 254–265, 1987, doi: 10.1287/opre.35.2.254.

C. Cobos, A. Paz, J. Luna, C. Erazo, and M. Mendoza, “A Multi-Objective Approach for the Calibration of Microscopic Traffic Flow Simulation Models,†IEEE Access, vol. 8, pp. 103124–103140, 2020, doi: 10.1109/ACCESS.2020.2999081.

E. Ruano-Daza, C. Cobos, J. Torres-Jimenez, M. Mendoza, and A. Paz, “A multiobjective bilevel approach based on global-best harmony search for defining optimal routes and frequencies for bus rapid transit systems,†Appl. Soft Comput. J., vol. 67, pp. 567–583, Jun. 2018, doi: 10.1016/j.asoc.2018.03.026.




DOI: http://dx.doi.org/10.18517/ijaseit.12.4.16048

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development