An Algorithm to Solve Heterogeneous Vehicle Routing Problem With Second Trip

Abstract

The realistic logistics not only involves vehicle capacity and working hours, but also factors such as the second trip of vehicles and heterogeneous vehicles. Aiming at the constraints of these VRP variants, an algorithm is proposed to solve the heterogeneous vehicle routing problem with a second trip. In the process of calculating the initial solution, the concept of k-ring shaped Voronoi neighbors reduces the computational complexity and avoids the problems caused by outliers. When allocating customers, the idea of “Borrow-In and Borrow-Out” proposed in this article is adopted to rationalize the route planning results. In the calculation process of considering the second trip, the customers closer to the depot are regarded as the final order. For heterogeneous vehicles, this article adopts a greedy strategy. The experimental results of multiple instances show that if the depot provides a heterogeneous fixed vehicles fleet, compared to when only a single vehicle type is provided, the result is a reduced number of vehicles used by 4.46% on average, and the loading utilization rate of vehicles is increased by 4.02% on average. And after the calculation of considering the second trip, the number of vehicles used is reduced by 5.09% on average, and the loading utilization rate of vehicles is increased by 4.41% on average. It can be seen that the algorithm proposed in this article can obtain high-quality route allocation results for large-scale orders.

Keywords

• Vehicle routing problem
• second trip
• heterogeneous vehicles
• large-scale logistics
• Voronoi diagram