INPROFORUM 2009

Methods for Solving the Time Limited Vehicle Routing Problem
Petr Kučera

Language: en
Last modified: 2013-09-03

Abstract


The traveling salesman problem (TSP) is the task to find the shortest possible cyclic route going through the given cities (places, points). In practice it is not possible to carry out the transportation using one cyclic route (e.g. because of capacity or time reasons) and so it is necessary to create more than one such route. Such problems are called vehicle routing problems (VRP). The TSP and all different versions of the VRP belong to the NPhard problems. It means that there exist no methods, which would be able to compute its theoretical optimum efficiently. Thus there exist a lot of heuristics (approximation methods), which give only approximate solutions but considered to be economic optima. This contribution is focused on so called time limited vehicle routing problem (TLVRP) which is the simplest and the most common version of the VRP with a route restriction caused by time. Selected methods for the TSP are reviewed according to the possibility and suitability of their modification for the TLVRP and some test results of several methods created in such a way are added.


Keywords


vehicle routing problem, heuristics (approximation methods)

Full Text: PDF