Hybrid Multi-Objective Optimization Approach With Pareto Local Search for Collaborative Truck-Drone Routing Problems Considering Flexible Time Windows

The collaboration of drones and trucks for last-mile delivery has attracted much attention. In this paper, we address a collaborative routing problem of the truck-drone system, in which a truck collaborates with multiple drones to perform parcel deliveries and each customer can be served earlier and later than the required time with a given tolerance. To meet the practical demands of logistics companies, we build a multi-objective optimization model that minimizes total distribution cost and maximizes overall customer satisfaction simultaneously. We propose a hybrid multi-objective genetic optimization approach incorporated with a Pareto local search algorithm to solve the problem. Particularly, we develop a greedy-based heuristic method to create initial solutions and introduce a problem-specific solution representation, genetic operations, as well as six heuristic neighborhood strategies for the hybrid algorithm. Besides, an adaptive strategy is adopted to further balance the convergence and the diversity of the hybrid algorithm. The performance of the proposed algorithm is evaluated by using a set of benchmark instances. The experimental results show that the proposed algorithm outperforms three competitors. Furthermore, we investigate the sensitivity of the proposed model and hybrid algorithm based on a real-world case in Changsha city, China.