Lagrangian relaxation method for integrated vehicles and drones routing model

Abstract

Nowadays, e-commerce increases parcel transportation demand year by year. Many companies are seeking the way to improve performance of delivery service and cost-efficiency. One among many solutions is using a drone attached with a truck for the last mile delivery. A drone can be launched from either depot or truck and returned to the depot or wait for the truck to take them back from the docking station around the delivery area. The vehicle routing problem with drones considers truck- and drone-route simultaneously. It is an enormous problem that cannot be solved by a normal linear programming method. This research proposes the Lagrangian relaxation technique, in conjunction with the Branch-and-Price technique, to estimate the lower bound of the solution in each iteration of the Branch-and-Price. The lower bound from the Lagrangian relaxation is tighter than the solution from the Column generation which can improve the total solution time. The bound use in Branch-and-Price as a fathom condition, these help the search tree not to explore unnecessary nodes. The computational experiment includes randomly generated instances and real-world instances. Moreover, the operation cost of truck-based and truck-drone-based are compared to point out the benefit of using drones.