Lagrangian Relaxation Method for Integrated Vehicles and Drones Routing Model

Abstract

Nowadays, e-commerce increases parcels 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. 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 delivery area. The vehicle routing problem with drone considers truck- and drone-route simultaneously. It is an enormous problem that cannot be solved by 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.