1. Introduction
Due to its practical applications, the VRP is one of the most popular combinatorial optimization problems in the operations research, computer science, and industrial engineering communities [1]. In a nutshell, the basic version of the VRP can be described as follows: A fleet of vehicles, each of them with a limited capacity, is employed to serve a set of customers’ demands; initially, all vehicles are located at a central depot, and there is a cost associated with traveling from one node (customer or depot) to another; hence, the traditional goal is to find the solution that services all customers while minimizing the total traveling cost without exceeding the capacity of the vehicles. From this basic version of the VRP, a huge number of variants have been introduced in the scientific literature in order to consider richer and more realistic scenarios [2,3], stochastic scenarios [4], dynamic scenarios [5], environmental criteria [6], synchronization issues [7], multi-objective scenarios [8], scenarios involving electric fleets [9], scenarios in which decisions are made over time [10], etc. In this paper, we focus mainly on VRPs under uncertainty and in dynamic scenarios, which also include synchronization issues and the need for providing solutions in real time, since these variants have increasing relevance in the context of smart cities, inter-connected vehicles, electric vehicles, and self-driving vehicles. In addition, this article is biased towards large-scale scenarios (with hundreds or even thousands of nodes), which are frequent in many real-life applications. For this reason, most of the solving approaches discussed here are based on approximated (heuristic or meta-heuristic) methods and do not consider exact approaches, despite their indubitable theoretical and practical relevance.
Using the Scopus scientific database, we searched for articles containing the terms “(vehicle routing problem) AND (uncertainty OR stochastic)” in the title, abstract, or keywords. A total of 1025 document results were obtained. Similarly, we searched for articles with the terms “(vehicle routing problem) AND dynamic”, obtaining a total of 1195 documents. Figure 1 shows the time evolution of both the VRP in uncertainty/stochastic scenarios and the VRP in dynamic scenarios. One should notice that despite some seminal works appearing during the 1980s, it was not until the mid-2000s that the interest in both versions of the VRP started to rise in a noticeable way. We can also observe that both versions are currently receiving a similar amount of interest from the scientific community.
Figure 2 displays the main journals that published articles on the VRP under uncertainty/stochastic or dynamic scenarios. Notice that the journals with a larger number of publications on these two topics were the European Journal of Operational Research, Transportation Science, Computers, and Operations Research, Computers and Industrial Engineering, Transportation Research Part E, Operations Research, Experts Systems with Applications, Networks, Annals of Operations Research, and Transportation Research Part B. In addition, some other journals published articles covering either VRPs under uncertainty or VRPs under dynamic conditions. The researchers in these articles explored and investigated different approaches ranging from exact algorithms to advanced techniques to handle uncertainty and dynamic scenarios. For example, Hu et al. [11] developed an algorithm based on a modified adaptive variable neighborhood search heuristic to tackle the demand and travel time uncertainty, and Pessoa et al. [12] utilized the branch-cut-and-price algorithm to solve the capacitated VRP. In addition, approaches to solving newly defined variants of the VRP were introduced, such as Yu et al. [13], who studied the heterogeneous fleet green VRP with time windows, and Lee [14], who considered nonlinear charging time in the electric vehicle routing problem. This paper reviews some of these works and the solution approaches for handling uncertainty or dynamic scenarios in VRPs.
The remainder of this paper is structured as follows: Section 2 offers a short overview of trending topics on VRPs, which include rich and real-life versions of the problem that consider the sustainability and social dimensions. Section 3 provides a review on the use of simulation–optimization approaches—and simheuritics in particular—to solve VRPs in uncertain scenarios. Similarly, Section 4 analyzes VRPs in dynamic scenarios and several approaches that can be used to deal with these. Among these approaches, the combination of machine learning methods with heuristics is considered. Section 5 performs a similar study, this time focusing on VRPs with synchronization issues and time-dependent events. Section 6 introduces the concept of agile optimization in the context of VRPs that need to be solved in real time, mainly in the context of self-driving vehicles in smart cities, where new data are continuously provided by Internet of Things (IoT) devices. Finally, Section 7 highlights the main conclusions of this work.
2. Recent Trends in VRPs
Knowing the importance of the VRP in the real world as it was depicted in the Introduction section, it is possible to highlight a long list of recent applications of routing models in many practical arenas. Some of the practical contributions of the VRP were historically presented by Laporte [15] and, more recently, by Caceres-Cruz et al. [2]; this last reference envisioned the would-be VRP applications and models for the following years. In a parallel way, Lin et al. [16] presented the green vehicle routing problem as a rich new paradigm that presented new challenges for supply chain management and transportation. Later, the general overview written by Braekers et al. [17] highlighted the importance of dynamic models in uncertain scenarios as the key problem for transportation and distribution problems in the near future. Furthermore, Rios et al. [18] offered a detailed description of the current taxonomy of dynamic VRPs and their relationship with applied problems in the real world. Apart from the previous dynamic scenarios, the novel paradigm of urban mobility based on non-internal-combustion vehicles (mainly electric vehicles) has suggested the need for the design of dynamic VRP models adapted to city logistics [19]. Hence, we can currently consider the following great topics as critical in the design and use of dynamic VRP models:
Minimization of pollutant emissions: The problem of minimizing pollutant emissions in routing, which is included in the green vehicle routing problem, was profiled in the period of 2005–2010. Even though the complete analysis is still in progress, this represents an essential challenge in current mobility paradigms [20]. This topic lies on the basis of the three typical sustainability dimensions of the VRP—the economic, environmental, and social dimensions—which are now omnipresent in the transportation and routing literature [21]. Usually, the environmental and social dimensions are considered key externalities associated with transportation [22].
Consideration of social issues related to transportation: In the last decade, the social externalities due to transportation—e.g., congestion, pollutant emissions, noise, infrastructure wearing, etc.—have been revealed as critical in the way of designing sustainable modes of mobility [21,22,23]. These traits also assume a very dynamic behavior in mobility problems, which should be contemplated in VRP modeling.
Greater importance of the urban scenarios: Knowing the importance of the previously mentioned sustainability dimensions, in recent years, it has become clear that the urban arena is the key location in which those dimensions present their critical facets [24]. Urban mobility problems need the support of agile procedures more and more [25].
Increase in scenarios based on accidents and catastrophes: Due to the higher demand for transportation and mobility, along with an increase in requests for logistic support in disaster scenarios [26], the quicker responses and solutions have been revealed as essential [27].
Greater importance of energetic objectives and constraints in the transportation programs: It is clear that most of the new challenges that transportation is going to face are going to be related to energy, not only for the use of more sustainable means of mobility, but also for the need to optimize consumption and production [28].
Necessity of collaboration as a way of facing complex distribution processes: Collaborative and cooperative approaches are becoming quite common in goods and merchandise distribution [29]. They allow for good performance in the sustainability dimensions, as presented by Muñoz-Villamizar et al. [30]. Finally, the dynamic VRP was contemplated by Basso et al. [31].
Greater occurrence of disruptions in urban and interurban mobility processes: This type of mobility incident is becoming extraordinarily common in real transportation, and there is a demand for quick answers, which represents the basis of the concept of ‘agile optimization’ [25].
Therefore, the popularity of these emerging VRP paradigms—which involve more uncertainty, more complexity, and quicker decisions—has spurred a thorough study of dynamic routing problems.
3. VRPs under Uncertainty
Real-life VRPs involve demand, travel distance, or time uncertainty. This uncertainty could be of a stochastic or fuzzy nature. Thus, the traditional heuristics that solve deterministic VRPs cannot be used to solve the uncertain versions of these problems. Uncertainty requires other components in the solution approach, such as simulations. Simulations can be used to evaluate different systems, including those of vehicle routing under stochastic conditions, but they cannot be used to solve problems. To overcome this challenge, researchers have combined simulation and optimization methods [32]. For example, Galvan et al. [33] combined evolutionary particle swarm optimization and Monte Carlo simulation (MCS) to find a solution to a VRP. The optimization method could be metaheuristics, mathematical programming, or machine learning. Accordingly, several simulation–optimization approaches could be identified based on the utilized optimization method and the function of the simulation in the hybridized approach. For more details on these approaches, the reader is directed to Figueira and Almada-Lobo [34]. One simulation–optimization approach integrates a metaheuristic algorithm and a simulation. This integration is called simheuristics, and it has become a popular approach among researchers for solving stochastic problems [35]. According to Figueira and Almada-Lobo [34], the metaheuristic algorithm generates solutions that are evaluated by using a simulation in simheuristics. Thus, the simulation in this hybridization approach assigns values to each solution with respect to the objective function(s). This approach could be considered as a “first resource” methodology when handling NP-hard problems and large-scale instances under stochastic uncertainty.
Figure 3 demonstrates the flow of a simheuristic approach. First, a deterministic version of the considered problem is defined. This definition might be achieved by replacing the stochastic random variables with their estimated values, e.g., means. Then, the metaheuristic algorithm generates solutions for the deterministic version of the problem. If the generated deterministic solution is promising, it is examined with a small number of simulations run under stochastic conditions. This process of generating and evaluating solutions continues until a pre-specified time has elapsed or a number of iterations has been reached. At this stage, an elite list of solutions is defined. These solutions are further examined with a more intense simulation process and a larger number of simulation runs in order to rank them.
Researchers have utilized different simulation approaches that have integrated into simheuristics, such as MCS and Petri nets. Calvet et al. [36] used MCS integrated into a metaheuristic algorithm to solve a multi-depot VRP. Another example of simheuristic utilization is found in the work of Guimarans et al. [37]. These authors considered two-dimensional VRPs. This type of problem appears in real-world cases when transported items cannot be stacked on top of each other. Guimarans et al. [37] integrated MCS into an iterated local search framework. Their problem considered stochastic travel times, and it triggered the integration of a simulation into their solution approach. [38] proposed an intertwined protocol for integrating Petri nets into simheuristics to solve stochastic VRPs with the correlated demand. It was noticed that simulations integrated into metaheuristic algorithms have formed solution approaches for different versions of VRPs.
In addition, electric vehicles have been considered in VRPs, and this combination constitutes a new class of problems. These problems raise additional constraints related to the limited driving range, making the resolution even more challenging. Hence, Reyes-Rubiano et al. [39] solved a version of this problem with stochastic travel times. They used MCS and a multi-start approach. In their approach, biased randomization techniques were utilized to generate solutions in every re-start of a heuristic.
The vehicle routing problem finds its applications in different real-world problems. For example, Gruler et al. [40] formulated a waste collection problem as a multi-depot VRP. They used a simheuristic approach to solve the stochastic demand version of the problem. The solution approach was based on a variable neighborhood search framework with a simulation. A similar application was considered by Yazdani et al. [41] in Sydney (Australia). Gruler et al. [42] solved a single-period inventory routing problem with stochastic demands, Their solution approach was based on simheuristics. In another extension of the VRP, Raba et al. [43] studied agri-food supply chains with stochastic demands. They proposed solution approaches for solving a real-world case. In a similar work, Onggo et al. [44] addressed this problem by using benchmark instances, which included perishable products.
The uncertainty in real-world problems is not limited to being of a stochastic nature. Fuzzy uncertainty is encountered in different aspects of problems as either demand or travel time. Thus, this uncertainty was considered by Tordecilla et al. [45]. They extended the concept of simheuristics by adding a fuzzy component to the simheuristic approach so that it could include non-stochastic uncertainty while solving VRPs.
4. VRPs in Dynamic Environments
In real life, there are plenty of unpredictable factors. In these cases, making decisions is not trivial, since every choice needs to be based on partially unknown aspects. A typical unpredictable factor that concerns the VRP is the travel time. As a matter of fact, even though it is usual to consider static traveling times, they may actually be affected by several factors, such as traffic jams, accidents, road work, or weather conditions. Other aspects that are hard to predict may be customers’ demands or the cost of a delivery delay in the case of VRPs with time windows. As previously discussed, solving VRPs under such dynamic factors may be difficult. Even predicting the actual quality of a given solution is not easy. Fortunately, machine learning (ML) methods can help us to develop predictive models [46]. In addition, with the support of new hardware solutions [47], once trained, most machine learning models can be executed on multiple small processors, providing a response in milliseconds. This allows for their integration with heuristics, thus bringing up the concept of learnheuristics [48]. Learnheuristics refer to the combination of metaheuristics with machine learning methods. This approach is proposed to solve combinatorial optimization problems in dynamic scenarios. Dynamic scenarios are defined by elements in the objective function or constraints. These elements might change while the solution is being constructed (they cannot be fixed in advance). For example, customers’ demands might change depending on the vehicle arrival time or a pre-specified time window; thus, the demand could depend on the constructed solution, which would involve the vehicle type, number of customers that have visited, vehicle travel time, etc. Another dynamic element might be the travel time, which is affected by traffic jams; thus, it is affected by the definition of the route in a solution, especially for routes in big cities. Accordingly, the solution approach should facilitate updates of the input models used by the metaheuristic algorithm at each iteration; this solution approach can coordinate learning mechanisms that update the input models and metaheuristics (Figure 4).
A learnheuristic-based approach was proposed by Arnau et al. [49] to solve the VRP in dynamic scenarios. In their problem, they considered a dynamic travel time that depended on the routing plan. Thus, the travel times changed and were updated while the solution was being constructed. In another work, Calvet et al. [50] studied a multi-depot VRP with heterogeneous depots in terms of their commercial offers. Customers’ demands and willingness to consume depended on whether the depot assignment fit their preferences or not. Accordingly, the solution approach should consider market-segmentation strategies and distribution costs; considering market-segmentation strategies increases sales and, hence, the total income. In the proposed learnheuristic algorithm, the customer demand was estimated based on the assigned depot. The objective function was enriched by the estimated customer expenditures. This enrichment guided a local search in the utilized metaheuristics. Similarly, Bayliss et al. [51] proposed a learnheuristic approach to solving an aerial drone surveillance problem. In the aerial drone surveillance problem, the aerial drones collected rewards by gathering information and observing a set of targets during a specified time. This collected reward was to be maximized by the objective function. The travel time between the targets was dynamic and was influenced by several factors. For example, the angle of ascent and air resistance affected the drone’s acceleration, and sharp turns decreased the drone’s speed. Hence, the prediction of travel times was outsourced to a machine learning algorithm.
5. VRPs with Synchronization Issues
Modern transportation systems are not only of a large scale, but are also characterized by a high level of dynamism—i.e., unexpected events may occur at any time, thus requiring a change in the schedule or routing—and synchronization—i.e., the observable and quantifiable phenomenon resulting from direct or indirect interactions between system elements or processes [52]. Exact approaches, as well as classic heuristics and meta-heuristics, are not usually designed for such dynamic scenarios. On the other hand, discrete-event heuristics (DEH) combine a fast heuristic algorithm with a discrete-event simulation [53]. As represented in Figure 5, while the heuristic is responsible for making decisions, the simulation updates the state of the system event by event in order to evaluate how the decisions made by the heuristic affect the overall system with all of its parallelisms, dynamism, and synchronization. In this way, every decision can be made by considering the exact state of the system at that time. A DEH is also more flexible and relatively easy to maintain, since a change in the system can usually be tackled with a slight change in the simulation component without affecting the heuristic. Furthermore, the simulation and heuristic components shown in Figure 5 might be intended as two distinct elements, which would allow us to implement them in two different workstations or endpoints. In this way, the same simulation may be used by different heuristics.
A typical set of problems in which DEHs might be beneficial are multi-tier vehicle routing problems and multi-vehicle routing problems, where different types of vehicles contribute to shipments. Belonging to this category are all multimodal supply chain scenarios [54], where a shipment might involve different transportation modes, such as planes, trains, ships, cargo ships, trucks, and vans. Bredström and Rönnqvist [55] might be considered some of the pioneers, since they first highlighted the need for combining heuristics with simulations. In greater detail, they approached the VRP with time windows and synchronized visits (VRPTWSyn) when applied to home healthcare services for elders. In their model, it might be necessary for more than one staff member to be present simultaneously or in a given order. They emphasized the importance of temporal synchronization and precedence constraints by suggesting a mixed integer programming formulation of the problem and employing a heuristic approach. However, in the concluding remarks, they mentioned the need for a more efficient model for larger instances. Years later, Afifi et al. [56] proposed a new approach based on simulated annealing with dedicated local searches for solving the VRPTWSyn. They tested it on instances from Bredström and Rönnqvist [55], showing that, in some cases, their solution was able to improve the best-known solutions.
Two further applications that might benefit from these solutions that are capable of dealing with high dynamism and synchronization are car-sharing and ride-sharing operations [57,58]. Car-sharing and ride-sharing are rapidly spreading, especially in big cities, and they are becoming part of our everyday life. Nowadays, customers require increasingly efficient service with fewer waits and delays. Both problems are marked by a rigid time dependency, the necessity of synchronizing the involved agents, and unexpected occurrences that arrive once the solution has already been computed—e.g., a driver that receives an unexpected request for a ride when they are already on their way. A solution that is able to consider all of these aspects was recently proposed by Fikar et al. [59], whose algorithm dealt with dynamic routing and scheduling scenarios and used combined trip sharing and walking.
A recently born and futuristic scenario is also that considered, for instance, by Boysen et al. [60], Das et al. [61], and Yetis and Karakose [62], where a last-mile delivery was fulfilled through collaborative truck–drone routing optimization. In this case, trucks were designed to transport both products and drones, and, along their paths, they were allowed to release drones and rejoin them afterward in a different location. This currently hard-to-implement scenario could speed up the delivery process and sidestep the short battery life in drones at the same time. Another solution belonging to the same research stream is that proposed by Deng et al. [63], where the authors tried to find the optimal route for a set of delivery vans with drones or sidewalk robots, i.e., in a system in which there was an independent vehicle that could move on its own and a special vehicle that assisted it. A similar problem was tackled by Grangier et al. [64], who approached the two-echelon VRP (2E-VRP)—i.e., two distinct fleets of vehicles were used to carry out deliveries—by considering time windows and synchronization constraints as well. The authors approached the problem by means of an adaptive large neighborhood search (ALNS) and found good solutions in a reasonable time.
Another interesting scenario characterized by high synchronization and dynamism was that faced by Arnau et al. [65], who analyzed a realistic and novel VRP variant. Their problem considered container transportation throughout a spoke–hub network. These containers were to be relocated from their original location to their destination, and the relocation of the containers was to be performed before a pre-specified deadline. The containers could be transported by different trucks and could be temporarily stored in network hubs before being delivered to their destinations. A truck could transport only one container at a time, and truck drivers were to return to their starting point by the given time. To solve this problem, a DEH was proposed to address the intrinsic dynamism of this time-evolving system.
Finally, as proved by Hashemi Doulabi et al. [66], healthcare applications may also benefit from algorithms that are able to deal with synchronization issues. In this case, the authors studied a VRP with synchronized visits and stochastic travel and service times, which was formulated as two-stage stochastic integer programming, and they applied the L-shaped algorithm and its branch-and-cut implementation to solve the problem. In addition, an operating room scheduling problem with stochastic durations was formulated and solved.
6. VRPs under Real-Time Constraints
At this point, we have seen how taking factors such as uncertainty (simheuristics), integration with ML models (learnheuristics), and synchronization issues (discrete-event heuristics) into account is crucial in dynamic systems. The next category aims to cover real-time constraints. Nowadays, we count on many devices and technologies that can provide data, such as current fleet locations, new customer requests, or the state of the traffic, which are useful for performing real-time decisions. The main applications for VRPs with these constraints are dynamic fleet management (real-time dispatching of vehicles), vendor-managed distribution systems (replenishing inventory to avoid stock-out), couriers (collecting parcels and sending them), rescue and repair service companies, dial-a-ride systems (services for transporting people between two nodes), emergency services (relocating idle vehicles, optimizing routes), and taxi cab services [67].
When it comes to VRPs with real-time constraints, some of the approaches in the literature can be summarized as shown in Table 1.
As can be concluded from Table 1, the most common real-time constraint is that related to customer requests, although variations in travel times are also tackled, but with less frequency. On the other hand, the methodologies used to solve these problems are various, but all of them agree on the most critical point: It is necessary for the implemented solution to be extremely fast and effective. The family of agile optimization (AO) algorithms [75] is a good choice for real-time decision making, since they are able to obtain extremely fast execution times. The main idea behind these algorithms is the parallelization of heuristics that are usually easy to implement, randomized, and count with a small number of parameters, thus easing the parameter fine-tuning process. The effectiveness of these algorithms has been shown in the literature, as they are able to provide quality solutions to complex problems of different natures, including large-scale dynamic or uncertain conditions that are present in the real world, such as those involving traffic, vehicle location, unexpected demands, disruptions, etc. Work regarding AO includes Martins et al. [25], where a fleet of homogeneous vehicles had to satisfy customers’ demands in a two-echelon network. This paper extended a constructive heuristic to a biased–randomized algorithm with parallelized runs. It was shown that this approach could improve upon the original version by about without increasing the required wall clock time. In Li et al. [76], the authors tackled the integration of IoT analytics into AO problems. By employing an AO biased–randomized heuristic, the goal was to solve a waste collection problem, which was modeled as a dynamic team orienteering problem with mandatory visits. It was shown that this approach outperformed the solutions provided by its original version. Similarly, Peyman et al. [77] provided a comprehensive review of the state of the art of the Internet of Things in intelligent transportation systems (ITSs). In this context, challenges were identified for cloud computing, fog computing, and edge computing. An AO-based methodology was introduced and used to solve a case study regarding the dynamic ride-sharing problem (DRSP) to illustrate these concepts. Their results outperformed those of traditional methods in terms of costs with instances of different sizes. Martins et al. [75] proposed an agile optimization algorithm to solve the uncapacitated facility location problem (UFLP), where the mapping of vehicles to roadside units (RSUs) needed to be re-optimized periodically over time while taking matters such as energy consumption of the RSUs, the service capabilities, and the required quality of service into account. Figure 6 presents the main idea behind the AO framework, in which n concurrent executions of a biased–randomized heuristic are run in parallel. The first execution, in which , refers to the deterministic heuristic. The remaining ones are smoothed by applying . In the end, the best solution among those that were simultaneously generated is found and returned.
7. Conclusions
In this paper, we discussed different general strategies for solving vehicle routing problems in dynamic and uncertain scenarios, as well as those in which real-time solutions are required. In connection with these scenarios, this paper also identifies some of the emerging topics in the area of VRPs, among which we can mention the following: the minimization of pollutant emissions and energy consumption, the inclusion of the social dimension in the design of routes, a focus on urban and peri-urban scenarios, the need for providing quick answers to catastrophic events and accidents, horizontal cooperation, and disruption management in vehicle routing plans.
Regarding VRPs under uncertainty, we discussed the concept of the simheuristic and how it has been already employed to solve different VRP variants with stochastic demands and/or stochastic random times. Extensions of this concept to include fuzzy uncertainty were also commented on. One of the main characteristics of these simheuristic algorithms is the flexibility that they offer when modeling random elements; because they are based on a simulation, any best-fit probability distribution can be utilized. Regarding VRPs under dynamic conditions, we analyzed the concept of learnheuristics and their application to VRPs with dynamic elements. In these scenarios, the incorporation of machine learning models into a metaheuristic can constitute a necessary step in order to successfully predict the evolution of dynamic inputs, such as travel times or penalty costs associated with the violation of a soft constraint. In relation to VRPs with synchronization issues and time dependencies, this paper commented on the concept of discrete-event heuristics. These special heuristics include a list of discrete events that are traversed in a similar way to that in any discrete-event simulation. As each new event is realized, a biased-randomized heuristic can make a rational decision, thus activating new events that are properly scheduled for the future and included in the list. This original strategy has started to provide relevant results for different VRPs in which the synchronization of agents has to be considered. Likewise, we have discussed the need for agile optimization algorithms, which must be capable of providing real-time solutions of good quality for complex and large-scale VRP instances.
As future research lines, it is natural to consider combinations of these families of algorithms to cope with more complex scenarios that combine uncertainty, dynamic, and real-time conditions. Hence, it seems relatively easy to integrate learnheuristics with simheuristics and simheuristics with discrete-event heuristics. Notice, however, that agile optimization algorithms are a little bit different due to the real-time requirement. Having said that, however, one can notice that agile algorithms for VRPs are also intrinsically related to scenarios under dynamic conditions; thus, they can significantly benefit from their combination with machine learning predictive models.
Conceptualization, A.A.J. and J.F.; methodology, A.A.J. and M.A.; investigation, E.M.H. and M.N.; writing—original draft preparation, E.M.H., M.A. and M.N.; writing—review and editing, A.A.J. and J.F. All authors have read and agreed to the published version of the manuscript.
Not applicable.
Not applicable.
Not applicable.
The authors declare no conflict of interest.
Footnotes
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
Enlarge this image.Figure 1. Evolution of Scopus-indexed papers on VRPs with uncertainty or dynamic conditions.
Enlarge this image.Figure 2. List of journals that published articles on VRPs under uncertainty or in dynamic scenarios.
Approaches to solving VRPs with real-time constraints in the literature.
| Article | Problem | Real-Time Consideration | Objective | Approach |
|---|---|---|---|---|
| Haghani and Jung [ |
Pick-up or delivery |
Real-time service requests |
To minimize the total |
Genetic Algorithm. |
| Hong [ |
Dynamic VRP with hard |
Real-time service requests. | To minimize the travel |
Large |
| Chen et al. [ |
Real-time time-dependent |
Real-time travel times and |
To determine optimal routes |
Heuristic. |
| Ferrucci et al. [ |
Dynamic VRP with soft |
Real-time service requests. | To minimize the total |
Tabu Search. |
| Barkaoui and Gendreau [ |
Dynamic VRP with time |
Real-time service requests. | To minimize the number |
Evolutionary |
| Azi et al. [ |
Dynamic VRP with time |
Real-time service requests. | To maximize the total |
Adaptive Large |
| Cardoso et al. [ |
Capacitated VRP with |
Real-time service requests. | To minimize the number |
Heuristic. |
References
1. Toth, P.; Vigo, D. Vehicle Routing: Problems, Methods, and Applications; SIAM: Philadelphia, PA, USA, 2014.
2. Caceres-Cruz, J.; Arias, P.; Guimarans, D.; Riera, D.; Juan, A.A. Rich vehicle routing problem: Survey. ACM Comput. Surv. (CSUR); 2014; 47, pp. 1-28. [DOI: https://dx.doi.org/10.1145/2666003]
3. Lahyani, R.; Khemakhem, M.; Semet, F. Rich vehicle routing problems: From a taxonomy to a definition. Eur. J. Oper. Res.; 2015; 241, pp. 1-14. [DOI: https://dx.doi.org/10.1016/j.ejor.2014.07.048]
4. Oyola, J.; Arntzen, H.; Woodruff, D.L. The stochastic vehicle routing problem, a literature review, part I: Models. EURO J. Transp. Logist.; 2018; 7, pp. 193-221. [DOI: https://dx.doi.org/10.1007/s13676-016-0100-5]
5. Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A.L. A review of dynamic vehicle routing problems. Eur. J. Oper. Res.; 2013; 225, pp. 1-11. [DOI: https://dx.doi.org/10.1016/j.ejor.2012.08.015]
6. Asghari, M.; Al-e, S.M.J.M. Green vehicle routing problem: A state-of-the-art review. Int. J. Prod. Econ.; 2021; 231, 107899. [DOI: https://dx.doi.org/10.1016/j.ijpe.2020.107899]
7. Drexl, M. Synchronization in vehicle routing—A survey of VRPs with multiple synchronization constraints. Transp. Sci.; 2012; 46, pp. 297-316. [DOI: https://dx.doi.org/10.1287/trsc.1110.0400]
8. Jozefowiez, N.; Semet, F.; Talbi, E.G. Multi-objective vehicle routing problems. Eur. J. Oper. Res.; 2008; 189, pp. 293-309. [DOI: https://dx.doi.org/10.1016/j.ejor.2007.05.055]
9. Kucukoglu, I.; Dewil, R.; Cattrysse, D. The electric vehicle routing problem and its variations: A literature review. Comput. Ind. Eng.; 2021; 161, 107650. [DOI: https://dx.doi.org/10.1016/j.cie.2021.107650]
10. Mor, A.; Speranza, M.G. Vehicle routing problems over time: A survey. Ann. Oper. Res.; 2022; 314, pp. 255-275. [DOI: https://dx.doi.org/10.1007/s10479-021-04488-0]
11. Hu, C.; Lu, J.; Liu, X.; Zhang, G. Robust vehicle routing problem with hard time windows under demand and travel time uncertainty. Comput. Oper. Res.; 2018; 94, pp. 139-153. [DOI: https://dx.doi.org/10.1016/j.cor.2018.02.006]
12. Pessoa, A.A.; Poss, M.; Sadykov, R.; Vanderbeck, F. Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty. Oper. Res.; 2021; 69, pp. 739-754. [DOI: https://dx.doi.org/10.1287/opre.2020.2035]
13. Yu, Y.; Wang, S.; Wang, J.; Huang, M. A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows. Transp. Res. Part B Methodol.; 2019; 122, pp. 511-527. [DOI: https://dx.doi.org/10.1016/j.trb.2019.03.009]
14. Lee, C. An exact algorithm for the electric-vehicle routing problem with nonlinear charging time. J. Oper. Res. Soc.; 2021; 72, pp. 1461-1485. [DOI: https://dx.doi.org/10.1080/01605682.2020.1730250]
15. Laporte, G. Fifty years of vehicle routing. Transp. Sci.; 2009; 43, pp. 408-416. [DOI: https://dx.doi.org/10.1287/trsc.1090.0301]
16. Lin, C.; Choy, K.L.; Ho, G.T.; Chung, S.H.; Lam, H. Survey of green vehicle routing problem: Past and future trends. Expert Syst. Appl.; 2014; 41, pp. 1118-1138. [DOI: https://dx.doi.org/10.1016/j.eswa.2013.07.107]
17. Braekers, K.; Ramaekers, K.; Van Nieuwenhuyse, I. The vehicle routing problem: State of the art classification and review. Comput. Ind. Eng.; 2016; 99, pp. 300-313. [DOI: https://dx.doi.org/10.1016/j.cie.2015.12.007]
18. Rios, B.H.O.; Xavier, E.C.; Miyazawa, F.K.; Amorim, P.; Curcio, E.; Santos, M.J. Recent dynamic vehicle routing problems: A survey. Comput. Ind. Eng.; 2021; 160, 107604. [DOI: https://dx.doi.org/10.1016/j.cie.2021.107604]
19. Fontaine, P.; Minner, S.; Schiffer, M. Smart and Sustainable City Logistics: Design, Consolidation, and Regulation. Eur. J. Oper. Res.; 2022; in press [DOI: https://dx.doi.org/10.1016/j.ejor.2022.09.022]
20. Figliozzi, M.; Saenz, J.; Faulin, J. Minimization of urban freight distribution lifecycle CO2e emissions: Results from an optimization model and a real-world case study. Transp. Policy; 2020; 86, pp. 60-68. [DOI: https://dx.doi.org/10.1016/j.tranpol.2018.06.010]
21. Abdullahi, H.; Reyes-Rubiano, L.; Ouelhadj, D.; Faulin, J.; Juan, A.A. Modelling and multi-criteria analysis of the sustainability dimensions for the green vehicle routing problem. Eur. J. Oper. Res.; 2021; 292, pp. 143-154. [DOI: https://dx.doi.org/10.1016/j.ejor.2020.10.028]
22. Sánchez-García, M.; Zouaghi, F.; Lera-López, F.; Faulin, J. An extended behavior model for explaining the willingness to pay to reduce the air pollution in road transportation. J. Clean. Prod.; 2021; 314, 128134. [DOI: https://dx.doi.org/10.1016/j.jclepro.2021.128134]
23. Lera-López, F.; Sánchez, M.; Faulin, J.; Cacciolatti, L. Rural environment stakeholders and policy making: Willingness to pay to reduce road transportation pollution impact in the Western Pyrenees. Transp. Res. Part D Transp. Environ.; 2014; 32, pp. 129-142. [DOI: https://dx.doi.org/10.1016/j.trd.2014.07.003]
24. Faulin, J.; Grasman, S.E.; Juan, A.A.; Hirsch, P. Sustainable transportation: Concepts and current practices. Sustainable Transportation and Smart Logistics; Elsevier: Amsterdam, The Netherlands, 2019; pp. 3-23.
25. Martins, L.d.C.; Hirsch, P.; Juan, A.A. Agile optimization of a two-echelon vehicle routing problem with pickup and delivery. Int. Trans. Oper. Res.; 2021; 28, pp. 201-221. [DOI: https://dx.doi.org/10.1111/itor.12796]
26. Zhang, M.; Wang, N.; He, Z.; Jiang, B. Vehicle routing optimization for hazmat shipments considering catastrophe avoidance and failed edges. Transp. Res. Part E Logist. Transp. Rev.; 2021; 150, 102337. [DOI: https://dx.doi.org/10.1016/j.tre.2021.102337]
27. Reyes-Rubiano, L.; Voegl, J.; Rest, K.D.; Faulin, J.; Hirsch, P. Exploration of a disrupted road network after a disaster with an online routing algorithm. Spectrum; 2021; 43, pp. 289-326. [DOI: https://dx.doi.org/10.1007/s00291-020-00613-w]
28. Ghorbanioskalaei, E.; Herrera, E.M.; Ammouriova, M.; Juan, A.A. On the Use of Agile Optimization for Efficient Energy Consumption in Smart Cities’s Transportation and Mobility. Future Transp.; 2022; 2, pp. 868-885. [DOI: https://dx.doi.org/10.3390/futuretransp2040048]
29. Serrano-Hernandez, A.; Juan, A.A.; Faulin, J.; Perez-Bernabeu, E. Horizontal collaboration in freight transport: Concepts, benefits and environmental challenges. Sort; 2017; 1, pp. 393-414.
30. Muñoz-Villamizar, A.; Quintero-Araújo, C.L.; Montoya-Torres, J.R.; Faulin, J. Short-and mid-term evaluation of the use of electric vehicles in urban freight transport collaborative networks: A case study. Int. J. Logist. Res. Appl.; 2019; 22, pp. 229-252. [DOI: https://dx.doi.org/10.1080/13675567.2018.1513467]
31. Basso, F.; D’Amours, S.; Rönnqvist, M.; Weintraub, A. A survey on obstacles and difficulties of practical implementation of horizontal collaboration in logistics. Int. Trans. Oper. Res.; 2019; 26, pp. 775-793. [DOI: https://dx.doi.org/10.1111/itor.12577]
32. Amaran, S.; Sahinidis, N.V.; Sharda, B.; Bury, S.J. Simulation optimization: A review of algorithms and applications. Ann. Oper. Res.; 2016; 240, pp. 351-380. [DOI: https://dx.doi.org/10.1007/s10479-015-2019-x]
33. Galvan, S.; Arias, J.; Lamos, H. A Simulation-Optimization Approach Based on EPSO for the Vehicle Routing Problem with Stochastic Demands. DYNA; 2013; 80, pp. 60-69.
34. Figueira, G.; Almada-Lobo, B. Hybrid simulation–optimization methods: A taxonomy and discussion. Simul. Model. Pract. Theory; 2014; 46, pp. 118-134. [DOI: https://dx.doi.org/10.1016/j.simpat.2014.03.007]
35. Chica, M.; Juan, A.A.; Bayliss, C.; Cordón, O.; Kelton, W.D. Why simheuristics? Benefits, limitations, and best practices when combining metaheuristics with simulation. SORT; 2020; 44, pp. 311-334. [DOI: https://dx.doi.org/10.2139/ssrn.2919208]
36. Calvet, L.; Wang, D.; Juan, A.; Bové, L. Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands. Int. Trans. Oper. Res.; 2019; 26, pp. 458-484. [DOI: https://dx.doi.org/10.1111/itor.12560]
37. Guimarans, D.; Dominguez, O.; Panadero, J.; Juan, A.A. A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times. Simul. Model. Pract. Theory; 2018; 89, pp. 1-14. [DOI: https://dx.doi.org/10.1016/j.simpat.2018.09.004]
38. Latorre-Biel, J.I.; Ferone, D.; Juan, A.A.; Faulin, J. Combining simheuristics with Petri nets for solving the stochastic vehicle routing problem with correlated demands. Expert Syst. Appl.; 2021; 168, 114240. [DOI: https://dx.doi.org/10.1016/j.eswa.2020.114240]
39. Reyes-Rubiano, L.; Ferone, D.; Juan, A.A.; Faulin, J. A simheuristic for routing electric vehicles with limited driving ranges and stochastic travel times. SORT; 2019; 1, pp. 3-24.
40. Gruler, A.; Quintero-Araújo, C.L.; Calvet, L.; Juan, A.A. Waste collection under uncertainty: A simheuristic based on variable neighbourhood search. Eur. J. Ind. Eng.; 2017; 11, pp. 228-255. [DOI: https://dx.doi.org/10.1504/EJIE.2017.083257]
41. Yazdani, M.; Kabirifar, K.; Frimpong, B.E.; Shariati, M.; Mirmozaffari, M.; Boskabadi, A. Improving construction and demolition waste collection service in an urban area using a simheuristic approach: A case study in Sydney, Australia. J. Clean. Prod.; 2021; 280, 124138. [DOI: https://dx.doi.org/10.1016/j.jclepro.2020.124138]
42. Gruler, A.; Panadero, J.; de Armas, J.; Moreno, J.A.; Juan, A.A. Combining variable neighborhood search with simulation for the inventory routing problem with stochastic demands and stock-outs. Comput. Ind. Eng.; 2018; 123, pp. 278-288. [DOI: https://dx.doi.org/10.1016/j.cie.2018.06.036]
43. Raba, D.; Estrada-Moreno, A.; Panadero, J.; Juan, A.A. A reactive simheuristic using online data for a real-life inventory routing problem with stochastic demands. Int. Trans. Oper. Res.; 2020; 27, pp. 2785-2816. [DOI: https://dx.doi.org/10.1111/itor.12776]
44. Onggo, B.S.; Panadero, J.; Corlu, C.G.; Juan, A.A. Agri-food supply chains with stochastic demands: A multi-period inventory routing problem with perishable products. Simul. Model. Pract. Theory; 2019; 97, 101970. [DOI: https://dx.doi.org/10.1016/j.simpat.2019.101970]
45. Tordecilla, R.D.; Martins, L.d.C.; Panadero, J.; Copado, P.J.; Perez-Bernabeu, E.; Juan, A.A. Fuzzy simheuristics for optimizing transportation systems: Dealing with stochastic and fuzzy uncertainty. Appl. Sci.; 2021; 11, 7950. [DOI: https://dx.doi.org/10.3390/app11177950]
46. Bertolini, M.; Mezzogori, D.; Neroni, M.; Zammori, F. Machine Learning for industrial applications: A comprehensive literature review. Expert Syst. Appl.; 2021; 175, 114820. [DOI: https://dx.doi.org/10.1016/j.eswa.2021.114820]
47. Sengupta, J.; Kubendran, R.; Neftci, E.; Andreou, A. High-speed, real-time, spike-based object tracking and path prediction on google edge TPU. Proceedings of the 2020 2nd IEEE International Conference on Artificial Intelligence Circuits and Systems (AICAS); Genova, Italy, 31 August–2 September 2020; pp. 134-135.
48. Calvet, L.; de Armas, J.; Masip, D.; Juan, A.A. Learnheuristics: Hybridizing metaheuristics with machine learning for optimization with dynamic inputs. Open Math.; 2017; 15, pp. 261-280. [DOI: https://dx.doi.org/10.1515/math-2017-0029]
49. Arnau, Q.; Juan, A.A.; Serra, I. On the use of learnheuristics in vehicle routing optimization problems with dynamic inputs. Algorithms; 2018; 11, 208. [DOI: https://dx.doi.org/10.3390/a11120208]
50. Calvet, L.; Ferrer, A.; Gomes, M.I.; Juan, A.A.; Masip, D. Combining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmentation. Comput. Ind. Eng.; 2016; 94, pp. 93-104. [DOI: https://dx.doi.org/10.1016/j.cie.2016.01.016]
51. Bayliss, C.; Juan, A.A.; Currie, C.S.; Panadero, J. A learnheuristic approach for the team orienteering problem with aerial drone motion constraints. Appl. Soft Comput.; 2020; 92, 106280. [DOI: https://dx.doi.org/10.1016/j.asoc.2020.106280]
52. Chankov, S.M.; Becker, T.; Windt, K. Towards definition of synchronization in logistics systems. Procedia CIRP; 2014; 17, pp. 594-599. [DOI: https://dx.doi.org/10.1016/j.procir.2014.02.034]
53. Castaneda, J.; Neroni, M.; Ammouriova, M.; Panadero, J.; Juan, A.A. Biased-Randomized Discrete-Event Heuristics for Dynamic Optimization with Time Dependencies and Synchronization. Algorithms; 2022; 15, 289. [DOI: https://dx.doi.org/10.3390/a15080289]
54. Kogler, C.; Rauch, P. Discrete event simulation of multimodal and unimodal transportation in the wood supply chain: A literature review. Silva Fenn.; 2018; 52, 9984. [DOI: https://dx.doi.org/10.14214/sf.9984]
55. Bredström, D.; Rönnqvist, M. Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Eur. J. Oper. Res.; 2008; 191, pp. 19-31. [DOI: https://dx.doi.org/10.1016/j.ejor.2007.07.033]
56. Afifi, S.; Dang, D.C.; Moukrim, A. Heuristic solutions for the vehicle routing problem with time windows and synchronized visits. Optim. Lett.; 2016; 10, pp. 511-525. [DOI: https://dx.doi.org/10.1007/s11590-015-0878-3]
57. Guo, J.; Long, J.; Xu, X.; Yu, M.; Yuan, K. The vehicle routing problem of intercity ride-sharing between two cities. Transp. Res. Part B Methodol.; 2022; 158, pp. 113-139. [DOI: https://dx.doi.org/10.1016/j.trb.2022.02.013]
58. Bayliss, C.; Martins, L.d.C.; Juan, A.A. A two-phase local search with a discrete-event heuristic for the omnichannel vehicle routing problem. Comput. Ind. Eng.; 2020; 148, 106695. [DOI: https://dx.doi.org/10.1016/j.cie.2020.106695]
59. Fikar, C.; Juan, A.A.; Martinez, E.; Hirsch, P. A discrete-event driven metaheuristic for dynamic home service routing with synchronised trip sharing. Eur. J. Ind. Eng.; 2016; 10, pp. 323-340. [DOI: https://dx.doi.org/10.1504/EJIE.2016.076382]
60. Boysen, N.; Briskorn, D.; Fedtke, S.; Schwerdfeger, S. Drone delivery from trucks: Drone scheduling for given truck routes. Networks; 2018; 72, pp. 506-527. [DOI: https://dx.doi.org/10.1002/net.21847]
61. Das, D.N.; Sewani, R.; Wang, J.; Tiwari, M.K. Synchronized truck and drone routing in package delivery logistics. IEEE Trans. Intell. Transp. Syst.; 2020; 22, pp. 5772-5782. [DOI: https://dx.doi.org/10.1109/TITS.2020.2992549]
62. Yetis, H.; Karakose, M. Collaborative Truck-Drone Routing Optimization Using Quantum-Inspired Genetic Algorithms. Proceedings of the IEEE 2021 25th International Conference on Information Technology (IT); Zabljak, Montenegro, 16–20 February 2021; pp. 1-4.
63. Deng, P.; Amirjamshidi, G.; Roorda, M. A vehicle routing problem with movement synchronization of drones, sidewalk robots, or foot-walkers. Transp. Res. Procedia; 2020; 46, pp. 29-36. [DOI: https://dx.doi.org/10.1016/j.trpro.2020.03.160]
64. Grangier, P.; Gendreau, M.; Lehuédé, F.; Rousseau, L.M. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. Eur. J. Oper. Res.; 2016; 254, pp. 80-91. [DOI: https://dx.doi.org/10.1016/j.ejor.2016.03.040]
65. Arnau, Q.; Barrena, E.; Panadero, J.; de la Torre, R.; Juan, A.A. A biased-randomized discrete-event heuristic for coordinated multi-vehicle container transport across interconnected networks. Eur. J. Oper. Res.; 2022; 302, pp. 348-362. [DOI: https://dx.doi.org/10.1016/j.ejor.2021.12.035]
66. Hashemi Doulabi, H.; Pesant, G.; Rousseau, L.M. Vehicle routing problems with synchronized visits and stochastic travel and service times: Applications in healthcare. Transp. Sci.; 2020; 54, pp. 1053-1072. [DOI: https://dx.doi.org/10.1287/trsc.2019.0956]
67. Ghiani, G.; Guerriero, F.; Laporte, G.; Musmanno, R. Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. Eur. J. Oper. Res.; 2003; 151, pp. 1-11. [DOI: https://dx.doi.org/10.1016/S0377-2217(02)00915-3]
68. Haghani, A.; Jung, S. A dynamic vehicle routing problem with time-dependent travel times. Comput. Oper. Res.; 2005; 32, pp. 2959-2986. [DOI: https://dx.doi.org/10.1016/j.cor.2004.04.013]
69. Hong, L. An improved LNS algorithm for real-time vehicle routing problem with time windows. Comput. Oper. Res.; 2012; 39, pp. 151-163. [DOI: https://dx.doi.org/10.1016/j.cor.2011.03.006]
70. Chen, H.K.; Hsueh, C.F.; Chang, M.S. The real-time time-dependent vehicle routing problem. Transp. Res. Part E Logist. Transp. Rev.; 2006; 42, pp. 383-408. [DOI: https://dx.doi.org/10.1016/j.tre.2005.01.003]
71. Ferrucci, F.; Bock, S.; Gendreau, M. A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods. Eur. J. Oper. Res.; 2013; 225, pp. 130-141. [DOI: https://dx.doi.org/10.1016/j.ejor.2012.09.016]
72. Barkaoui, M.; Gendreau, M. An adaptive evolutionary approach for real-time vehicle routing and dispatching. Comput. Oper. Res.; 2013; 40, pp. 1766-1776. [DOI: https://dx.doi.org/10.1016/j.cor.2013.01.022]
73. Azi, N.; Gendreau, M.; Potvin, J.Y. A dynamic vehicle routing problem with multiple delivery routes. Ann. Oper. Res.; 2012; 199, pp. 103-112. [DOI: https://dx.doi.org/10.1007/s10479-011-0991-3]
74. Cardoso, P.J.; Schütz, G.; Mazayev, A.; Ey, E.; Corrêa, T. A solution for a real-time stochastic capacitated vehicle routing problem with time windows. Procedia Comput. Sci.; 2015; 51, pp. 2227-2236. [DOI: https://dx.doi.org/10.1016/j.procs.2015.05.501]
75. Martins, L.d.C.; Tarchi, D.; Juan, A.A.; Fusco, A. Agile optimization for a real-time facility location problem in Internet of Vehicles networks. Networks; 2022; 79, pp. 501-514. [DOI: https://dx.doi.org/10.1002/net.22067]
76. Li, Y.; Peyman, M.; Panadero, J.; Juan, A.A.; Xhafa, F. IoT Analytics and Agile Optimization for Solving Dynamic Team Orienteering Problems with Mandatory Visits. Mathematics; 2022; 10, 982. [DOI: https://dx.doi.org/10.3390/math10060982]
77. Peyman, M.; Copado, P.J.; Tordecilla, R.D.; Martins, L.d.C.; Xhafa, F.; Juan, A.A. Edge Computing and IoT Analytics for Agile Optimization in Intelligent Transportation Systems. Energies; 2021; 14, 6309. [DOI: https://dx.doi.org/10.3390/en14196309]
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Details
; Herrera, Erika M 1
; Neroni, Mattia 2
; Juan, Angel A 3
; Faulin, Javier 4
1 Computer Science Department, Universitat Oberta de Catalunya, 08018 Barcelona, Spain
2 Research & Development Team, aHead Research—Spindox SpA, 10149 Torino, Italy
3 Department of Applied Statistics and Operations Research, Universitat Politècnica de València, 03801 Alcoy, Spain
4 Institute of Smart Cities, Department of Statistics, Computer Science and Mathematics, Public University of Navarra, 31006 Pamplona, Spain