Victor Pillac
email: victor.pillac@emn.fr

Christelle Gueret

Andres Medaglia

Dynamic Vehicle Routing Problems: State Of The Art and Prospects

This scientific report summarizes the results of a literature review on dynamic vehicle routing problems. After a brief description of vehicle routing problems in general, a classification is introduced to distinguish between static and dynamic problems. Then a more precise definition of dynamism is presented, supported by example of real-world applications of such problems. Finally, a detailed study of the current state of the art in dynamic vehicle routing optimization is drawn.

Résumé

Ce rapport scientifique a été rédigé comme synthèse de travaux de recherche bibliographique sur les tournées de véhicules dynamiques. Après une brêve description des problèmes de tournées en général, nous proposons une classification permettant de distinguer les problèmes statiques et dynamiques. Par la suite, une description plus détaillée de ces derniers est présentée, se basant sur des exemples tirés d'applications réelles. Enfin, une étude de l'état de l'art sur les problèmes de tournées dynamiques est développée, puis complétée par une analyse des thématiques n'ayant rec ¸u à ce jour qu'un faible intérêt de la part de la communauté scientifique, et suceptibles de constituer des pistes intéressantes de recherche.

Resumen

Este reporte científico fue escrito como síntesis de una investigaci ón bibliográfica sobre los problemas de ruteo de vehículo dinámicos. Después de una breve descripci ón general de los problemas de ruteo, se propone una clasificaci ón permitiendo una distinci ón entre problemas staticos y dinámicos, los últimos siendo el objeto de una definici ón mas detallada, basada en ejemplos de aplicaciones reales. Por fin, se presenta un estudio del estado del arte sobre los problemas de ruteo dinámico, completada por una análisis de las temáticas que podrían constituir direcciones interesantes de investigaci ón.

Introduction

The Vehicle Routing Problem (VRP) formulation was first introduced by [START_REF] Dantzig | The truck dispatching problem[END_REF], as a generalization of the Travelling Salesman Problem (TSP) presented by [START_REF] Flood | The traveling-salesman problem[END_REF]. The VRP is generally defined on a graph G = (V, E, C), with V = {v 0 , ..., v n } being the set of vertices, E = {(v i , v j )|(i, j) ∈ V 2 , i = j} the arc set and C = c ij (i,j)∈E a cost matrix defined on E, representing distances, travel times or travel costs. Traditionally, vertex v 0 is called depot, while the remaining vertices represent clients that need to be serviced. The VRP consists in finding a set of routes for K vehicles of identical capacity based at the depot, such that each of the vertices is visited exactly once, while minimizing the overall routing cost.

Beyond this classical formulation, a number of variants have been identified and studied. Among the most commonly cited are the VRP with Time Windows (VRP-TW), requiring the customers to be visited during a specific time interval; the VRP with Pickup and Delivery (VRP-PD or PDP), where goods have to be either picked-up or delivered in specific amounts in each of the vertices, and its variation with time windows (PDP-TW). Other variations include the Heterogeneous fleet Vehicle Routing Problem (HVRP) and its variants with time windows or pickup and delivery, in which the vehicles have different capacities. When transportation of people between two locations is considered, the problem is referred to as Dial A Ride Problem (DARP) for land transport; or Dial A Flight Problem (DAFP) for air transport.

In contrast with the canonical definition of the vehicle routing problem, real-world applications often include two important dimensions: evolution and quality of information [START_REF] Psaraftis | A dynamic-programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF]. Evolution of information is related to the fact that in some problems the information available to the planner may change during the execution of the routing, for instance with the arrival of new client requests or changes in the travelling times. Quality of information reflects possible uncertainty on the available data, for example when the demand of a client is only known as an estimation of its real demand. From this two dimensions, four categories of problems can be identified, as summarized in Table 1. In static and deterministic problems, all input is known beforehand and no change can be applied to the routing plan. This is the historical class of problem, and it includes the classical vehicle routing problem and its variations discussed earlier.

Information quality

Static and stochastic problems are characterized by input partially known as random variables, of which the realization is only revealed to the planner during the execution of the routing. Additionally, only minor changes on the routing are allowed: generally a vehicle can only plan a trip to the depot, or skip a client. Applications falling in this category do not require any technological support: the planning is done before-hand INTRODUCTION and subsequent decisions are taken autonomously by vehicles.

In dynamic and deterministic problems, part or all of the input is unknown and revealed dynamically during the design or execution of the routing [START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF], while no stochastic data is available regarding the dynamically revealed information [START_REF] Flatberg | Dynamic and stochastic vehicle routing in practice[END_REF]. In this case, the routing plan can be completely redefined in an on-going fashion. Applications in this class of problem require technological support, allowing in particular real time communication between the vehicles and the decision maker, for instance with the use of mobile phones, personal digital assistants (PDA) or smart-phones, possibly coupled with global positioning systems (GPS).

Similarly, dynamic and stochastic problems have part or all of their input unknown and revealed dynamically during the determination or execution of the plan [START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF], but in this case, exploitable stochastic knowledge is available on the dynamically revealed information [START_REF] Flatberg | Dynamic and stochastic vehicle routing in practice[END_REF]. As before, the routing plan can be completely redefined in an on-going fashion, and technological support is required.

It is important to note that some variations exist among author on the classification of vehicle routing problems [START_REF] Flatberg | Dynamic and stochastic vehicle routing in practice[END_REF][START_REF] Ghiani | Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies[END_REF][START_REF] Psaraftis | Dynamic vehicle routing problems[END_REF][START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF], nevertheless the above definitions will be used as a reference in the remainder of this document.

Static and deterministic problems have been extensively studied in the literature. We refer the interested reader to the recent reviews of exact and approximated approaches by [START_REF] Baldacci | Recent advances in vehicle routing exact algorithms[END_REF], Cordeau et al. (2007b) and [START_REF] Toth | The vehicle routing problem[END_REF].

As stated before, a problem is said to be static and stochastic if part of the input is uncertain but can be modelled as random variables of known distribution. Uncertainty may affect any of the input data. Nonetheless, as identified by Cordeau et al. (2007b), the three most studied cases are stochastic customers, when each customer i is present in the instance with probability p i and absent with probability 1p i [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Waters | Vehicle-scheduling problems with uncertainty and omitted customer[END_REF]; stochastic times, in which case the time s i needed to serve customer i, or the travel time t ij on the edge (i, j) are random variables [START_REF] Kenyon | stochastic vehicle routing with random travel times[END_REF][START_REF] Laporte | The vehicle-routing problem with stochastic travel-times[END_REF][START_REF] Verweij | The sample average approximation method applied to stochastic routing problems: a computational study[END_REF]; and finally stochastic demands, with the demand ξ i of a customer i being defined as a random variable [START_REF] Christiansen | A branchand-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Dror | Vehicle routing with stochastic demands: Properties and solution frameworks[END_REF][START_REF] Laporte | An integer l-shaped algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Mendoza | A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands[END_REF][START_REF] Secomandi | Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[END_REF][START_REF] Secomandi | Reoptimization approaches for the vehicle-routing problem with stochastic demands[END_REF].

In most cases, the realization of random variables is revealed only at operation time. For instance the actual demand of a client may only become known when it is actually visited. However, internal or external factors prohibit the enforcement of decisions in a real-time manner. Thus the objective in static and stochastic routing problems is to build a robust plan beforehand, that will undergo only limited changes during its execution. Therefore, in this context, the qualifier static does not mean that the available information or the actual routing are not subject to changes, but instead that these changes are not directly considered.

Uncertainty in the stochastic VRPs input has been addressed by various solution frameworks, of which the two most studied are the Chance Constrained Programming (CCP) and the Stochastic Programming with Recourse (SPR). Both frameworks are based on a two-stage approach: the first phase is performed before the start of the planning horizon and aims to design a robust routing plan; while the second phase takes place during its execution, and consists in taking recourse or corrective actions as the realizations of the random variables are disclosed. The conceptual difference between the two approaches lies in the objective of the first-stage optimization: in CCP, the goal is to ensure an upper bound on the probability of a failure, regardless of the expected cost of the second phase; while SPR seeks the minimization of the expected cost of recourse actions. Recourse actions, on the other hand, are common to most approaches and depend on the application. For instance, for the commonly studied VRP with Stochastic Demands (VRPSD), a route failure may occur any time a customer demand exceeds the associated vehicle remaining capacity. In this case, an intuitive recourse action is for the vehicle to go back to the depot to restore its initial capacity and then resume its route [START_REF] Mendoza | A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands[END_REF], or to allow the service of additional customers before returning to the depot [START_REF] Novoa | A set-partitioning-based model for the stochastic vehicle routing problem[END_REF]. As mentioned by [START_REF] Secomandi | Reoptimization approaches for the vehicle-routing problem with stochastic demands[END_REF], a distinction must be made between reactive actions, which are only taken when a failure occurs, and proactive actions, that are decided by anticipating the likeliness of a failure.

Further details on the static stochastic vehicle routing can be found in the reviews by [START_REF] Bertsimas | A new generation of vehicle routing research: robust algorithms, addressing uncertainty[END_REF], Cordeau et al. (2007b) and [START_REF] Gendreau | Stochastic vehicle routing[END_REF].

The remainder of this document focuses on dynamic routing and is organised as follows. Section 1 introduces a general description of such problems. This section also presents the degree of dynamism and detail indicators to measure it, then reviews different applications related to dynamic routing. Section 3 provides a comprehensive survey of solution approaches, for both deterministic and stochastic dynamic routing. Finally directions for further research will be drawn, with an emphasis on the problem that we tackle in the future.

Dynamic routing 1.A general definition

To the best of our knowledge, the first reference to a dynamic vehicle routing problem is due to [START_REF] Wilson | Computer control of the rochester dial-a-ride system[END_REF]. They studied a dial-a-ride problem (DARP) with a single vehicle, in which customers requests are trip from an origin to a destination that appear dynamically. Their approach uses insertion heuristics able to perform well with low computational requirement. Later work by [START_REF] Psaraftis | A dynamic-programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF] introduced the concept of immediate request: a customer requesting service always wants to be served as early as possible, requiring the immediate re-planning of the current vehicle route. They propose a dynamic-programming algorithm for the static case, as well as an adaptation to the dynamic context tested on a ten-customer instance.

