UNIVERSITY OF VIENNA
Faculty of Business, Economics and Statistics Department of Business Administration

040661 KFK PM/SCM/TL: Seminar B (E) WS /2014 Stochastic Vehicle Routing Problem with Restocking

Professor :
O.Univ.Prof.Dr. Richard Hartl Vienna,2014

Student:
Shkodran Ahmeti 0851254

Table of contents
Table of contents List of figures 1.Introduction 1.2. Problem Presentation 2. Stochastic Vehicle Routing Problem With Optimal Restocking 3. Single Vehicle Routing Problem 4. Multiple Vehicle Routing 4.1. Heuristic Algorithms 4.1.1. Route-First-Cluster-Next Heuristic Algorithm 4.1.2. Cluster-First- Route- Second Algorithm 4.1.3. Improving the Heuristic Solution 5. Computational Study and Results 5.1. Set – partitioning problem formulation 5.2.Test of Algorithms over Problem Sizes and Expected Route Length Limits 5.3. Comparison of the Algorithms over Demand Variations 5.4. Comparison with a Deterministic Method

6. Summary References

List of figures
Figure 1 A desired truck route with restocking action of returning to the depot when a stockout occurs or in anticipation of a stockout Figure 2 The two updating Strategies a and b Figure 3 Defined or particular route of a single vehicle Figure 4 Expected costs of going directly to the next node Figure 5 Expected costs of the restocking action Figure 6 Monotonicity of function fj(q) Figure 7 Choosing the unused vehicle Figure 8 Forming the clusters Figure 9 Routing through the clusters Figure 10 Cyclic transfer Figure 11 String cross Figure 12 String exchange Figure 13 String relocation

ABSTRACT
This paper presents a Stochastic Vehicle Routing Problem SVRP, where just the customer demand was unknown and other parameters were determined. In comparison with the deterministic, problems in stochastic vehicle routing are harder to be solved because the uncertainity. In place just to take a recourse the authors developed a strategy wich is called Restocking policy, where after a route failure a vehicle should get back to the depot for replenishing. Two heuristics are represented to find a better results for this problems and comparation between them is to be seen and a comparison between this heuristic and deterministic vehicle routing.

KEYWORDS Vehicle Routing – Stochastic Vehicle RoutingRestocking – VRP Heuristics

1.INTRODUCTION
Vehicle Routing Problem with Stochastic Demand (VRPSD) becomes an very important part in area of VRP. In the last years the interest for this problem has grown from the side of researchers. Vehicle Routing Problem in almost all papers is presented through a graph consisting from vertices and edges
G = (V,A)

where number of points

represent consumers denoted by V, and A represents number of arcs, with a strong correlation and which are presented in a graph. Designing optimal routes to visit the nodes (consumers) by vehicles with the minimum costs is another form or representation of the Vehicle Routing Problem (VPR). In many books and papers which deal with VRP one can find that, this problem is divided in many forms and for many problems which occurs in a real-life. Constructing the routes for the vehicles, is not so easy because

in this process we have to take care about the vehicle capacity, and in most papers one can find that, capacity is presented as a constraint that should not be exceeded. To hold this constraint we have to know the consumers’ demand, which should be fulfilled by the vehicles. There are another parameters to be known too, e.g. consumer sets, demand, time windows, etc. which are important for defining a problem if it’s a deterministic or stochastic. At this point if the demand is already known we have to deal with Deterministic Vehicle Routing and if the demand is random or not known than we have to deal with the Stochastic Vehicle Routing Problem (SVRP or VRPSD). In this paper the consumer demand is known or revealed only when the visit to the consumer occurs. This is a sign that the whole this paper will do with the Stochastic Vehicle Routing Problem (SVRP), where only the consumer demand is unknown or uncertain and all other parameters are known or determined. 1.1. Problem Presentation Problems where the companies have to deal with the stochastic demand are often to be seen in real life. Data collection for the demand is very difficult because there could be an absence of advanced reports of inventories or as I mentioned before the demand could not be known until the consumer is visited. Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou have given some examples about this problem. One of them is the daily demand for a cash at the banks ATMs where we don’t know how large the withdraw will be. The maximal amount of cash that one vehicle could bring is dictated by security policy. In this case not all ATMs could be supplied on a route from just one vehicle. It can happen that the supply can exeed the vehicle capacity and in this case the vehicle should be restocked. Another problem is the volume of trash, which is not known at each stop on a waste collection route. Because all trash shouold be collected and vehicle capacity is limited, the vehicle may emtying and then returning to its

