=Paper=
{{Paper
|id=None
|storemode=property
|title=Applying Simulation and Reliability to Vehicle Routing Problems with Stochastic Demands
|pdfUrl=https://ceur-ws.org/Vol-589/paper02.pdf
|volume=Vol-589
|dblpUrl=https://dblp.org/rec/conf/aiia/JuanGFRMR09
}}
==Applying Simulation and Reliability to Vehicle Routing Problems with Stochastic Demands==
https://ceur-ws.org/Vol-589/paper02.pdf
Applying Simulation and Reliability to Vehicle
Routing Problems with Stochastic Demands
Angel A. Juan1 , Scott E. Grasman2 , Javier Faulin3 , Daniel Riera1 , Carlos
A. Méndez4 , and Bernardo Ruiz1
1
Department of Computer Science, Multimedia and Telecommunication
Open University of Catalonia
Barcelona, Spain
ajuanp@uoc.edu, drierat@uoc.edu, bruizsa@uoc.edu
2
Department of Engineering Management and Systems Engineering
Missouri University of Science & Technology
Rolla, MO, USA
grasmans@mst.edu
3
Department of Statistics and Operations Research
Public University of Navarre
Pamplona, Spain
javier.faulin@unavarra.es
4
INTEC
Universidad Nacional del Litoral - CONICET
Santa Fe, Argentina
cmendez@intec.unl.edu.ar
Abstract
Vehicle Routing Problems (VRPs) cover a wide range of well-known
NP-hard problems where the aim is to serve a set of customers with
a fleet of vehicles under certain constraints. Literature contains sev-
eral approaches -coming from different fields like Operations Research,
Artificial Intelligence and Computer Science- which try to get good
(near-optimal) solutions for small-, mid- and large-size instances. The
Vehicle Routing Problem with Stochastic Demands (CVRPSD) is a
particular case of VRP where demands made by clients are random,
which introduces uncertainty in the problem. Thus, a good aprioris-
tic solution may become unfeasible during the delivery phase if total
demand in a route exceeds total vehicle capacity. This paper presents
a flexible approach for the CVRPSD, which is based on the combined
use of Monte Carlo simulation and reliability indices. Our methodology
provides a set of alternative solutions for a given CVRPSD instance.
These solutions depend on a parameter which controls the probability
of suffering route failures during the actual delivering phase. A numer-
ical example illustrates the methodology and its potential applications.
Proceedings of the 16th International RCRA workshop (RCRA 2009):
Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Reggio Emilia, Italy, 12 December 2009
1 Introduction
The Vehicle Routing Problem with Stochastic Demand (VRPSD) is a well-
known NP-hard problem in which a set of stochastic customers’ demands
must be served by a fleet of homogeneous vehicles departing from a depot,
which initially holds all available resources. There are some tangible costs
associated with the distribution of these resources from the depot to the
customers. In particular, it is usual for the model to explicitly consider
costs due to moving a vehicle from one node -customer or depot- to another.
These costs are usually related to the total distance traveled, but can also
include other factors such as the number of vehicles employed, service times
for each customer, etc. The classical goal here consists of determining the
optimal set of routes that minimizes those tangible costs under the following
set of constraints:
i All routes begin and end at the depot.
ii Each vehicle has a maximum load capacity, which is considered to be
the same for all vehicles.
iii Each customer has a (stochastic) demand that must be satisfied.
iv Each customer is supplied by a single vehicle.
v A vehicle cannot stop twice at the same customer -at least without
incurring in a penalty cost.
Even though the deterministic Capacitated Vehicle Routing Problem
(CVRP) -the one which assumes well-known customers’ demands- has been
studied for decades and a large set of efficient optimization methods, heuris-
tics and metaheuristics have been developed [9, 15, 20], the non-deterministic
VRPSD is still in its infancy and new efficient methodologies need to be de-
veloped [22]. All in all, the number of VRP articles published in refereed
journals has grown exponentially in the last 50 years [12], which shows the
relevance of the topic for current researchers and practitioners.
The main difference between the CVRP and the VRPSD is that in the
former each customer’s demand is known beforehand, while in the latter
the actual demand of each customer has a stochastic nature -i.e., only its
statistical distribution is known beforehand, but its exact value is revealed
only when the vehicle reaches the customer. This random behavior of the
customers’ demands could cause an expected feasible solution to become an
unfeasible one if the final demand of any route exceeds the actual vehicle
capacity. This situation is referred to as “route failure”, and when it occurs
corrective actions -i.e., changes in the original routes- must be introduced to
obtain a new feasible solution. While some authors have tried to model the
costs associated with these route failures [25], the presented approach also
2
focuses on reducing the probability of occurrence of such undesirable situa-
tions to a reasonable value -a parameter to be defined by the decision-maker.
In other words, our methodology proposes the construction of reliable solu-
tions, i.e., solutions with a low probability of suffering a route failure. This
is basically attained by constructing routes in which expected demand will
be somewhat lower than the vehicle capacity. Put in another way, the idea
is to keep a certain amount of vehicle capacity surplus while designing the
routes, so that if final routes’ demands exceed their expected values up to a
certain limit, they can be satisfied without incurring in a route failure. Of
course, a trade-off exists between routes’ reliability and costs minimization
and, therefore, an optimal balance must be set for these two factors, which
is the main goal of the methodology presented here.
2 Related Work
The VRPSD is often modeled as a two-stage problem where the solution
from stage one specifies a route for each vehicle, and customer demands are
revealed at each stop along the planned routes. When routes fail, recourse
actions are implemented to serve any remaining customers, and the solution
from stage two specifies the actual route of each vehicle taking into account
the recourse actions. Thus, the objective of the VRPSD is to construct a set
of planned routes that minimize the sum of the costs of the planned routes
and the expected cost of the recourse action.
Historically speaking, Tillman [26] is considered the first to study the
VRPSD problem in a multidepot context. He proposed a saving based
heuristic for its solution. Later, Golden and Stewart [14] presented a chance
constrained model and two recourse models. The first model defined a
penalty proportional to vehicle overcapacity, while in the second one, the
penalty is proportional to the expected demand in excess of the vehicle ca-
pacity. In the following decade, Dror and Trudeau [11] developed further
procedures showing that for VRPSD the expected travel cost depends on
direction of the travel even in the symmetric case. Nevertheless, the most
interesting contributions to this problem are due to Bertsimas [1, 3, 2]. Fur-
thermore, Dror et al. [10] proved that some of the properties established by
Jaillet [16, 17] and Jaillet and Odoni [18] extend to the VRPSD.
The VRPSD occurs in many practical situations. Chepuri and Homem
de Mello [6] investigate the delivery of petroleum products, industrial gases,
and home heating oil. Dessouky et al. [8] present the example of delivering
supplies to cities under a state of emergency, Yang et al. [27] consider the
delivery of items to hospitals and restaurants, and Markovic et al. [21]
suggest that VRPSD can be used to model the delivery and pickup of mail,
packages, and recycled material from offices and industrial plants. Gendreau
et al. [13] first presented an exact solution for the VRPSD using an integer L-
3
shaped method for solving a stochastic linear program; however, the number
of customers is limited. Bertsimas and Simchi-Levi [4] offered an early review
of stochastic vehicle routing research and a comprehensive set of references.
Most approaches to the VRPSD can be divided into static and dynamic.
The static, or aprioristic approach, designs routes before actual demands be-
come known and the route sequence does not change during real-time execu-
tion. The already mentioned Jaillet [17] introduced the aprioristic-solution
approach to the probabilistic TSP with stochastic customer requests, later
generalized to the VRP with stochastic customers and demand. Other pa-
pers related to the static approach are those of Jaillet and Odoni [18] and
Bertsimas et al. [3]. The dynamic -or re-optimization- approach does not
plan routes in advance, but instead makes routing decisions one step at
a time. Information is updated each time a vehicle arrives at a customer
and observes demand. The problem is typically modeled as a Markov de-
cision process where a decision is defined as which customer to visit next
and whether or not to return to the depot. Examples of re-optimization
approaches can be seen in Secomandi [23, 24]. Additionally, the VRPSD
-and probabilistic traveling salesman problem- are generally considered to
be aprioristic routing even though there is a probability of route failure.
Campbell and Thomas [5] provide a comprehensive review of advances and
challenges in aprioristic routing.
3 The Logic Behind our Approach
Our approach is based on the fact that, while the VRPSD is yet an emerg-
ing research area, extremely efficient metaheuristics do already exist for
solving the CVRP -which can be seen as a particular case of VRPSD with
constant demands. In fact, techniques based on the use of Genetic Algo-
rithms, Tabu Search, Ant Colony Optimization or Hybrid GRASP are able
to provide near-optimal solutions for most known small- and medium-size
CVRP benchmarks. Thus, our approach aims at transforming the problem
of solving a given VRPSD instance to a problem of solving several asso-
ciated CVRP instances, each of them characterized by a specific level of
route-failures risk.
Consider a VRPSD instance defined by a set of n customer nodes with
stochastic demands Di following a well-known statistical distribution, and a
vehicle maximum capacity, V M C. In this scenario, we propose to apply the
methodology shown in Fig.1, which basically reduces the problem of solving
a VRPSD instance to the problem of solving several “conservative” CVRP
instances. The term conservative refers here to the fact that only a certain
percentage k, with 0 < k ≤ 1, of the vehicle total capacity will be considered
during the routing design phase (in other words, a percentage of the total
vehicle capacity will be reserved for attending possible “emergencies” caused
4
Figure 1: Flow diagram for the proposed methodology
by under-estimated random demands during execution time). This reserve
is usually known in inventory theory literature as safety stocks.
The details of the methodology are given next:
1. Set a value for k, the percentage of the maximum vehicle capacity that
will be used during the routing design stage, giving V M C ∗ = k·V M C.
2. Consider the CV RP (k) defined by a total vehicle capacity of V M C ∗
and by the deterministic demands d∗i = E[Di ] (mean or expected value
of each random demand).
3. Solve the CV RP (k) by using any efficient metaheuristic. Notice that
the solution of this CVRP is also a possible solution for the original
5
VRPSD. Moreover, it will be a feasible VRPSD solution as far as there
will be no route failure, i.e., as far as the extra-demand that might be
originated during execution time in each route does not exceed the
vehicle reserve capacity V RC ∗ = (1 − k) · V M C. Notice also that the
cost given by this solution, CCV RP (k), can be considered as the base or
fixed cost of the VRPSD solution, i.e., the cost of the VRPSD in case
that no route failures occur. Should a route failure occur, corrective
actions like vehicle returning to the depot for a reload will need to be
considered and, of course, related variable costs, CRF (k), will need to
be added for obtaining the total costs of the solution associated to the
current k-value, CV RP SD (k) = CCV RP (k) + CRF (k).
4. Obtain an estimate for the reliability of each route, Rj (1 ≤ j ≤ m for
a solution with m routes). In this context, the reliability of a route
is defined as the probability that that route does not suffer a failure.
This value can be estimated by direct Monte Carlo simulation using
the statistical distributions that model the demands of the nodes in
each route -observe that in each route over-estimated demands could
be sometimes compensated by under-estimated demands. To this end,
a number of trials (e.g. one thousand or more) can be randomly gen-
erated. Each of these trials will provide a random value for the total
demand in a given route. Then, the relative frequency of trials in
which that total demand has not exceeded V M C can be used as an
estimate of the route’s reliability.
j
5. Estimate the costs of each route failure, CRF (k) with 1 ≤ j ≤ m. It
seems reasonable to do this by calculating the costs associated with a
roundtrip from the depot to an imaginary client located at a distance
from the depot that equals the average distance from the depot to the
clients in the route. In fact, this could be considered even a conser-
vative estimate, since for routes with an appropriate orientation the
potential failure is likely to occur in clients closer to the depot than the
aforementioned imaginary client. In other words, if the transportation
costs are symmetric, route’s orientation should be selected so that the
last clients being served will be closer to the depot than the first clients
being served, since potential route failures are more likely to occur in
the final part of the route (See Fig.2).
6. Obtain an estimate for the solution’s variable costs, CRF (k), by using
the probabilistic expression shown in Eq.1:
m
j
X
CRF (k) = (1 − Rj ) · CRF (k) (1)
j=1
7. Obtain an estimate for the solution reliability level. This can be at-
tained by simply multiplying the reliabilities of each route -we are
6
Figure 2: Choosing the correct orientation for a given route
assuming here that nodes’ demands are independent among routes,
which seems a reasonable assumption to make in most real cases. A
solution reliability level can be considered as a measure of the feasi-
bility of that solution in the VRPSD context.
8. Depending on the total costs and the reliability indices associated with
the solution already obtained, repeat the process from Step 1 with a
new value of the parameter (that is, check how different levels of “being
conservative” when reserving some vehicle capacity for emergencies
affect to the final VRPSD solution).
9. Finally, provide the best solution found so far, i.e., the one with a
lowest total expected cost.
As far as we know, the approach presented here offers some interesting
advantages over other existing approaches for solving the VRPSD. Next,
some potential benefits offered by this approach are discussed:
• The methodology is valid for any statistical distribution with a known
mean, either theoretical (e.g.: Normal, Log-Normal, Weibull, Gamma,
etc.) or experimental (in which case bootstrapping techniques can be
used to generate the random values). In our opinion, real-life demands
should not necessarily follow a Normal or a Poisson distribution (as it
is often assumed in the VRPSD literature), but it should be possible
7
to model them by using any theoretical (both discrete and contin-
uous) or experimental distribution offering either non-negative values
or asymmetries generated by long right-hand tails (e.g. a Log-Normal,
a Weibull, a Gamma, etc.).
• In some sense, the methodology is “reducing” a complex VRPSD -
where no efficient metaheuristics have been developed yet-, to a more
tractable CVRP where excellent, fast and extensively tested meta-
heuristics exists. This adds credibility to the quality of the final solu-
tion or solutions provided to the decision-maker.
• Moreover, the fact that we can consider different scenarios based on
different values for the parameter k, which represents a certain level
of risk, makes the methodology flexible.
• Providing the reliability indices for each solution allows the decision-
maker to select that solution that best fits his/her utility function,
including those with a lower fixed cost but higher variability (risk) or
those with a higher fixed cost but lower variability (even if the total
expected costs are the same for both solutions). In this sense, our
approach could provide a list of selected solutions and their associated
properties as shown in Table 1.
• Enterprises dealing with routing problems create (routing) plans very
often -e.g. daily or weekly. They usually work with the same clients,
and they have deep information on their real time behaviour. That
makes these enterprises to have valuable information about possible
future changes in demands when applying the current plans. That
can be translated into higher or lower risk levels when choosing both
the k-values and the solution to apply. Thus, the flexibility of the
presented methodology is not used blindly, but with the support of
previous experience.
# routes k Fixed Expected Total Estimated
cost variable cost expected cost reliability
11 0.9 3200 1700 4900 0.76
12 0.8 3520 1200 4720 0.83
13 0.7 4020 950 4970 0.95
Table 1: Example of a possible output offered to the decision-maker
4 Experimental Results
The methodology described in this paper has been implemented as a Java
application. Java was used here since, being an object-oriented language,
8
it facilitates the rapid development of a prototype. A standard personal
computer, Intel R CoreTM 2 Duo CPU at 1.6 GHz and 2 GB RAM, was used
to perform the experiment described next, which was run directly on the
Eclipse IDE for Java. For illustration of our methodology, we constructed a
mid-size VRPSD instance based on a well-know CVRP instance, the A-n80-
k10 (available at http://www.branchandcut.org/ ). We used the same nodes
and vehicle maximum capacity as in the original A-n80-k10 (V M C = 100)
but we substituted the deterministic demands, di , for random demands, Di ,
with E[Di ] = di and V ar[Di ] = 2 for all 1 ≤ i < 80. We also required that
each of these random demands follow a log-normal distribution with location
parameter µi and scale parameter σi which -according to the properties of
the log-normal distribution- will be given by the expressions shown in Eq.’s
2 and 3:
1 V ar[Di ]
µi = ln(E[Di ]) − · ln 1 + (2)
2 E[Di ]2
s
V ar[Di ]
σi = ln 1 + (3)
E[Di ]
Notice that, by setting E[Di ] = di for all 1 ≤ i < 80, we can recover the
CVRP A-n80-k10 instance by just defining V ar[Di ] = 0 for all 1 ≤ i < 80.
In other words, we are just introducing some variance to the CVRP A-n80-
k10 instance to construct our own VRPSD instance based on the log-normal
distribution.
Next, we set k = 0.95 (i.e., we reserved 5% of total vehicle capacity for
attending potential route failures during the current execution of the delivery
stage) and solved -using the SR-GCWS algorithm [19]- the CVRP(0.95)
instance defined by the following parameters: d∗i = E[Di ] = di and V M C ∗ =
0.95 · V M C = 95. After some seconds of execution, we obtained a 10-route
solution with a base cost CCV RP = 1833.37, which we considered to be a
reasonable good value since it improved in about 2.9% the solution provided
by the Clarke & Wright heuristic [7] for this CVRP(0.95) instance, which
has an associated cost of 1882.84. Notice that, in the case of the standard A-
n80-k10 instance, the gap between the best-known solution (cost = 1766.50)
and the one provided by the Clarke & Wright heuristic (cost = 1860.94) is
only about 5.3%. Now, we used Monte Carlo simulation to estimate the
reliability of each route in the obtained solution: for each client i in a route
r, we used the corresponding statistical distribution to generate a random
value for Di and then we checked whether or not the total demand in r
exceeded the real vehicle capacity V M C = 100 (notice that we are assuming
here independency among different clients’ demands). By repeating this
process 1, 000 times we obtained an estimate of the probability that each
route can be implemented without suffering a route failure, Rj with 1 ≤ j ≤
10. Finally, we estimated the solution’s reliability by simply multiplying its
9
routes’ reliabilities (since a solution will be safely implemented without route
failures if, and only if, each and every route in that solution is implemented
without route failures, i.e., a solution can be seen as a series system of
routes). Table 2 shows the estimated values obtained for the reliability of
each route and for the global reliability. It also shows the estimated cost
j
for a route failure, CRF with 1 ≤ j ≤ 10, the corresponding variable costs
associated to each route and also the total estimated variable costs for the
whole solution, CRF .
Element Reliability Cost of a Estimated
potential failure variable costs
Route 1 0.84 2 · 101.37 32.03
Route 2 0.97 2 · 36.12 2.53
Route 3 0.96 2 · 45.73 3.29
Route 4 0.93 2 · 32.11 4.56
Route 5 0.86 2 · 81.45 22.97
Route 6 0.88 2 · 89.65 20.80
Route 7 0.99 2 · 60.99 1.30
Route 8 0.91 2 · 71.68 12.90
Route 9 0.94 2 · 75.72 8.48
Route 10 0.91 2 · 70.59 13.41
Solution 0.43 — 122.32
Table 2: Reliability and variable costs values for each route
In summary, for k = 0.95, the total estimated cost for the VRPSD
solution is CV RP SD = CCV RP + CRF = 1955.69. From a computational
point of view, the whole process described before can be completed in just a
few minutes, and probably in just a few seconds if we use a multi-threaded
C/C++ version of the algorithm and a more powerful computer. Therefore,
it seems reasonable to repeat these steps with other values of the parameter
k. Table 3 shows different VRPSD solutions that we obtained by using
the values k = 0.90 and 0.85. For each of the three considered solutions,
the following information is provided: number of routes employed, base
costs (those from the associated CVRP(k) instance), gap between the CVRP
solution and the one provided by the Clarke & Wright heuristic (for the A-
n80-k10, we consider our CVRP solution to be a reasonable good one when
this gap is about 3% or higher), estimates for the variable and total costs,
and an estimate of the solution reliability index.
Notice that, as expected by the discussion developed during the method-
ology explanation, higher values of the parameter k tend to produce solu-
tions with less routes and lower base costs, but they also tend to have lower
reliability levels and, therefore, higher variable costs which can significantly
affect the expected total costs of the associated VRPSD solution.
10
k # Routes Base cost Gap (%) Variable Total Reliability
cost costs
0.95 10 1833.37 2.9 122.32 1955.69 0.43
0.90 11 1910.06 3.1 11.31 1921.37 0.93
0.85 12 1997.15 4.4 1.47 1998.62 0.99
Table 3: Costs and Reliability levels for different VRPSD solutions
Figure 3: Solution for stochastic A-n80-k10 with k = 0.90 (11 routes)
Among the three options presented in Table 2, the one which would be
probably selected for most decision-makers would be the VRPSD solution
obtained with k = 0.90, since it combines the lowest total costs with a
reasonable reliability level. Fig.3 shows a graphical representation of this
solution. Observe, however, that other values of the parameter k (e.g. k =
0.92 or k = 0.88) could also be explored before taking a final decision.
5 Future Work
As a future research work, we plan to compare the efficiency and robustness
of the proposed approach against alternative optimization methods lying
on mathematical or constraint programming models. More specifically, the
major idea is to replace the meta-heuristic used in the step 3 of the proposed
methodology by a rigorous two-stage stochastic optimization approach. In
this way, the solution generated will simultaneously consider multiple scenar-
ios for the customer demands instead of the one based only on the expected
value of each random demand. By considering the uncertain information of
demands in a proactive way, we expect being able to generate cost-effective
11
solutions with higher reliability, although at the expense of a potential sig-
nificant increase of the computational cost. The trade-off between solution
quality and computational time will be carefully evaluated. In addition,
since routes failures may be reduced but never eliminated, we also plan to
developed efficient dynamic optimization methods for quickly updating the
original solution after the occurrence of route failures.
6 Conclusions
We have presented a hybrid approach to solving the Vehicle Routing Prob-
lem with Stochastic Demands. The approach combines Monte Carlo simula-
tion with reliability indices and a well-tested metaheuristic developed by the
authors. The basic idea of our methodology is to consider a vehicle available
capacity lower than the actual maximum vehicle capacity when constructing
VRP solutions. This way, this capacity surplus can be used when necessary
to cover routes failures without having to assume the usually high costs in-
volved in vehicle restock trips. Our approach provides the decision-maker
with a set of alternative solutions, each of them characterized by their to-
tal estimated costs and their reliability values -the former reflecting the
probability of that solution being a feasible one-, leaving to him/her the
responsibility of selecting the specific solution to be implemented according
to his/her utility function. Some tests have been performed to illustrate the
methodology and discuss its potential benefits over previous works.
Acknowledgments
This work was supported in part by the IN3-UOC Knowledge Community
Program under grant HAROSA09. We would also like to thank NVIDIA
Inc. by their support to our research.
References
[1] D. Bertsimas. Probabilistic combinatorial optimization problems. PhD
thesis, Operations Research Center, Massachusetts Institute of Tech-
nology, Cambridge, MA, USA, 1988.
[2] D. Bertsimas. A vehicle routing problem with stochastic demand. Op-
erations Research, 40:574–585, 1992.
[3] D. Bertsimas, P. Jaillet, and A. Odoni. A priori optimization. Opera-
tions Research, 38:1019–1033, 1990.
12
[4] D. Bertsimas and D. Simchi-Levi. A new generation of vehicle rout-
ing research: robust algorithms, addressing uncertainty. Operations
Research, 44(2):216–304, 1996.
[5] A. Campbell and B. Thomas. Challenges and Advances in a priori
Routing. Springer, 2008.
[6] K. Chepuri and H. Homem de Mello. Solving the vehicle routing with
stochastic demands using the cross entropy method. Annals of Opera-
tions Research, 135:153–181, 2005.
[7] G. Clarke and J. Wright. Scheduling of vehicles from a central depot to
a number of delivering points. Operations Research, 12:568–581, 1964.
[8] M. Dessouky, F. Ordóñez, H. Jia, and Z. Shen. Rapid distribution of
medical supplies, pages 309–339. Patient flow: Reducing delay manage-
ment in health care systems. Springer, USA, 2005.
[9] R. Dondo, C. Méndez, and J. Cerdá. An optimal approach to the
multiple-depot heterogeneous vehicle routing problem with time win-
dow and capacity constraints. Latin American Applied Research,
33:129–134, 2003.
[10] M. Dror, G. Laporte, and P. Trudeau. Vehicle routing with stochastic
demands: Properties and solution frameworks. Transportation Science,
23:166–176, 1989.
[11] M. Dror and P. Trudeau. Stochastic vehicle routing with modified
savings algorithm. European Journal of Operational Research, 23:228–
235, 1986.
[12] B. Eksioglu, A. Volkan, and A. Reisman. The vehicle routing problem:
A taxonomic review. Computers & Industrial Engineering, 2009.
[13] M. Gendreau, G. Laporte, and R. Seguin. An exact algorithm for
the vehicle routing problem with stochastic demands and customers.
Transportation Science, 29(2):143–155, 1995.
[14] B. Golden and W. Stewart. Vehicle routing with probabilistic demands.
In D. Hogben and D. Fife, editors, Computer Science and Statistics:
Tenth Annual Symposium on the Interface. NBS Special Publication,
volume 503, pages 252–259, Slovenia, 1978.
[15] S. Golden, B.; Raghavan and E. Wasil, editors. The Vehicle Routing
Problem: Latest Advances and New Challenges. Springer, New York,
2008.
13
[16] P. Jaillet. Probabilistic traveling salesman problem. PhD thesis, Oper-
ations Research Center, Massachusetts Institute of Technology, Cam-
bridge, MA, USA, 1985.
[17] P. Jaillet. A priori solution of a traveling salesman problem in which
a random subset of the customers are visited. Operations Research,
36:929–936, 2002.
[18] P. Jaillet and A. Odoni. The probabilistic vehicle routing problem.
North-Holland, Amsterdam, 1988.
[19] A. Juan, J. Faulin, R. Ruiz, B. Barrios, and S. Caballe. The SR-GCWS
hybrid algorithm for solving the capacitated vehicle routing problem.
Applied Soft Computing, 2009.
[20] G. Laporte. What you should know about the vehicle routing problem.
Naval Research Logistics, 54:811–819, 2007.
[21] H. Markovic, I. Cavar, and T. Caric. Using data mining to forecast
uncertain demands in stochastic vehicle routing problem. In Proceed-
ings of the 13th International Symposium on Electronics in Transport
(ISEP), Slovenia, 2005.
[22] C. Novoa and R. Storer. An approximate dynamic programming ap-
proach for the vehicle routing problem with stochastic demands. Euro-
pean Journal of Operational Research, 196:509–515, 2009.
[23] N. Secomandi. A rollout policy for the vehicle routing problem with
stochastic demands. Operations Research, 49(5):796–802, 2001.
[24] N. Secomandi. Analysis of a rollout approach to sequencing problems
with stochastic routing applications. Journal of Heuristics, 9(4):321–
352, 2003.
[25] K. Tan, C. Cheong, and C. Goh. Solving multiobjective vehicle routing
problem with stochastic demand via evolutionary computation. Euro-
pean Journal of Operational Research, 177:813–839, 2007.
[26] F. Tillman. The multiple terminal delivery problem with probabilistic
demands. Transportation Science, 3:192–204, 1969.
[27] W. Yang, K. Mathur, and R. Ballou. Stochastic vehicle routing problem
with restocking. Transportation Science, 34(1):99–112, 2000.
14