A multi-objective optimization approach for the capacitated vehicle routing problem with time windows (CVRPTW)

Investigating complex combinatorial optimization problems such as the capacitated vehicle routing problem with time windows (CVRPTW) commonly benefits the advancement of logistic systems and telecommunications fields. CVRPTW is a elaborate strain of the well studied capacitated vehicle routing problem (CVRP) with a time window framework as an added constraint. As the problems are known to be NP-hard, meta-heuristics proficiently explore the search space to obtain near optimal solutions. In this manuscript, we explore the strength Pareto evolutionary algorithm SPEA2 hybridized with a hill climbing method as a local search, which yields a very sophisticated yet promising population based meta-heuristic algorithm. The novelty of our approach is in the AQ1 selection of multi objective evolutionary algorithm namely SPEA2, its proposed evolutionary operators, and the optimization for three targets: the total distance traveled, the number of routes, and the average time per route - a newly introduced objective -, which offers an interesting trade-off opportunity scenarios for practitioners or supply chain managers. Based on our experimental results, such multiple objective optimization can guide the search toward favorable reduction of the total distance as well as offering a margin of compromise in the selection of the objectives of the final solution in general. The presented algorithm is a Python implementation tested extensively on the Solomon's instances benchmark. Encouraging results are recorded (sometimes reaching the best
known in literature) and hints for further refinement are proposed for future research.