Some extensions to the sweep algorithm

Abstract

The sweep algorithm has been widely used for the vehicle routing problem and its variants since it was published in 1971. It clusters a group of stops into a route according to the polar angle between the stops and the depot. In this paper, we point out the weakness of grouping stops solely by the polar angle in the sweep algorithm and propose some extensions to the algorithm. The sweep nearest algorithm and the usage of various reference points are proposed. The effectiveness of the extensions is demonstrated by computational results on the benchmark problems of the capacitated vehicle routing problem.