designated route again. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000). Such examples can be found at the other papers e.g. cash collection from bank branches, sludge disposal, etc. The authors noted that the most important characteristic of the SVRP is that some changes in routes could occur. They may not be followed in the desired or planned manner. Because the demand is unknown or stochastic, at some point on the route, after supplying some consumers, the vehicle load will become less before all demand on the route is fulfilled. This means that some consumers on the route wont be served because the vehicle capacity. That’s why the vehicle capacity is one of the important constraint in this problems. In this case there are some possibilities or some actions that should be taken. One of them is that, when a vehicle visits a consumer there should be decided how much to satisy the demand of this consumer in order to have enough goods for other consumers. The worst case is that consumer dissatisfaction or revenue loos are possible because of unsatisfied demand of consumers. Another action is to not supply any consumers after the inventory in the vehicle is exhausted. The third one and the main topic in this paper is, that after the vehicle is empty it should return to the depot for reloading and return again at the same consumer where the out-of-stock occurred. Than the vehicle continues the route as planned. This action is called Vehicle Restocking Problem and is the target of the study in this paper. Figure 1. will demonstrate this problem.

Fig. 1. A desired truck route with restocking action of returning to the depot when a stockout occurs or in anticipation of a stockout.

As we can see from Fig.1 the vehicle starts from the depot and at some point its exhausted. Next action is to return to the deport for restocking and return back to the point where the out-of-stock occurred, and continuing to the next point or consumer. From this figure we can see the two problems which may happen during the delivery. First one is restocking, which means after a stock-out, the vehicle returns back to depot and after loading returns to the same point and continues, whereas the second is before the stock-out occurs or in anticipation of stock-out, which means the vehicle goes to the depot for the restocking before a stock-out occurs and continues to the next consumer or point. But these actions generate extra costs, which are not wanted or are against the objective of all Vehicle Routing Problems. To have a greater control on this costs the second problem is taken in consideration in this paper, anticipation of possible stock-outs. The objective is to trade off the extra cost occurred from returning to the depot after a stockout with the cost of

returning to the depot for reloading before out-of-stock actually occurs at a stop. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) For this problem Bertsimas has proposed a strategy. In place of redesign the routes each day, his proposal is to update the routes and presents two strategies for the routes with stochastic customer demand, namely Strategy a and Strategy b. He determined a fixed a priori sequence among all potencial customers. Strategy a This strategy tells us that the consumers will be visited in the same fixed order but here will be served just the customers that require service that day. The total expected distance traveled corresponds to the fixed length of the a priori sequence, adding the distance when the route fails or must return to the depot for the restocking. Strategy b This strategy is similar with Strategy a with only difference that the consumers with no demand will be skipped. This strategy seems to be more deterministic. The difference between this two strategies can be seen in Figure 2. (Dimitris J. Bertsimas, 1991)

Fig.2. The two updating Strategies a and b From this figure we can see the a priori tour, depot denoted with 0, vehicle capacity 3 and demand of the consumers. Then we have a Strategy a and b. Here we have a restocking recourse where at node three the vehicle is forced to return to the depot. Strategy a presents situation where the demand of a customer is known only when the consumer is visited, and when the capacity is reached the vehicle must return to depot. Strategy b shows that demand is already known before the start of a tour e.g. customers call, and the saving in cost is achieved by skipping the zero demands. With this presentation he tries to find the a priori sequence of minimum expected length using the Strategy a and b and called this problem the probabilistic vehicle routing problem (PVRP) under Strategy a and b. (Dimitris J. Bertsimas, 1991)

