Lagrangian Relaxation Algorithm for Solving Multi-Fleet Feeder Vehicle Routing Problem

Receiving fast, flexible, reliable and low-cost delivery services by customers is one of the important challenges for the distribution of goods, especially in urban areas. After that, with the increase in demand and as a result, the increase in vehicles for the purpose of goods' transportation, it causes congestion in urban transportation networks. Therefore, in this study, the multi-fleet feeder vehicle routing problem is investigated in a situation where several trucks and motorcycles cooperate with each other to satisfy the demand at the same time. The feeding vehicle routing problem consists of a heterogeneous fleet of vehicles, including trucks and it makes it possible for motorcycles to pass in high-traffic areas and distribute urban traffic easily.  In fact, the feeder approach in the VRP is to reduce the number of times of returning to the main depot for loading and to save the cost and time of tours. Here, at first, a mathematical model is presented, then, due to the high complexity of the mixed integer programming model and in order to reduce the runtime of solving the model in large dimensions, the Lagrangian relaxation algorithm with the sub-gradient optimization approach is proposed. The results showed that with the increase in the dimensions of the problem, the runtime of the proposed algorithm is less compared to the outputs of GAMS. Also, the runtime saving resulting from solving the model with the Lagrangian relaxation algorithm is significant, and as a result, this algorithm is effective for solving the model.