Sweep Algorithm in Vehicle Routing Problem for Public Transport

Abstract

This paper investigates the capability of Sweep Algorithm in solving the vehicle routing problem for public transport. The Sweep Algorithm is firstly introduced as a method to search shortest route in the vehicle routing problem. In order to evaluate the result of the algorithm, current routes profile of a public transport is presented. An application is constructed based on algorithm and tested using current routes data. The route generation is performed repeatedly using different constraints in order to obtain the optimal solution. A route is selected based on shortest distance and capacity constraint. Each constraint affects the route selection to gain different combination of routes. Two methods in sweep algorithm are implemented and compared to find the better method. The result shows that Sweep Algorithm is capable of solving vehicle routing problem for public transport under certain constraints.