차량경로문제를 위한 새로운 서클 클러스터링 방법

Abstract

Vehicle routing problem has been widely solved by the various algorithms. The sweep algorithm is one of the frequently used algorithms in which the fan-shaped area is calculated after the grouping considering vehicle’s capacity and polar-angle routes in one plane. In this paper, a circle algorithm is proposed which can be used in the particular situations where stops are scattered in a lantern ring area. The proposed circle algorithm considers stops and depot on 2D plane and the plane is divided into ring-shapes with its center of weight. Mathematical models for calculating of vehicle routing distance for both algorithms are derived. Both algorithms are compared based on the derived mathematical models and simulation experiments. The result shows that circle algorithm performs better than sweep algorithm. In order to take advantage of both algorithms, the combined circle and sweep algorithm is suggested for practical use.