1 Introduction

The Vehicle Routing Problem (VRP), introduced by Dantzig and Ramser (1959), involves the design of a set of minimum-cost routes for the vehicles of a logistics company. The routes must start at the depot, serve a group of geographically scattered customers, and finally return to the depot. Each customer can only be visited once by one single vehicle. The total demand of each route cannot exceed the capacity of the vehicle and the duration of each route cannot exceed a given limit. VRP has broad applications in distribution and logistics management fields. In the last 50 years, strides have been made in the development of efficient and effective solution algorithms using both exact and heuristic approaches (Laporte 2009). More than one hundred software companies are now selling commercial vehicle routing software and thousands of logistics companies are using VRP software (Drexl 2012).

In the literature, a number of VRP variants have been intensively studied (Toth and Vigo 2002; Golden et al. 2008; Leung et al. 2011; Norouzi et al. 2012; Yu et al. 2011; Escuín et al. 2012; Li et al. 2012). Vehicle routing problems with time windows (VRPTW) form a large proportion of the matters studied. One example is the request for a vehicle to start service within a given time interval (i.e. time window). The time window constraints can be modeled as either hard or soft. In the hard time window case, customers refuse the service of late arrival vehicles (Solomon 1987; Savelsbergh 1992; Cordeau et al. 2002; Nagata et al. 2009; Yu and Yang 2011). In the soft time window case, customers accept the vehicle service regardless of arrival time, but nonetheless penalties for earliness or tardiness are incurred (Koskosidis et al. 1992; Balakrishnan 1993; Taillard et al. 1997; Chiang and Russell 2004; Liberatore et al. 2011). In both the hard and soft cases, early arrival vehicles must wait until the customer’s requested service time arrives.

In most of VRP studies, the three elements including demand, customers and travel times are assumed to be deterministic. In reality, however, all these elements can be highly stochastic due to the complexity of the real logistics applications. For example, travel times in urban road networks are highly stochastic due to roadway capacity variations and traffic demand fluctuations (Lam et al. 2008; Chen et al. 2011, 2012; Li et al. 2012; Wei et al. 2012). Ignoring the stochastic nature of these elements may lead to sub-optimal even infeasible delivery solutions. In view of this, researchers have investigated the stochastic vehicle routing problem (SVRP) by considering stochastic demands and/or customers (Bertsimas and van Ryzin 1991; Gendreau et al. 1995; Laporte et al. 2002; Lei et al. 2011) and uncertain travel times (Laporte et al. 1992; Lambert et al. 1993; Kenyon and Morton 2003; Zhang et al. 2012).

Some researchers have also investigated SVRP with time windows under travel time uncertainties. Ando and Taniguchi (2006) studied SVRP with soft time window constraints. A model was proposed to minimize carrier’s total cost, which is comprised of the fixed vehicle employment cost, operating cost and penalty cost. The operating cost was assumed to be proportional to the total mean travel time, while the penalty cost was formulated as the expected earliness and tardiness of vehicles at customer locations. Travel time distributions were estimated from probe vehicle data.

Russell and Urban (2008) developed a multiple-objective model for SVRP with soft time window constraints. Priorities among different objectives were assumed in order of the number of required vehicles, total distance traveled and time-window penalties incurred. The model minimizes a weighted average of these objectives. A tabu search heuristics was developed to solve the model. To reduce the number of required vehicles, the fixed vehicle employment cost was multiplied by a large weighting parameter in the objective function. The earliness and tardiness penalties due to time window violation were deduced based on the assumption of Erlang travel time distributions.

Li et al. (2010) investigated SVRP in both the hard and soft time window cases. Uncertain service times were also considered. In the soft time window case, a two-stage stochastic programming with recourse model was built. The objective of the model is to design a set of routes in the first stage and to minimize the expected costs in the second stage when random travel and service times are realized. A tabu search heuristics was also developed to solve the model. Travel and service times were assumed to be normally distributed and stochastic simulation was used for probability check and computing expected values. In the hard time window case, a chance-constrained model was proposed to ensure that the probability of vehicles arriving at customers within the time windows is at least a pre-specified value. Expected earliness and tardiness of vehicles were not included in carrier’s total cost in the hard time window case.

On the basis of the previous works, this paper aims to investigate SVRP with soft time window constraints under travel and service time uncertainties. In the rest of the paper, the SVRP with soft time window constraints is referred to as SVRPSTW. The previous works is extended in the following two aspects.

  1. (1)

    A new stochastic programming model is proposed in this paper not only to minimize carrier’s total cost, but also to guarantee a minimum on-time arrival probability at each customer location. The previous SVRPSTW models mainly focused on reducing carrier’s total cost. This optimization approach is essentially formulated from the perspective of the carrier in order to provide shipment delivery service at minimum total cost. By this approach, the probability of late shipment delivery for some customers may be quite high. In practice, inventories are limited due to high holding costs and therefore production or sales processes may be disrupted by frequently delayed shipments. It is common for customers to require a certain probability of on-time shipment delivery, though late service is at times permitted. In this paper, the on-time arrival probability at each customer location is explicitly formulated in the proposed model by the introduction of a customer service level constraint. The probability of on-time shipment delivery to each customer can be then ensured. The advantages of the proposed model are listed below.

    • The proposed model is a generalization of the conventional recourse models for SVRPSTW in the literature (Russell and Urban 2008; Li et al. 2010). When no customer service level constraint is imposed, solutions of the proposed model are the same as the previous SVRPSTW models.

    • The proposed model provides an easy way of exploring trade-offs between carrier’s total cost and customer service level, simply by adjusting the customer service level constraints.

    • The proposed model can easily be adapted to multi-class customers with various service level preferences by imposing appropriate customer service level constraints.

  2. (2)

    An iterated tabu search heuristic algorithm is developed to solve the proposed model. A route reduction mechanism is designed and incorporated in the developed heuristics. When performing a neighborhood search, trial move costs that remain unchanged in one iteration are kept in the memory for use in the next iteration. On the basis of these cost records, every route that can be decomposed and inserted into other routes is identified in an SVRPSTW solution. In this way, the number of routes can be reduced. Additionally, inspired by Miller-Hooks and Mahmassani (1998) and Chen et al. (unpublished), an approximation method called α-discrete is proposed in this paper for generating arrival time distributions of vehicles in the presence of time windows. Using this approximation method, SVRPSTW solutions can be evaluated without suffering restrictions on the assumption of travel and service time distributions.

The remainder of this paper is organized as follows. The proposed model is formulated in the following section. The iterative tabu search heuristics designed for solving the proposed model is presented in Section 3. The approximation method for estimating arrival time distributions is described in Section 4. Computational results are shown in Section 5. Finally, concluding remarks are given in Section 6.

2 Model Formulation

