The formulation of a linear programming model for the vehicle routing problem in order to minimize idle time

Abstract

The paper deals with the question, "What is the Vehicle Routing Problem, Which Is Minimized Idle Time, and How Its Linear Programming Model Is Written?" In this study, a linear programming (LP) model has been developed for the vehicle routing problem (VRP) in order to minimize the total idle time (MIT). This problem was realized while managing the route operations of a company transporting long-distance passengers by bus in Turkey. The differences between this problem and other VRPs first arise from its objective function. It suggests that vehicles should work more because they make profit if they work. So, its objective function should be defined so as to minimize the sum of the idle time of those vehicles. Contrary to the VR problems examined so far, vehicles should work more, sometimes preferring long-distance routes as well. The other two differences pertain to constraints: Some locations should be visited more than once in different time periods, and subtours could be allowed in some situations. In order to present the problem, a total of 34 routes of the company which belongs to one of the five subgroups were chosen for the samples. To solve this kind of problems, it is very important that exact methods, such as linear programming or branch and bound, should be used.