IJASEIT

International Journal on Advanced Science, Engineering and Information Technology, Vol. 12 (2022) No. 4, pages: 1335-1343, DOI:10.18517/ijaseit.12.4.16048

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).