Robust Optimisation Approach for Vehicle Routing Problems with Uncertainty

Abstract

We formulated a solution procedure for vehicle routing problems with uncertainty (VRPU for short) with regard to future demand and transportation cost. Unlike E-SDROA (expectation semideviation robust optimisation approach) for solving the proposed problem, the formulation focuses on robust optimisation considering situations possibly related to bidding and capital budgets. Besides, numerical experiments showed significant increments in the robustness of the solutions without much loss in solution quality. The differences and similarities of the robust optimisation model and existing robust optimisation approaches were also compared.

Liang Sun 1, 2 and Bing Wang 1

Academic Editor:Babak Shotorban

1, School of Mechatronics Engineering and Automation, Shanghai University, Shanghai 200072, China
2, School of Transportation and Vehicle Engineering, Shandong University of Technology, Zibo 255049, China

Received 15 November 2014; Accepted 19 March 2015; 31 March 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Nowadays, vehicle routing problem (VRP for short) is a crucial and critical issue in industrial and systems engineering [1, 2]. The vehicle routing problem involves routing a fleet of vehicles from a depot to service a set of customers. If one or both of the demand and edge costs (distance, transportation cost, travel time, etc.) are uncertain, the variant vehicle routing problem becomes a vehicle routing problem with uncertainty (VRPU for short). VRPU is faced daily by courier services, local trucking companies, demand-response transportation services, and so forth. From the perspective of managers, the expected total transportation cost in failure scenarios given the coexistence of failure and successful scenarios results in a number of practical contexts where the routes followed by different drivers remain almost the same from day to day.

The sum of all demands in such a scenario exceeds the capacities that the vehicles can serve by assuming that the demand is known before vehicles start their routes: such a scenario is considered as a "failure." In contrast, if vehicles in the depot satisfy the demands of all customers when it is assumed that the demands are known before vehicles start their routes, such scenario is considered as a successful one.

Contrary to existing robust optimisation models for VRPU, we summarise the contributions of this research as follows.

(1) Supposing the coexistence of failure and successful scenarios, we proposed a robust optimisation approach to minimise the sum of the expected total transportation cost in all failure scenarios and its variation multiplied by a weighted coefficient on the condition of coexistence of failure and successful scenarios.

(2) Unlike robustness measure of E-SDROA, our approach can deal with some situations involving bidding or capital budget decisions.

(3) Solving for the robust optimal solution of our approach for VRPU is no more difficult than solving a single deterministic SDVRP (split delivery vehicle routing problem) while satisfying all demands in a given bounded uncertainty set.

The rest of this paper is organised as follows: Section 2 reviews the relevant literature; Section 3 modifies the original SDVRP statement to incorporate the demand and transportation cost uncertainties [3-5]. Besides, a robust optimisation formulation for VRPU in demand and transportation cost is constructed and a solution method for our robust optimisation formulation is proposed. In Section 4, theoretical analysis shows the relationship between our approach and E-SDROA for the proposed problem. The computational results of some instances in Section 5 verified the effectiveness of our robust optimisation approach. Conclusions are drawn and further research topics are outlined in Section 6. To understand better our robust optimisation approach, a brief introduction to E-SDROA for the proposed problem is described in the Appendix.

2. The literature Reviewed

Stochastic optimisation approaches for solving VRPU were designed to optimise the expected value of all possible scenarios [6-8]. However, the approaches lead to large variations in the objective values for different scenarios even if the expected value is optimal. To compensate for the limitations of stochastic optimisation approaches for VRPU, the robustness concept has recently been introduced. The robust optimisation approaches for VRPU have many practical advantages over estimated probability distributions in a stochastic optimisation approach to the problem [9, 10]. Firstly, in many cases, it is easier to define the uncertainty set than to estimate the probability distributions. Secondly, under certain conditions, the robust approach does not significantly increase the complexity of the problem.

However, robust optimisation approaches available for VRPU fail to solve situations involving either bidding or capital budget decisions [9, 11-13]. Meanwhile, robust optimisation approaches available for VRPU are doubted in their application to service industries in recent years (e.g., each customer is served by exactly one vehicle; individual demands larger than the vehicle capacity are not allowed).

Generally speaking, there are two types of robust optimisation approach used for VRPU.

