Implementing vehicle routing algorithms

TLDR

Heuristic programming algorithms often tackle large problems that require handling massive data sets, and their performance can be enhanced by employing efficient data structures. The study evaluates heuristic vehicle routing algorithms, comparing Clarke and Wright, Gillett and Miller, and Tyagi methods, and seeks to develop modifications enabling rapid solutions for large‑scale problems. The authors compare these techniques and introduce extensions, including a multi‑depot routing algorithm, that allow solving problems with hundreds of demand points in seconds. The methods were demonstrated on an urban newspaper routing problem serving over 100,000 customers, showing practical applicability.

Abstract

Abstract Heuristic programming algorithms frequently address large problems and require manipulation and operation on massive data sets. The algorithms can be improved by using efficient data structures. With this in mind, we consider heuristic algorithms for vehicle routing, comparing techniques of Clarke and Wright, Gillett and Miller, and Tyagi, and presenting modifications and extensions which permit problems involving hundreds of demand points to be solved in a matter of seconds. In addition, a multi‐depot routing algorithm is developed. The results are illustrated with a routing study for an urban newspaper with an evening circulation exceeding 100,000.