Distance based sweep nearest algorithm to solve capacitated vehicle routing problem

• Main Authors: Akhand, M. A. H, Sultana, Tanzima, Peya, Zahrul Jannat, Rahman, M.M. Hafizur
• Format: Conference or Workshop Item
• Language: English
• Published: 2016
• Subjects: TK Electrical engineering. Electronics Nuclear engineering
• Online Access: http://irep.iium.edu.my/51765/1/51765_Distance_based_Sweep_Nearest_Algorithm.pdf; http://irep.iium.edu.my/51765/; http://www.icetss.org/

Capacitated Vehicle Routing Problem (CVRP) is a real life constraint satisfaction problem to find minimal travel distances to serve customers with homogeneous fleet of vehicles. Among several methods, Sweep algorithm in 2-phase approach is popular in solving CVRP. Sweep (SW) method solely depends on customers’ polar angle: sort the customers according to polar angle; and a cluster starts with customer having smallest polar angle and complete it considering others according to polar angle. On the other hand, Sweep Nearest (SN) algorithm, an extension of Sweep, also considers smallest polar angle customer to initialize a cluster but inserted other customer based on the nearest neighbor approach. This study investigates a different way of clustering based on nearest neighbor approach. The proposed Distance based Sweep Nearest (DSN) method starts clustering from the farthest customer point and continue for a cluster based on nearest neighbor concept. The proposed method does not rely on polar angle of the customers like SW and SN. To identify the effectiveness of the proposed approach, SW, SN and DSN have been implemented in this study. For route optimization, Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) are considered in this study. The experimental studies on a large number of the benchmark CVRPs identified that proposed DSN outperformed SN and SW most of the cases and hence DSN with PSO is a suitable method for CVRP.