Start Submission Become a Reviewer

Reading: An improved two-phased heuristic algorithm for the capacitated vehicle routing problem and a...

Download

A- A+
Alt. Display

Research Articles

An improved two-phased heuristic algorithm for the capacitated vehicle routing problem and a case study

Authors:

M. K. D. D. Sandaruwan ,

Rajarata University of Sri Lanka, Mihintale, LK
About M. K. D. D.
Department of Physical Sciences, Faculty of Applied Sciences


Postgraduate Institute of Science, University of Peradeniya, Peradeniya
X close

D. M. Samarathunga,

University of Ruhuna, Matara, LK
About D. M.
Department of Mathematics, Faculty of Science
X close

W. B. Daundasekara

University of Peradeniya, Peradeniya, LK
About W. B.
Department of Mathematics, Faculty of Science
X close

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is a special variant of the Vehicle Routing Problem which has been extensively addressed in the literature of Operations Research. Since CVRP is a NP-hard problem, only heuristic algorithms are capable of solving relatively large-scale problems. In this research paper, a new Improved Two-phased Heuristic algorithm is presented for solving CVRP. The Improved Two-phased Heuristic algorithm is comprised of two phases and cluster-first rout-second approach is used. In the first phase, best sets (≤ five) of clusters are obtained using an iterative procedure based on five parameters. In the second phase, the Traveling Salesman Problem (TSP) of each cluster of the obtained sets of clusters is separately solved by applying the standard Genetic algorithm (GA). Subsequently, the best set of clusters with the minimum total traveling distance is selected as the final solution. The performance of the improved algorithm was compared with three prominent algorithms find in the literature: Efficient Two-phased Heuristic algorithm, Savings algorithm and GA, using thirty well-known benchmarked instances. The computational results of the comparison revealed that the Improved Two-phased Heuristic algorithm finds the least total traveling distance within a reasonable CPU time, compared to the three stated prominent algorithms. To illustrate the proposed algorithm and its applicability, the algorithm was applied for a food manufacturing company located in Sri Lanka. The results showed that there was a significant impact in reducing the transportation cost in distributing the company products by reducing the total traveling distance.
How to Cite: Sandaruwan, M. K. D. D., Samarathunga, D. M., & Daundasekara, W. B. (2020). An improved two-phased heuristic algorithm for the capacitated vehicle routing problem and a case study. Ceylon Journal of Science, 49(4), 477–484. DOI: http://doi.org/10.4038/cjs.v49i4.7828
Published on 24 Dec 2020.
Peer Reviewed

Downloads

  • PDF (EN)

    comments powered by Disqus