Waiting and Relocation Strategies in Online Stochastic Vehicle Routing

1 Introduction

Vehicle routing with time windows is a hard combinatorial optimization problem with many important applications in distribution and transportation scheduling. It has received considerable attention in the last decades and sophisticated algorithms are now available to find near-optimal solutions in reasonable time. In recent years, attention has shifted to online and/or stochastic versions of the problem. The stochastic and online versions are motivated by the inherent uncertainties arising in many industrial problems and technological developments, such as onboard computers and communication systems, which give transportation systems the opportunity to update plans even after the vehicle has been deployed.

In online stochastic problems, customers arrive dynamically as the algorithm proceeds and each customer request has a time window during which it can be served. The algorithm must decide whether to accept or reject the request upon arrival. If it is accepted, the online algorithmmust serve the request. The online algorithm typically has two blackboxes available to make decisions: an optimization algorithm for the deterministic version of the problem and a conditional sampling procedure to generate future requests (e.g., [Chang et al., 2000; Benoist et al., 2001]).

Online stochastic vehicle routing was first studied in [Bent and Van Hentenryck, 2003; Bent and Van Hentenryck, 2004c]

using a sampling-based approach. Their idea is to generate scenarios consisting of existing and sampled customers, to solve the scenarios using large neighborhood search [Shaw, 1998], and to make online decisions based on the scenario solutions. Compared to other online stochastic problems such as packet scheduling [Chang et al., 2000] 1 and reservation systems [Benoist et al., 2001], online stochastic vehicle routing introduces an additional difficulty: it takes time to serve a request. Indeed serving a request involves moving to the customer, and then processing the request. In addition, a routing plan for a scenario may schedule a "sampled" customer (in contrast to an actual request) on a vehicle, something that never occurs in these other applications. How to best proceed when this situation arises is the key issue studied in this paper.

[Bent and Van Hentenryck, 2004c] took a conservative approach to this issue: Their algorithm, which is reviewed subsequently, first filters all the "sampled" customers from the plans, leaving only actual requests. Vehicles, when they become idle, are then sent to actual customers, chosen from the filtered solutions of the scenarios. Apparently, their design decision was motivated by the fact that sampled customers may never actually place a request. However, the fact that a sampled customer is served next in a scenario solution provides insight into the nature of the uncertainty and solutions.

The key contribution of this paper is to propose two novel strategies, waiting and relocation, to address this issue and to better exploit stochastic information in online vehicle routing. The waiting strategy recognizes that it is sometimes beneficial for a vehicle to wait at the current location instead of moving to a known customer. The relocation strategy goes one step further and may move vehicles to customer locations where no requests were placed (yet). These new strategies make several fundamental contributions:

• The vehicles can wait or relocate anywhere and at any time during the algorithm execution. This contrasts with earlier approaches (e.g., [Larsen et al., 2004; van Hemert, 2004]) where waiting and relocation points are defined a priori using knowledge of the distribution, clustering of the customers, and heuristics.
• The decisions of when and where to wait are systematically derived from stochastic information. Indeed, wait-

1 This paper also contains a comparison between online stochastic optimization and POMDP approaches.

ing and relocation simply make available to the online algorithms decisions that are necessarily sub-optimal in the offline setting. This contrasts with heuristics to distribute waiting time in routing plans (e.g., [MitrovicMinic et al., 2004; Mitrovic-Minic and Laporte, 2004]) which do not use stochastic information.

• A decision to wait or relocate solely relies on the scenario solutions, not on specific properties of the distribution which is used as a black-box. Hence the strategies should naturally transfer to a variety of applications.

Experimental results show that the waiting and relocation strategies may produce dramatic improvements in customer service compared to earlier algorithms, bridging much of the gap between the online solution and an offline, a posteriori solution where all the uncertainty has been revealed. The improvements are particularly impressive for highly dynamic instances with many late customers, which are particular challenging for earlier algorithms.

