A Time Limited Vehicle Routing Problem

Abstract

A vehicle routing problem is a classical problem in operation research consisting in delivery routes optimization in communications network containing depot of all routes and a given number of cities, which is necessary to include in delivery routes. The demand of all cities is given and the condition is that the sum of demands of the cities on the route should be less or equal to the capacity of a vehicle.
The paper deals with a modification of the vehicle routing problem in which the capacity of a vehicle is not limited but the times of pickup to all cities are limited by a given value. A similar problem and model can be formulated for optimization of pick-up routes with pick-up time limited. The mathematical model proposed for the problem is based on Miller-Tucker-Zemlin formulation of the traveling salesman problem. As the time limited vehicle routing problem is NP hard, a solution to huge problems cannot be obtained in acceptable computation time. The following heuristics are proposed for the time limited traveling salesman problem: nearest neighborhood method, insert method and savings method. Use of all methods is illustrated by numerical experiment. The difference between results obtained by those methods is shown on the case study.