A Heuristic Algorithm for the Vehicle-Dispatch Problem

TLDR

The paper proposes the sweep algorithm to efficiently solve medium‑ and large‑scale vehicle‑dispatch problems with load and distance constraints. The sweep algorithm constructs routes by sorting locations by polar‑coordinate angle, iteratively improving total distance, and scales linearly with the number of locations when the average locations per route remain constant. The algorithm solves a 75‑location problem in ~75 s and a 100‑location problem in ~115 s on an IBM 360/67, scales quadratically with average locations per route, and outperforms Gaskell’s savings approach while slightly lagging behind Christofides and Eilon in efficiency.

Abstract

This paper introduces and illustrates an efficient algorithm, called the sweep algorithm, for solving medium- as well as large-scale vehicle-dispatch problems with load and distance constraints for each vehicle. The locations that are used to make up each route are determined according to the polar-coordinate angle for each location. An iterative procedure is then used to improve the total distance traveled over all routes. The algorithm has the feature that the amount of computation required increases linearly with the number of locations if the average number of locations for each route remains relatively constant. For example, if the average number of locations per route is 7.5, the algorithm takes approximately 75 seconds to solve a 75-location problem on an IBM 360/67 and approximately 115 seconds to solve a 100-location problem. In contrast, the time to solve a problem with a fixed number of locations increases quadratically with the average number of locations per route. The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell's and is slightly less so than Christofides and Eilon's.