The rest of the paper is organized as follows. Sections 2-3 present the offline and online problems. Sections 4-6 present the online stochastic algorithm in stepwise refinements, concluding with the waiting and relocation strategies. Section 7 presents the problem instances and the experimental results.

2 The Offline Problem

The Input Data A vehicle routing problem is specified by a number of customers that must be visited by a pool of vehicles. Each customer makes a request that must be served within a time window and takes some capacity from the vehicle. Each vehicle starts at the depot, serves some customers, and must return to the depot by the deadline.

Each problem contains a set R of n customers and a depot o. The set S of sites is thus R∪{o}. The travel time between sites i and j is denoted by d(i, j). Each request is associated with a customer and, since each customer makes at most one request, we use customer and request interchangeably. Every request c has a demand q(c) ≥ 0 and a service time p(c) ≥ 0. Each instance has a pool of m identical vehicles with capacity Q. Each vehicle starts from the depot.

Each customer c has a time window specified by an interval [e(c), l(c)] satisfying e(c) ≤ l(c). The time window represents the earliest and latest possible arrival times of a vehicle serving customer c. In other words, the service for customer c may start as early as e(c) and as late as l(c). A customer c may not be served before e(c) but a vehicle arriving early to serve c may wait at the site until time e(c) before beginning service. The depot has a time window H = [e0, l0], which represents the earliest departure and latest possible return for the vehicles. Typically, e0 denotes the beginning of the day and l0 is the deadline by which all vehicles must return.

Routing Plans Optimization algorithms for vehicle routing typically return a routing plan that specifies the order in which each vehicle visits its customers. A vehicle route, or route for short, starts at the depot, serves some customers, and returns to the depot. A customer appears at most once on a route. Hence a route is a sequence 〈o, c1, . . . , cn, o〉, where ci ∈ R and all ci are distinct. The capacity of a route ρ is the sum of its customer capacities, i.e., q(ρ) = ∑ni=1 q(ci). A routing plan is a tuple of routes (ρ1, . . . , ρm) one for each vehicle, in which each customer appears at most once. We also use cust(ρ) and cust(γ) to denote the customers of a route ρ and a plan γ. A routing plan assigns a unique successor and predecessor for each served customer and depot. For a plan γ, the successor of site c is denoted by c+ and the predecessor is denoted by c-.

Departure Times Routing plans do not prescribe departure times for the vehicles. These departure times are typically not uniquely defined: a vehicle may depart at different times from specific customers and still visit all its assigned customers before the deadline. In addition to the routing plan, a solution will also consist of an assignment σ : R → H of starting times to all customers.

The Vehicle Routing Problem We are now in position to describe the vehicle routing problem. A solution to a vehicle routing problem with time windows (VRPTW) is a routing plan γ = (ρ1, . . . , ρm) and a starting time assignment σ satisfying the capacity and time window constraints, i.e.,

The objective is to find a solution maximizing the number of served customers |cust(γ)|. This objective function differs from the optimization criterion used the Solomon benchmarks, where the goal is to minimize the number of vehicles and, in case of ties, to minimize the total travel time. This highlights the difference between strategic planning and operational decision making. As maximizing the number of served customers is very difficult on the problems considered here, the cost associated with relocating or waiting (as factored into the travel time) is negligible.

Notations If S is a non-empty sequence, FIRST(S) and LAST(S) denote the first and the last element of a non-empty sequence. The concatenation of two sequences S1 and S2 is denoted by S1 : S2. If S is a sequence and S- is a prefix of S, then S-S- denotes the suffix S + such that S = S: S +. If S is a sequence and R is a set, FILTER(S,R) denotes the sequence obtained by removing the elements of R from S.

3 The Online Problem

In the online problem, requests arrive dynamically as the algorithm proceeds. The online algorithm maintains a partial routing plan γ= 〈ρ-1 , . . . , ρ-m〉 consisting of a partial route ρi for each vehicle i. It also maintains a partial assignment σ- of starting times for all customers in cust(γ-) \ {LAST(ρ1), . . . , LAST(ρm)}. These times specify when the vehicle serving a given customer has departed to the next customer on the same vehicle. The last customers on the vehicles have no departure times, since they have not been served yet.

