A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows

The Capacitated Vehicle Routing Problem with Time Windows is an important combinatorial optimization problem consisting in the determination of the set of routes of minimum distance to deliver goods, using a fleet of identical vehicles with restricted capacity, so that vehicles must visit customers within a time frame. A large number of algorithms have been proposed to solve single-objective formulations of this problem, including meta-heuristic approaches, which provide high quality solutions in reasonable runtimes. Nevertheless, in recent years some authors have analyzed multi-objective variants that consider additional objectives to the distance travelled. This paper considers not only the minimum distance required to deliver goods, but also the workload imbalance in terms of the distances travelled by the used vehicles and their loads. Thus, MMOEASA, a Pareto-based hybrid algorithm that combines evolutionary computation and simulated annealing, is here proposed and analyzed for solving these multi-objective formulations of the VRPTW. The results obtained when solving a subset of Solomon’s benchmark problems show the good performance of this hybrid approach.

► We analyze two multi-objective variants of the vehicle routing problem with time windows.
► We present a Pareto-based meta-heuristic that combines evolutionary computation and simulated annealing.
► The algorithms are analyzed according to the multi-objective formulation, runtime, and type of problem.
► The hybrid approach outperforms NSGA-II and SPEA2 in terms of convergence and diversity.
► Pareto-based meta-heuristics provide competitive non-dominated fronts in a short runtime.