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...
Saved in:
Main Authors: | , , , |
---|---|
Format: | Conference or Workshop Item |
Language: | English |
Published: |
2016
|
Subjects: | |
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/ |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
my.iium.irep.51765 |
---|---|
record_format |
dspace |
spelling |
my.iium.irep.517652018-05-22T00:55:01Z http://irep.iium.edu.my/51765/ Distance based sweep nearest algorithm to solve capacitated vehicle routing problem Akhand, M. A. H Sultana, Tanzima Peya, Zahrul Jannat Rahman, M.M. Hafizur TK Electrical engineering. Electronics Nuclear engineering 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. 2016-08-22 Conference or Workshop Item REM application/pdf en http://irep.iium.edu.my/51765/1/51765_Distance_based_Sweep_Nearest_Algorithm.pdf Akhand, M. A. H and Sultana, Tanzima and Peya, Zahrul Jannat and Rahman, M.M. Hafizur (2016) Distance based sweep nearest algorithm to solve capacitated vehicle routing problem. In: 2nd International Conference on Engineering, Technologies, and Social Sciences (ICETSS 2016), 22nd-24th Aug. 2016, Kuala Lumpur. (Unpublished) http://www.icetss.org/ |
institution |
Universiti Islam Antarabangsa Malaysia |
building |
IIUM Library |
collection |
Institutional Repository |
continent |
Asia |
country |
Malaysia |
content_provider |
International Islamic University Malaysia |
content_source |
IIUM Repository (IREP) |
url_provider |
http://irep.iium.edu.my/ |
language |
English |
topic |
TK Electrical engineering. Electronics Nuclear engineering |
spellingShingle |
TK Electrical engineering. Electronics Nuclear engineering Akhand, M. A. H Sultana, Tanzima Peya, Zahrul Jannat Rahman, M.M. Hafizur Distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
description |
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. |
format |
Conference or Workshop Item |
author |
Akhand, M. A. H Sultana, Tanzima Peya, Zahrul Jannat Rahman, M.M. Hafizur |
author_facet |
Akhand, M. A. H Sultana, Tanzima Peya, Zahrul Jannat Rahman, M.M. Hafizur |
author_sort |
Akhand, M. A. H |
title |
Distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
title_short |
Distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
title_full |
Distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
title_fullStr |
Distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
title_full_unstemmed |
Distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
title_sort |
distance based sweep nearest algorithm to solve capacitated vehicle routing problem |
publishDate |
2016 |
url |
http://irep.iium.edu.my/51765/1/51765_Distance_based_Sweep_Nearest_Algorithm.pdf http://irep.iium.edu.my/51765/ http://www.icetss.org/ |
_version_ |
1643614033904926720 |
score |
13.18916 |