Let G = (V 0, A) be a complete digraph, where V 0 = {0, …, n} is the vertex set and A = {(i,j) : i, j ∈ V 0, i ≠ j} is the arc set. Vertex 0 represents the depot where m 0 identical vehicles with capacity Q are available. The customer set is denoted as \( \mathbf{V}=\mathbf{V}0/\left\{0\right\}=\left\{1,\dots, n\right\} \). Each customer i ∊ V has a nonnegative demand q i , a service time S i and a time window [e i , l i ]. It is expected that service at customer i begins within [e i , l i ]. If the vehicle arrives at customer i’s location before e i , it has to wait until e i ; if it arrives at customer i’s location after l i , a penalty proportional to the lateness must be paid. A time window [e 0, l 0] is also associated with the depot, where e 0 represents the earliest possible departure time from the depot and l 0 represents the latest possible arrival time at the depot. A travel time T ij is associated with each arc (i, j) ∊ A. Both T ij and S i are random variables with distributions assumed to be known and independent of everything else. Additional assumptions are: Q ≥ q i , i ∊ V (i.e. each vehicle can serve at least one customer) and m 0 is big enough (i.e. there are sufficient vehicles at the depot). Additional notation is listed as follows:

M :

a sufficiently large number

f :

fixed cost of employing one vehicle

m :

number of required vehicles in a feasible solution, m ≤ m 0

m * :

number of required vehicles in the optimal solution, m * ≤ m

K :

the set of required vehicles in a feasible solution, K = {1, 2, …, m}

x ijk :

a binary variable associated with each arc (i, j) ∊ A. It is equal to 1 if and only if arc (i, j) is traversed by vehicle k and 0 otherwise, k ∊ K

R k :

route k defined as \( {\mathbf{R}}_k=\left\{{r}_0=0,{r}_1,\dots, {r}_j,{r}_{j+1},\dots, {r}_{n_k},{r}_{n_k+1}=0\right\} \), where n k is the number of customers assigned to vehicle k, r j  ∊ V 0, 0 ≤ j ≤ n k  + 1, k ∊ K

\( {A}_{r_jk} \) :

arrival time of vehicle k at vertex r j ’s location, r j  ∊ R k , 1 ≤ j ≤ n k  + 1, k ∊ K

\( {T}_{r_jk}^{ss} \) :

service start time of vehicle k at customer r j , r j  ∊ R k , 1 ≤ j ≤ n k , k ∊ K

d 0k :

departure time of vehicle k from the depot, k ∊ K

\( {D}_{r_jk} \) :

departure time of vehicle k from customer r j ’s location, r j  ∊ R k , 1 ≤ j ≤ n k , k ∊ K

\( {W}_{r_jk} \) :

earliness (waiting time) of vehicle k at customer r j ’s location, r j  ∊ R k , 1 ≤ j ≤ n k , k ∊ K

\( {P}_{r_jk} \) :

tardiness of vehicle k at vertex r j ’s location, r j  ∊ R k , 1 ≤ j ≤ n k  + 1, k ∊ K

B k :

duration of route k, k ∊ K

h :

upper bound of the duration of each route

Z k :

excess route duration for vehicle k, k ∊ K

λ 1i :

penalty coefficient for earliness at customer i’s location, i ∊ V

λ 2i :

penalty coefficient for tardiness at customer i’s location, i ∊ V

λ 2,0 :

penalty coefficient for tardiness when a vehicle returns to the depot

λ 3 :

penalty coefficient for excess route duration

α i :

required probability of on-time shipment delivery (i.e. required service level) by customer i, i ∊ V

α 0 :

required on-time arrival probability when a vehicle returns to the depot

β :

required probability that duration of each route is smaller than h.

The stochastic programming model for SVRPSTW proposed in this paper is given below.

Min

$$ Mf\cdot m+{\displaystyle \sum_{\left(i,j\right)\in \mathbf{A}}{\displaystyle \sum_{k\in \mathbf{K}}\mathrm{E}\left({T}_{ij}\right){x}_{ij k}}}+{\displaystyle \sum_{k\in \mathbf{K}}\left({\displaystyle \sum_{j=1}^{n_k}{\lambda}_{1{r}_j}\mathrm{E}\left({W}_{r_jk}\right)}+{\displaystyle \sum_{j=1}^{n_k+1}{\lambda}_{2{r}_j}\mathrm{E}\left({P}_{r_jk}\right)}+{\lambda}_3\mathrm{E}\left({Z}_k\right)\right)} $$
(1)

Subject to

$$ {\displaystyle \sum_{j\in {\mathbf{V}}_0}{\displaystyle \sum_{k\in \mathbf{K}}{x}_{ijk}}}=1,\kern0.9em \forall i\in \mathbf{V} $$
(2)
$$ {\displaystyle \sum_{j\in \mathbf{V}}{x}_{0 jk}}=1,\kern0.9em \forall k\in \mathbf{K} $$
(3)
$$ {\displaystyle \sum_{i\in \mathbf{V}}{x}_{i0k}}=1,\kern0.9em \forall k\in \mathbf{K} $$
(4)
$$ {\displaystyle \sum_{i\in {\mathbf{V}}_0}{x}_{ijk}}-{\displaystyle \sum_{i\in {\mathbf{V}}_0}{x}_{jik}}=0,\kern0.9em \forall j\in \mathbf{V},\kern0.3em k\in \mathbf{K} $$
(5)
$$ {\displaystyle \sum_{i\in \mathbf{V}}{q}_i{\displaystyle \sum_{j\in {\mathbf{V}}_0}{x}_{ijk}}}\le Q,\kern0.9em \forall k\in \mathbf{K} $$
(6)
$$ \mathrm{P}\left\{{A}_{r_jk}\le {l}_{r_j}\right\}\ge {\alpha}_{r_j},\kern0.9em \forall {r}_j\in {\mathbf{R}}_k,1\le j\le {n}_k+1,k\in \mathbf{K} $$
(7)
$$ \mathrm{P}\left\{{B}_k\le h\right\}\ge \beta, \kern0.8em \forall k\in \mathbf{K} $$
(8)
$$ {x}_{ijk}=\left\{0,1\right\},\kern1em \forall i,j\in {\mathbf{V}}_0,\kern0.3em k\in \mathbf{K} $$
(9)

The objective function Eq. (1) consists of three parts: 1. fixed vehicle employment cost, 2. total mean travel time as the operating cost, and 3. weighted expected earliness, tardiness and excess route duration as penalty cost. \( {W}_{r_jk} \), \( {P}_{r_jk} \) and Z k are given in Eqs. (10), (11) and (13) respectively. Illustrations of the penalty coefficients λ 1i and λ 2i , i ∊ V can be found in Fig. 1. The proposed model has a hierarchical optimization objective: the primary objective is to minimize the number of required vehicles to satisfy constraints (2) to (9); the secondary objective is to minimize the operating and penalty costs given the minimized number of vehicles m. This hierarchical optimization objective implies that one SVRPSTW solution with fewer routes but higher operating and penalty costs is better than another with more routes but lower operating and penalty costs.

Fig. 1
figure 1

Time window [e i , l i ] and arrival time A ik of vehicle k at customer i′s location