2. STOCHASTIC VEHICLE ROUTING PROBLEM WITH OPTIMAL RESTOCKING
The authors began to explain this problem through a completed graph G = (V, A, C), where they define: V={0, 1, . . . , n} a set of nodes and with node 0 denoting the depot and other nodes 1, 2, .. , n corresponding to the customers A={(i, j): i, j∈ V, i ≠ j}, the set of arcs joining the nodes and C=(cij), travel costs or distances between nodes i and j. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) Here is assumed, as I said before that the nodes are fully interconnected, including the depot, and the cost matrix is symmetric. The customer demand is stochastic denoted by ξi, i = 1, . . . , n, which is independently distributed and this demand is known only when the vehicle arrives at their location. Its assumed that the stochastic demand does not exceed the vehicle capacity Q, and is distributed with a discrete distribution with m possible values ξ1, ξ2, … , ξm and probability mass function pik = Prob(ξi = ξ k). (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) After defining the stochastic demand and constraints of vehicle capacity now the problem is going to be defined. With the given vehicle fleet, each with with capacity Q, SVRPOR will try to find vehicle routes and a restocking policy for each node. Another thing that should be found is determining if the vehicle should return to the depot before visiting the next customer in order to minimize total expected cost. The costs which should be minimized are:  Cost of traveling from one customer to another  Restocking cost  Costs of returning to depot for restocking because the remaining stock in vehicle is not sufficient to satisfy demand at a customer

location (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000)

There are two important topics which are studied recently related to the stochastic parameters, the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demand (VRPSD). PTSP is presented with just one vehicle and no demand. The stochastic component is a customer that requires to be visited with some probability pi. Constructing an a priori route, only the random subset of points requires a visit, and the objective is to find an a priori tour of minimum expected length. In his paper Liu presented the PTSP as a extension of the TSP. He formulated the objective of the PTSP as a minimization of the expected length of a priori tour, where the customers require visits only with a given probability. (Liu, 2008) According to Liu the main difference between the PTSP and TSP is that the probability of each node being visited is between 0.0 and 1.0 for PTSP whereas for TSP is 1.0. Designing the routes for the stochastic vehicle routing problem is very hard for the researchers in real-life applications because of unknown demand. SVRPOR is a part of this research. This problem has been studied in different frameworks and two of them are chance constrained approach and VRPSD- with- recourse. The chance constrained approach try to minimize the total distance traveled and controlling the route failure but ignoring the travel costs. The VRPSD-with- recourse on the other side tries to minimize the total expected cost, cost of travel and cost of returning to the depot.

3. SINGLE VEHICLE ROUTING PROBLEM
In this case the researchers wanted to find an optimal route for a single vehicle through the development of an efficient procedure, which evaluates defined route. The objective is to find its expected cost under an optimal restocking policy. I will try to present this problem through a graph wich presents the defined route.

j j+1 2

n 0

1

Fig.3. Defined or particular route of a single vehicle The problem is defined in a such way that after the vehicle has finished the service at customer j, its supposed that the remaining capacity in vehicle is denoted by q. The total expected cost from node j onwards is denoted by fj(q) and Sj represents the set of all possible loads. The mathematical formulation of this problem looks like this: fj(q) = Minimum

and the boundary condition

These equation is divided in two parts the upper part and the lower part of minimization function. The upper part represents the expected costs of going directly to the next customer. From the previous graph its would look like this:

j j+1 2

n 0

1

Fig.4. Expected costs of going directly to the next node The lower part represents the expected cost of the restocking action.

j j+1 2

n 0

1

Fig.5. Expected costs of the restocking action

After this step they tried to find and optimal policy, which is derived from the following equations and the theorem.

LEMMA 1.

From this Lemma we can se that expected cost to continue to the next node is smaller or equal than total vehicle capacity and the restocking which occurs at node j. This is proved from Eq.1 and gives

As

C

satisfies

the

triangular

inequality

Eq.1

derives

This equation means that the vehicle can continue serving node j+1 directly from node j without restocking. With all this equations the researchers tried to find when and which is the best policy to serve all consumers. They want to find is it better or more cost efficient to continue from one node to another or there will be a point where the vehicle have to return back to the depot for reload. Combining these two above equations derives the following one:

From this equations the researches tried to calculate the triangular inequality, to find the better route policy. As the result came:

