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.