We consider a dynamic vehicle routing problem with time windows and stochastic customers (DS-VRPTW), such that customers may request for services as vehicles have already started their tours. To solve this problem, the goal is to provide a decision rule for choosing, at each time step, the next action to perform in light of known requests and probabilistic knowledge on requests likelihood. We introduce a new decision rule, called Global Stochastic Assessment (GSA) rule for the DS-VRPTW, and we compare it with existing decision rules, such as MSA. In particular, we show that GSA fully integrates nonanticipativity constraints so that it leads to better decisions in our stochastic context. We describe a new heuristic approach for efficiently approximating our GSA rule. We introduce a new waiting strategy. Experiments on dynamic and stochastic benchmarks, which include instances of different degrees of dynamism, show that not only our approach is competitive with state-of-the-art methods, but also enables to compute meaningful offline solutions to fully dynamic problems where absolutely no a priori customer request is provided.
Quite similar to the consensus algorithm is the Dynamic Sample Scenario Hedging Heuristic introduced by @cite_8 for the stochastic VRP. Also, @cite_27 designed a Tabu Search heuristic for the DS-VRPTW and introduced a vehicle-waiting strategy computed on a future request probability threshold in the near region. Finally, @cite_1 extends MSA with waiting and relocation strategies so that the vehicles are now able to relocate to promising but unrequested yet vertices. As the performances of MSA has been demonstrated in several studies @cite_1 @cite_3 @cite_17 @cite_23 , it is still considered as a state-of-the-art method for dealing with DS-VRPTW.
@cite_8 @cite_1 @cite_3 @cite_27 @cite_23 @cite_17
2011300857 1998816621 2163352112 2212025445
Abstract This paper proposes a state-of-the-art branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands (VRPSD). We adapt the model of Christiansen and Lysgaard [6] and formulate the VRPSD as a set partitioning model with additional constraints. Feasible routes are generated using a dynamic programming algorithm executed over a state-space graph. Our method combines 2-cycle elimination with ng -routes. In addition, our pricing problem is significantly accelerated by the introduction of a new aggregate dominance rule. To speed up the generation of negative reduced cost columns, we use a tabu search heuristic and a bidirectional labeling algorithm. We also add capacity and subset-row inequalities dynamically in order to strengthen the linear relaxation of the master problem. As extensive computational tests illustrate, our algorithm is very competitive with the one of [6] . We solve 20 additional instances from the 40-instance set considered by these authors and we considerably improve the computing times for instances already closed. We also solve 17 new instances from the literature. The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15 . Moreover, improvements of up to 41 can be achieved for some test instances. We consider the courier delivery problem (CDP), a variant of the vehicle routing problem with time windows (VRPTW) in which customers appear probabilistically and their service times are uncertain. We use scenario-based stochastic programming with recourse to model the uncertainty in customers and robust optimization for the uncertainty in service times. Our proposed model generates a master plan and daily schedules by maximizing the coverage of customers and the similarity of routes in each scenario, while minimizing the total time spent by the couriers and the total earliness and lateness penalty. To solve large-scale problem instances, we develop an insertion-based solution heuristic, called master and daily scheduler (MADS), and a tabu search improvement procedure. The computational results show that our heuristic improves the similarity of routes and the lateness penalty at the expense of increased total time spent when compared to a solution of independently scheduling each day. Our experimental results also show improvements over current industry practice on two real-world data sets. In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon's benchmark test cases for VRPTW. Experimental results show that our approach yields very good solutions when compared with the benchmarking solutions.