The online algorithms have at their disposal an optimization algorithm O. Given a set of customer requests R and

ONLINE ALGORITHM A(〈R1, . . . , Rh〉) 1 ρ0 ← 〈〉; 2 σ0 ← σ⊥; 3 Γ← GENERATESOLUTIONS(ρ0, σ0,R1); 4 for t ∈ H 5 do At ← ACCEPTREQUESTS(ρt-1, σt-1,Rt,At-1, Γ); 6 Γ← UPDATEPLANS(ρt-1, σt-1,At, Γ); 7 if IDLE(ρt-1, σt-1) 8 then st ← CHOOSEREQUEST(ρt-1, At, Γ); 9 ρt ← ρt-1 : st; 10 σt ← σt-1[LAST(ρt-1) ← t]; 11 Γ← { ρ ∈ Γ | FIRST(ρ-ρt-1) = st }; 12 else ρt ← ρt-1; 13 σt ← σt-1; 14 Γ←Γ ∪ GENERATESOLUTIONS(ρt, σt,At); 15 return (ρh, σh); GENERATESOLUTIONS(ρt, σt , At) 1 Γ← ∅; 2 repeat 3 R ← SAMPLE(t); 4 Γ ← Γ ∪ {O(ρt, σt , At, R)}; 5 until time t +1 6 return Γ;

a pair (γ-, σ-), O(γ-, σ-,R) returns a routing plan γ+ = 〈ρ-1 : ρ+1 , . . . , ρ-m : ρ+m〉 maximizing |cust(γ+)| and satisfying C-(γ+), where C- denotes the problem-specific constraints C where the time windows of each customer c in cust(γ-) \ {LAST(ρ1), . . . , LAST(ρm)} have been tightened to [σ-(c), σ-(c)]. The online algorithms also use a procedure SAMPLE(t) to conditionally sample the request distribution from time t to the time horizon.

The rest of this paper describes the online stochastic algorithms in stepwise refinements using the algorithms of [Bent and Van Hentenryck, 2004a] as a basis to clearly identify our contributions. The algorithms are presented for a single vehicle, their generalization to multiple vehicles being obtained naturally using pointwise decisions [Bent and Van Hentenryck, 2004a].

4 Online Vehicle Routing

We now present the generic online routing algorithm. Since there is only one vehicle, a routing plan is simply the vehicle route and we use both terms interchangeably. The generic online algorithm is depicted in Figure 1. It maintains a set of plans Γ representing scenario solutions that are used to make decisions over the course of the computation. At every time t, the algorithm also maintains a partial routing plan ρt, its associated departure times σt, and Rt the requests that become available. Finally, the algorithm assumes that the set of requests R1 is available before the start of the computation. The implementation also includes service guarantees: Once a request is accepted, it must be served.

Lines 1-2 initialize the partial routing plan and the departure times, while line 3 generates the initial set of plans used in the decisions. The body of the algorithm (lines 5-15) first

CHOOSEREQUEST-C(ρt, Rt, Γ) 1 F ← ⋃ti=1 Ri; 2 for r ∈ F 3 do f(r) ← 0; 4 for ρ ∈ Γ 5 do r ← FIRST(FILTER(ρ-ρt, F)); 6 f (r) ← f (r) + 1; 7 return argmax(r ∈ F) f(r);

