Improved algorithms speed up delivery with vehicles of different speeds
Improved Approximations for Vehicle Routing with Nonuniform Speeds
Data Structures and Algorithms
Summary
This work tackles the problem of routing vehicles that travel at different speeds to deliver goods or visit locations, aiming to finish all routes as quickly as possible. The authors present better methods that find routes close to the best possible, improving over earlier less efficient approaches. They handle versions where deliveries can be split across visits or must be delivered in one go, and where vehicles can carry limited loads and return to reload. Their results make planning more efficient when vehicles vary in speed and capacity.
What this means in practice
- •For logistics planners: Create delivery schedules that minimize total finish time using fleets with mixed vehicle speeds and capacities more effectively.
- •For fleet management teams: Optimize routing for heterogeneous vehicle fleets to improve dispatch and reduce delivery delays when speeds vary.
Authors
Hong Li
Abstract
We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances satisfy the triangle inequality. Each vehicle has a specified speed, and if the total length traveled by a vehicle of speed $s$ is $L$, its completion time is $L/s$. In the heterogeneous traveling salesman problem (HetTSP), each vehicle executes one tour starting and ending at the depot, and the tours collectively visit all clients. The objective is to minimize the maximum completion time among the vehicles. We give a $6$-approximation algorithm for HetTSP, improving the previous $90(1+δ)$-approximation for any fixed $δ>0$. We also consider two versions of the heterogeneous capacitated vehicle routing problem (HetCVRP). Each client has a demand, and the vehicles have identical capacities. A vehicle may execute several tours, each starting and ending at the depot, and reload at the depot between consecutive tours; the total demand delivered on each tour cannot exceed the vehicle capacity. In the split-delivery version of HetCVRP, the demand of a client may be divided among multiple visits, possibly by different vehicles. We give a $\frac92+2\sqrt3<7.965$-approximation algorithm for this problem. In the unsplit-delivery version of HetCVRP, the entire demand of each client must be delivered in a single visit. We give a $\frac{11}{2}+3\sqrt2<9.743$-approximation algorithm, improving the previous $450(1+δ)$-approximation for any fixed $δ>0$.