Full size image
$$ {W}_{r_jk}= \max \left\{{e}_{r_j}-{A}_{r_jk},0\right\},\kern1em {r}_j\in {\mathbf{R}}_k,\kern0.3em 1\le j\le {n}_k,\kern0.3em k\in \mathbf{K} $$
(10)
$$ {P}_{r_jk}= \max \left\{{A}_{r_jk}-{l}_{r_j},0\right\},\kern0.9em {r}_j\in {\mathbf{R}}_k,\kern0.3em 1\le j\le {n}_k+1,\kern0.3em k\in \mathbf{K} $$
(11)
$$ {B}_k={T}_{r_0{r}_1}+{\displaystyle \sum_{j=1}^{n_k}\left({W}_{r_jk}+{S}_{r_j}+{T}_{r_j{r}_{j+1}}\right)},\kern0.9em {r}_j\in {\mathbf{R}}_k,\kern0.3em k\in \mathbf{K} $$
(12)
$$ {Z}_k= \max \left\{{B}_k-h,0\right\},\kern0.9em k\in \mathbf{K} $$
(13)

Equation (2) indicates that each customer must be visited exactly once by one vehicle. Equations (3) and (4) ensure that each vehicle starts and ends its route at the depot. Equation (5) ensures that each vehicle departs from a customer location after it visits the customer. Equation (6) is the capacity constraint. Equation (7) is the customer service level constraint and ensures that the probability of on-time shipment delivery (i.e. service level) to each customer is at least a predefined value α i (i.e. required service level). Similarly, when a vehicle returns to the depot, the on-time arrival probability at the depot must be larger than a threshold α 0. The required service level of each customer can be adjusted according to practical requests. Equation (8) ensures that each route is completed within h with at least probability β. If α i in Eq. (7) and β in Eq. (8) are set to zero, the proposed model then reduces to the conventional recourse models for SVRPSTW (Russell and Urban 2008; Li et al. 2010). Equation (9) defines the domain of the decision variables.

Figure 1 shows the relationship between the time window specified by customer i and possible arrival times of vehicle k. If the vehicle arrives earlier (later) than e i (l i ), an earliness (tardiness) penalty cost will then be incurred with unit earliness (tardiness) penalized by λ 1i (λ 2i ). The probability density functions (PDF) of three possible vehicle arrival times are also shown in Fig. 1. In deterministic cases, arrival times μ 1 and μ 2 may be accepted because both lie within the time window. While under travel time uncertainties, arrival times with PDF1 and PDF2 might not be accepted since PDF1 can possibly lead to a long waiting time and PDF2 may result in a large late arrival probability. In this sense, it is reasonable and necessary to incur an earliness penalty cost and to impose a constraint on the vehicle’s minimum on-time arrival probability.

In the proposed model, objective function Eq. (1) represents carrier’s total cost and constraint Eq. (7) guarantees customers’ required service level. In order to highlight the primary optimization objective of the proposed model, fixed vehicle employment cost is multiplied by a sufficiently large number M in Eq. (1). By adjusting α i , i ∊ V in Eq. (7), various trade-offs between carrier’s total cost and customer service level can be obtained.

An alternative way to trade off between carrier’s total cost and customer service level is to adjust the penalty coefficient λ 2i , i ∊ V in Eq. (1), without imposing any customer service level constraint as Eq. (7). If M in Eq. (1) is a moderate number, λ 2i can be then increased to a level such that tardiness penalty cost is comparable to the fixed vehicle employment cost. In this way the trade-off between cost and service can also be found. However, the increase of λ 2i may be irrational as fixed cost of employing one vehicle is usually much larger than the unit penalty cost (e.g. 1000 versus 0.5 in Russell and Urban 2008). Irrational increase of λ 2i may lead to unrealistic cost coefficients and even irrational routing solutions (Koskosidis et al. 1992). Compared with this method, the proposed model in this paper provides a more straightforward way of achieving the goal of exploring trade-offs between carrier’s total cost and customer service level. The probability of on-time arrival to each customer is explicitly formulated in the proposed model and guaranteed by customer service level constraints. This has a clear implication in practical applications.

3 Solution Algorithm

In this section, a heuristic algorithm based on an iterated tabu search (ITS) by Cordeau and Maischberger (2012) is developed for solving the proposed model. In ITS, an iterated local search (Lourenço et al. 2002) is used as the general framework and a tabu search is adopted as the local search improvement method. The major strengths of ITS are simplicity, flexibility and efficiency. The neighborhood structure of the tabu search heuristics in ITS is simple and a single type of solution perturbation is adopted. ITS is also flexible as it can solve many VRP variants without changing the methodology and parameter settings. Finally, ITS is reasonably fast and effective. Cordeau and Maischberger (2012) reported solving classical VRP and seven VRP variants by using ITS, and showed the competitiveness of ITS with other heuristics for each particular problem variant.

The heuristic algorithm developed in this section is a modified version of ITS, denoted as SVRP-ITS. Minor extensions of ITS are made in SVRP-ITS: (a) a direct route reduction mechanism is incorporated in SVRP-ITS, aiming to reduce the number of required vehicles in a SVRPSTW solution; (b) when performing a neighborhood search, trial move costs that remain unchanged in one iteration are kept in the memory for use in the next iteration. These cost records can be used to avoid possible repetitive computing in both neighborhood search and route reduction processes. In the following sections, the main framework of SVRP-ITS is shown first, followed by brief descriptions of each component.

3.1 Main Framework of SVRP-ITS

The main framework of SVRP-ITS is summarized in Algorithm SVRP-ITS. Firstly a feasible initial solution s 0 is constructed (Section 3.2). In each iteration of SVRP-ITS, tabu search (Section 3.3) is then used to improve the current solution s′, resulting in an improved solution \( \tilde{s} \). The best feasible solution s * is updated accordingly. Before the start of the next iteration, s′ is renewed employing a perturbation mechanism (Section 3.5). If \( \tilde{s} \) satisfies the acceptance criterion (Section 3.4), \( \tilde{s} \) is then perturbed, otherwise s * is perturbed. Let η be the maximum number of tabu search iterations allowed to be performed during the entire search process of SVRP-ITS. ζ represents the total number of tabu search iterations performed so far. SVRP-ITS stops if ζ is larger than η. Note that a tabu search iteration denotes an iteration within a tabu search process (see Step 2 in Procedure Tabu Search); c(s) is set to the objective function Eq. (1).

figure a

3.2 Initial Solution Construction

In ITS (Cordeau and Maischberger 2012), an initial solution with m * + 1 routes was constructed for a benchmark problem, where m * is the number of routes in the best known solution of the benchmark problem. For SVRPSTW, no benchmark problem exists and m * is unavailable. Alternatively, Solomon’s Insertion heuristics (Solomon 1987) is used to construct an initial solution for SVRP-ITS. Both the two criteria c 1(i, u, j) and c 2(i, u, j) in Solomon (1987) are set to c(s) in SVRP-ITS. The resulting initial solution is feasible and the number of routes in the initial solution is an upper bound of m * .

3.3 Tabu Search

