Managing in Real-Time a Vehicle Routing Plan with Time-Dependent
Travel Times on a Road Network
M. Gendreaua,b , A. Lodia,b, J.-Y. Potvinc,b, M. Gmira b,d*a

Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal , Canada
michel.gendreau@cirrelt.net , andrea.lodi@polymtl.cab
CIRRELT, Montréal , CanadacDépartement d’informatique et de recherche opérationnelle, Université de Montréal, Montréal , Canada
potvin@iro.umontreal.cadÉcole d’Ingénierie Digitale et d’Intelligence Artificielle, Euromed University of Fez, Fez , Moroccom.gmira@ueuromed.org* Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 12, 2022
Keywords: Vehicle routing, Road network, Dynamic travel times, Metaheuristics, Tabu search

1

INTRODUCTION

Vehicle routing has been a core logistic problem since it was introduced by Dantzig and Ramser(Dantzig and Ramser, 1959). Over the last 60 years, numerous papers have dealt with a large number ofvariants of this basic problem (see, for example, Toth and Vigo, 2014). While early vehicle routing
papers considered problems in which all inputs are static, it is now commonly accepted that, especiallyin urban areas, travel times do vary during a typical planning horizon, e.g., a day. This has led to asignificant body of literature on time-dependent vehicle routing problems (Gendreau et al., 2015). Most
reported work is based on customer-based graphs, where an arc between two customers corresponds toa fixed path in the underlying road network. It is only recently that some authors have stressed that amore realistic setting is obtained by defining the time-dependent problem directly on the road network(Huang et al., 2017; Ben Ticha et al., 2019; Gmira et al., 2021). In this setting, not only do we have adifferent travel time to go from one customer to the next depending on the time of the day, but even thepath used to go from one customer to the next may change (i.e., the path is not fixed anymore). Thismay be of great concern if one wishes to avoid traffic congestion, either to shorten travel durations (Koket al., 2012; Ben Ticha et al., 2019; Huang et al., 2017) or to reduce vehicle emissions (Qian and Eglese,2016; Ehmke et al., 2016). Considering different paths to travel from one customer to the next in theroad network, as well as accounting for the time-dependent travel time on each one of those paths, makethe problem much more complex, which may explain the few works dedicated to this problem. In thispaper, we extend these recent developments to a dynamic setting where the time-dependent travel times
change dynamically.
In (Gmira et al., 2021), we developed a tabu search heuristic for a delivery application in the Montreal
area where large items (furniture, appliances) are delivered at home from retailers to customers. For thisapplication, we used static time-dependent travel times derived from historical data. However, it is wellknown that unexpected events, such as accidents and non-recurrent traffic congestion, may have an
important impact on travel times. Thus, delivery plans may not be directly applicable in the actual state

TRISTAN XI Symposium

Original abstract submittal

M. Gendreau, A. Lodi, J.-Y. Potvin and M. Gmira

2of the road network and must be adjusted to the most recent speed or travel time information. Ourpurpose here is to address this dynamic version of the problem that falls in the class of Dynamic Vehicle
Routing Problems (DVRPs) where new inputs are received while the current planned routes areexecuted. We propose a methodology that reacts to modifications to travel times by maintaining as muchas possible the current planned routes, but without compromising too much solution quality. To the bestof our knowledge, this is the first work that presents a method for reacting in real-time to dynamic
perturbations of time-dependent travel times in a real urban road network with thousands of nodes andarcs, for a less-than-truckload application (i.e., with consolidation of customer requests).

2STATIC PROBLEM

We consider here a static vehicle routing problem with time windows and time-dependent travel times
defined on a road network. It can be described as follows. The road network is a directed graph 𝐺 =(𝑉, 𝐴), where 𝑉 = {0, 1, 2, . . . , 𝑛} is the set of nodes (i.e., road junctions) and 𝐴 is the set of arcs (i.e.,road segments between two junctions). A set of customers 𝐶 = {1, 2, . . . , 𝑛} and a depot (node 0) arelocated in the network. Each customer 𝑖 has a demand 𝑞! , a time window [𝑎! , 𝑏! ] for the service start
time, with ai and bi the lower and upper bounds of the time window, respectively, and a service or dwell
time si. A set of vehicles K, where the number of vehicles in that set is a decision variable, is located atthe depot. Each vehicle has capacity Q. A vehicle cannot arrive at customer i after the upper bound 𝑏!
of the time window, but can arrive before the lower bound 𝑎! , in which case the vehicle waits until time
ai to start the service. The time window at the depot [𝑎" , 𝑏" ] defines the beginning and end of theplanning horizon.
Each arc (i, j) À A is associated with a distance 𝑑!# , a time-dependent speed function 𝑣!# : t → R+ that
returns the speed at time t, and a time-dependent cost function 𝑐!# : t → R+ that returns the cost oftraversing arc (i, j) at time t (here, the cost corresponds to the travel time). The time-dependent speedfunctions have a stepwise form, that is, a different speed is associated with each time interval definedover the planning horizon. From this time-dependent travel speed function, a piecewise linear timedependent travel time function can be derived. A time-dependent variant of Dijkstra’s algorithm canthen use these arc-based functions to compute shortest paths (with respect to travel times) between anypair of nodes for any departure time, as it is done in (Gmira et al., 2021).
The aim is to generate feasible vehicle routes that start and end at the depot, one for each vehicle, andserve all customers at minimum cost. The latter corresponds to the total duration of the routes (i.e., travel
time + waiting time + dwell time). A solution is feasible if it satisfies the capacity constraints and time
windows at the customers and at the depot.