Since then, a number of technological advances have increased the importance of online or real-time applications. With the introduction of the Global Positioning System (GPS) in 1996, the development and widespread use of cell-phones and smart-phones, combined with accurate Geographic Information Systems (GIS), companies are now able to track and manage their fleet in real-time and cost effectively. While traditionally a two-step process, vehicle routing can now be done dynamically, introducing greater opportunities to reduce operation costs, improve customer service, and reduce environmental impact.

The most common source of dynamism in vehicle routing is the online arrival of customer requests during the operation. More specifically, a request is generally composed of a location and a demand [START_REF] Attanasio | Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem[END_REF][START_REF] Goel | A general vehicle routing problem[END_REF][START_REF] Ichoua | Exploiting knowledge about future demands for real-time vehicle dispatching[END_REF][START_REF] Mes | Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems[END_REF], Mitrovic-Minic and Laporte, 2004), although in some cases, the only relevant information is the location [START_REF] Beaudry | Dynamic transportation of patients in hospitals[END_REF][START_REF] Bent | Online stochastic and robust optimization[END_REF][START_REF] Bertsimas | A stochastic and dynamic vehicle-routing problem in the euclidean plane[END_REF][START_REF] Gendreau | Parallel tabu search for real-time vehicle routing and dispatching[END_REF][START_REF] Larsen | The a priori dynamic traveling salesman problem with time windows[END_REF], or the demand [START_REF] Secomandi | Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[END_REF][START_REF] Secomandi | Reoptimization approaches for the vehicle-routing problem with stochastic demands[END_REF][START_REF] Thomas | Waiting strategies for anticipating service requests from known customer locations[END_REF][START_REF] Van Hemert | Dynamic routing problems with fruitful regions: Models and evolutionary computation[END_REF]. Travel time, a dynamic component of most real-world applications, 1 DYNAMIC ROUTING 1.2 Differences with static routing has been recently taken into account [START_REF] Attanasio | Real-time fleet management at ecourier ltd[END_REF][START_REF] Barcelo | Vehicle routing and scheduling models, simulation and city logistics[END_REF], Chen et al., 2006[START_REF] Fleischmann | Dynamic vehicle routing based on online traffic information[END_REF][START_REF] Haghani | A dynamic vehicle routing problem with time-dependent travel times[END_REF][START_REF] Haghani | Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies[END_REF], while service time, that is, the time spent at the location of a client, has not been explicitly studied but remains considered in most approaches. Finally, some recent work considers vehicle availability (Li et al., 2009a,b), with the source of dynamism being the possible breakdown of vehicles.

Differences with static routing

By their nature, dynamic routing problems differ from their static equivalent by adding more degrees of freedom for the decision making, and introducing new metrics for the objective function.

In some contexts, such as the pick-up of express courier studied in (Gendreau et al., Degrees of freedom 1999), the transport company does not have the obligation to service a customer request. As a consequence, it can reject a request, either because it is simply impossible to serve it, or because the cost of serving it is too high compared with the company objectives. This process of acceptance/denial has been used in many approaches [START_REF] Attanasio | Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem[END_REF][START_REF] Fagerholt | A decision support model for establishing an air taxi service: a case study[END_REF][START_REF] Gendreau | Parallel tabu search for real-time vehicle routing and dispatching[END_REF][START_REF] Ichoua | Diversion issues in real-time vehicle dispatching[END_REF][START_REF] Chavan | A heuristic approach to solve air taxi scheduling problem[END_REF], 2006, Li et al., 2009a), and is sometimes referred to as service guarantee [START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF]. In some cases, the knowledge of stochastic information on customer can be used to refine the acceptance criteria. For instance in scenario-based approach [START_REF] Bent | Online stochastic and robust optimization[END_REF], Bent and Van Hentenryck, 2004a,b, 2007[START_REF] Hvattum | Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic[END_REF], artificial clients are generated to create scenarios, allowing the acceptance of a request to be conditioned on the fact that a minimum proportion of scenarios can accommodate the new request, possibly by removing up to a certain number of sampled customers. Therefore, a request is accepted or rejected not only based on the currently known requests, but also on the expected requests. A consequence is that highly restrictive requests, located for instance in remote areas, are likely to be rejected to preserve more promising expected ones.

In most of the literature, a vehicle cannot be diverted while moving toward its next destination. However, being able to redirect a moving vehicle to a new request near its current position could allow additional savings. Nevertheless, it requires real-time knowledge of the vehicle positions and to be able to communicate rapidly with drivers to assign them new destinations. Thus, this strategy has received limited interest, with the main contributions being the early work by [START_REF] Regan | Evaluation of dynamic fleet management systems -simulation framework[END_REF], the study of diversion issues by [START_REF] Ichoua | Diversion issues in real-time vehicle dispatching[END_REF], and the work by [START_REF] Branchini | Adaptive granular local search heuristic for a dynamic vehicle routing problem[END_REF]. However, it is worth noting that diversion has been more widely applied in the context of emergency services operations (Gendreau et al., 2001, Haghani and[START_REF] Haghani | Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies[END_REF].

Aside from the difference in the way input is revealed, dynamic problems also fre-Objective functions quently differ from their static counterparts in their objective function [START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF].

In particular, while a common objective in static context is to minimize a routing cost, dynamic routing may introduce other notions such as service level, throughout or revenue maximization.

Having to answer dynamic customer requests introduce the notion of response time: a customer might request to be served as soon as possible, in which case the main objective may become to minimize the time between a request and its service.

Another difference is that in static planning, if not specified, all requests have the same priority. By contrast, in a dynamic context, nearer term events are generally more important [START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF]. In fact, mobilizing resources for future requests may reveal 1 DYNAMIC ROUTING 1.3 Measuring the dynamism to be suboptimal if intermediate requests are to appear in the meantime. Therefore and as stated before, the decision maker might have the possibility to delay or reject customer requests. Resulting objectives could be the maximization of the number of served clients (referred to as throughout), or the total expected revenue, which may include both the routing costs and the revenue generated by the served customers.

Finally, other objectives could be introduced, for instance a pragmatic approach could be to mitigate changes in the routes when a new client request is accepted.

Measuring the dynamism

Before presenting the different applications of dynamic vehicle routing, it is important to introduce a notion that has been widely used to characterize the degree of dynamism of a problem. In fact, it appears that the level of dynamism can greatly vary between problems or even instances of a same problem. For instance, an on-demand transportation company may request their customers to book their trip in advance to only face limited requests for the same day. In contrast, emergency services will have to respond quickly to purely dynamic requests [START_REF] Haghani | Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies[END_REF].

Two dimensions can be identified to characterize the dynamism of a problem [START_REF] Ichoua | Exploiting knowledge about future demands for real-time vehicle dispatching[END_REF]: the frequency of changes, which is the rate at which new information becomes available, and the urgencies of requests, defined as the time available between the arrival of a request and its expected service date. [START_REF] Lund | Vehicle routing problems with varying degrees of dynamism[END_REF] proposed a first metric to measure the dynamism of a problem.

Degree of dynamism

The degree of dynamism δ is defined as the ratio between the number of dynamic requests n d and the total number of requests n tot :

δ = n d n tot
Based on the fact that the arrival time of requests is also important, as stressed by Effective degree of dynamism [START_REF] Psaraftis | Dynamic vehicle routing problems[END_REF][START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF], [START_REF] Larsen | The Dynamic Vehicle Routing Problem[END_REF] proposed another indicator, namely, the effective degree of dynamism δ e . This metric can be interpreted as the normalized average of the arrival times. Let T be the length of the planning horizon, R the set of requests, and t i the arrival time -or disclosure date [START_REF] Jaillet | Online routing problems: Value of advanced information as improved competitive ratios[END_REF]) -of request i ∈ R.

