Load-dependent vehicle routing problem with route time constraint: a heuristic approach - Nguyen Thuy Trang; Parthana Parthanadee; Jirachai Buddhakulsomsiri; Pham Duc Tai (Cogent Engineering)
This article explores a vehicle routing problem originating from the delivery operations of an e-commerce retailer in Thailand. The problem requires consideration of load-dependent distance objective and route time restriction. A mathematical model is formulated for the problem to minimize the total load-dependent distance subject to the time limit of a route. To take the last leg of a delivery route, where a vehicle returns empty, into consideration, a base load is placed on the vehicle. In addition, a heuristic algorithm is developed to solve large problem instances, with which the mathematical cannot be solved. The heuristic features a customized saving algorithm for route construction in combination with a series of route improvement mechanisms. The performance of the proposed mathematical model and the heuristic algorithm is evaluated by using adapted problem instances, where different combinations of capacity, route time limitations, and base loads are included. The results show that for instances with known optimal solutions, the heuristic algorithm can reach solutions with small gaps to the optimal. For those with only lower bounds, the heuristic algorithm can produce solutions close to these bounds. Moreover, the results reveal that choosing an appropriate base load improves the performance of the heuristic.