(1) Robust optimisation based on the definition of model robustness [14]: this approach mainly focuses on the feasibility of the optimal solution from a set of scenarios. Sungur et al. introduce a robust optimisation approach to solving the VRP with demand uncertainty [9]. The approach yielded routes minimising transportation costs while satisfying all demands in a given bounded uncertainty set. They solved the problem directly by using an off-the-shelf mixed integer programming solver. Their results indicated that the robust optimisation approach is attractive as it produced a much more robust solution with only a small penalty in the objective value.

Lee et al. investigated a vehicle routing problem with deadlines, wherein the objective is to satisfy the requirements of a given number of customers with minimum travel distances while regarding both the customers' deadlines and vehicle capacities [13]. Gounaris et al. derived the robust optimisation counterparts of several deterministic CVRP formulations. At the same time, they developed robust rounded-capacity inequalities for two broad classes of demand supports and showed how they were able to be efficiently separated [12].

Yao et al. designed a robust linear programming model on the basis of a robust optimisation approach wherein hard constraints are guaranteed within an appropriate uncertainty set [15]. Erera et al. created a robust optimisation framework for dynamic empty repositioning problems using time-space networks [16]. They derived necessary and sufficient conditions for the flow to be robust for three types of allowable recovery actions. Chung et al. formulated a robust network design problem as a tractable linear programming model [17, 18]. They illustrated its robustness by comparing the performance of its solution with the nominal solution of the corresponding deterministic model.

Najafi et al. presented a robust approach for a multiobjective, multimodal, multicommodity, and multiperiod stochastic model to manage the logistics of both commodities and injured personnel in response to an earthquake. The model was used to ensure that the distribution plan performed well under various chaotic situations arising in the aftermath of an earthquake [19]. Agra et al. proposed two new formulations for robust VRP. The first extended the well-known resource inequalities by using adjustable robust optimisation. Another generalised a path inequalities formulation to cater for the uncertain context [20].

(2) A robust optimisation approach that can measure the trade-off between solution and model robustness [14]: the objective function of the model was a utility function that embodied a trade-off between optimisation objective and variability therein [14, 21]. List et al. established a formulation and a solution procedure for fleet sizing under uncertainty in future demand and operating conditions [10]. Their formulation concentrated on robust optimisation, using a partial moment measure of risk.

Naumann et al. proposed a robust optimisation approach to vehicle scheduling in public bus transport [22]. In their optimisation, the approach used typical disruption scenarios to minimise the expected sum of planned costs and costs caused by disruptions. To incorporate the stochastic disturbances of daily passenger demand that occurred in actual operations, Yan and Yang built an E-SDROA for routing buses with stochastic demand. This model combined the concept of semivariance devised by Markowitz, the robust optimisation model of Mulvey and Ruszczynski, and the actual operating characteristics of a bus company [21, 23-25]. The method aimed to minimise the sum of the expected total transportation cost (the optimisation objective) and its variability (the robustness measure) multiplied by a weighting value. Yan et al. presented a reliable, novel bus route schedule design solution by considering uncertainty in the buses' travel times and the bus drivers' schedule-recovery efforts [26]. The objective was to minimise the sum of the expected values of the random schedule deviation and its variability multiplied by a weighting value.

Moreover, Montemanni et al. presented a new extension for solving the traveling salesman problem, where edge costs were specified as a range of possible values [11]. They applied a robust deviation criterion to propel optimisation over the interval data problem so obtained. Sungur et al. introduced scenario-based stochastic programming with recourse to model the uncertainty in customers and robust optimisation for the uncertainty in service times [27].

Moreover, robust optimisation has been extended to multistage problems where the here-and-now decision is amended by a recourse decision [16]. Sun and Wang proposed a robust optimisation model for VRP under uncertainty to decrease the variability encountered in EVM (a special case of E-SDROA) [28]. The approach did not ensure the feasibility of the optimal solution for all scenarios. Meanwhile, its solution was complicated.

3. CE-SDROA (Conditional Expectation Semideviation Robust Optimisation Approach) for VRPU

3.1. Primary Sources of Uncertainty