determines whether to accept any new requests that have arrived. Next those plans that cannot accommodate the new accepted requests At (line 6) are removed from Γ. It is important to stress that a least one plan p ∈ Γ should be able to accommodate the requests in At (through insertion or replacement of an equivalent sampled customer) since otherwise the algorithm cannot provide the necessary service guarantees. In this paper, customers are accepted greedily whenever a routing plan can accommodate them. Using stochastic information for accepting/rejecting did not bring significant improvements. The algorithm then determines whether the vehicle is idle, that is whether service is completed for the last customer in ρt-1 given the departure times in σt-1. If the vehicle is busy traveling or servicing the last customer in ρt-1, the routing plan and departure times remain the same (lines 12-13) and the algorithm simply continues generating plans (line 14). Otherwise, the vehicle is idle and the algorithm chooses a request st to serve using the plans in Γ (line 8), augments the routing plan (line 9) and the departure times (line 10), and updates Γ to remove the plans incompatible with the decisions (line 11). It is useful to review some of the details of the algorithm.

• a vehicle is idle at time t for a plan 〈s1, . . . , sk〉 and departure times σ if

In other words, a vehicle is idle when its route has no customers or when it has finished serving its last customer sk by time t.

• The algorithm assigns the departure time of the last customer in ρt-1 to time t in line 10. The vehicle thus departs for customer st at time t.
• A routing plan ρ that next visits a customer other than st must be removed from Γ since its decisions are incompatible with ρt (line 11).

Figure 1 also depicts how to generate plans. Line 3 of function GENERATESOLUTIONS generates a scenario by sampling the distribution from time t to the horizon (the time in which the vehicles must return to the depot). Line 4 calls the optimization algorithm with the routing plan and departure times at time t. It remains to specify how to make decisions. Figure 2 shows how to implement function CHOOSEREQUEST to obtain the consensus algorithm C from [Bent and Van Hentenryck, 2004d] where the details can be found. Algorithm C considers all known requests F (line 1) and initializes their evaluations (lines 2-3). It then considers each routing plan ρ ∈ Γ (line 4), retrieves the request served

CHOOSEREQUEST-CW(ρt , At, Γ) 1 F ← ⋃ti=1 Ai; 2 for r ∈ F ∪ {⊥} 3 do f(r) ← 0; 4 for ρ ∈ Γ 5 do r ← FIRST(ρ-ρt); 6 if r ∈ F 7 then f (r) ← f (r) + 1; 8 else f(⊥) ← f(⊥) +1; 9 return argmax(r ∈ F ∪ {⊥}) f(r);

next in ρ, and increments its credit (line 6). The request in F with the best evaluation is selected in line 7.

It is important to emphasize a critical point in this implementation. A solution ρ ∈ Γ is a routing plan ρ = ρt-1 : ρ+ starting with partial route ρt-1 followed by a sequence of requests coming from F and the sampling. As a consequence, there is no guarantee that the request s served next on the vehicle, i.e., s = FIRST(ρ+), is an actual request (s ∈ F), not a sampled customer (s /∈ F). This is precisely why the implementation in Figure 2 uses FILTER(ρ+, F) to prune plan ρ+ and keep only the requests in F. This guarantees that FIRST(FILTER(ρ+, F)) returns a real customer and that the vehicle departs for a customer who requested service.

5 AWaiting Strategy

The algorithm by [Bent and Van Hentenryck, 2004c] filters sampled customers before selecting the request. This conservative approach ensures that the vehicle always moves to a known customer, not a sampled request. This section investigates a waiting strategy based on the recognition that it may be beneficial for the vehicle to wait at its current location instead of serving customers too eagerly. For instance, the fact that the solution ρ to a scenario at time t starts with a sampled customer, that is

indicates that it may be beneficial to wait since the sampled request may materialize, in which case it must be served before the first accepted customer. The difficulty is to decide when to wait in a systematic fashion given that the algorithm has solved multiple scenarios, all of which may have different customers to serve next in their routing plans. Figure 3 depicts a natural implementation. Its key idea is to add a wait action ⊥ to the accepted requests. When considering a plan ρ ∈ Γ, the algorithm retrieves the request r to serve next in the scenario (line 5). In the case of an accepted request (r ∈ F), the evaluation of r is incremented. Otherwise, if r is a sampled customer (r /∈ F), the evaluation of the wait action is incremented. The implementation then selects the element of F ∪ {⊥} with the best evaluation, which may be either an accepted request or the wait action. The online generic routing algorithm must also be generalized slightly to wait. When the request is the wait action, the algorithmmodifies neither the routing plan nor the departure times.

