Featured Story Luly-August 2015
Service Reliability in Vehicle Routing Problems

by Mr. Anastasios Varias, Doctoral Candidate

Most studies in vehicle routing seek to minimize investment and operating costs, acknowledging only as side issues customer service aspects. However, there are cases that servicing the customers may be perturbed by unexpected events dealing with the travel and service times, the number of customers and /or their demand. Considering all these uncertainties, promising a precise service time can be impossible or extremely costly to satisfy. For that reason, a logistics provider may want to quote time windows to a set of customers in order to achieve reliable service, and to avoid the extra costs caused by delays and bad reputation. To that end, it is of major importance to generate robust routing plans that guarantee stable and reliable service despite the unforeseeable events.

Spliet and Gabor (2014) illustrate the time window assignment vehicle routing problem (TWAVRP). The demand of each customer is considered as a discrete random variable that follows a known probability mass function according to a set of scenarios. The time windows are endogenously imposed within time windows that are exogenously determined, for example, when the legislation allows trucks to serve locations in highly populated areas during specific time periods a day. Furthermore, they are quoted to customers before any realization of the stochastic demands. The main objective of this problem is to communicate the time windows in order to minimize the expected traveling costs. Regarding the proposed solution methodology, computational experiments have been implemented applying the column generation scheme in a branch-and-price algorithm.

Ehmke et al. (2015) seek to provide reliable service to customers considering the vehicle routing problem with time windows and stochastic travel times (SVRPTW). The stochastic travel times are modeled as continuous random variables following the normal, the shifted gamma and the shifted exponential probability distribution as well. The extreme value theory is employed so as to approximate the start-service time at each customer. The service reliability is attained by introducing probabilistic chance constraints, meaning that each constraint in the context of the vehicle routing problem with time windows (VRPTW) can be violated under some probability. The computational results are obtained by the LANTIME tabu-search metaheuristic algorithm, see Maden et al. (2010).

Jabali et al. (2015) present the vehicle routing problem with self-imposed time windows (VRP-SITW) where the carrier communicates time windows to customers taking into account stochastic travel times. After the time windows are quoted, the service provider has to serve each customer in the proposed time window. The VRP-SITW imposes endogenously the time windows, in contrast to the VRPTW, where the time windows are exogenously determined by the customers. Uncertainty in travel times is modeled by disruption scenarios. During a route at most one arc is allowed to be disrupted under some probability. Moreover, the length of each disruption is considered a discrete random variable that follows a known probability mass function. The proposed solution framework consists of a hybrid tabu-search/LP algorithm implemented in two stages. In the first stage, the tabu-search metaheuristic algorithm is applied so as to assign the customers to vehicles and determine their sequence in each route, while in the second stage an LP is solved to impose the time windows.

In conclusion, the literature indicates that in order to achieve reliability when servicing the customers, the distributor has to take into account the stochastic environment that a vehicle routing problem may face. Achieving high service level is of great importance if the logistics provider seeks to attain long term service contracts.


Ehmke, J.F., Campbell, A.M. and Urban, T.L. (2015). Ensuring service levels in routing problems with time windows and stochastic travel times. European Journal of Operational Research 240(2), 539-550.

Jabali, O., Leus, R., van Woensel, T., and de Kok, A. (2015). Self-imposed time windows in vehicle routing. OR Spectrum 37(2), 331-352.

Maden, W., Eglese, R. and Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society 61(3), 515-522.

Spliet, Remy and Gabor, Adriana F. (2014). The time window assignment vehicle routing problem. Transportation Science, (article in advance).

M A N A G E M E N T    S C I E N C E    L A B O R A T O R Y   








Copyright 2013 Website Management Science Laboratory. All rights reserved.