Considering that requests known beforehand have a disclosure date equal to 0, δ e can be expressed as: [START_REF] Larsen | The Dynamic Vehicle Routing Problem[END_REF] also extended the effective degree of dynamism to problems with time Time windows windows, in order to reflect the level of urgencies of requests. He defines the reaction time r i as the difference between the arrival date t i and the end of the corresponding time window l i , highlighting that greater reaction times mean more flexibility to insert the request into the current routes. Thus the effective degree of dynamism measure is extended as follows:

δ e = 1 n tot i∈R t i T
δ e T W = 1 n tot i∈R 1 - r i T
It is worth noting that these three metrics only take values in the interval [0, 1] and increase with the level of dynamism of a problem. [START_REF] Larsen | Partially dynamic vehicle routing-models and algorithms[END_REF][START_REF] Larsen | Classification of dynamic vehicle routing systems[END_REF] use the effective degree of dynamism to define a framework classifying DVRPs among weakly, moderately and strongly dynamic problems, with values of δ e being respectively lower than 30%, comprised between 30% and 80%, or higher than 80%.

Although the effective degree of dynamism and its variations have proven to capture well the time-related aspects of dynamism, it could be argued that they do not take into account the other possible sources of dynamism listed previously. In particular, the geographical distribution of requests, or similarly the traveling times between requests, are also of great importance in applications aiming at the minimization of response time. In addition, the frequency of changes mentioned earlier is not directly reflected, although it can have dramatical impact on the time available for optimization between the arrival of two events.

A review of applications

As it has been stated before, recent advances in technology allowed the emergence ITS of a wide new range of applications for vehicle routing. In particular, the last decade has seen the development of Intelligent Transport Systems (ITS), based on the combination of geolocation technologies, with precise geographic information systems, and increasingly efficient hardware and software for data processing and operations planning. We refer the interested reader to the study by [START_REF] Crainic | Intelligent freight-transportation systems: Assessment and the contribution of operations research[END_REF] for more details on ITS and the contribution of operations research to this relatively new domain.

Among the ITS, the Advanced Fleet Management Systems (AFMS) are specifically AFMS dedicated to the management of a corporate vehicle fleet. The problem faced is generally to deliver (pickup) goods or persons to (from) locations distributed in a specific area. Customer requests can be either known in advance or appear dynamically during the day, and the vehicles have therefore to be dispatched and routed in real-time, potentially by taking into account other factors such as traffic conditions. On top of the technological requirements, an important component of such systems is the optimization of the decision process. Traditionally, vehicle routing relied on teams of human dispatchers, meaning that the performance of the organisation as a whole was highly related to the competence and experience of the people in charge, but also that management costs were directly linked to the size of the fleet [START_REF] Attanasio | Real-time fleet management at ecourier ltd[END_REF]. Advances in computer science allowed the transfer of techniques from operational research to such systems, as presented in the studies by [START_REF] Attanasio | Real-time fleet management at ecourier ltd[END_REF], [START_REF] Godfrey | An adaptive dynamic programming algorithm for dynamic fleet management, i: Single period travel times[END_REF], [START_REF] Powell | Fleet management[END_REF], [START_REF] Simao | An approximate dynamic programming algorithm for large-scale fleet management: A case application[END_REF] and [START_REF] Slater | Specification for a dynamic vehicle routing and scheduling system[END_REF].

The remainder of this section presents more details on some of the applications where dynamic routing has been -or can be -implemented.

Visiting of clients

Applications in this category do not include the transport aspect of other routing problems: a request is only composed by a customer location and a possible time window, thus the routing plan has to ensure that each customer is visited, without considering capacity constraints.

A common application of dynamic routing can be found in the technical mainte-Equipment maintenance nance operations, for instance for copying machines, heating systems, elevators or even water meters. Companies offering such services are bound by contract to their clients, which can specify periodical, or planned maintenance visits, but may as well define a maximum delay before an intervention in the case of an equipment failure. As a consequence, at the beginning of the day, the planner or dispatcher has a set of customer requests, either from contractual visits or emergencies from the day before. Each technician is assigned a set of requests, and a routing plan is produced. However, new urgent requests appearing during the day, or changing traffic conditions in urban areas require to dynamically re-evaluate the routing of the technician fleet to ensure the best level of service. An important feature often present in such companies is the qualification of technicians for specific equipments or their assignation to geographic zones, increasing the complexity of the routing.

Another interesting application of dynamic routing is provided by the problem

Traveling physician faced by a french organization: SOS Médecins. This non-profit organization was created to match a gap between proximity physicians who only provide limited service outside business hours, and emergency services operating 24/7 but with limited capacity for lesser urgent concerns. It operates with a fleet of physicians, in contact with a call center coordinated with other emergency services. When a person calls, the priority of the situation is evaluated, and a visit by a practitioner is planned accordingly. As for other emergency services, having an efficient dispatching system can allow a reduction in the response time, improving the level of service for the society. It requires to be able to decide the routing of the practitioner fleet in real-time, depending on the current emergencies, but also to ensure a proper coverage of the considered area, in order to have practitioners available where emergencies are likely to come up.

Transport of goods

Due to the fact that urban areas are often characterized by travelling times vary-

City Logistics

ing greatly depending on the time of the day, transport of goods in such areas have led to the definition of a specific category of applications: city logistics. [START_REF] Taniguchi | Modeling city logistics[END_REF] defined city logistics as the process for totally optimising the logistics and transport activities by private companies in urban areas while considering the traffic environment, the traffic congestion and energy consumption within the framework of a market economy. [START_REF] Barcelo | Vehicle routing and scheduling models, simulation and city logistics[END_REF] developed a general framework for these applications, presenting the different modules required, from the modelling of the city road network, to the acquiring of real-time traffic data, and the dynamic routing of a fleet of vehicles in this environment.

An example of application in city logistics is the courier service present in ma-Courier jor urban areas. A case study by [START_REF] Attanasio | Real-time fleet management at ecourier ltd[END_REF] outlines the benefits of using computer-based techniques over human-based dispatching. They studied the case of eCourier Ltd, a London based company offering courier services. Their clients are mainly law firms, financial institutions and advertising agencies, and other entities requiring fast delivery of items or original signatures on documents. When a customer request is being known and accepted, a courier is sent to the client location to pick-up the item, that will then be delivered at its destination, in exchange of a signature. Depending on the level of service asked by the customer, the courier may consolidate or not its pick-up and deliveries, meaning that he may pick-up from various clients before delivering an item, or provide an exclusive expedited service. Companies offering courier services often have an heterogeneous fleet, composed in the case of eCourier of bicycles, motorbikes, cars and small vans. The problem is then to dynamically affect requests to couriers, depending on the type of request and its pick-up and delivery location and possible time windows, but also taking into account traffic conditions and varying travel times. This study showed that the use of an AFMS, including optimization algorithms, was highly profitable for courier companies. In fact, aside from the improvements in service quality, response time, and courier efficiency, the use of an automated system allows to increase the fleet size without the need of additional supervisors. A direct consequence is that the growth of the fleet does not require more supervisors, therefore company growth also increases the margin on each delivery, providing a strong competitive advantage.

The delivery of newspapers and magazines, as studied by [START_REF] Bieding | Online routing per mobile phone: A case on subsequent deliveries of newspapers[END_REF],

Newspaper delivery constitutes another highly competitive market where the satisfaction of subscribers is considered as extremely important. When a magazine or newspaper is not delivered, a subscriber can contact a call center and is offered to choose between a voucher or a subsequent delivery. In the latter case, the request is then forwarded to the delivering company, and finally transmitted to a driver that will do the proper delivery. Traditionally, this process relies on different medias, with phone calls, faxes and printed documents, and the subsequent delivery requests are not transmitted to the drivers until they come back to the depot. In response to this problem, their study proposes a centralized application, that makes use of mobile phones to communicate with drivers and intelligently perform the routing in real-time, to accommodate subsequent deliveries in shorter delays, reducing costs, and improving customer satisfaction.

Apart from classical routing problems on a road network, similar problematic can Other applications also be found in the internal operation of organisations. The review by [START_REF] Stahlbock | Operations research at container terminals: a literature update[END_REF] on operations research applications in container terminals gives an interesting example of such problem, in particular with the dynamic stacker crane problem [START_REF] Balev | Dynamical handling of straddle carriers activities on a container terminal in uncertain environment -a swarm intelligence approach[END_REF][START_REF] Berbeglia | Dynamic pickup and delivery problems[END_REF], which considers the scheduling and routing of container carriers operating the loading and unloading of ships in a terminal. Other applications include transport of goods inside warehouse [START_REF] Smolic-Rocak | Time windows based dynamic routing in multi-agv systems[END_REF], factories, or even hospitals where documents or equipments have to be transferred efficiently between services [START_REF] Fiegl | Online scheduling of pick-up and delivery tasks in hospitals[END_REF].