The tabu search heuristics employed in SVRP-ITS is summarized in the Procedure Tabu Search. The input solution s′ (may be infeasible) is inherited from Step 2.1 in Algorithm SVRP-ITS. At the beginning of each tabu search iteration, route reduction procedure (Section 3.3.6) is performed on the current solution s. If the procedure fails, the best non-tabu neighborhood solution \( \overline{s} \) in N(s) (Section 3.3.1) is selected to renew s, considering tabu tenure and aspiration criterion (Section 3.3.4). \( \overline{s} \) may deteriorate compared with s. Let ζ 1 be the number of consecutive iterations in which \( \tilde{s} \) has not been improved. The tabu search stops if the best feasible solution \( \tilde{s} \) has not been improved for η 1 consecutive iterations.

figure b

3.3.1 Neighborhood Structure

A neighborhood solution of s is constructed by removing a customer from its original route and then inserting it into another route. This process is performed on every customer in s and the neighborhood N(s) is then obtained. When a customer is removed, its original route is reconstructed by connecting the predecessor and successor vertices of the customer. The customer is inserted into another route with minimum increase in the value of f(s) (Section 3.3.2).

The definition of attribute was used in Cordeau et al. (2001). If customer i is assigned to vehicle k in solution s, then s is said to have an attribute (i, k) and all the attributes of s form the attribute set B(s). The generation of a neighborhood solution of s is just the substitution of one attribute in B(s) with a new attribute.

3.3.2 Solution Evaluation

To diversify the search, capacity, route duration and customer service level constraints are relaxed during the tabu search, with their violations penalized in the objective function. The augmented objective function is f(s) = c(s) + γ 1 q(s) + γ 2 d(s) + γ 3 w(s), where q(s), d(s) and w(s) are violations of capacity, route duration and customer service level constraints respectively. γ 1, γ 2 and γ 3 are three parameters adjusted dynamically. These parameters are initially set to 1 and any one of them is divided by 1 + δ if the corresponding constraint is satisfied, otherwise it is multiplied by 1 + δ. δ is set to 0.5 in SVRP-ITS. Different from Cordeau et al. (2001), γ 1, γ 2 and γ 3 are restricted in the interval [10−4, 104] in SVRP-ITS. A similar restriction was applied by Brandão (2004).

3.3.3 Diversification

Consider a move that substitutes attribute (i, k′) with (i, k) in B(s). To direct the search into less explored search space, if this move generates a non-improving neighborhood solution \( \overline{s} \) with respect to s, then \( \overline{s} \) is penalized by a term proportional to the frequency (ρ ik ) that attribute (i, k) is added into the current solution in the tabu search process. The penalty term is \( p\left(\overline{s}\right)=0.015c\left(\overline{s}\right)\sqrt{ nm}{\rho}_{ik} \). The new evaluation function for \( \overline{s} \) is \( g\left(\overline{s}\right)=f\left(\overline{s}\right)+p\left(\overline{s}\right) \), \( p\left(\overline{s}\right)=0 \) if \( f\left(\overline{s}\right)<f(s) \).

3.3.4 Tabu Tenure and Aspiration Criterion

To prevent cycling, moves that lead to previously encountered solutions are forbidden for a number of iterations. For example, if attribute (i, k′) is replaced with (i, k) in a particular move and the resulting solution \( \overline{s} \) is selected to renew s for the next iteration, (i, k′) is then assigned a tabu status and can not be added to the current solution for the next θ iterations. θ is set to [7.5log10 n], where [x] is the integer nearest to x. In following iterations, if a move adding attribute (i, k′) to B(s) leads to a better solution than the best solution so far identified having attribute (i, k′), the move is then allowed to be performed even if the tabu status of attribute (i, k′) still exists.

In SVRP-ITS, the aspiration criterion is further refined to account for both feasible and infeasible solutions. During the tabu search process, both the best feasible and infeasible solutions identified having attribute (i, k′) are recorded. If a move adding attribute (i, k′) results in a better feasible or infeasible solution, the tabu status of attribute (i, k′) can be then overridden.

3.3.5 Cost Records

In SVRP-ITS, cost records are used for storing the costs of removing each customer from its original route and inserting it into every possible position in another route. These costs can be used in both neighborhood search and route reduction processes. At the end of each tabu search iteration, only two routes in the current solution s will be changed. Therefore, only the costs related to the two changed routes need to be updated and the remainder can still be used in the next iteration. This mechanism aims to avoid possible repetitive computing and reduce the computational effort of SVRP-ITS.

Suppose that there are m routes in a particular solution and n customers in total. On average there will be n/m customers per route. If no mechanism such as cost records exists, then approximately n ⋅ (n/m) ⋅ (m − 1) trial moves need to be evaluated in each tabu search iteration. If a mechanism such as cost records is adopted, about n ⋅ (n/m) ⋅ 2 trial moves then need to be evaluated in each iteration. When m is larger than 3, a reduction of about n ⋅ (n/m) ⋅ (m − 3) in computing occurs. For SVRPSTW with customer service level constraints in this paper, it is normal for m to be larger than 3. A similar mechanism can be found in Brandão (2004) and the author reported a reduction of at least 30 % of the computational effort using this mechanism.

3.3.6 Route Reduction

The original ITS does not have a direct mechanism to minimize the number of routes (Cordeau and Maischberger 2012). The performance of ITS in solving VRPTW was tested on Solomon’s benchmark problems (Solomon 1987), for which best known solutions exist in the literature. The number of routes m * in these best known solutions was utilized in ITS for solving the benchmark problems. With this useful information of m * , the authors provided an indirect route reduction mechanism in ITS. Details can be found in Cordeau and Maischberger (2012).

For SVRPSTW, no benchmark problem exists in the literature and the information of m * is unavailable. The number of routes in an initial solution of SVRP-ITS is an upper bound of the optimal value m * (Section 3.2). To reduce the number of routes to m * in a SVRPSTW solution, a direct route reduction mechanism for SVRP-ITS is developed in this section. With the use of cost records, the mechanism checks every route in each tabu search iteration to find if all customers on that route can be removed and feasibly inserted into other routes. The mechanism is briefly described below and summarized in the Procedure Route Reduction.

The procedure begins with checking the feasibility of the input solution s, as an infeasible solution has little possibility of becoming a feasible one with fewer routes. The procedure then examines whether there is such a route that all customers on that route can be feasibly inserted into other routes. If such a route exists, then ways of inserting the customers are investigated and the one with the least cost is selected. Owing to cost records, this procedure does not need much computational effort. In most cases the procedure stops at an early stage because either, the input solution is found not feasible or the procedure fails to find a route that can be decomposed.

3.4 Solution Perturbation

In Step 2.3 of Algorithm SVRP-ITS, s′ is perturbed for a tabu search restart. More specifically, firstly a seed customer is selected at random. The seed customer and its π closest customers are then removed and reinserted into s′ with minimum cost in a random order, where \( \pi \sim U\left(0,\sqrt{n}\right) \). This cluster removal heuristics has the potential to prevent the removed customers from being reinserted into their original routes (Pisinger and Ropke 2007).

