Multi-criteria vehicle routing problem for a real-life parcel locker-based delivery

In this paper, a multi-criteria Vehicle Routing Problem with distance and capacity constraints for modeling a delivery system with parcel locker, is considered. The problem is formulated and two optimization criteria are defined. The first criterion minimizes the total travel time of all vehicles and the second criterion minimizes the total penalty for late delivery of orders. Three solving methods, relying on the concept of Pareto-optimality, are proposed: a greedy constructive heuristic, a Tabu Search metaheuristic and a Genetic Algorithm. A number of benchmark instances are created using real-life parcel locker locations and traveling times, from one of the major cities in Poland. In preliminary research, sorting strategies for the greedy method are tested, with the sorting based on deadline–arrival difference to priority ratio yielding the best performance in all tested cases. Next, computer experiments are performed to evaluate the quality of the proposed methods, using the concept of Hypervolume Indicator. Results confirm that both Tabu Search and Genetic Algorithm significantly improve the solution provided by the greedy algorithm, with Genetic Algorithm being the most effective on average. However, results also indicate that both Tabu Search and Genetic Algorithm have different effectiveness in different cases. It is concluded that the best performance is achieved by both algorithms being used in parallel, complementing each other.