Waiting heuristics have attracted considerable attention recently (see, for instance, [Mitrovic-Minic et al., 2004;

CHOOSEREQUEST-CR(ρt , At, Γ) 1 for r ∈ Customers 2 do f(r) ← 0; 3 for ρ ∈ Γ 4 do r ← FIRST(ρ-ρt); 5 f (r) ← f (r) + 1; 6 return argmax(r ∈ Customers) f(r);

Mitrovic-Minic and Laporte, 2004]). The beauty in the algorithm presented here is that the choice of when and where to wait is fully automatic and guided by the scenarios.

6 ARelocation Strategy

The waiting strategy recognizes that it may be beneficial to wait at the current location instead of serving an accepted request. It is especially appropriate for problems in which the bottleneck is to minimize travel times and it is reasonably easy to serve the customers. When the challenge is in maximizing the number of served requests, it is appealing to explore a relocation strategy and to consider moving to the location of sampled customers. Once again, the difficulty is to determine when and where to move. Figure 4 proposes a natural relocation strategy. Its fundamental idea is to avoid differentiating between accepted and sampled customers: the vehicle simply moves to the request with the best evaluation. Lines 1-2 initialize the evaluation of all customers, lines 45 increments the first request, and line 6 selects the request with the best evaluation. The selected request may be either an accepted or a sampled request.

A relocation strategy may be beneficial for improving the number of served requests because it anticipates future requests and positions the vehicle to serve them quickly. It is never advantageous when minimizing travel times, since it may move to locations where no requests will ever materialize. Observe also that when and where to relocate is also fully automatic and systematically derived from the scenario solutions. This contrasts with other approaches (e.g., [Larsen et al., 2004; van Hemert, 2004]) where relocation points are created using heuristics based on a priori information for specific problems, instances, and distributions.

7 Experimental Results

We now describe the experiments that compare our algorithms with those of [Bent and Van Hentenryck, 2004c].

The Benchmarks The online vehicle-routing problems are generated from the Solomon benchmarks [Solomon, 1987], a collection of very challenging vehicle-routing problems with 100 customers, many of which have yet to be solved optimally. The stochastic versions were developed by [Bent and Van Hentenryck, 2004c] where the details are found. We review the salient features of these benchmarks. The problems are divided into classes 1 through 5. The degree of a dynamism (DOD) of a problem is the ratio of the number of stochastic customers over the number of total customers. The class 1 problems are characterized by early arriving requests. and class 2 problems by more late arriving requests. The third class mixes class 1 and 2. For these three classes, the average DOD is 44%. Class 4 considers problems with more late arriving customers than class 2 and have an average DOD of 59%. Class 5 considers problems with a higher proportion of stochastic customers, i.e. an average DOD of 81%. In all problems, the expected number of customers is 100.

The Algorithms The results compare local optimization (LO) with the consensus and regret algorithms which may include the waiting and relocation strategies. Algorithm LO is a generalization of the parallel tabu-search algorithm in [Gendreau et al., 1999]. It generates multiple routing plans on the accepted customers. These plans are then used to accept or reject new customers and to select the decisions at each time step. LO is thus close to algorithm C, the main difference being that no stochastic information is exploited. The consensus algorithms C, CW, and CR have been fully described in this paper: C is the algorithm originally proposed by [Bent and Van Hentenryck, 2004c], while CW and CR respectively include the waiting and relocation strategies. The regret algorithms, R, RW, and RR, improved upon the consensus algorithms by using a sub-optimality approximation to evaluate the value of scheduling each request next on the vehicles and are described in detail in [Bent and Van Hentenryck, 2004b]. They use a simple and fast sub-optimality approximation whose details are described in [Bent et al., 2005]. Consider the decision of choosing which customer to serve next on vehicle v and let st be the next customer on the route of vehicle v at time t. To evaluate the regret of another customer r on the same vehicle v, the sub-optimality approximation determines whether there is a feasible swap of r and st on v, in which case the regret is zero. Otherwise, if such a swap violates the time-window constraints, the regret is 1.