3DYNAMIC PROBLEM

The dynamic version of our problem is obtained by allowing dynamic perturbations to the timedependent travel speeds. When a perturbation impacts one or more arcs at a given time, the timedependent speed function of each arc is modified, as indicated by the dotted lines in Figure 1.
Clearly, if one of these arcs is part of the path leading from one customer to the next in a delivery route,the travel time between these two customers will change, with further impacts the customers down theroute, since the travel times are time-dependent. This is illustrated in Figure 2, where a vehicle route
starts from the depot, and while it is en route to its current destination (customer 𝐶$ ), a travel speed
update occurs, as indicated by the black dot.
In this example, the system reacts by first recalculating the new arrival and departure times at customer
𝐶$ from the current vehicle’s position. This is repeated for each customer along the route, including theend depot. Eventually, it may be that the best path to reach the next location, starting with the current
vehicle’s position, will need to be recalculated, as it is illustrated in the figure. It may even be that thesequence of customers along the route has to be modified to account for the perturbation.

TRISTAN XI Symposium

Original abstract submittal

M. Gendreau, A. Lodi, J.-Y. Potvin and M. Gmira

3

Figure 1: Example of a dynamic perturbation to a travel speed function

Figure 2 : Vehicle dispatching in a dynamic setting (at the time of a travel time update)In the dynamic version, it is not possible to guarantee anymore that the service will take place within
the customers’ time windows or that a vehicle will return to the depot before the end of the time horizon.
Accordingly, the objective function of the dynamic problem includes a penalty for lateness at customers
and at the depot. The penalty is linear and is obtained by multiplying the total lateness by a penalty
factor.
A variant of the dynamic problem is also considered where it is possible to cancel a customer request if
the lateness at this customer exceeds a given threshold. In this case, a large fixed penalty for eachcancellation is added to the objective.

4DISPATCHING METHODOLOGYThis is basically a rolling-horizon approach where a new static problem is defined when a speed update
occurs, based on the current status of each planned route. Considering the real-time context though, wewant a quick response to each speed update and we also want to maintain some route stability, whilestill accounting for solution quality. The proposed procedure works as follows for each new speed
update:For each route affected by the speed update do:
1
2

Calculate new arrival and departure times for each customer along the planned route.
If the route is still feasible, then keep the route as it is.

TRISTAN XI Symposium

Original abstract submittal

M. Gendreau, A. Lodi, J.-Y. Potvin and M. Gmira

4

3 If the route is not feasible then:
3.1 Recompute the best path (minimum travel time) in the road network between two consecutive
service locations, starting with the vehicle’s current location and current destination and ending
with the last customer and end depot.
3.2 If the route becomes feasible, then keep it. In this case, the sequence of customers does notchange, only the paths leading from one customer to the next (or the end depot).
3.3 Otherwise, modify the sequence of customers (except the current destination) by applying a local
search descent based on Or-opt exchanges. Keep the route obtained at the end, feasible or not.
The Or-opt neighborhood in step 3.3 is explored in a systematic way by considering sequences of threeconsecutive customers, two consecutive customers and one customer, in this order. A sequence is firstremoved from the route and then reinserted at the best possible place, based on the objective function.
We recall that the latter sums route duration and a linear penalty for lateness at the customers and at thedepot.

5EXPERIMENTS

Our methodology is tested on instances based on a part of the road network of Montreal with up to 500
customers. A central depot and a number of customers varying between 100 and 500 were randomly
chosen in the road network. More precisely, we have created five instances each with 100, 200, 300,
400 and 500 customers, for a total of 25 instances. The results are reported and compared with a strategy
that maintains the planned routes, whatever the cost. We observed that the routes produced by thereactive procedure were always different from the planned routes at the beginning of the day, thus
indicating that a reaction always took place. The detailed results will be presented at the conference.

6REFERENCES

Ben Ticha, H., Absi, N., Feillet, D., Quilliot, A., Van Woensel, T., 2019. A branch-and-price algorithm
for the vehicle routing problem with time windows on a road network. Networks 73 (4), 401–417.
Dantzig, G., Ramser, J., 1959. The truck dispatching problem. Manage. Sci. 6 (1), 80–91.
Toth, P., Vigo, D., 2014. Vehicle Routing: Problems, Methods, and Applications. SIAM.
Ehmke, J., Campbell, A., Thomas, B., 2016. Vehicle routing to minimize time-dependent emissions inurban areas. European J. Oper. Res. 251 (2), 478–494.
Gendreau, M., Ghiani, G., Guerriero, E., 2015. Time-dependent routing problems: A review. Comput.
Oper. Res. 64, 189–197.
Gmira, M., Gendreau, M., Lodi, A., Potvin, J.-Y., 2021. Tabu search for the time-dependent vehicle
routing problem with time windows on a road network. European J. Oper. Res. 288 (1), 129–140.
Huang, Y., Zhao, L., Van Woensel, T., Gross, J.-P., 2017. Time-dependent vehicle routing problem withpath flexibility. Transp. Res. Part B 95, 169–195.
Kok, A., Hans, E., Schutten, J., 2012. Vehicle routing under time-dependent travel times: The impact ofcongestion avoidance. Comput. Oper. Res. 39 (5), 910–918.
Qian, J., Eglese, R., 2016. Fuel emissions optimization in vehicle routing problems with time-varying
speeds. European J. Oper. Res. 248 (3), 840–848.

TRISTAN XI Symposium

Original abstract submittal