All this equations are made to proof the theorem 1 of this paper. THEOREM 1. For each customer j, there exists a quantity hj, such that the optimal decision, after serving node j, is to continue to node j+1 if , or return to the depot if Kamlesh Mathur and Ronald H. Balou, 2000) . (Wen-Huei Yang,

From this theorem results that if in the vehicle remains enough capacity after serving costumer j, the vehicle can continue serving the node j+1, and if not the vehicle must return to the depot. The last node, node n is independent from the q. In the following there will be proved the monotonically non-increasing function of fj(q). Equation 1 is studied more in the paper and the first part is denoted with Hj(q) and the second part with H’j(q). Now the values of the two load q1 and q2 are demonstrated as:

The total expected cost from node j onwards fj(q) is presented as a minimum of a non-icreasing function Hj(q) and a constant function H’j(q). (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) As we know there is a demand of customer hj, which helps to define the optimal decision. This decision presents, that after serving node j the vehicle can continue to the j+1 if or return to the depot if .

Fig.6. Monotonicity of function fj(q) As we know that the SVRP objective is to find a solution with the least total travel cost, for the real life applications, some heuristic algorithms

have to be developed. The researchers tries to find savings through some iterations with the string of nodes in the route. Inserting a string of nodes in a partial tour makes possible to evaluate the costs and deleting some nodes from the tour makes possible to see if there is saving in costs. For example Or-opt algorithm compute saving from deleting a string of 3, 2, or 1 from a tour and then computing the cost of inserting it back somewhere else in the tour to check if this switch results in a cost savings. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) In the paper there is a model of computing the insertion cost when between two nodes some other nodes are inserted e.g. between node i and j. Formula for the Approximation the Insertion Cost is: , where current partial tour and is cost at node i of the

is the resulting cost vector at node i. For

this procedure of inserting the nodes in the tour Or-opt algorithm is used and compared with 2-Opt, where they found that 2-Opt requires more computational time but gave slightly better results. But in our case the overall stochastic routing problem is to be evaluated, procedure has been used. so the Or-opt

4. MULTIPLE VEHICLE ROUTING
Multiple vehicles are used in a case where the demand exceeds the vehicle capacity. But because of the restocking recourse policy the researchers told that the single route as explained earlier seems to be more optimal than multiple routes or vehicles. This fact will be argued through the Theorem 2, which tells that there exists a single route that is as economical as multiple routes. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000). This theorem will be proved by a route partition of n consumers. The researches showed that in connecting two routes will be less or equal than

holding each route separated. A mathematical model is presented in a paper for this problem. Here are the notations:

And now its needed to show that the optimal route costs of partition are smaller or equal to the first route and the second . The

total expected costs of a particular optimal route of partition are presented with the formula . This formula represents

the restocking recourse trying to find if the the vehicle can continue from the node i to node j and is there still capacity left. Now the next equation is presented like Equation 1. with only difference that here the cost of a particular route are computed, that’s mean if its possible to connect two routes in one.

Combination of this inequality with the equation above gives :

Because the second route r2 coincides with

from j onward, hence:

Because the first route r1 coincides with hence:

from i backward tot he depot

The main objective of this calculations was to prove that

.

Being able to apply all this calculations and combinations, as a input there will be that a single route which its total expected costs will be less or equal to the total expected costs of multiple routes. But in the real world problems and in complex problems, a good results or optimal results can be attained with help of heuristics. In the following I will try to write about some heuristics, which are used in this paper. 4.1. Heuristic Algorithms For this problem of multiple routes or vehicles, two heuristics are used with an additional restriction that the expected costs can not exceed a specified value T. The heuristics that are used in this research are : route- firstcluster-second and cluster- first-route-second. 4.1.1. Route-First-Cluster-Next Heuristic Algorithm This heuristic was first used by Beasley, who told that the cluster phase is a standard shortest path problem. (Gilbert Laporte, Frederic Semet, 2002) From the name of this heuristic we can see that this heuristic first finds a single route through all customers and then clusters the consumers or divides the route into small subroutes. The researchers have proposed a procedure to partition the big route into small routes, while the sequence of

nodes will remain the same.A dynamic programming procedure is used to partition this route. Here I present some notations: - the minimum expected costs from node ik onward, assuming that the best partition is used along the subsequence (ik, ik+1, . . . , iN). - the first partitioning point along the subsequence - the expected cost of the route through the partitioned set of nodes T – a specified value for the route constraint From this notations derives the dynamic programming recourse: with the boundary condition For the deterministic problem there are much more heuristics developed. I want to bring an example for this heuristic. Its deterministic but I brought it just to try to understand this method better, and this is a very simple heuristic. Assuming the giant tour and knowing the demands we can partition this route into subroutes.

and we get these result with vehicle capacity 4, C = 4:

