Distance based sweep nearest algorithm to solve capacitated vehicle routing problem

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)

PDF - Published Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

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.

Item Type:	Conference or Workshop Item (Plenary Papers)
Additional Information:	6724/51765
Uncontrolled Keywords:	Capacitated Vehicle Routing Problem (CVRP)
Subjects:	T Technology > TK Electrical engineering. Electronics Nuclear engineering
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Dr. M.M. Hafizur Rahman
Date Deposited:	23 Aug 2016 15:47
Last Modified:	22 May 2018 08:55
URI:	http://irep.iium.edu.my/id/eprint/51765

Actions (login required)

View Item