Transport of persons

The transport of persons is in general -and by many aspects -similar to the transport of goods. However, it is characterized by additional constraints, in particular regarding waiting times and travel times for the passengers that generally have to respect maximal values.

Taxi services are the most common on-demand individual transport system. Re-Taxi services quests from customers are composed of a pick-up location and time, possibly coupled with a destination. They can be either known in advance, for instance when a client book a cab for the next day, or arrive dynamically, in which case a taxi must be dispatched in the shortest time. When clients cannot share a same vehicle, there is only limited space for optimization, and the closest free taxi is generally the one which takes the ride. The study by [START_REF] Caramia | Routing a fleet of vehicles for dynamic combined pick-up and deliveries services[END_REF], generalized by [START_REF] Fabri | On dynamic pickup and delivery vehicle routing with several time windows and waiting times[END_REF], focuses on a multi-cab metropolitan transportation system, where a taxi can transport more than one client at the same time. In this case the online algorithms aim at minimizing the total travel distance while assigning requests to vehicles and computing the cabs routes.

The above mentioned multi-cab transportation systems can be generalized to other

On-demand transport on-demand or door-to-door services. Main applications include transport of children, elderly or disabled people, or patients, for instance from their home to schools, place of work or medical centers [START_REF] Lehuede | Un systeme d'aide a la decision pour planifier les transports vers les etablissements medico sociaux[END_REF]. An extensive review of this class of problems can be found in Cordeau et al. (2007a).

A singular application of on-demand person transportation can be found in ma-Patient transport jor hospitals, with services possibly spread across various buildings on one or more campuses. Depending on the results of a consultation or surgery, or the arrival of an emergency, a patient may need to be transferred on short notice from one service to another, possibly requiring trained staff or specific equipment for its care. This application as been for instance studied by [START_REF] Beaudry | Dynamic transportation of patients in hospitals[END_REF].

Air taxis services developed as a response to limitations of traditional air transport Air taxi systems. Firstly, with the increase of operating costs and the constant pressure on reducing expenses, companies are increasingly reluctant to invest in private aircraft, preferring to pay for this service only when needed. Secondly, major airlines only operate from a limited number of airports, to reduce their costs first, but also because technical restrictions do not allow them to land their aircraft on smaller airports. Besides, hub airports often suffer from high congestion, either on the runways or inside the airport itself, thus increasing travel times. Finally, airline flight schedules are fixed and therefore do not offer a convenient alternative to the use of private jets when flexibility is needed. In contrast, air taxi companies offer an on-demand service: customers book a flight at most a few days in advance, specifying whether they are willing to share the aircraft, stop at an intermediate airport, or have flexible traveling hours. Then the company accommodates these requests, trying to consolidate flights whenever possible. Passengers can travel through smaller airports, avoiding waiting times at check-in and security checks. Between the years 2001 and 2006, the NASA conducted a study on a Small Aircraft Transportation System (SATS), aiming at providing an efficient alternative to classical air transport, by making use of a new generation of cheap small aircraft [START_REF] Abbott | Small aircraft transportation system, higher volume operations concept: Normal operations[END_REF][START_REF] Holmes | Small aircraft transportation system concept and technologies[END_REF] and relying on smaller air taxi companies. To our knowledge, the related optimisation problems have not been subject to much attention, except in the studies by [START_REF] Chavan | A heuristic approach to solve air taxi scheduling problem[END_REF], Cordeau et al. (2007a), Espinoza et al. (2008a,b) and [START_REF] Fagerholt | A decision support model for establishing an air taxi service: a case study[END_REF]. A similar problematic can be found in the helicopter transportation systems, for instance for the transport of persons between offshore petroleum platforms [START_REF] Romero | A genetic algorithm for the pickup and delivery problem: An application to the helicopter offshore transportation[END_REF].

Emergency services, such as ambulances, police or fire services, constitute a do-Emergency services main where strong dynamism is present. Although their operation might differ, the efficiency of such services is directly linked to their response time. In other words the system has to provide guarantees between the call and arrival time. For instance, the United States Emergency Medical Services Act of 1973, requires 95% of the medical emergency calls to be treated in less than 10 minutes. The operation of emergency services is traditionally decomposed into three main aspects: the deployment of the fleet to predefined sites, to provide adequate coverage of the service area; the assignment of vehicle to emergencies, possibly by diverting an on-route vehicle; and finally, the proper routing of vehicles, possibly depending on traffic information. The survey of ambulance deployment by [START_REF] Brotcorne | Ambulance location and relocation models[END_REF] reveals that this aspect has mainly been considered at the strategic level, with static approaches, but that dynamic approaches such as the one proposed by [START_REF] Gendreau | A dynamic model and parallel tabu search heuristic for real-time ambulance relocation[END_REF] with their case study of the Montreal ambulance system, or the later work by [START_REF] Haghani | Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies[END_REF], who proposed an integrated management of emergency services, including ambulance, police and fire services, would lead to major improvements in emergency services performance.

In a context of increasing concern on the environmental footprint of human activi-

Car pooling

ties, in addition to traffic issues in major urban areas, car-pooling has been a subject of in-

13/33
creasing interest. Currently most systems rely on an open market place, where drivers and passengers meet and match their offer and demand for trips. An enhanced system could include a suggestion process that will find the best matches between drivers and passengers. However, the drawback most commonly cited about car-pooling is that passengers are bound to their driver and might therefore have due to unexpected delays. One could therefore imagine a dynamic car-pooling framework, where both drivers and passengers could modify their travel date at any time, with an assignment or recommendation system being in charge of finding the best matches.

State of the art

Few research was conducted on dynamic routing between the work of [START_REF] Psaraftis | A dynamic-programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF] and the late 1990s. However, the last decade has seen an important increase in the interest for this class of problems [START_REF] Eksioglu | The vehicle routing problem: A taxonomic review[END_REF], with the introduction of a variety of methods ranging from linear programming to metaheuristics. The interested reader is referred to the work by [START_REF] Ghiani | Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies[END_REF], [START_REF] Ichoua | Problèmes de gestion de flottes de véhicuies en temps réel[END_REF], [START_REF] Ichoua | Exploiting knowledge about future demands for real-time vehicle dispatching[END_REF], [START_REF] Jaillet | Online vehicle routing problems: A survey[END_REF], [START_REF] Larsen | Recent developments in dynamic vehicle routing systems[END_REF] and [START_REF] Psaraftis | Dynamic vehicle routing: Status and prospects[END_REF] to complement our review.

Dynamic and deterministic routing

In the context of dynamic problems, critical information is revealed over time, meaning that the complete definition of an instance of a given problem is only known at the end of the planning horizon. As a consequence, an optimal solution can only be found a-posteriori. Therefore, most approaches use fast approximation methods that give a good solution in a relatively low computational time, rather than exact methods that would only provide an optimal solution for the current state, providing no guarantee that the solution will be optimal once new data becomes available.

The following paragraphs will present some approaches that have been successfully applied to dynamic routing, when no stochastic information is considered.

Dynamic programming

The first application of an optimization technique to dynamic routing is due to [START_REF] Psaraftis | A dynamic-programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF], with the development of a dynamic programming approach. His research focuses on a dynamic program formulation to solve the static version of the dial-a-ride problem, which is then adapted to the dynamic context by running it to find the new optimal route each time a new request is made known.

It has been long known that the main drawback of dynamic programming is its computational complexity, namely the curse of dimensionality (see Powell, 2007, Chap. 1), therefore it has not been applied to large instances. [START_REF] Yang | Realtime multivehicle truckload pickup and delivery problems[END_REF] that is directly linked to the spatial distribution of customer requests. Consequently, the optimization will tend to reject isolated jobs, and avoid arcs that are far from potential requests.

Linear programming

Exploring a new area of linear programming, [START_REF] Chen | Dynamic column generation for dynamic vehicle routing with time windows[END_REF] designed a dy-Dynamic column generation namic column generation algorithm (DYCOL) for the dynamic version of the classical Vehicle Routing Problem with Time Windows (D-VRPTW). The authors define K decision epochs over the planning horizon, corresponding to the dates when the solution is re-evaluated along with the newly available requests. The innovation consists in dynamically generating columns for the linear model, by iterating over a four step algorithm at each decision epoch. The initialization of the algorithm is done by generating a set of routes Π 0 covering all the currently accepted requests and based on the columns used at the previous decision epoch. During the first step, a set-partitioning model is build up and its linear relaxation solved to retrieve the optimal dual values that will be used to calculate the reduced costs in the next steps. In the second and third steps, a predetermined number of new columns are generated by applying a two-phase local search to the elements of Π 0 . The last step consists in generating columns for the newly arrived requests, before updating the formulation of the first step and starting a new iteration. The authors compared this new approach to a traditional column generation with no time limit (COL), solved to termination with the data available at each epoch. Computational results based on the Solomon benchmark [START_REF] Solomon | Algorithms for the vehiclerouting and scheduling problems with time window constraints[END_REF] demonstrate that the DYCOL procedure yields comparable results in terms of objective function, but with running times limited to 10 seconds, against up to various hours for COL.