figure c

3.5 Acceptance Criterion

When performing solution perturbation, the improved solution \( \tilde{s} \) has a 1 − (ζ/η)2 probability of being the target to be perturbed. A second choice is the best feasible solution so far s * . At the early stage of SVRP-ITS, \( \tilde{s} \) is very likely to be selected and perturbed, aiming at exploring a broad solution space. As SVRP-ITS approaches the end, it will revert to s * .

4 Arrival Time Distribution Approximation

When evaluating a SVRPSTW solution s, (e.g. calculating c(s) and f(s) in Section 3.3.2), arrival time distributions of vehicles need to be computed first. Consider route R k for vehicle k, in the soft time window case, the arrival time \( {A}_{r_{j+1}k} \) of vehicle k at customer r j+1′s location can be recursively computed by Eqs. (14) to (17).

$$ {A}_{r_1k}={d}_{0k}+{T}_{r_0{r}_1} $$
(14)
$$ {T}_{r_jk}^{ss}= \max \left\{{A}_{r_jk},{e}_{r_j}\right\},\kern0.8em 1\le j\le {n}_k $$
(15)
$$ {D}_{r_jk}={T}_{r_jk}^{ss}+{S}_{r_j},\kern0.7em 1\le j\le {n}_k $$
(16)
$$ {A}_{r_{j+1}k}={D}_{r_jk}+{T}_{r_j{r}_{j+1}},\kern0.7em 1\le j\le {n}_k $$
(17)

For VRPTW, \( {A}_{r_{j+1}k} \) can be predicted deterministically. For SVRPSTW, determining the distribution of \( {A}_{r_{j+1}k} \) is difficult in the presence of time windows. In Chang et al. (2009), travel and arrival times of vehicles were assumed to be normally distributed. The mean and variance of departure time \( {D}_{r_jk} \) were estimated based on the distribution of \( \max \left\{{A}_{r_jk},{e}_{r_j}\right\}+{S}_{r_j} \). In Thompson et al. (2011), assumptions of normal distribution were also made. The mean and variance of arrival time distributions were estimated based on truncated normal distributions. Travel time distributions, however, are far from normal in some real-life cases (van Lint et al. 2008; Fosgerau and Karlström 2010). Methods based on normal assumptions may lead to large estimation errors in those particular cases. Even if travel times do follow normal distribution, arrival time distributions are not normal in the presence of time windows (Thompson et al. 2011). In the remainder of this section, the approximation method, α-discrete is presented as a new method for estimating vehicle arrival time distributions in the presence of time windows.

Take route R k for example. For travel time \( {T}_{r_j{r}_{j+1}} \), a set of L discrete points 0.5ε, 1.5ε, …, Lε − 0.5ε in the space of cumulative probability [0, 1] is considered, where ε = 1/L. Correspondingly, a sequence of discrete travel times \( {b}_{\tau}^{T_{r_j{r}_{j+1}}},\tau =1,\dots, L \) can be generated by Eq. (18), where F −1( ⋅ ) is the inverse cumulative distribution function (CDF) of \( {T}_{r_j{r}_{j+1}} \). The resulting approximated inverse CDF of \( {T}_{r_j{r}_{j+1}} \) is shown in Eq. (19). Distribution of service time \( {S}_{r_j} \) can be estimated in the same way as \( {T}_{r_j{r}_{j+1}} \).

$$ {b}_{\tau}^{T_{r_j{r}_{j+1}}}={F}^{-1}\left(\tau \epsilon -\frac{\epsilon }{2}\right),\kern0.9em \tau =1,\dots, L $$
(18)
$$ {v}^{T_{r_j{r}_{j+1}}}\left(\tau \epsilon \right)={b}_{\tau}^{T_{r_j{r}_{j+1}}},\kern0.9em \tau =1,\dots, L $$
(19)

Given departure time d 0k and distribution of \( {T}_{r_0{r}_1} \), distribution of arrival time \( {A}_{r_1k} \) in Eq. (14) can be computed as shown in Eq. (20).

$$ {v}^{A_{r_1k}}\left(\tau \epsilon \right)={b}_{\tau}^{T_{r_0{r}_1}}+{d}_{0k},\kern0.9em \tau =1,\dots, L $$
(20)

In Eq. (15), given \( {e}_{r_j} \) and distribution of \( {A}_{r_jk} \), distribution of \( {T}_{r_jk}^{ss} \) can be estimated using Eqs. (21) to (23).

