DefinePK

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.