Meta-heuristics

As it was stated earlier, the optimal solution at a time t is biased by the knowledge of the input at this same period. Therefore, enforcing a decision that is optimal at time t may reveal to be sub-optimal at time t + 1. Hence exact methods are not necessarily best fitted in the context of dynamic routing, given that approximated solution could reveal to be better when new data becomes available.

As a consequence, most of the research in the field of dynamic vehicle routing problem is based on heuristics in the general sense, including local search procedures, tabu search and evolutionary algorithms, as they will be presented in the following paragraphs.

To the best of our knowledge, the first application of a tabu search procedure to a Tabu search dynamic routing problem is due to the study by [START_REF] Gendreau | Parallel tabu search for real-time vehicle routing and dispatching[END_REF]. It was motivated by the local operation of long distance express courier services, which can be seen as a vehicle routing problem with time windows (VRP-TW). Their approach consisted in the adaptation of the framework introduced by [START_REF] Taillard | A tabu search heuristic for the vehicle routing problem with soft time windows[END_REF] to a dynamic context. The general idea is to maintain a pool of good routing plans -the adaptive memory -which is used to generate initial solutions for a parallel tabu search. The parallelization of the search is done by partitioning the routes of the current solution, each subset being optimized by an independent thread. Whenever a new customer request arrives, it is checked against all the solutions from the adaptive memory with rapid insertion heuristics to decide whether it should be accepted or rejected. Once accepted, the tabu search is resumed including the new request. It is worth noting that because the current routing is subject to change at any time, vehicles do not know their next destination until they finish the service of a request. This framework was also implemented for the D-VRP [START_REF] Ichoua | Vehicle dispatching with time-dependent travel times[END_REF] and for the PDP [START_REF] Ichoua | Diversion issues in real-time vehicle dispatching[END_REF], while other variations of tabu searches have been applied to the D-PDP [START_REF] Barcelo | Vehicle routing and scheduling models, simulation and city logistics[END_REF][START_REF] Chang | Realtime vehicle routing problem with time windows and simultaneous delivery/pickup demands[END_REF], or to the the DARP [START_REF] Attanasio | Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem[END_REF][START_REF] Beaudry | Dynamic transportation of patients in hospitals[END_REF].

The main idea behind Variable Neighborhood Search (VNS) is to iteratively im-VNS prove a solution by considering different neighborhoods successively. An overview of the approach is given by Algorithm 1. The algorithm starts with an initial solution X and generates a neighbor X t from the current neighborhood (shake line 6), which is then improved by a local search procedure (ls line 7). If the new solution is accepted (accept line 8), it replaces the current solution and a new iteration is performed with the first neighborhood (line 10); otherwise, the next neighborhood is selected (line 12) and a new iteration is done with the unchanged current solution. As for other heuristics, iterations are performed until a stop criterion is met, usually a maximum time or number of iterations. VNS was originally developed to tackle static combinatorial problems (Hansen and[START_REF] Hansen | Variable neighborhood search: Principles and applications[END_REF][START_REF] Mladenovic | Variable neighborhood search[END_REF]), yet its low computational times has allowed applications in dynamic contexts, with for instance the work of [START_REF] Goel | A general vehicle routing problem[END_REF] [START_REF] Bent | A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[END_REF]. Algorithm 2 presents the general structure of LNS. The exploration is done by firstly destroying the current solution (destroy line 6) and then repairing it (repair line 6). The resulting neighbour X n is then accepted or rejected depending on an implementation specific criterion (accept line 7). In the original implementation by [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF], the destroy method removes a subset of clients from the routes, while the repair function reinserts them by using heuristics and constraint propagation. On the other hand, it uses a simple acceptance criterion, accepting only improving solutions. The main idea behind LNS is to effi-ciently explore an exponential neighborhood. In fact, with n clients, there are 2 n candidate subsets to be removed and reinserted. In the implementation by [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF], this is achieved by the destroy function that considers subsets of iteratively incremented cardinality, increasing the neighborhood size each time a given number of consecutive non-improving neighbors are found1 . After being successfully applied to static routing problems [START_REF] Bent | A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[END_REF], Bent and Van Hentenryck, 2004c[START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF][START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF][START_REF] Rousseau | Using constraint-based operators to solve the vehicle routing problem with time windows[END_REF], large neighborhood search was adapted to dynamic routing, either directly as in the study by [START_REF] Goel | Large neighborhood search for rich vrp with multiple pickup and delivery locations[END_REF] on the D-PDP, or as an optimization subroutine of other algorithms such as the MSA (Van Hentenryck and Bent, 2006).

Algorithm 2

The Large Neighbourhood Search generic algorithm Input: X a valid solution, z an evaluation function Output: X * the best solution found 1: function LNS(X) 2:

X * ← X; [START_REF] Bent | Scenariobased planning for partially dynamic vehicle routing with stochastic customers[END_REF] MPA to tackle the D-VRPTW, and is presented as a generalization of the tabu search with adaptive memory developed by [START_REF] Gendreau | Parallel tabu search for real-time vehicle routing and dispatching[END_REF]. As illustrated in Figure 1, the general idea is to populate and maintain a pool of routing plans that are used to generate a distinguished plan2 . Time between events is used to continuously improve the plans of the pool. Whenever a new request arrives, a procedure is called to check whether it can be serviced or not, for instance by checking if at least one plan can accommodate it. If the answer is positive, the request is inserted in the plans of the pool, while incompatible plans are discarded. Pool updates are performed periodically, or whenever a vehicle finishes the service of a customer. This phase is crucial and ensures that all plans are coherent with the current state of both vehicles and customers requests. The pool can be seen as an adaptive memory [START_REF] Taillard | Adaptive memory programming: A unified view of metaheuristics[END_REF] and allows the maintaining of a variety of solutions, the goal being to have a variety of plans to choose from when a new requests arrives.

3: i ← 0 ⊲ Number of iterations 4: k ← 0 ⊲ Number of

Plan optimization and selection

Plan optimization and selection

Plan generation Plan generation

Outputs Outputs

Pool update Pool update Events Events

Multiple Plan Approach (MPA)

Evolutionary algorithms have not received much interest in the field of dynamic

