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...

Full description

Bibliographic Details
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/ http://irep.iium.edu.my/51765/ http://irep.iium.edu.my/51765/1/51765_Distance_based_Sweep_Nearest_Algorithm.pdf

id	iium-51765
recordtype	eprints
spelling	iium-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 NonPeerReviewed 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/
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
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/ http://irep.iium.edu.my/51765/ http://irep.iium.edu.my/51765/1/51765_Distance_based_Sweep_Nearest_Algorithm.pdf
first_indexed	2023-09-18T21:13:23Z
last_indexed	2023-09-18T21:13:23Z
_version_	1777411401345662976

Distance based sweep nearest algorithm to solve capacitated vehicle routing problem

Similar Items