A Proposed Metaheuristic for Solving Multi-Objective Heterogeneous Vehicle Routing Problems with Time Windows

Abstract

Multi-objective optimization (MOO) has gained popularity and research interests due to its closeness in real-life applications. One of the applications of MOO is in routing problems such as the vehicle routing problems (VRP). The heterogeneity of fleet raises the complexity in VRP and a number of research has been devoted to solve the multi-objective heterogeneous vehicle routing problems (MO-HVRP) and its variants such as MO-HVRP with time windows (MO-HVRPTW). One study has attempted to develop an algorithm for MO-HVRPTW but the reported 5-6 hours of computation time is considered not practical especially in logistics problems that require fast solutions even at the cost of optimality, such as in the health sector (distribution of vaccines, blood, etc.). This paper aims to remedy the situation by improving the previous algorithm. The hybridization of elitist non-dominated sorting genetic algorithm (NSGA-II) and genetic algorithm (GA) is maintained, but a better memory management is developed in the new algorithm by keeping track of infeasible chromosomes and allowing soft time windows instead of hard time windows. Four scenarios were tested, alternating the hard and time windows and also the mutation probabilities. Compared to the results from the previous algorithm, the new algorithm reduces the computation time by 68.37% and the number of infeasible splitting by 52.84%.