MODIFIED SWEEPING ALGORITHM FOR SOLVING CAPACITATED VEHICLE ROUTING PROBLEM WITH RADIAL CLUSTERED PATTERNS - Altarawneh, Lubna; Kwon, Soongeol (International Journal of Industrial Engineering: Theory, Applications and Practice, 2023)
This research proposes a modification to the Sweeping Algorithm (SWA) to solve the Capacitated Vehicle Routing Problem (CVRP) for real-world cases where locations are present on radial patterns. The SWA solves CVRP instances efficiently by performing angular sweeping to obtain clusters of locations. However, the SWA does not consider radial distances when clustering the locations, which may cause inefficient clustering when there is a presence of locations on radial patterns. Therefore, this research proposes a systematic approach to solve CVRP instances with apparent radial clusters by considering their angular and radial distances in the clustering phase. This method is configurable to locations’ geography and can handle different locations’ assignments. The experimental results indicate that the proposed heuristic outperforms SWA and its well-known variant, Sweep Nearest Neighbor (SNN), for the targeted instances designed with radial clusters. The results for CVRP benchmark instances show comparable performance when using the proposed heuristic.