PST-Prim Heuristics for the Open Vehicle Routing Problem

Abstract

The objective of this paper is to present and demonstrate the validation of the functioning of a recursive heuristic based on the algorithm of Prim and that gives solution to the problem of open vehicle routing (OVRP). Today this problem has a considerable approach, so it is part of a broad literature review that sets the theoretical basis for the work. The OVRP is formally shown and the covering tree with paths (PST) is defined. Next, the subroutine that follows the PST-Prim algorithm is indicated to construct the PST of any graph, as well as the modification that must be made to arrive at the PST-Prim Heuristic that gives solution to the OVRP. To illustrate and validate its effectiveness, it is used to solve 25 widely used problems to verify and compare the behavior of this type of algorithms. An illustrative example of the construction of a PST to an example graph is presented. In addition, comparative graphs of the PST constructions and the OVRP soluti ons of the 25 comparative problems are presented. Of the latter, the value of the objective function is presented. At the end the con sistency, use and importance of the heuristic is discussed.