Initial Plans andOnline Process The online stochastic algorithms generate and solve 50 scenarios to select the decisions at time 0. The algorithms also generate and solve 50 additional samples to create plans given the set of decisions at time 0. As these scenarios are generated and solved ahead of time, the number of scenarios can be arbitrarily large depending on the application. Each such optimization is allocated one minute. During the online execution, each optimization runs for 10 seconds and uses the LNS procedure from [Shaw, 1998]. All algorithms are executed on an AMD Athlon 64 3000 processor with 512MB of RAM running Linux. Each of the instances is run 50 times to account for the nondeterministic nature of the algorithms. In the results, we often omit the words "in the average" for brevity.

The Results Figures 5 and 6 summarize all the results for the regret and consensus algorithms regarding the number of unserviced customers. (All customers can be served in the offline, a posteriori problems.) The figures depict the results for the specific instances and a linear regression for each class of algorithms. Some specific results are cropped by the graph extent to maintain its readability. The main result is the outstanding behavior of RR, i.e., the regret algorithmwith a relocation strategy. From the interpolations, it can be seen that algorithm RR dominates all the algorithms for DODs over 50% and that the improvements increase substantially as the DOD grows. The improvement over R is significant, indicating the importance of using relocation on this set of instances. Subsequent results will characterize more precisely when the relocation strategy is of paramount importance. Algorithm RW is also quite effective in general, but it is dominated by RR as the DOD increases. Similar results can be observed for the consensus algorithms C, CW, and CR but, in general, they serve fewer customers than their regret counterparts.

Results on Class 4 Figure 7 depicts the results on class 4. We highlight the best and second best result for each problem in boldface and italics respectively. Algorithms RR and RW are reasonably close. For small DODs, R performs the best, however, what is noteworthy is the significant gain RR and RW show as the DOD increases. These results show the significance of the waiting and relocation strategies on class 4. Observe that LO misses more than 25 customers on instance rc104-2, while only about 10 customers are not served by RR. Their consensus counterparts also behave well.

Results on Class 5 Class 5 contains the most difficult instances and the experimental results are depicted in figure 8. On these instances, some algorithms may miss up to 30 customers. This is the case of algorithms LO, C, and R on rc104-4. Once again, algorithmRR is the most effective algorithm overall and only misses 7 customers on rc104-4. The improvements of RR over other algorithms are quite dramatic on class 5 and grow with the degree of dynamism. They clearly demonstrate the value of a relocation strategy on online vehicle routing with time windows.

It is important to point out that the relocation is completely guided by the stochastic information and does not include any problem-specific knowledge: a vehicle simply moves to the selected customer whether this is an accepted customer or a sampled customer. As a consequence, the relocation strategy is simple to implement, yet it is critical to obtain high-quality solutions on these instances. The regret algorithmRW with a waiting strategy is also effective and provides significant over the other algorithms, but it is dominated by RR.

8 Conclusion

This paper considered the online vehicle routing problem where customer requests arrive dynamically. It demonstrated the effectiveness of two novel strategies to further exploit stochastic information: waiting and relocation. The strategies were shown as natural instantiations of the generic stochastic optimization framework by making available actions that are sub-optimal in an offline setting. The effectiveness of the strategies were demonstrated and validated in the experimental results. As future work, it will be interesting to see the performance of these techniques on classes of VRPs where waiting and relocation may have more impact on cost. Finally, as the decision to relocate or wait solely relies on scenario solutions, not on any prior knowledge of the problem or distribution, the results should naturally extend to a variety of applications in planning and scheduling.

Acknowledgments

This research is partly supported by NSF Award DMI0600384 and ONR DEPSCOR Award N000140610607.