Routing (electronic design automation)

Gene

Algorithm

Engineering

Transport engineering

Biology

Drone

Robustness (evolution)

Vehicle routing problem

Biochemistry

Computer science

Integer programming

Computer network

Genetics

Simulated annealing

Truck

Automotive engineering

Artificial intelligence

Cluster analysis

Chemistry

Tabu search

Machine learning

IEEE Transactions on Intelligent Transportation Systems

The COVID-19 pandemic calls for contactless deliveries. To prevent the further spread of the disease and ensure the timely delivery of supplies, this paper investigates a collaborative truck-drone routing problem for contactless parcel delivery (CRP-T&D), which allows multiple trucks and multiple drones to deliver parcels cooperatively in epidemic areas. We formulate a mixed-integer programming model that minimizes the delivery time, with the consideration of the energy consumption model of drones. To solve CRP-T&D, we develop an improved variable neighborhood descent (IVND) that combines the Metropolis acceptance criterion of Simulated Annealing (SA) and the tabu list of Tabu Search (TS). Meanwhile, the integration of K-means clustering and Nearest neighbor strategy is applied to generate the initial solution. To evaluate the performance of IVND, experiments are conducted by comparing IVND with VND, SA, TS, variants of VND, and large neighborhood search (LNS) on instances with different scales. Several critical factors are tested to verify the robustness of IVND. Moreover, the experimental results on a practical instance further demonstrate the superior performance of IVND.

Collaborative Truck-Drone Routing for Contactless Parcel Delivery During the Epidemic