|
Journal of Computer Science Technology Updates (Volume 3 Issue 2)
|
| A Simple Heuristic for Basic Vehicle Routing Problem |
 |
Pages 38-44
Nodari Vakhania, Jose Alberto Hernandez, Federico Alonso-Pecina and Crispin Zavala
DOI: http://dx.doi.org/10.15379/2410-2938.2016.03.02.04
Published: 29 December 2016 |
| Abstract |
| The vehicle routing problem is an important real-life transportation problem. We propose a two-phase construction heuristic for the solution of the classical Euclidean (uncapacitated) vehicle routing problem in which the minimum cost distinct vehicle tours are to be formed for the given customer locations. At the first phase we construct a polygon in the 2-dimensional Euclidean space that girds all the given points (customer locations and the depot). The second phase consists of two stages. At the first stage the interior polygon area is partitioned into triangle areas, and at the second stage the tours for each of these areas are constructed. |
| Keywords |
| Vehicle routing problem, Heuristic algorithm, Euclidean distance, Weighted graph. |
 |