4.1.2. Cluster-First- Route- Second Algorithm This algorithm is the opposite of the previous one. From the title we can se that first the nodes or the customers on the route have to be clustered and than the route will be constructed. This algorithm is adopted from the deterministic VRP algorithm, with substanical modification from the stochastic demand situation. (Wen-Huei Yang, Kamlesh Mathur and

Ronald H. Balou, 2000) Laporte and Semet have determined some methods as elementary clustering methods. One of them is Sweep algorithm. They told that a feasible clusters are initially formed by rotating a ray centered at the depot. Then a vehicle route is obtained for each cluster by solving a TSP. (Gilbert Laporte, Frederic Semet, 2002) This algorithm works in this way: assuming that each vertex i has his polar cordiantes, angle and ray length. These are the steps of this algorithm:

Step 1 (route initialization). Choose an unused vehicle k. Step 2 (route construction). Starting from the unrouted vertex having the smallest angle, assign vertices to vehicle k as long as its capacity or the maximal route length is not exceeded. If unrouted vertices remain, go to Step 1. Step 3 (route optimization). Optimize each vehicle route separately by solving the corresponding TSP(exactly or approximately). (Gilbert Laporte, Frederic Semet, 2002) I will present an example for this algorithm just to be little bit clear how does this algorithm works. Starting with Step 1 choosing an unrouted vehicle with capacity in our case 4, C = 4. (Parragh, 2011)

Fig.7. Choosing the unused vehicle Going to Step 2 we have to choose the nodes with the smallest angle and then to assign them on the cluster.

Fig.8. Forming the clusters In the end we have to determine the routes through the clusters.

Fig.9. Routing through the clusters In the paper these steps are explained separately and little bit different as the Savelsbergh and Goetschalck made. Now I will try to explain the method presented in the paper for clustering the customers and than determining the route. The clustering method begins with the selection of the seed points. Determination of Seed Points This methos is presented through the covering circles of Savelsbergh and Goetschalck. The method begins like this: 1. For each of the customer i, one should find the largest circle which originates from i,in a way that the total demand of the customers

who are covered from circle should not exceed the vehicle capacity Q. 2. The customers should be ranked by their radius of their associated circle in ascending order. 3. Iteratively selection of a customer, which is still not selected by the circles of previously selected seed points, as the next seed point. When all the customers are selected or covered the process stops. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) After the covering the selected nodes provide the seed points, and using this seed points the clusters are formed as follows. Forming Customer Clusters 0. The seed that have the smallest covering circle should be seleceted and then the cluster should be initialized 1. Constructing the seed route that goes from depot to the seed point and then returns to the depot. 2. For each unconnected node, the computation of the cost of insertion at the best location in the seed route ,should be done through the approximation method. Nodes should be ranked in ascending order of the insertion cost. 3. The unconnected nodes have to be inserted with the least insertion cost into the route successively. Nodes that make the route infeasible are rejected. 4. Stopping criterion is achieved when all the nodes are assigned to a cluster. If not, k have to be incremented and from the nodes that have not yet benn assigned, the one with the smallest circle have to be picked and go to step 1. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000)

Routing Through Clusters In this phase one has to construct the routes through the clusters. The method works like this: 1. Starting the initial clusters and routes constructed by the clustering procedure 2. After we have to compute the approximate cost improvement of repositioning it from the current position to the any other position, either on the same route or to other routes. 3. The node with the largest improvement should be moved from one position to another one. 4.1.3. Improving the Heuristic Solution The solution from the previous heuristics can be further improved by using the inter- route and intra-route exchanges, while no further improvement can be made. Inter-route Exchange Inter-route exchange procedure attempts to improve the routes by moving a segment of nodes from one route to another. In the paper this method is explained in this way: 1. Initializing the sets k=3 2. In the second step, one has to evaluate the improvement if the string of routes is moved from its current route to the best location in the other route. 3. All the sets with positive improvement are considered and the new exact costs of the new routes are computed through the dynamic programic recursion.. 4. If k= 0 stop. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) Several authors presented in their paper some operators and exchange schemes. E.g. Thompson and Psaraftis in their paper describes a general b-

cyclic, k-transfer scheme in which a circular permutation of b routes is considered and k customers from each route are shifted to the next route of the cyclic permutation. They show than this technique results. (Gilbert Laporte, Frederic Semet, 2002) yields interesting

Fig.10. Cyclic transfer

Another author Van Breedam made some classifications of the improvement operations, for e.g. string cross, string exchange, string relocation and string mix.  String cross (SC). Two strings of vertices are exchanged by crossing two edges of two different routes.

