Column-and-row generation based exact algorithm for relay-based on-demand delivery systems

This paper studies an operation optimization problem in a relay-based on-demand delivery system that uses couriers and drones to transport customers’ parcels. For a batch of customer orders with their delivery due times, the system must decide which orders to accept and which courier to dispatch to pick up each accepted order and transport it to a suitable station, from where a drone will transport it to another station and then another courier will transport it to its final destination. Using mixed-integer linear programing, this paper formulates a novel arc-based set-packing model with two types of columns, i.e., drone plans and courier plans, to maximize the profit from transporting a batch of orders. By combining branch-and-price, column-and-row generation, and some tailored acceleration tactics, an exact algorithm is designed and implemented to efficiently solve the model. Experimental results validate the efficiency of the proposed exact algorithm. Moreover, we find that large numbers of couriers, drones, or stations do not always substantially improve the system’s performance; if order due times are urgent, the benefit of drones (couriers) is more (less) significant. The model’s robustness and the applicability of our methodology in large-scale applications are validated.