期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2019
卷号：10
期号：10
页码：259-264
出版社：Science and Information Society (SAI)
摘要：The Capacitated Vehicle Routing Problem (CVRP)
is an optimization problem owing to find minimal travel
distances to serve customers with homogeneous fleet of vehicles.
Clustering customers and then assign individual vehicles is a
widely-studied way, called cluster first and route second (CFRS)
method, for solving CVRP. Cluster formation is important
between two phases of CFRS for better CVRP solution. Sweep
(SW) clustering is the pioneer one in CFRS method which solely
depends on customers’ polar angle: sort the customers according
to polar angle; and a cluster starts with customer having smallest
polar angle and completes 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 inserts other customer(s)
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
continues 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 solving benchmark CVRPs. For route optimization of
individual vehicles, Genetic Algorithm, Ant Colony Optimization
and Particle Swarm Optimization are considered for clusters
formation with SW, SN and DSN. The experimental results
identified that proposed DSN outperformed SN and SW in most
of the cases and DSN with PSO was the best suited method for
CVRP.