$$ {v}^{T_{r_jk}^{ss}}\left(\tau \epsilon \right)={e}_{r_j},\kern0.9em \tau =1,\dots, L,\kern0.5em \mathrm{if}\kern0.2em {e}_{r_j}\ge {b}_L^{A_{r_jk}} $$
(21)
$$ {v}^{T_{r_jk}^{ss}}\left(\tau \epsilon \right)=\left\{\begin{array}{l}{e}_{r_j},\kern0.9em \tau =1,\dots, {\tau}_{erj}\\ {}{b}_{\tau}^{A_{r_jk}},\kern0.9em \tau ={\tau}_{erj}+1,\dots, L\end{array}\right.,\kern0.4em \mathrm{if}\kern0.2em {b}_{\tau_{erj}}^{A_{r_jk}}\le {e}_{r_j}<{b}_{\tau_{erj}+1}^{A_{r_jk}},\kern0.5em 1\le {\tau}_{erj}\le L-1 $$
(22)
$$ {v}^{T_{r_jk}^{ss}}\left(\tau \epsilon \right)={b}_{\tau}^{A_{r_jk}},\kern0.9em \tau =1,\dots, L,\kern0.5em \mathrm{if}\kern0.2em {e}_{r_j}<{b}_L^{A_{r_jk}} $$
(23)

In Eq. (16), based on distributions of \( {T}_{r_jk}^{ss} \) and \( {S}_{r_j} \), a set of L 2 discrete values \( {\overline{b}}_{\tau },\tau =1,\dots, {L}^2 \) can be generated using Eq. (24). Another set of discrete values b τ , τ = 1, …, L 2 can be obtained by sorting the elements in \( {\overline{b}}_{\tau },\tau =1,\dots, {L}^2 \) in an ascending order. Distribution of \( {D}_{r_jk} \) is then computed as shown in Eq. (25). Given distributions of \( {D}_{r_jk} \) and \( {T}_{r_j{r}_{j+1}} \), distribution of \( {A}_{r_{j+1}k} \) in Eq. (17) can be computed in the same way as \( {D}_{r_jk} \).

$$ {\overline{b}}_{\tau }={v}^{T_{r_jk}^{ss}}\left({\tau}_1\epsilon \right)+{v}^{S_{r_j}}\left({\tau}_2\epsilon \right),\kern0.9em {\tau}_1=1,\dots, L,\kern0.5em {\tau}_2=1,\dots, L,\kern0.4em \tau ={\tau}_1{\tau}_2 $$
(24)
$$ {v}^{D_{r_jk}}\left({\tau}_1\epsilon \right)\leftarrow \frac{1}{L}{\displaystyle \sum_{\tau_2=1}^L{b}_{\left({\tau}_1-1\right)L+{\tau}_2}},\kern0.8em {\tau}_1=1,\dots, L $$
(25)

Expected values \( \mathrm{E}\left({W}_{r_jk}\right) \), \( \mathrm{E}\left({P}_{r_jk}\right) \) and E(Z k ) in Eq. (1) can be estimated as shown in Eqs. (26), (27) and (28) respectively, given the distribution of \( {A}_{r_jk} \).

$$ \mathrm{E}\left({W}_{r_jk}\right)=\left\{\begin{array}{l}0,\kern0.9em \mathrm{if}\kern0.2em {e}_{r_j}<{b}_1^{A_{r_jk}}\\ {}{\displaystyle \sum_{\tau =1}^{\tau_{erj}}\epsilon \left({e}_{r_j}-{b}_{\tau}^{A_{r_jk}}\right)},\kern0.8em \mathrm{if}\kern0.2em {b}_{\tau_{erj}}^{A_{r_jk}}\le {e}_{r_j}<{b}_{\tau_{erj}+1}^{A_{r_jk}},\kern0.5em 1\le {\tau}_{erj}\le L-1\\ {}{\displaystyle \sum_{\tau =1}^L\epsilon \left({e}_{r_j}-{b}_{\tau}^{A_{r_jk}}\right)},\kern0.9em \mathrm{if}\kern0.2em {e}_{r_j}\ge {b}_L^{A_{r_jk}}\end{array}\right. $$
(26)
$$ \mathrm{E}\left({P}_{r_jk}\right)=\left\{\begin{array}{l}{\displaystyle \sum_{\tau =1}^L\epsilon \left({b}_{\tau}^{A_{r_jk}}-{l}_{r_j}\right)},\kern0.9em \mathrm{if}\kern0.2em {l}_{r_j}<{b}_1^{A_{r_jk}}\\ {}{\displaystyle \sum_{\tau ={\tau}_{lrj}+1}^L\epsilon \left({b}_{\tau}^{A_{r_jk}}-{l}_{r_j}\right)},\kern1em \mathrm{if}\kern0.2em {b}_{\tau_{lrj}}^{A_{r_jk}}\le {l}_{r_j}<{b}_{\tau_{lrj}+1}^{A_{r_jk}},\kern0.5em 1\le {\tau}_{lrj}\le L-1\\ {}0,\kern0.9em \mathrm{if}\kern0.2em {l}_{r_j}\ge {b}_L^{A_{r_jk}}\end{array}\right. $$
(27)
$$ \mathrm{E}\left({Z}_k\right)=\left\{\begin{array}{l}{\displaystyle \sum_{\tau =1}^L\epsilon \left({b}_{\tau}^{A_{r_jk}}-{d}_{0k}-h\right)},\kern0.9em \mathrm{if}\kern0.2em {d}_{0k}+h<{b}_1^{A_{r_jk}},\kern0.5em j={n}_k+1\\ {}{\displaystyle \sum_{\tau ={\tau}_h+1}^L\epsilon \left({b}_{\tau}^{A_{r_jk}}-{d}_{0k}-h\right)},\kern1em \mathrm{if}\kern0.2em {b}_{\tau_h}^{A_{r_jk}}\le {d}_{0k}+h<{b}_{\tau_h+1}^{A_{r_jk}},\kern0.5em 1\le {\tau}_h\le L-1,\kern0.5em j={n}_k+1\\ {}0,\kern0.9em \mathrm{if}\kern0.2em {d}_{0k}+h\ge {b}_L^{A_{r_jk}},\kern0.5em j={n}_k+1\end{array}\right. $$
(28)

The probabilities in Eqs. (7) and (8) can also be estimated, as shown in Eqs. (29) and (30) respectively.

$$ \mathrm{P}\left\{{A}_{r_jk}\le {l}_{r_j}\right\}=\left\{\begin{array}{l}0,\kern0.9em \mathrm{if}\kern0.2em {l}_{r_j}<{b}_1^{A_{r_jk}}\\ {}{\tau}_{lrj}\epsilon, \kern0.9em \mathrm{if}\kern0.2em {b}_{\tau_{lrj}}^{A_{r_jk}}\le {l}_{r_j}<{b}_{\tau_{lrj}+1}^{A_{r_jk}},\kern0.5em 1\le {\tau}_{lrj}\le L-1\\ {}1,\kern0.9em \mathrm{if}\kern0.2em {l}_{r_j}\ge {b}_L^{A_{r_jk}}\end{array}\right. $$
(29)
$$ \mathrm{P}\left\{{B}_k\le h\right\}=\left\{\begin{array}{l}0,\kern0.9em \mathrm{if}\kern0.2em {d}_{0k}+h<{b}_1^{A_{r_jk}},\kern0.5em j={n}_k+1\\ {}{\tau}_h\epsilon, \kern0.9em \mathrm{if}\kern0.2em {b}_{\tau_h}^{A_{r_jk}}\le {d}_{0k}+h<{b}_{\tau_h+1}^{A_{r_jk}},\kern0.5em 1\le {\tau}_h\le L-1,\kern0.5em j={n}_k+1\\ {}1,\kern0.9em \mathrm{if}\kern0.2em {d}_{0k}+h\ge {b}_L^{A_{r_jk}},\kern0.5em j={n}_k+1\end{array}\right. $$
(30)

Expressions for estimating violations of route duration and service level constraints (see Section 3.3.2) in solution s are shown in Eqs. (31) and (32) respectively.

$$ d(s)={\displaystyle \sum_{k\in \mathbf{K}} \max \left\{{v}^{A_{r_jk}}\left(\left[\beta /\epsilon \right]\cdot \epsilon \right)-{d}_{0k}-h,\kern0.4em 0\right\}},\kern0.9em {r}_j\in {\mathbf{R}}_k,\kern0.5em j={n}_k+1 $$
(31)
$$ w(s)={\displaystyle \sum_{k\in \mathbf{K}}{\displaystyle \sum_{j=1}^{n_k+1} \max \left\{{v}^{A_{r_jk}}\left(\left[{\alpha}_{r_j}/\epsilon \right]\cdot \epsilon \right)-{l}_{r_j},\kern0.4em 0\right\}}},\kern0.9em {r}_j\in {\mathbf{R}}_k $$
(32)

5 Computational Results

5.1 Accuracy of the α-Discrete Approximation Method

In this section, the accuracy of the proposed α-discrete approximation method was tested by comparison with Chang’s method (Chang et al. 2009). Stochastic simulation (Li et al. 2010) provided the ground true value for the comparison. The test example is a simple partial route shown in Fig. 2, where D denotes the depot and C i represents the customer, i = 1, …, 5. In Fig. 2, numbers within square brackets are customers’ soft time windows, whereas numbers within round brackets represent the mean and variance of link travel times. Departure time from D was set to zero.

Fig. 2
figure 2

A simple partial route

Full size image

For the proposed α-discrete approximation method, L was set to 100. For stochastic simulation, a total of 106 iterations were performed. Since arrival times were assumed to be normally distributed in Chang’s method (Chang et al. 2009), expressions for computing \( \mathrm{E}\left({W}_{r_jk}\right) \), \( \mathrm{E}\left({P}_{r_jk}\right) \) and customer service levels under the assumption of normal arrival time distribution are given below,

$$ \mathrm{E}\left({W}_{r_jk}\right)=\sqrt{\mathrm{Var}\left({A}_{r_jk}\right)}\left[\phi \left({z}_1\right)+{z}_1\varPhi \left({z}_1\right)\right],\kern0.9em {r}_j\in {\mathbf{R}}_k,\kern0.5em 1\le j\le {n}_k $$
(33)
$$ \mathrm{E}\left({P}_{r_jk}\right)=\sqrt{\mathrm{Var}\left({A}_{r_jk}\right)}\left\{\phi \left({z}_2\right)-{z}_2\left[1-\varPhi \left({z}_2\right)\right]\right\},\kern0.7em {r}_j\in {\mathbf{R}}_k,\kern0.5em 1\le j\le {n}_k+1 $$
(34)
$$ \mathrm{P}\left\{{A}_{r_jk}\le {l}_{r_j}\right\}=\varPhi \left({z}_2\right),\kern1em {r}_j\in {\mathbf{R}}_k,\kern0.5em 1\le j\le {n}_k+1 $$
(35)

where \( {z}_1=\left({e}_{r_j}-\mathrm{E}\left({A}_{r_jk}\right)\right)/\sqrt{\mathrm{Var}\left({A}_{r_jk}\right)} \); \( {z}_2=\left({l}_{r_j}-\mathrm{E}\left({A}_{r_jk}\right)\right)/\sqrt{\mathrm{Var}\left({A}_{r_jk}\right)} \); ϕ( ∙ ) is the probability density function of standard normal distribution; Φ(∙) is the cumulative distribution function of standard normal distribution.

The test was conducted in two scenarios. Link travel times in Fig. 2 were assumed to follow normal distribution in Scenario 1 and lognormal distribution in Scenario 2. Given mean and variance of link travel times, parameters for the lognormal distribution of link travel times can be computed using Eqs. (36) and (37). In both scenarios, service times at customers were assumed to follow the same normal distribution N(10,52). The test results are shown in Tables 1 to 4.

Table 1 Estimated service level at each customer by different methods
Full size table
$$ \mu \left({T}_{r_j{r}_{j+1}}\right)= \log \left(\mathrm{E}{\left({T}_{r_j{r}_{j+1}}\right)}^2/\sqrt{\mathrm{Var}\left({T}_{r_j{r}_{j+1}}\right)+\mathrm{E}{\left({T}_{r_j{r}_{j+1}}\right)}^2}\right),\kern0.9em {r}_j\in {\mathbf{R}}_k,\kern0.5em 0\le j\le {n}_k $$
(36)
$$ \sigma \left({T}_{r_j{r}_{j+1}}\right)=\sqrt{ \log \left(\mathrm{Var}\left({T}_{r_j{r}_{j+1}}\right)/\mathrm{E}{\left({T}_{r_j{r}_{j+1}}\right)}^2+1\right)},\kern0.9em {r}_j\in {\mathbf{R}}_k,\kern0.5em 0\le j\le {n}_k $$
(37)

In Scenario 1, it can be seen from Tables 1 to 3 that Chang’s method performed well at the first customer C 1, but not at the rest of the customers. This result is expected, since the arrival time at C 1 is exactly normally distributed in Scenario 1, but arrival times at customers C 2 to C 5 are not, due to the impact of time windows. In Scenario 2, the estimation error is even larger than that in Scenario 1 by Chang’s method. For example, the relative error between the estimated expected tardiness at C 3 by Chang’s method and that by stochastic simulation is −37.09 % in Scenario 1, while it is −63.52 % in Scenario 2 (Table 3). The reason is clear that travel and arrival times are not normally distributed in Scenario 2. This, however, is a basic assumption of Chang’s method.

For the proposed α-discrete approximation method, it was found that larger errors were produced when estimating expected tardiness. The largest relative error between the results of α-discrete and stochastic simulation is −1.44 % in Tables 1 and 2, while it is −9.89 % in Table 3. However, the estimation error by α-discrete is still much smaller compared with that of Chang’s method, as shown in Tables 1 to 3. In addition, the accuracy of α-discrete can be further improved by increasing the value of L (e.g. 200).

Table 2 Estimated expected earliness at each customer by different methods
Full size table
Table 3 Estimated expected tardiness at each customer by different methods
Full size table

Table 4 shows that the difference between the estimation error by Chang’s method and that by α-discrete is small in terms of the total cost of the partial route (−0.52 % versus −0.14 % in Scenario 1 and −2.23 % versus −0.42 % in Scenario 2). This is because penalty cost takes up only a small part of the total cost in this test example and mean travel times are the same for both methods. Even though this difference can be ignored, however, the difference in estimating service levels at each customer by these two methods is sometimes large (Table 1) and thus can not be neglected.

Table 4 Estimated cost of the partial route by different methods
Full size table

In conclusion, the accuracy of the proposed α-discrete approximation method is higher than that of Chang’s method, especially when travel times are not normally distributed. Thus α-discrete is selected as the approximation method for solution evaluation and used in the remainder of this paper.

5.2 Performance of the Proposed Model for SVRPSTW

In this section, several of Solomon’s benchmark problems (Solomon 1987) were adapted as test instances to demonstrate the performance of the proposed model. In the remainder of this section, the test dataset and experiment settings are introduced first, followed by the computational results of the proposed model on this dataset.

5.2.1 Test Dataset and Experiment Settings

The well-known Solomon’s benchmark problems (Solomon 1987) have been chosen as test datasets by many previous studies on VRPTW (Taillard et al. 1997; Cordeau et al. 2001; Chiang and Russell 2004; Nagata et al. 2009). Several factors were considered when these benchmark problems were generated, such as geographical locations of customers and tightness of time windows. In this study, seven of the benchmark problems were chosen and adapted for the demonstration of the proposed model. Their major characteristics are listed in Table 5.

Table 5 Characteristics of the test dataset
Full size table

Three types of problems according to the geographical locations of customers are shown in Table 5. For each problem type, two or three instances were chosen with different time window width sizes. For each problem instance, there are a total of 20 customers and the sum of customer demands is listed in Table 5. Vehicle capacity is 200 units in each problem instance. Travel times were assumed to follow lognormal distribution and service times were assumed to be normally distributed. The COV of the travel times was randomly generated from [0.2, 0.6]. Given the mean and variance of travel times, parameters for the lognormal distribution of travel times can be computed using Eqs. (36) and (37). This dataset is chosen to demonstrate the applicability of the proposed model on problem instances with different characteristics. Additional data (e.g. coordinates and time windows) of the dataset can be found on http://web.cba.neu.edu/~msolomon/problems.htm.

The proposed solution algorithm SVRP-ITS was implemented in Matlab 7.5.0 and run on a PC with a four-core Inter Core i7 3.40 GHz CPU (only one core was used) and 4 GB RAM. The maximum number of tabu search iterations η was set to 2000. In local search improvement phases, tabu search stops if the best feasible solution has not been improved for 200 consecutive iterations. For the proposed α-discrete approximation method, L was set to 100.

Each problem instance was tested in four scenarios, with parameter settings of the proposed model in these scenarios shown in Table 6. In the last scenario, customers were divided into two groups: the first 6 customers being the first group and the rest 14 the second group. It was assumed that customers in the first group require higher service levels than those in the second group.

Table 6 Parameter settings of the proposed model for each problem instance in different scenarios
Full size table

5.2.2 Computational Results of the Proposed Model on a Typical Problem Instance

In this section, one of the problem instances RC101.20 in Table 5 was selected as a typical example to demonstrate the performance of the proposed model. RC101.20 was considered typical because of the mixed (randomly distributed and/or clustered) geographical locations of customers in that problem and because the time window width (30 min) is common in just-in-time production (Chang et al. 2009). Computational results of the proposed model on RC101.20 are shown in Table 7.

Table 7 Computational results of the proposed model on RC101.20
Full size table

Table 7 shows that the number of vehicles used m in Scenario 1 is the smallest among all the four scenarios. Because in achieving the primary objective of the proposed model (i.e. minimizing m while satisfying all the constraints, Section 2), constraints are the weakest in Scenario 1 with no customer service level constraints imposed (Table 6). In such a case, capacity constraint Eq. (6) determines the number of required vehicles in the solution. As the sum of customer demands is 430 units in RC101.20 (Table 5) and the vehicle capacity is 200, at least 3 vehicles are required in the solution, as shown in Table 7. With limited number of vehicles used in Scenario 1, customer service levels cannot be ensured. The tardiness penalty cost is the largest and the mean customer service level is the lowest in this scenario.

In Scenario 2, a minimum service level of 50 % was specified for each customer in RC101.20. Consequently, the number of required vehicles increases in this scenario (Table 7). With one more vehicle used, the mean customer service level is greatly improved compared with that in Scenario 1. This result implies that carriers may consider adding one more vehicle to their fleet to improve their service quality. In Scenario 3, required customer service levels were further increased to 80 %, resulting in a high mean customer service level (Table 7). Whereas the number of required vehicles in this scenario is the largest among all the four scenarios.

In Scenario 4, only thirty percent of the customers in RC101.20 (i.e. customers in the first group) were guaranteed a minimum service level of 80 %, while for others (i.e. customers in the second group) the value was 50 %. This differentiation among customers according to their diverse service level preferences leads to a reduction in the number of required vehicles in Scenario 4, compared with that in Scenario 3 (Table 7).

It can be also found from Table 7 that mean travel time increases when more vehicles are used. For example, mean travel time increases by 26.89 % in Scenario 2 compared with that in Scenario 1. Earliness penalty cost also increases in line with the increase in the number of vehicles used. The reason is that, in such a case, on average, fewer customers will be assigned to one vehicle. Additionally, the duration of each route will not necessarily become shorter, due to the existence of time windows. Therefore more time might be spent in waiting at customer locations. Finally, it is shown in Table 7 that the total cost is the highest in Scenario 3, since the number of vehicles used is the largest in that scenario.

5.2.3 Computational Results of the Proposed Model on Other Problem Instances

To demonstrate the applicability of the proposed model on different types of problems, the proposed model was solved on the other six problem instances in Table 5 (except RC101.20) in this section. The computational results are displayed in Table 8.

Table 8 Computational results of the proposed model on the other 6 problem instances
Full size table

A large increase in the number of vehicles used in the solution (from 2 to 5) is found from Scenario 1 to Scenario 2 for problem R105.20 in Table 8. The trade-off is that the mean customer service level is greatly improved (from 30.65 % in Scenario 1 to 90.40 % in Scenario 2). For Scenarios 2 to 4 of problem R105.20, the number of vehicles used is the same, although the required customer service levels differ in these scenarios (Table 5). In these cases, the trade-off is between the mean travel time and the tardiness penalty cost, with the number of required vehicles kept the same. Similar trends can be found for problem R109.20, except that the increase in the number of vehicles used from Scenario 1 to Scenario 2 is smaller for R109.20 than that for R105.20. The reason is that the time windows specified by customers were tighter in Problem R105.20 than those in R109.20 (Table 5).

For problems C101.20 and C106.20, the total cost is the smallest in Scenario 2 among all four scenarios as shown in Table 8. This is because the cost paid for additional vehicles is compensated by the reduction in the tardiness penalty cost. In Scenario 4 of these two problem instances, a reduction in the number of required vehicles is seen again because of the differentiation among customers according to their diverse service level preferences.

For problems RC106.20 and RC107.20, it can be seen from Table 8 that solutions in some of the scenarios are the same. For example, the solution of problem RC106.20 in Scenario 1 is the same as that in Scenario 2. The reason is that for problem RC106.20 at least 3 vehicles were required in Scenario 1 with no customer service level imposed (for the same reason as stated in Section 5.2.2 for problem RC101.20). With this number of vehicles used, customer service levels in Scenario 1 already reached the required level in Scenario 2. Therefore the problem solution for Scenario 2 is the same as that in Scenario 1.

6 Conclusions

A stochastic vehicle routing problem with soft time windows considering travel and service time uncertainties is presented in this paper. A new stochastic programming model has been proposed to minimize carrier’s total cost while ensuring a minimum on-time arrival probability at each customer location. To solve the proposed model, an iterated tabu search heuristic algorithm was developed. A route reduction mechanism was incorporated in this heuristics to reduce the number of required vehicles. A discrete approximation method has been proposed to estimate the arrival time distributions of vehicles in the presence of time windows.

Computational results showed that the accuracy of the proposed α-discrete approximation method is higher than that of Chang’s method (Chang et al. 2009), especially when travel times are not normally distributed. Although travel times were assumed to be normal or lognormal in the test example, it is noted that α-discrete can also be applied for other travel time distributions. In addition, several numerical examples were carried out to demonstrate the performance of the proposed SVRPSTW model. Computational results confirmed that the proposed model can be applied on different types of problems. Various trade-offs between carrier’s total cost and customer service level can be explored using the proposed model. Results indicated that the proposed model can easily be adapted to multi-class customers with various service level preferences by imposing appropriate customer service level constraints.

The computational efficiencies of the proposed α-discrete approximation method, Chang’s method (Chang et al. 2009) and stochastic simulation (Li et al. 2010) will be investigated in future work. More effort is also required to improve the efficiency of the proposed solution algorithm for solving larger problem instances. In addition, it is noted that VRP has been studied in combination with other problems. For example, location-routing problems (Bozkaya et al. 2010; Toyoglu et al. 2012; Silva and Gao 2012) combine the problems of facility location and vehicle routing. It is interesting to investigate the effects of travel time uncertainties on these problems.