Distance based sweep nearest algorithm to solve capacitated vehicle routing problem
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 depend...
| Main Authors: | , , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/51765/ http://irep.iium.edu.my/51765/ http://irep.iium.edu.my/51765/1/51765_Distance_based_Sweep_Nearest_Algorithm.pdf |
| Summary: | 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. |
|---|