Capacitated Vehicle Routing Problem Solving using Adaptive Sweep and Velocity Tentative PSO
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 12
Abstract
Vehicle Routing Problem (VRP) has become an integral part in logistic operations which determines optimal routes for several vehicles to serve customers. The basic version of VRP is Capacitated VRP (CVRP) which considers equal capacities for all vehicles. The objective of CVRP is to minimize the total traveling distance of all vehicles to serve all the customers. Various methods are used to solve CVRP, among them the most popular way is splitting the task into two different phases: assigning customers under different vehicles and then finding optimal route of each vehicle. Sweep clustering algorithm is well studied for clustering nodes. On the other hand, route optimization is simply a traveling salesman problem (TSP) and a number of TSP optimization methods are applied for this purpose. In Sweep, cluster formation staring angle is identified as an element of CVRP performance. In this study, a heuristic approach is developed to identify appropriate starting angle in Sweep clustering. The proposed heuristic approach considers angle difference of consecutive nodes and distance between the nodes as well as distances from the depot. On the other hand, velocity tentative particle swarm optimization (VTPSO), the most recent TSP method, is considered for route optimization. Finally, proposed adaptive Sweep (i.e., Sweep with proposed heuristic) plus VTPSO is tested on a large number of benchmark CVRP problems and is revealed as an effective CVRP solving method while outcomes compared with other prominent methods.
Authors and Affiliations
M. A. H. Akhand, Zahrul Jannat Peya, Kazuyuki Murase
Keywords
Related Articles
- EP ID EP258417
- DOI 10.14569/IJACSA.2017.081237
- Views 134
- Downloads 0
An Efficient Segmentation of Retinal Blood Vessels using Singular Value Decomposition and Morphological Operator
The extensive study on retinal fundus images has become an essential part in medical domain to detect pathologies including diabetic retinopathy, cataract, glaucoma, macular degeneration,etc.which are the major causes of...
Graph-based Semi-Supervised Regression and Its Extensions
In this paper we present a graph-based semi-supervised method for solving regression problem. In our method, we first build an adjacent graph on all labeled and unlabeled data, and then incorporate the graph prior with t...
QR Code Patterns Localization based on Hu Invariant Moments
The widespread utilization of QR code and its coincidence with the swift growth of e-commerce transactions have imposed the computer vision researchers to continuously devise a variety of QR code recognition algorithms....
The Mathematical Model of Hybrid Schema Matching based on Constraints and Instances Similarity
Schema matching is a crucial issue in applications that involve multiple databases from heterogeneous sources. Schema matching evolves from a manual process to a semi-automated process to effectively guide users in findi...
LNG Import Contract in the perspective of Associated Technical and Managerial Challenges for the Distribution Companies of Pakistan
Energy Managers and Government Office Holders in Pakistan are nowadays pondering over multiple options for the resolution of ongoing Energy crises in the country. LNG (Liquefied Natural Gas) import has been finalized for...