Distance based Sweep Nearest Algorithm to Solve Capacitated Vehicle Routing Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 10
Abstract
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.
Authors and Affiliations
Zahrul Jannat Peya, M. A. H. Akhand, Tanzima Sultana, M. M. Hafizur Rahman
Keywords
Related Articles
- EP ID EP665078
- DOI 10.14569/IJACSA.2019.0101036
- Views 112
- Downloads 0
IMPLEMENTATION OF NODE ENERGY BASED ON ENCRYPTION KEYING
This paper deals with Designing cost-efficient, secure network protocols for any Networks is a challenging problem because node in a network itself is resource-limited. Since the communication cost is the most dominant f...
Big Brother: A Road Map for Building Ubiquitous Surveillance System in Nigeria
In this paper, we propose a method to improve the security challenges in Nigeria by embedding literally hundreds of invisible computers into the environment with each computer performing its tasks without requiring human...
Color, texture and shape descriptor fusion with Bayesian network classifier for automatic image annotation
Due to the large amounts of multimedia data prevalent on the Web, Some images presents textural motifs while others may be recognized with colors or shapes of their content. The use of descriptors based on one’s features...
User-Based Interaction for Content-Based Image Retrieval by Mining User Navigation Patterns.
In Internet, Multimedia and Image Databases image searching is a necessity. Content-Based Image Retrieval (CBIR) is an approach for image retrieval. With User interaction included in CBIR with Relevance Feedback (RF) tec...
MAS based on a Fast and Robust FCM Algorithm for MR Brain Image Segmentation
In the aim of providing sophisticated applications and getting benefits from the advantageous properties of agents, designing agent-based and multi-agent systems has become an important issue that received further consid...