Evolutionary algorithms routing until recently. In an early work, [START_REF] Benyahia | Decision support for vehicle dispatching using genetic programming[END_REF] studied the D-PDP and proposed a Genetic Algorithm (GA) modeling the decision process of a human dispatcher. More recently, GA were also used for the same problem (Cheung et al., 2008, Haghani and[START_REF] Haghani | A dynamic vehicle routing problem with time-dependent travel times[END_REF], and for the D-VRP [START_REF] Van Hemert | Dynamic routing problems with fruitful regions: Models and evolutionary computation[END_REF]. Genetic Algorithms in dynamic contexts are very similar to those designed for static problems: a population of individuals representing routing plans is maintained, and subject to crossovers, mutations and selection. The main difference is that the GA is generally running throughout the planning horizon, and the solutions are constantly adapting to the changes made to the input. [START_REF] Montemanni | Ant colony system for a dynamic vehicle routing problem[END_REF] developed an Ant Colony System (ACS) to solve the dy-

Ant colonny

namic vehicle routing problem. Their approach makes use of the time slices, as introduced by [START_REF] Kilby | Dynamic VRPs: a study of scenarios[END_REF], that divide the day in n ts periods of equal duration T n ts . The processing of a request arriving during a time slice is postponed until the end of it, thus the problem solved during a time slice only considers the requests known at its beginning. Hence the optimization is run independently during each of the time slice, resolving a static problem. The main advantage of this partition of time is that similar computational effort are allowed for each time slice, while if optimization was performed on the arrival of each new request there will be no guarantee on the time available for computation. It is made possible by the nature of requests that are never urgent, and which processing can therefore be postponed, in contrast with other studies [START_REF] Gendreau | Parallel tabu search for real-time vehicle routing and dispatching[END_REF].

Dynamic and stochastic routing

As presented before, stochastic and dynamic routing problems can be seen as an extension of their deterministic counterparts, where additional knowledge is available on the dynamically revealed input, under the form of stochastic information.

From this observation, two main strategies can be identified in the stochastic and Sampling v.s.

pricing dynamic routing literature, that will be referred to as either based on sampling or pricing.

As their name suggests, sampling strategies incorporate the stochastic knowledge by producing various scenarios or simulations resulting from the sampling of the input variable distributions, the goal being to capture the likeliness of an event and create a routing plan that will be able to accommodate it. Generally speaking, such a method will generate sampled requests and find a route servicing them with a method from deterministic routing. This is for instance the case of the Mutliple Scenario Approach (MSA) ( [START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF].

On the other hand, approaches based on pricing integrate stochastic knowledge by evaluating expected values, for instance the expected traveled distance when servicing a customer with a given vehicle, knowing the probability of seeing the arrival of a new request in the meantime requiring a deviation from the initial plan. Markov Decision Process (MDP) based approaches (Novoa andStorer, 2009, Secomandi and[START_REF] Secomandi | Reoptimization approaches for the vehicle-routing problem with stochastic demands[END_REF] or Approximate Dynamic Programming (ADP) [START_REF] Powell | A comparative review of alternative algorithms for the dynamic vehicle allocation problem[END_REF][START_REF] Powell | A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers[END_REF] are examples of such strategies.

Generally speaking, the advantage of sampling is its simplicity of implementation, while its drawback is that a large number of samples is required to effectively reflect the reality. Alternatively, pricing strategies are often more complex in their formulation and require to compute efficiently possibly complex expected values, but they capture more formally the stochastic nature of the problem.

Examples of these two strategies, as well as other variations, will be given in the following paragraphs.

Markov processes

Early research by [START_REF] Powell | Maximizing profits for north american van lines' truckload division: A new framework for pricing and operation[END_REF] on dynamic routing formulated the problem as a Markov process. Unfortunately, the state and action space tends to grow exponentially as the dimension of the problem increases, inducing prohibitive computational times. Besides such modeling requires simplification assumptions that are incompatible with real world applications. Nonetheless, it allowed new insights in the field of dynamic programming, as it will be presented in the next paragraph.

Markov decision process was for instance used by [START_REF] Novoa | An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[END_REF], [START_REF] Secomandi | Reoptimization approaches for the vehicle-routing problem with stochastic demands[END_REF] to model and solve a Vehicle Routing Problem with Stochastic Demands (VRP-SD), where the set of customers is known but with random demands. Although the authors do not explicitly state it, the use of a reoptimization policy classifies the problem as dynamic in our taxonomy.

Approximate dynamic programming

The work by [START_REF] Powell | A comparative review of alternative algorithms for the dynamic vehicle allocation problem[END_REF][START_REF] Powell | A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers[END_REF] opened a new branch in the area of dynamic vehicle routing by introducing the notion of predictive algorithms, which take advantage of the stochastic knowledge of the future to take predictive or preventive actions. In his early work, [START_REF] Powell | A comparative review of alternative algorithms for the dynamic vehicle allocation problem[END_REF] addressed the issue of anticipatory relocation of vehicles based on prediction of future demands. His approach considered a time-space graph, with nodes for known and forecasted requests. At each period, the problem is solved by minimizing the deterministic cost of the current period, and the expected cost of future periods. [START_REF] Powell | A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers[END_REF] later furthered this research by considering the driver-request assignment aspect. The problem is modelled as a dynamic-stochastic network composed of an assignment and a forecast component, with the cost of possible recourse actions being included in the arc costs. Consequently the initial problem is approximated as a transportation problem in the resulting network, which is then efficiently solved by a network algorithm.

Since then, different research has been led on this field, in particular by Powell and ADP the CASTLE laboratory who developed a new optimization framework now known as Approximate Dynamic Programming (ADP). In dynamic programming, one defines a value function at each decision step, and then generally uses a backward induction to determine the optimal actions at each decision time. However, this method suffers from the curse of dimensionality, making it useless when the state or action spaces are too vast. The general idea of ADP is to work in a forward fashion, avoiding the evaluation of all possible states by approximating the value function. We refer the interested reader to [START_REF] Powell | What you should know about approximate dynamic programming[END_REF][START_REF] Powell | Approximate dynamic programming: solving the curses of dimensionality[END_REF] for a more detailed description of the framework.

During the last decade, ADP has been successfully applied to fleet management problems [START_REF] Godfrey | An adaptive dynamic programming algorithm for dynamic fleet management, i: Single period travel times[END_REF][START_REF] Powell | Fleet management[END_REF][START_REF] Simao | An approximate dynamic programming algorithm for large-scale fleet management: A case application[END_REF], freight transport [START_REF] Powell | Dynamic models for freight transportation[END_REF][START_REF] Powell | Stochastic programming in transportation and logistics[END_REF], with in particular an application to the VRPSD [START_REF] Novoa | An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[END_REF], but also dynamic assignment problem, which extend the fleet management (Powell, 1996, Spivey and[START_REF] Spivey | The dynamic assignment problem[END_REF], or other dynamic flow problems [START_REF] Topaloglu | Dynamicprogramming approximations for stochastic time-staged integer multicommodity-flow problems[END_REF]. As in [START_REF] Powell | A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers[END_REF], ADP proceeds by defining the problem at each decision time using a state-action graph representation, adding the information given by the approximated value function as costs on specific arcs, and using a graph algorithm to solve the resulting flow problem.

Online stochastic combinatorial optimization

The other main branch in predictive approaches for the online VRP is the work done by Bent and Van Hentenryck (Bent and Hentenryck, 2005, Bent and Van Hentenryck, 2004a,b,c,d, Hentenryck et al., 2010[START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF] who developed generic frameworks and algorithms for the D-VRP under the name Online Stochastic Combinatorial Optimization (OSCO) with contributions and adaptations from the area of online scheduling. Figure 2 presents an overview of the research done in this area.

Multiple Scenario Approach (MSA), of which an overview is given in Figure 3, was MSA first presented as a predictive adaptation of the MPA framework discussed earlier [START_REF] Bent | Scenariobased planning for partially dynamic vehicle routing with stochastic customers[END_REF]. The main idea is to include stochastic knowledge of the problem by considering possible future requests and by maintaining a pool of scenarios, each one composed by a tour visiting all actual nodes and a set of virtual requests. Scenarios are build in three steps, as illustrated in Figure 4. Firstly virtual requests are generated by sampling the clients distributions; then an optimization procedure finds a good tour that serves both real and sampled requests; finally, sampled requests are removed from the tour. This process introduces room in the resulting scenarios that could then be used to accommodate future requests, improving the robustness of the routing, as illustrated in Figure 4. While the optimal tour for the currently known requests would start by areas where customers are likely to appear in the afternoon, the generated scenario guides the routing toward regions with early clients first, leaving for instance room to accommodate potential mid-day requests between clients C and D.

Another idea behind the MSA scheme is to take advantage of the time between de-

Immediate decision making

cisions to continuously improve the current pool of scenarios. During the initialization of the algorithm, a first set of scenarios is created based on the requests known beforehand, that will then be re-optimized and completed with new scenarios during the idle time of the dispatcher. When a decision is required (Decision event in Figure 3), the scenario optimization procedure is suspended, and the scenario pool is used to find the best routing plan. Scenarios present in the pool that are incompatible with the resulting routing are discarded, and the continuous improvement algorithm is resumed. Computational experimentations on instances adapted from the Solomon benchmark [START_REF] Solomon | Algorithms for the vehiclerouting and scheduling problems with time window constraints[END_REF] showed that MSA outperforms MPA both in terms of served customers and traveled distances, especially for instances with high degrees of dynamism.

We will now briefly present three predictive algorithms, which were originally designed for an online job scheduling where the goal is to select a job -or requestr * to be scheduled at the current time t, from the set of feasible requests R (Hentenryck et al., 2010, Van Hentenryck andBent, 2006). Let O be an optimization algorithm for the considered problem, for instance an implementation of VNS ( [START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF], z(γ) a function evaluating the profit of a solution -or planγ defined as a permutation of the n pending requests (γ 0 , ..., γ n-1 ), and f • (r) an evaluation function for the benefit of scheduling request r first. The selected request r * is formally defined as:

r * = arg max r∈R f • (r)
Chang et al. (2000) designed a first selection process for online scheduling based Expectation on sampling, referred to as expectation algorithm (Bent and Van Hentenryck, 2004a,d, Hentenryck et al., 2010[START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF]. The evaluation of the expected profit for r is done by solving the scheduling problem defined by the combination of Actual and sampled requests, and tour resulting from the optimization.

Resulting Scenario: actual requests, final tour and sampled requests.

Step 0.

Steps 1.&2.

Step 3. The a-priori optimal tour of step 0. is not actually calculated and would be the result of a myopic optimization.

pending and sampled requests from the set of scenarios S, imposing that r is scheduled first:

f E (r) = s∈S z (O(r, s))
The main drawback of this method is that the optimization needs to be performed |R × S| times, for each pair request-scenario, which can be restrictive when the set of feasible requests grows and the computational time is limited, as it is the case for online vehicle routing ( [START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF].

In the consensus algorithm (Bent and Van Hentenryck, 2004b,d), optimization is only Consensus performed once for each of the generated scenarios. Consensus is obtained as follows: a request r is granted a profit of 1 each time r is scheduled first on a plan γ s resulting from the optimization O(s) of scenario s :

f C (r) = s∈S y r,s
Where y r,s ≡ (r = γ s0 ), with γ s0 being the first request of plan γ s . It is important to notice that only |S| calls to the optimization procedure are required to calculate all the γ s . Therefore, the main advantage in comparison with the expectation algorithm is that more scenarios can be evaluated in the same computational time. On the other hand, one of its flaws is the elitism of the selection process, which exclusively considers the first scheduled request, while ignoring requests that might be scheduled later in all scenarios, but still be robuster overall.

In (Bent and Van Hentenryck, 2004a), the authors propose an approach combining the advantages of both expectation and consensus algorithms: the consensus is used to identify a subset of promising requests, which are then compared against all scenarios in the expectation algorithm.

In further work, Bent and Van Hentenryck (2004a) proposed another predictive Regret approach combining the strengths of expectation and consensus: the regret algorithm (Bent and Van Hentenryck, 2004a[START_REF] Hentenryck | Online stochastic optimization under time constraints[END_REF][START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF]. The general idea is to firstly perform an optimization for each scenario, yielding the γ s , to then estimate for each scenario the degradation of the profit function incurred if a suboptimal request r is scheduled in place of γ s0 . This lost of profit is called regret, and it is used to approximate the benefit z(O(r, s) of the expectation algorithm, which exact calculation has been shown to have a prohibitive computational time.

Let Regret(r, s, γ s ) by the previously mentioned regret value associated with the scheduling of request r in place of γ s0 for scenario s. It is important to note that, in our notation, Regret(γ s0 , S, γ s ) = 0. The overall profit of request r is defined as:

f R (r) = s∈S [z(γ s ) -Regret(r, s, γ s )]
As for the consensus algorithm, the optimization is only performed on |S| scenarios, which is a guarantee of performance if optimization is the most time consuming task. Nevertheless, an important requirement is that the evaluation of the Regret(r, s, γ s ) function has to be efficient, otherwise the flaw of the expectation algorithm will reappear. A possible definition of the Regret(r, s, γ s ) function would be to return the value 0 is there is a feasible swap between r and γ s0 , and a value 1 otherwise ( [START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF]. These three algorithms have been described for the case of online scheduling. The Multiple vehicles generalization to multiple vehicle routing raises a number of issues ( [START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF]. In particular the routing has to be performed whenever at least one vehicle is available, and decisions for a single vehicle influence and are influenced by decisions for the rest of the fleet. Another characteristic is that decisions are now tuples of K requests (r 1 , ..., r K ) corresponding to the next request to be assign to each of the K vehicles. As a consequence, a routing plan γ s for scenario s is now defined as a tuple of routes (γ s1 , ..., γ sK ), where each γ sk is a route (γ sk0 , ..., γ skn ) associated with vehicle k.

Van Hentenryck and Bent (2006) extended the consensus and regret algorithms to Multiple pointwise decisions multiple vehicle problems by introducing a two step procedure named multiple pointwise decisions. The first step consists in the evaluation of each decision across all plans, similarly to the previous versions, and independently of the associated vehicle. In the second step, each plan is evaluated according to its own decisions, and the best plan is selected. More formally, the first produces values for f(r) for all requests r ∈ R, and each plan γ s is evaluated by the function g defined as follows:

g(γ s ) = K k=1 f(γ sk0 )
Where γ sk0 is the first request served by vehicle k in plan γ s . Finally, the best plan γ * = arg max s∈S g(γ s ) is selected and each vehicle k that is currently available is affected to request γ * k0 . It is important to note that the distinguished plan is in this case directly selected from the pool, for a plan composed by the best requests for each vehicle might not respect problem specific constraints, while the plan γ * does by construction.

We refer the interested reader to the book by [START_REF] Hentenryck | Online stochastic optimization under time constraints[END_REF] for an in-depth presentation of the OSCO framework.

Other work

Aside from ADP and OSCO, other research has been carried on stochastic dynamic problems, mainly by adapting deterministic methods by introducing sampling or pricing.

Another approach similar to the consensus algorithm for VRP was proposed by DSHH [START_REF] Hvattum | Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic[END_REF] under the name of Dynamic Sample Scenario Hedge Heuristic (DSHH). This method is based on the division of the planning horizon into time intervals, at the beginning of which the routing is revised. Routing optimization is done as follows: firstly, a set of scenarios is generated by sampling the customer distributions. In a second step, a subset P of promising requests is identified by iteratively solving the scenarios, imposing that all requests from P, initially empty, have to be served during upcoming time interval. When all scenarios have been solved, the request that is the most frequently visited during upcoming time interval is added to P, and a new iteration is performed, unless a stop criterion has been matched. The final step performs the actual planning of requests from P, thanks to another iterative process, by successively adding them to vehicle routes, depending on the frequency of this assignment over all the scenarios.

Various local search approaches have been developed for the stochastic and dy-

Local search namic problems. [START_REF] Ghiani | Anticipatory algorithms for same-day courier dispatching[END_REF], developed a sampling-based algorithm for the D-PDP where sampling is done only for the near future in order to reduce the computational effort. The main difference with MSA is that no scenario pool is used, and the selection of the distinguished plan is based on the expected penalty of accommodating requests in the near future.

Tabu search as also been adapted to dynamic and stochastic problems, with for Tabu search instance the research of [START_REF] Ichoua | Exploiting knowledge about future demands for real-time vehicle dispatching[END_REF] for the D-VRPTW or [START_REF] Attanasio | Real-time fleet management at ecourier ltd[END_REF] for an application of the D-PDP, both adaptations being based on the sampling of the requests distributions.

As presented in paragraph 3.1, [START_REF] Yang | Realtime multivehicle truckload pickup and delivery problems[END_REF] proposed a LP formulation for the Linear programming PDP that adds opportunity costs to the valuation of arcs, in order to reflect the expected cost of going on isolated areas. In later work, [START_REF] Yang | Online dispatching and routing model for emergency vehicles with area coverage constraints[END_REF] studied the emergency vehicle dispatching and routing and proposed a mathematical formulation later used by [START_REF] Haghani | Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies[END_REF] on a similar problem.

Additional strategies

In addition to the general frameworks described in the previous paragraphs, the introduction of probabilistic knowledge of the future allows the design and implementation of new strategies, that aim at producing a more adequate response to possible upcoming events.

Waiting strategy consists in deciding the period of time a vehicle will wait after Waiting strategy servicing a request before heading toward its next customer, or planing a waiting period on a strategic location. This strategy is particularly important in problem with time windows, where lag can appear between the servicing of two requests. Mitrovic-Minic et al. (2004) proved that in all cases it is better to wait after servicing a customer than to drive directly, but that more refined strategy can lead to further improvements in terms of travelled distances and serviced customers. The problem is in general to evaluate the probability of a new request in the neighbourhood of a serviced request, and to plan a waiting period accordingly. It has been implemented in various frameworks for the D-VRP [START_REF] Branke | Waiting' strategies for dynamic vehicle routing[END_REF][START_REF] Thomas | Waiting strategies for anticipating service requests from known customer locations[END_REF] and D-VRPTW [START_REF] Bent | Waiting and relocation strategies in online stochastic vehicle routing[END_REF][START_REF] Branchini | Adaptive granular local search heuristic for a dynamic vehicle routing problem[END_REF][START_REF] Ichoua | Exploiting knowledge about future demands for real-time vehicle dispatching[END_REF][START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF], the D-PDP [START_REF] Ghiani | Anticipatory algorithms for same-day courier dispatching[END_REF], Mitrovic-Minic et al., 2004) or the Resource Allocation Problem (RAP) [START_REF] Godfrey | An adaptive dynamic programming algorithm for dynamic fleet management, i: Single period travel times[END_REF], and have shown to bring significant improvements, especially in the case of a limited fleet facing high new request rate.

In addition to the waiting after or before servicing a client, a vehicle can be moved

Relocating strategies to a strategic location, in the neighborhood of which new requests are likely to arrive. This strategy is the keystone of emergency fleet deployment, also known as Emergency Vehicle Dispatching -or Redeployment -Problem, with for instances the studies by [START_REF] Gendreau | A dynamic model and parallel tabu search heuristic for real-time ambulance relocation[END_REF] and [START_REF] Haghani | Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies[END_REF]. It has also been applied to other vehicle routing problems, such as the D-VRP [START_REF] Larsen | The Dynamic Vehicle Routing Problem[END_REF] and D-VRPTW [START_REF] Bent | Waiting and relocation strategies in online stochastic vehicle routing[END_REF][START_REF] Branchini | Adaptive granular local search heuristic for a dynamic vehicle routing problem[END_REF][START_REF] Ichoua | Exploiting knowledge about future demands for real-time vehicle dispatching[END_REF][START_REF] Van Hentenryck | Online stochastic combinatorial optimization[END_REF], the D-TSPTW [START_REF] Larsen | The a priori dynamic traveling salesman problem with time windows[END_REF], the D-PDP [START_REF] Ghiani | Anticipatory algorithms for same-day courier dispatching[END_REF], or the Resource Allocation Problem (RAP) [START_REF] Godfrey | An adaptive dynamic programming algorithm for dynamic fleet management, i: Single period travel times[END_REF].

Request buffering was introduced by [START_REF] Pureza | Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows[END_REF]. It consists in dif-Request buffering fering the assignment to vehicles of some requests, by storing them in a buffer, allowing more urgent requests to be treated first. It introduces more flexibility in the service guarantee by postponing the assignment decision.

Performance evaluation

In contrast with static problems where measuring the performance of an algorithm is straightforward and consists in comparing running times or results, dynamic contexts require the introduction of new metrics to prove analytical properties or compare empirical results, and assess the performance of a particular method or algorithm.

Conclusions

Recent technological advances provided the tools for companies to manage their fleet in a real-time fashion. Nonetheless, these new technologies also caused a dramatical increase in the complexity of the fleet management tasks, reinforcing the need for decision support systems adapted to dynamic contexts. Consequently, during the last decade the research community have demonstrated a growing interest for the resulting optimization problem, leading to the creation of a new family of approaches specifically designed to efficiently address dynamism and uncertainty. Analyzing the current state of the art, some directions can be drawn for future research in this relatively new field.

Firstly further work should aim at creating a taxonomy of dynamic vehicle routing problem, possibly by extending existing research on static routing [START_REF] Eksioglu | The vehicle routing problem: A taxonomic review[END_REF]. This would allow a more precise classification of approaches, quantify similarities between problems, and foster the development of generic frameworks.

Secondly, there is currently no reference benchmark for dynamic vehicle routing problems, and most papers on the subject use custom made instances that do not allow accurate comparison between methods. There is therefore a strong need for the development and publication of benchmarks for the most common dynamic vehicle routing problems, that could be used to make an objective comparative analysis of the solution frameworks available in the literature.

With the advent of multi-core processors on any desktop computer, parallel computing is now made affordable. Specifically tailored algorithms should be developed making use of this technique to reduce the time needed for optimization and provide decision makers with highly reactive tools.

Our review of the existing literature revealed that approximately the two thirds of the work done in the area of dynamic routing ignored the stochastic nature of the problem. As we have seen, it can be due to the unavailability or irrelevance of stochastic data. However, we sense that developing algorithms that make use of this valuable information would improve the fleet performance and reduce operating costs, and should therefore be a priority.

Finally, researchers have mainly focused on the routing aspect of the dynamic fleet management. However, in some applications there is more that can be done to improve performance and user satisfaction. For instance in equipment maintenance services, the call center has a certain degree of freedom in setting an appointment. In other words, it means that the client time windows can be defined, or influenced, by the service company. As a consequence, a system which on top of giving a yes/no answer to a client request would be able to suggest convenient times for the company would be of higher interest in such contexts.

Figure 1 :

 1 Figure 1: An overview of the Multiple Plan Approach (MPA) framework. Plan generation, reoptimization and selection can be interrupted by incoming events, and are then resumed.

Figure 2 :

 2 Figure 2: Online Stochastic Combinatorial Optimization (OSCO) research overview for the VRP.

Figure 3 :

 3 Figure 3: An overview of the Multiple Scenario Approach (MSA) framework from an event-driven perspective. New events are ordered by priority and treated by the corresponding event handler.Events with continuous border are preemptive and cause the suspension of the handling of any lower priority event.

Figure 4 :

 4 Figure 4: Scenario generation in the Multiple Scenario Approach. The AM, Noon and PM areas represents regions where clients are likely to appear during the corresponding periods of the day.The a-priori optimal tour of step 0. is not actually calculated and would be the result of a myopic optimization.

Table 1 :

 1 Taxonomy of vehicle routing problems by information evolution and quality.

			Deterministic knowledge	Stochastic knowledge
			of input data	of input data
	Information	Input is known beforehand	Static Deterministic	Static Stochastic
	evolution	Input changes over time	Dynamic Deterministic	Dynamic Stochastic

  addressed the real-time Multivehicle Truckload Pickup and Deliv-Rolling horizon ery Problem by introducing two reoptimization strategies: MYOPT and OPTUN. Their studied problem is based on a company with a fleet of K trucks that has to serve point to point transport requests arriving dynamically. Important assumptions are that each truck can only carry one request at a time, with no possible pre-emption, and moves at

the same constant speed. Both reoptimization strategies are based on a Linear Program (LP) that is solved whenever a new request arrives. However, while MYOPT only uses deterministic costs, OPTUN introduces an additional opportunity cost on each of the arcs

  on a Generalized Vehicle Routing Problem (GVRP). The Variable Neighbourhood Search generic algorithm Input: X a valid solution, z an evaluation function and N = {N 1 , .., N K } a set of neighborhood structures Output: X * the best solution found

	Algorithm 1 3: repeat
	4:	k ← 1;		⊲ Select first neighborhood
	5:	repeat
	6: X 9:	X ← X t ;	⊲ Update current solution
	10:		k ← 1;	⊲ Restart from first neighbourhood
	11:	else
	12:		k ← k + 1;	⊲ Go to next neighbourhood
	13:	end if
	14:	if z(X t ) < z(X * ) then	⊲ An improvement has been found
	15:		X * ← X t ;	⊲ Update best solution
	16:	end if
	17:	until k = K;
	18:	until stopCriterion();
	19:	return X * ;
	20: end function
	LNS	Large Neighborhood Search (LNS) was first introduced by Shaw (1998) and can be
	seen as a special case of VNS

1: function VNS(X) 2: X * ← X; t ← shake(N k , X); ⊲ Generate a neighbour from neighbourhood N k 7: X t ← ls(X t ); ⊲ Local search to improve X t 8:

if accept(X t , X) then ⊲ X t is accepted as current solution

Therefore LNS can be interpreted as a special case of VNS, considering that each cardinality defines a neighborhood.

The distinguished plan is not necessarily the best plan of the pool[START_REF] Bent | Scenariobased planning for partially dynamic vehicle routing with stochastic customers[END_REF]

url: http://www.fernuni-hagen.de/WINF/inhalte/benchmark_data.htm

Acknowledgements

Financial support for this work was provided by the Region Pays de la Loire (France) and the Centro de Estudios Interdisciplinarios Básicos y Aplicados en Complejidad (CeiBA, Colombia). This support is gratefully acknowledged.

 [START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF]were the first to introduce a now commonly used metric, Competitive ratio at least as far as theoretical performance is concerned: the competitive analysis (Jaillet andWagner, 2008, Larsen et al., 2007). Consider a minimization problem P and I the corresponding set of possible instances. Let z * (I of ) be the optimal cost for the offline instance I of corresponding to I ∈ I. By offline instance we mean that in I of all the input data from instance I, either static or dynamic, is available when building the solution.

In contrast, the data of the online version is revealed in a real-time fashion, thus an algorithm A has to take into account new information on-the-go, and produce a solution relevant to the current state of knowledge. Let z A (I) = z(x A (I)) be the cost of the final solution x A (I) found by the on-line algorithm A. Algorithm A is said to be c-competitive, or equivalently to have a competitive ratio of c, if there is a constant α such that

In the case where α = 0, the algorithm is said to be strictly-c-competitive, meaning that in all cases the objective value of the solution found by A will be at most of c times the optimal value. The competitive ratio metric allows a worst-case absolute measure of an algorithm performance in terms of objective value. We refer the reader to [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF] for an in-depth analysis of this measure.

The main drawback of the competitive analysis is that it requires to prove the pre-Value of information viously stated inequality for all instances of a given problem, which can reveal to be a complex task for real-world applications. The value of information proposed by Mitrovic-Minic and Laporte ( 2004) constitutes a more flexible metric. We will denote by z A (I of ) the value of the objective function returned by algorithm A for the offline instance I of .

The value of information V A for algorithm A and instance I is then defined as

Therefore the value of information can be interpreted as the gap between the solution returned by an algorithm A on a instance I and the solution returned by the same algorithm when all information from I is known beforehand.

In contrast with the competitive ratio, the value of information gives information on the performance of an algorithm based on empirical experience, without requiring optimal solutions for the offline instances. It captures the impact of the dynamism on the solution yield by the considered algorithm.

Benchmarks

To the best of our knowledge, there is presently no reference benchmark for dynamic routing problems. It appears that a great proportion of authors create their own instances to test their algorithms. It is worth noting though that various have based their benchmarks on the one designed by [START_REF] Solomon | Algorithms for the vehiclerouting and scheduling problems with time window constraints[END_REF] for static routing (Bent and Van Hentenryck, 2004a,b, Chen et al., 2006[START_REF] Chen | Dynamic column generation for dynamic vehicle routing with time windows[END_REF][START_REF] Gendreau | Parallel tabu search for real-time vehicle routing and dispatching[END_REF]. A description of how the original benchmark can be adapted is given in Van Hentenryck and Bent (2006, Chap. 10).

The interested reader is referred to the web page of Dr. G. Pankratz and V. Krypczyk 3 for an updated list of publicly available instances sets for dynamic vehicle routing problems.