In practice, estimating transportation cost (a type of marginal cost) is also a difficult task except for demand uncertainty caused by many unpredictable factors, including traffic conditions, accidents, congestion, and weather conditions. For this reason, the proposed robust optimisation approach focuses on two primary sources of uncertainty: the future demands that are to be served by the vehicle fleet and the transportation cost.

3.2. Problem Statement

VRP with demand and transportation cost uncertainty is a variant of VRPU. It can be defined by a complete undirected graph [figure omitted; refer to PDF] with vertex set [figure omitted; refer to PDF] and edge set [figure omitted; refer to PDF] . Vertex [figure omitted; refer to PDF] represents a depot (with no demand) at which a fleet of [figure omitted; refer to PDF] identical vehicles of capacity [figure omitted; refer to PDF] is located; vertices [figure omitted; refer to PDF] correspond to customers. Let [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is a set of scenarios with respect to total demand and transportation cost. [figure omitted; refer to PDF] refers to the number of scenarios. A scenario [figure omitted; refer to PDF] is a realisation of total demand for all customers and the transportation cost for each route.

We introduced a cost function [figure omitted; refer to PDF] , a demand function [figure omitted; refer to PDF] , and a set of vehicles [figure omitted; refer to PDF] . The transportation cost [figure omitted; refer to PDF] of an edge [figure omitted; refer to PDF] is a realisation of transportation cost between customers [figure omitted; refer to PDF] and [figure omitted; refer to PDF] from scenario [figure omitted; refer to PDF] . It was supposed to be nonnegative. The costs [figure omitted; refer to PDF] were assumed to be symmetric (although the results can easily be modified to hold even in asymmetric cases) and they satisfied the triangle inequality. [figure omitted; refer to PDF] is a realisation of the demand of customer [figure omitted; refer to PDF] from scenario [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] is serviced by more than one vehicle. The total demand from scenario [figure omitted; refer to PDF] is [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is a random variable relating to [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is a random variable with respect to [figure omitted; refer to PDF] . The probability of scenario [figure omitted; refer to PDF] is [figure omitted; refer to PDF] [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .

Suppose that the total demand in a scenario is known before the vehicle begins its route; then operators attach primary importance to the expected value of total transportation cost with regard to a failure scenario on the condition of coexistence of failure and successful scenarios. The vehicle routing problem with demand and cost uncertainty consists of finding a set of [figure omitted; refer to PDF] routes, minimizing the sum of the cost threshold and risk of potentially high costs in the presence of a failure scenario and satisfying the following conditions.

(1) Each client is assigned to, at least, one route.

(2) The demand [figure omitted; refer to PDF] of every customer is totally satisfied and can be serviced by more than one vehicle.

(3) Each route must begin and end at the depot and visits at least one customer.

(4) The total demand serviced by any vehicle does not exceed its capacity.

3.3. Formulation of CE-SDROA for the Proposed Problem

3.3.1. Optimisation Objective

The total transportation cost of a solution [figure omitted; refer to PDF] due to scenario [figure omitted; refer to PDF] can be represented by [figure omitted; refer to PDF]

[figure omitted; refer to PDF] is a random variable with respect to [figure omitted; refer to PDF] . Considering a feasible solution [figure omitted; refer to PDF] , the expected value of the total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios is [figure omitted; refer to PDF]

To simplify the process, let [figure omitted; refer to PDF] . Equation (2) refers to the expected total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios.

3.3.2. Reference Level of CE

[figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) is a reference level of (2). Thus, [figure omitted; refer to PDF] is a reference point from which deviation was measured. Besides [figure omitted; refer to PDF] , [figure omitted; refer to PDF] can reflect some matters of concern to decision makers at the depot, such as bidding ( [figure omitted; refer to PDF] ) and capital budget situations ( [figure omitted; refer to PDF] ).

3.3.3. The Robustness Measure

The potential risk of the total transportation cost caused by demand and transportation cost uncertainty is defined as follows.

Definition 1.

Potential risk with respect to a solution [figure omitted; refer to PDF] caused by sources of uncertainty is expressed as [figure omitted; refer to PDF]

The robustness measure of CE-SDROA is defined by [figure omitted; refer to PDF]

In (4), [figure omitted; refer to PDF] denotes the level of concern about exceeding [figure omitted; refer to PDF] . [figure omitted; refer to PDF] protects against potential scenarios that can incur extremely high costs.

3.3.4. Formulation

Combining (2) and (4), we provided the following mixed integer programming formulation for the proposed problem. The notations were as follows:

: [figure omitted; refer to PDF] is a boolean variable which is equal to 1 if vehicle [figure omitted; refer to PDF] travels directly from [figure omitted; refer to PDF] to [figure omitted; refer to PDF] and to 0 otherwise;

: [figure omitted; refer to PDF] is the quantity of the demand of [figure omitted; refer to PDF] delivered by the [figure omitted; refer to PDF] th vehicle;

: [figure omitted; refer to PDF] is a sufficiently large constant.

The CE-SDROA for the proposed problem can now be formulated as follows.

(CE-SDROA) Minimise [figure omitted; refer to PDF] subject to [figure omitted; refer to PDF]

Constraints (6)-(8) are the classical routing constraints: constraints (6) impose that each vertex is visited at least once, (7) are the flow conservation constraints, and (8) are the subtours elimination constraints. Constraints (9)-(11) concern the allocation of the demands of the customers among the vehicles: constraints (9) impose that customer [figure omitted; refer to PDF] can be served by vehicle [figure omitted; refer to PDF] only if [figure omitted; refer to PDF] passes through [figure omitted; refer to PDF] . Constraints (10) ensure that the entire demand of each vertex is satisfied while constraints (11) impose that the quantity delivered by each vehicle does not exceed the capacity.

3.3.5. Solution Method

Let [figure omitted; refer to PDF] be a unique integer [figure omitted; refer to PDF] such that [figure omitted; refer to PDF] . This integer [figure omitted; refer to PDF] is the integer part of [figure omitted; refer to PDF] .

[figure omitted; refer to PDF] is expressed as follows: [figure omitted; refer to PDF]

[figure omitted; refer to PDF] can be constructed as follows.

Given an instance [figure omitted; refer to PDF] of CE-SDROA, one is able to build a reduced instance which denotes [figure omitted; refer to PDF] by modifying the demand [figure omitted; refer to PDF] of each customer to [figure omitted; refer to PDF] . A solution [figure omitted; refer to PDF] for [figure omitted; refer to PDF] can be transformed into a solution [figure omitted; refer to PDF] for [figure omitted; refer to PDF] by adding [figure omitted; refer to PDF] direct trips for each customer. Now, given instance [figure omitted; refer to PDF] of CE-SDROA, an algorithm (genetic algorithm, tabu search, etc.) that first determines an optimal solution [figure omitted; refer to PDF] for the reduced instance [figure omitted; refer to PDF] was considered, and then the associated solutions [figure omitted; refer to PDF] for [figure omitted; refer to PDF] were built.

We use Nazif's algorithm [29] to determine [figure omitted; refer to PDF] for the reduced instance [figure omitted; refer to PDF] . The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost.

According to the definition of [figure omitted; refer to PDF] , [figure omitted; refer to PDF] satisfies all demands in [figure omitted; refer to PDF] . The method stated that solving CE-SDROA for the proposed problem was no more difficult than solving a single deterministic SDVRP while satisfying all demands in [figure omitted; refer to PDF] . The solution method is not described in detail here because it was not the focus of this paper.

4. Relationship between the Proposed CE-SDROA and E-SDROA

Proposition 2.

If all realisations of the total demand exceeded [figure omitted; refer to PDF] , then E-SDROA (see Appendix) becomes a special case of CE-SDROA given by setting [figure omitted; refer to PDF] .

Proof.

If all realisations of the total demand exceeded [figure omitted; refer to PDF] , then [figure omitted; refer to PDF] : [figure omitted; refer to PDF]

Then, [figure omitted; refer to PDF]

CE-SDROA becomes [figure omitted; refer to PDF]

Hence, Proposition 2 holds.

Proposition 2 indicated that E-SDROA was a special case of CE-SDROA in the situation where all realisations of the total demand exceeded [figure omitted; refer to PDF] .

5. Numerical Experiments

5.1. Introduction to Test Instances and Hardware Platform

We generated some new test instances derived from classical instances of SDVRP [5]. The name of each instance should allow one to rapidly determine its characteristics. In particular, the names have the form SDnnn - [figure omitted; refer to PDF] and are composed of three positional fields.

The first field of the name, nnn , is a three-digit integer that denotes the number of vertices in the problem graph, that is, including the depot vertex. The second field, kk , a two-digit integer, represents the number of scenarios. The last field of the name, [figure omitted; refer to PDF] , is an alphabetical character that identifies the test instances differing from other test instances for SDVRP with deterministic demands and transportation cost. The demand from each vertex and the transportation cost of each edge were generated according to their Poisson distributions, which had a mean value equal to the vertex demand and edge transportation cost, respectively [3]. The probability of a failure scenario arising was defined as follows: [figure omitted; refer to PDF]

It was obtained from [figure omitted; refer to PDF]

Simulations were carried out on a PC (Windows 7 operating system, Pentium CPU B950 running at 210 GHz, with 4 GHz internal memory) using CPLEX 12.1 software.

Demand and transportation uncertainty sets are defined as follows.

Transportation cost Uncertainty set [figure omitted; refer to PDF] . For each [figure omitted; refer to PDF] , the transportation cost [figure omitted; refer to PDF] takes values in [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] represents the maximum deviation from the nominal transportation cost [figure omitted; refer to PDF] . We introduce a nonnegative integer [figure omitted; refer to PDF] as a parameter for controlling the degree of robustness for the transportation cost uncertainties. Then, the uncertainty set of transportation cost data is given as [figure omitted; refer to PDF]

Demand Uncertainty set [figure omitted; refer to PDF] . For each customer [figure omitted; refer to PDF] , the demand [figure omitted; refer to PDF] takes values in [figure omitted; refer to PDF] ; where [figure omitted; refer to PDF] represents the maximum deviation from the nominal demand value [figure omitted; refer to PDF] . We introduce a nonnegative integer [figure omitted; refer to PDF] as a parameter for controlling the degree of robustness for the demand uncertainties. Then, the uncertainty set of demand data is given as [figure omitted; refer to PDF] The computational results of the Solomon problems are summarized in Table 1. The headings [figure omitted; refer to PDF] and [figure omitted; refer to PDF] refer to the degrees of robustness for the transportation cost and demand, which determine the uncertainty sets [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. The solutions with [figure omitted; refer to PDF] , [figure omitted; refer to PDF] are a nonrobust (deterministic) version of the problem and are used for comparison with robust aware solutions having [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . The numbers of vehicles to be used are shown under the headings [figure omitted; refer to PDF] using our solution method. The numbers of vehicles to be used are shown under the headings [figure omitted; refer to PDF] using robust optimization approach proposed by [7]. For all instances, we set [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . The asterisk ( [figure omitted; refer to PDF] ) indicates that the time limit (one hour) was reached.

Table 1: Results for the Augerat problems.

	[figure omitted; refer to PDF] , Λ	Time	opt
A-n32-k5	0, 0	3600*	1041
100, 100	3600*	1028
B-n34-k5	0, 0	3600*	827
100, 100	3600*	1023
A-n34-k5	0, 0	3600*	827
100, 100	3600*	1021
P-n19-k2	0, 0	3600*	261
100, 100	3600*	278
P-n22-k8	0, 0	3.727	612
100, 100	29.268	653
B-n39-k5	0, 0	3600*	639
100, 100	3600*	842
B-n31-k5	0, 0	3600*	696
100, 100	3600*	812

Table 1 reports the computational results for the Augerat problems. We see significant increments in the robustness of the solutions without much loss in solution quality.

5.2. Comparison between Optimal Solutions of CE-SDROA and E-SDROA

For the given parameters [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , we generated some scenarios using the scheme mentioned in Section 5.1 Table 1 shows the effect of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] on the optimal objective value and robustness measure. Headings opt and dev represent values of (5) and (3) with respect to SD096- [figure omitted; refer to PDF] . A series of robust optimal solutions can be generated as We changed the weighting parameters, [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . When we set [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , the model corresponded to, and focuses strictly on, the expected total transportation cost given that all realisations of the total demand exceeded [figure omitted; refer to PDF] . For illustrative purposes, we chose the solution corresponding to [figure omitted; refer to PDF] for further discussion, but a similar discussion could be framed with a different choice of [figure omitted; refer to PDF] . For [figure omitted; refer to PDF] , the robust optimal objective value was 11136.12. This implied that it was larger than the stochastic optimal objective value by 17.9% when [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . However, dev dropped by 17.2% relative to the stochastic optimal objective value when [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

Table 2 shows the relationship between the optimal objective values of CE-SDROA and E-SDROA. According to the formulation of E-SDROA for the proposed problem, the optimal objective value of the formulation was greater than or equal to the optimal objective value of the stochastic optimisation approach. Unlike the optimal objective value of E-SDROA, the optimal objective value of CE-SDROA was possibly better than that of the stochastic optimisation approach.

Table 2: Effect of [figure omitted; refer to PDF] and μ on optimal objective value and robustness measure for SD096-60^* .

[figure omitted; refer to PDF]	μ	opt	dev
0.6	0.1	7736.26	3566.85
0.7	0.2	7963.11	3419.80
0.8	0.3	8369.23	3180.24
0.9	0.4	8923.21	2832.48
1.0	0	9136.66	2615.06
1.1	0.6	11136.12	2165.45
1.2	0.7	10873.69	2016.27
1.3	0.8	14273.86	827.10
1.4	0.9	16523.82	2704.21
1.5	1	19216.39	2166.27

The results in Tables 2 and 3 showed that the optimal objective value of E-SDROA only paid attention to the level of concern about cost threshold ( [figure omitted; refer to PDF] ) being exceeded, while CE-SDROA for VRPU made a trade-off between the optimal objective value and the risk of potentially high costs with the aid of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

Table 3: Relationship between the optimal objective values of CE-SDROA and stochastic optimisation approach.

Test instances	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	opt
SD032-60*	0.6	0.1	1128.61 (<CE)
SD032-40*	0.7	0.2	876.32 (<CE)
SD048-60*	0.8	0.3	4972.36 (<CE)
SD064-35*	0.9	0.4	2931.27 (<CE)
SD080-50*	1.0	0.5	7527.63 (=CE)
SD120-40*	1.2	0.7	10873.69 (>CE)
SD144-30*	1.3	0.8	14273.86 (>CE)
SD160-30*	1.4	0.9	16523.82 (>CE)
SD240-30*	1.5	1	37216.39 (>CE)

5.3. Performance Analysis of Our Solution Method

In order to examine the performance of our solution method, PSO algorithm (determine [figure omitted; refer to PDF] for the reduced instance [figure omitted; refer to PDF] , and then the associated solutions [figure omitted; refer to PDF] for [figure omitted; refer to PDF] were built) and ant colony algorithm (determine [figure omitted; refer to PDF] for the reduced instance [figure omitted; refer to PDF] , and then the associated solutions [figure omitted; refer to PDF] for [figure omitted; refer to PDF] were built) are used for comparison with our solution method. GA is denoted as our solution method.

The search methods mentioned above have been programmed in MATLAB R2013a and have ran on an Intel(R) Core(TM) i5-3337U [email protected] GHz 8.00 GB-RAM.

It can be observed from Table 4 that the solution quality of our solution method is obviously better than PSO and ant colony algorithm. It can be explained that the crossover operator can enlarge the search space and improve the performance of PSO and Ant colony algorithm. Therefore, the crossover operator can ensure the better optimization.

Table 4: The computational results on 7 test instances.

Instance name	[figure omitted; refer to PDF] , [figure omitted; refer to PDF]	PSO	Ant colony algorithm	GA
A-n32-k5	150, 50	977	977	977
B-n34-k5	150, 50	1026	1045	1015
A-n34-k5	150, 50	1216	1210	1197
P-n19-k2	150, 50	625	636	597
P-n22-k8	150, 50	756	765	702
B-n39-k5	150, 50	1256	1253	1156
B-n31-k5	150, 50	1123	1101	997

6. Conclusion and Future Work

Unlike E-SDROA, CE-SDROA made a trade-off between the expected value of total transportation cost in all failure scenarios and its variation under conditions of the coexistence of failure and successful scenarios. Compared with stochastic optimisation approaches for VRPU, CE-SDROA dealt with the expected value of total transportation cost in all failure scenarios under conditions of the coexistence of failure and successful scenarios. The existence of this trade-off was intuitive, but the model provided a means of quantifying the trade-off and determining optimal choices for varying levels of risk acceptance. This provided a basis for improved decision making in a variety of situations.

We draw the following conclusions through theoretical analysis.

(1) Compared with stochastic optimisation approaches available, CE-SDROA made a trade-off between its cost threshold and accepting the risk of potentially high costs.

(2) E-SDROA failed to solve situations relevant to bidding or capital budget decisions. On the contrary, CE-SDROA considered these situations using a reference level of CE.

(3) Solving CE-SDROA for VRPU was no more difficult than solving a single deterministic SDVRP while satisfying all demands in a given bounded uncertainty set.

Although CE-SDROA for VRPU does present some significant improvements over E-SDROA as described above, there remained some problems to be addressed by future research. The optimal solution of CE-SDROA yielded extra inventory costs for some customers in some scenarios.

It is also worth considering the relationship of the current formulation to an explicit multistage dynamic optimization. The current model defines stages by types of decisions (i.e., fleet acquisition versus operational allocation). An alternative modeling approach might consider time stages, with both fleet acquisition and operational variables at each stage. This would make the model more similar to dynamic vehicle allocation models. This is also likely to be a useful effort for future research.

Acknowledgment

The authors are grateful to the anonymous reviewers for their valuable comments and suggestions which help improve the quality of the paper.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] T.-M. Choi, K. Govindan, L. Ma, "Logistics systems optimization under competition," Mathematical Problems in Engineering , vol. 2015, 2015.

[2] X. Duan, S. Song, J. Zhao, "Emergency vehicle dispatching and redistribution in highway network based on bilevel programming," Mathematical Problems in Engineering , vol. 2015, 2015.

[3] L. Berbotto, S. Garcia, F. J. Nogales, "A randomized granular tabu search heuristic for the split delivery vehicle routing problem," Annals of Operations Research , vol. 222, no. 1, pp. 153-173, 2014.

[4] C. Archetti, M. G. Speranza, A. Hertz, "A tabu search algorithm for the split delivery vehicle routing problem," Transportation Science , vol. 40, no. 1, pp. 64-73, 2006.

[5] S. Chen, B. Golden, E. Wasil, "The split delivery vehicle routing problem: applications, algorithms, test problems, and computational results," Networks , vol. 49, no. 4, pp. 318-329, 2007.

[6] J. C. Goodson, J. W. Ohlmann, B. . Thomas, "Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand," European Journal of Operational Research , vol. 217, no. 2, pp. 312-323, 2012.

[7] C. Novoa, R. Storer, "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research , vol. 196, no. 2, pp. 509-515, 2009.

[8] A. L. Erera, J. C. Morales, M. Savelsbergh, "The vehicle routing problem with stochastic demand and duration constraints," Transportation Science , vol. 44, no. 4, pp. 474-492, 2010.

[9] I. Sungur, F. Ordoñez, M. Dessouky, "A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty," IIE Transactions , vol. 40, no. 5, pp. 509-523, 2008.

[10] G. F. List, B. Wood, L. K. Nozick, M. A. Turnquist, D. A. Jones, E. A. Kjeldgaard, C. R. Lawton, "Robust optimization for fleet planning under uncertainty," Transportation Research Part E: Logistics and Transportation Review , vol. 39, no. 3, pp. 209-227, 2003.

[11] R. Montemanni, J. Barta, M. Mastrolilli, L. M. Gambardella, "The robust traveling salesman problem with interval data," Transportation Science , vol. 41, no. 3, pp. 366-381, 2007.

[12] C. E. Gounaris, W. Wiesemann, C. A. Floudas, "The robust capacitated vehicle routing problem under demand uncertainty," Operations Research , vol. 61, no. 3, pp. 677-693, 2013.

[13] C. Lee, K. Lee, S. Park, "Robust vehicle routing problem with deadlines and travel time/demand uncertainty," Journal of the Operational Research Society , vol. 63, no. 9, pp. 1294-1306, 2012.

[14] J. M. Mulvey, R. J. Vanderbei, S. A. Zenios, "Robust optimization of large-scale systems," Operations Research , vol. 43, no. 2, pp. 264-281, 1995.

[15] T. Yao, S. R. Mandala, B. D. Chung, "Evacuation transportation planning under uncertainty: a robust optimization approach," Networks and Spatial Economics , vol. 9, no. 2, pp. 171-189, 2009.

[16] A. L. Erera, J. C. Morales, M. Savelsbergh, "Robust optimization for empty repositioning problems," Operations Research , vol. 57, no. 2, pp. 468-483, 2009.

[17] B. D. Chung Robust and dynamic models for supply chain and transportation networks [Ph.D. dissertation] , The Pennsylvania State University, 2010.

[18] B. D. Chung, T. Yao, C. Xie, A. Thorsen, "Robust optimization model for a dynamic network design problem under demand uncertainty," Networks and Spatial Economics , vol. 11, no. 2, pp. 371-389, 2011.

[19] M. Najafi, K. Eshghi, W. Dullaert, "A multi-objective robust optimization model for logistics planning in the earthquake response phase," Transportation Research Part E: Logistics and Transportation Review , vol. 49, no. 1, pp. 217-249, 2013.

[20] A. Agra, M. Christiansen, R. Figueiredo, L. M. Hvattum, M. Poss, C. Requejo, "The robust vehicle routing problem with time windows," Computers & Operations Research , vol. 40, no. 3, pp. 856-866, 2013.

[21] J. M. Mulvey, A. Ruszczynski, "A new scenario decomposition method for large-scale stochastic optimization," Operations Research , vol. 43, no. 3, pp. 477-490, 1995.

[22] M. Naumann, L. Suhl, S. Kramkowski, "A stochastic programming approach for robust vehicle scheduling in public bus transport," Procedia-Social and Behavioral Sciences , vol. 20, pp. 826-835, 2011.

[23] S. Yan, C.-H. Tang, "An integrated framework for intercity bus scheduling under stochastic bus travel times," Transportation Science , vol. 42, no. 3, pp. 318-335, 2008.

[24] S. Yang, S. Rui, H. Shiwe, "Robust optimization for transit timetable design under stochastic demands," System Engineering Theory and Practice , vol. 31, no. 5, pp. 986-992, 2011.

[25] H. Markowitz, "Portfolio selection," The Journal of Finance , vol. 7, no. 1, pp. 77-91, 1952.

[26] Y. Yan, Q. Meng, S. Wang, X. Guo, "Robust optimization model of schedule design for a fixed bus route," Transportation Research Part C: Emerging Technologies , vol. 25, pp. 113-121, 2012.

[27] I. Sungur, Y. Ren, F. Ordoñez, M. Dessouky, H. Zhong, "A model and algorithm for the courier delivery problem with uncertainty," Transportation Science , vol. 44, no. 2, pp. 193-205, 2010.

[28] L. Sun, X. Y. Wang, "A robust optimization model based on conditional expectation for vehicle routing problem with stochastic demands," International Journal of Applied Mathematics and Statistics , vol. 41, no. 11, pp. 157-162, 2013.

[29] H. Nazif, L. S. Lee, "Optimised crossover genetic algorithm for capacitated vehicle routing problem," Applied Mathematical Modelling , vol. 36, no. 5, pp. 2110-2117, 2012.

Appendix

Appendix

A. Preliminary Introduction of E-SDROA for VRP under Uncertainty

A.1. Optimisation Objective

Let [figure omitted; refer to PDF] be the probability of scenario [figure omitted; refer to PDF] occurring in [figure omitted; refer to PDF] . Then, the expected value of the total transportation cost for all scenarios regarding solution [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , is [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . For the sake of brevity, let [figure omitted; refer to PDF] .

A.2. The Robustness Measure

If the values of the optimisation objective for different scenarios were higher than expected, they would then affect the minimisation of the total transportation cost. The robustness measure is given by [figure omitted; refer to PDF]

A.3. Formulation

By combining (A.1) and (A.2), the objective function of E-SDROA becomes [figure omitted; refer to PDF] where [figure omitted; refer to PDF] denotes the influence of the robustness measure on the optimisation objective, [figure omitted; refer to PDF] . There are many variants of E-SDROA for vehicle routing problems under uncertainty. As for the constraints and decision variables of a specific variant of E-SDROA, readers can directly refer to literatures [8, 20, 24].