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

  • Ömer Nuri Çam Uludag University, Faculty of Economics and Administrative Sciences, Bursa, Turkey
  • Hayrettin Kemal Sezen Altınbaş University, School of Applied Sciences, Istanbul, Turkey
Keywords: vehicle routing problem; minimizing idle time; linear programming; location and time point.


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.


Download data is not yet available.


Beck, J. C., Prosser, P., & Selensky, E. (2003). Vehicle Routing and Job Shop Scheduling : What’s the difference? Artificial intelligence, 267–276.

Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2015). The vehicle routing problem: State of the art classification and review. Computers and Industrial Engineering, 99, 300–313.

Brailsford, S.C., Potts, C.N. & Smith, B.M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557–581.

Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A.A. (2014). Rich Vehicle Routing Problem. ACM Computing Surveys, 47(2), 1–28.

Cordeau, J.-F., Laporte, G., Savelsbergh, M.W.P. & Vigo, D. (2007). Vehicle Routing. Transportation, 14, 367–428.

Daneshzand, F. (2011). The Vehicle-Routing Problem. Elsevier.

El-Sherbeny, N. A. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science, 22(3), 123–131.

Koç Ç., & Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing, 39, 154–164.

Kramer, R., Maculan, N., Subramanian, A., & Vidal, T. (2015). A speed and departure time optimization algorithm for the pollution-routing problem. European Journal of Operational Research, 247(3), 782–787.

Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation science, 43(4), 408–416.

Laporte, G. (2013). Scheduling issues in vehicle routing. Annals of Operations Research, 25(2), 1–12.

Sezen, H.K., (2017). Yöneylem Araştırması, Dora Yayınevi, Baski, 3(1), 2-24.

Wang, Y., Liao, Z., Tang, T., & Ning, B. (2017). Train scheduling and circulation planning in urban rail transit lines. Control Engineering Practice, 61, 112–123.

How to Cite
Çam, Ömer N., & Sezen, H. K. (2020). The formulation of a linear programming model for the vehicle routing problem in order to minimize idle time. Decision Making: Applications in Management and Engineering, 3(1), 22-29.