Fig.11. String cross  String exchange (SE). Two strings of at most k vertices are exchanged between two routes

Fig.12. String exchange  String relocation (SR). A string of at most k vertices is moved from one route to another, typically with k = 1 or 2.

Fig.13. String relocation  String mix (SM). The best move between SE and SR is selected. (Gilbert Laporte, Frederic Semet, 2002) Intra-route Exchange After the Inter-route improving method follows the Intra-route

improvement. In Laporte and Semet book this technique presented from Lin’s λ-opt mechanism. (Gilbert Laporte, Frederic Semet, 2002)In this mechanism λ edges are removed from the tour, and the λ remaining segments are reconnected in all possible ways. For this method Or proposed Or-opt method, which displace strings of 3, 2, or 1 consecutive vertices to another location. (Gilbert Laporte, Frederic Semet, 2002)

5.COMPUTATIONAL STUDY AND RESULTS
In this part the procedures of the heuristics described above are presented and a comparison of this two methods is presented. The two methods are denoted with H1 for route-first-cluster-second and H2 the cluster-firstroute-second. The researchers try to test the quality of the solutions, which are obtained from this methods. 5.1. Set – partitioning problem formulation This problem is presented through this notations, where V is the set of customers, and R represent all feasible subsets of V. The subset is feasible when the total length of the route is less or the same with the time limitation T. The objective of this problem is, that the multiple vehicle SVRPOR has to find a partition of V, and each customer will be served by just one vehicle, and the expected total cost of all routes is minimized.

(Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) Mathematical formulation of this problem looks like this:

where dj is minimum expected cost of a route that starts and ends at the depot and each costumer is visited in costumer set. e is an n-vector of all 1s, and aj is a binary n-vector with element aij equal to 1 if i ϵ rj and 0 otherwise. The binary variable xj determines the inclusion or exlusion of the route. 5.2.Test of Algorithms over Problem Sizes and Expected Route Length Limits The methods described above are tested for problems in size from 10 to 60 customers and the expected route length T was limited from 200 to 400. Table 1 presents the results of this test.

Up to 15 customers, the solutions from the two heuristics are compared to the lower bound solution, which is found from the linear programming relaxation of the set-partitioning formulation. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000)From the results which are obtained, the researchers showed that both of the algorithms produce near optimal solutions. But H1 gave better results, not only its average deviation from the lower bound is less, but the maximum deviation is significantly lower than that of H2. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) 5.3. Comparison of the Algorithms over Demand Variations In this phase the algorithms H1 and H2 are compared for different degrees of demand variations. In this case for each particular combination of demand range and problem size, five problems were tested. For the problems with 40 nodes, Table 2 shows the average percent deviation from the better of the two solutions and percent of times it produced the better solution. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) Again as before the H1 performed better than H2, except for the demand range 0.6-0.8.

5.4. Comparison with a Deterministic Method For this comparison problem researchers compared the deterministic approach using the Clarke-Wright savings algorithm with the heuristic H1, on random problems ranging in size from 10 to 60 nodes and for demand range of 0.2 to 1.0. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000) In Table 3 the results indicate that the stochastic algorithms produce significant savings for the majority of the test cases.

Even though the average improvement differs from case to case, the results of this comparison show the following general guidelines in case of application of the stochastic routing algorithms: 1. The greater the demand variation, the greater the benefit obtained by SVRPOR. 2. The same is in case of a larger problem size 3. When individual customer demand approaches full truck load, the nominal savings can be expected from the SVRPOR method, because both the stochastic and deterministic approaches will tend to use single routes. (Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou, 2000)

References
Dimitris J. Bertsimas. (1991). A vehicle routing problem with stochastic demand. Gilbert Laporte, Frederic Semet. (2002). Classical Heuristics for the Capacitated VRP. In D. V. Paolo Toth, The Vehicle Routing Problem . Philadelphia: Society for Industrial and Applied Mathematics. Liu, Y.-H. (2008). Solving the Probabilistic Travelling Salesman Problem Based on Genetic Algorithm with the Queen Selection Scheme. Taiwan: InTech. Parragh, S. (2011). Transportation Logistics; Part V: An introduction to VRP. Vienna. Wen-Huei Yang, Kamlesh Mathur and Ronald H. Balou. (2000). Stochastic Vehicle Routing Problem with Restocking. Transportation Science.