Modified sweeping approach for solving capacitated vehicle routing problem

This research proposes a modification to the Sweeping Approach (SWA) that can solve the Capacitated Vehicle Routing Problem (CVRP) to handle instances with clusters on radial positions. Obtaining a near-optimal solution to the CVRP in an efficient amount of time is a critical task for many delivery companies in the competitive market of today to reduce their overall transportation costs and enhance their service level since the complexity of this problem grows exponentially with the problem size. The SWA can find a near-optimal solution to the CVRP efficiently by performing angular sweeping in the assignment of locations into different vehicles. However, this approach does not work well when there is apparent clustering of locations on their radial positions. Therefore, this research proposes a Modified Sweeping Approach (Modified SWA) that considers both the locations’ polar angle and radial position to handle cases when there is apparent radial clustering of locations. The performance and sensitivity of the proposed approach are tested and compared to that of the classical SWA method. The experimental results prove the robustness of the proposed algorithm to different levels of noise and indicate its effectiveness in solving the CVRP for the targeted class of problems with an average improvement of 5% in the total distance traveled when compared to the classical SWA. However, the overall difference in the computational time for both SWA and modified SWA is insignificant.