Linear programming formulation for vehicle routing problem which is minimized 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 & time point


Paper is related to “What is a Vehicle Routing Problem Which Is Minimized Idle Time and how to write its Linear Programming model”. In this study, a Linear Programming (LP) model has been developed for a Vehicle Routing Problem (VRP) to minimize total idle time (MIT).  This problem has been realized according to manage the route operations of a company carrying long-distance passengers by bus in Turkey. The differences of this problem from the other VRP firstly comes from its objective function. It suggests vehicles should work more because they make profit if they work. So its objective function should be defined as to minimize the sum of idle time of those vehicles.  To the contrary of VRP problems which are examined so far, vehicles should work more and sometimes they should prefer long distance route also. Other two differences are related with constraints: Some locations should be visited more than once for different time periods and sub-tours could be allowed to occur in some situations. For presentation of the problem, 34 routes of the company which belong to one of five sub groups have been chosen as samples. For solving this kind of problems, it is very important using exact methods such as Linear programming or Branch and Bound.


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. (2019). Linear programming formulation for vehicle routing problem which is minimized idle time. Decision Making: Applications in Management and Engineering, 3(1-2), 22-29. Retrieved from