Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The Vehicle Routing Problem (VRP) was proposed more than 50 years ago [6] and it is a challenging combinatorial optimization problem. One of the most studied real-world features are the so called time windows constraints [15]. Customers receiving goods often demand delivery within a time interval or time window. Time windows are classified as Hard (VRPHTW), if customers must be visited within the specified time interval, and Soft (VRPSTW), if time windows can be violated at the expense of customer inconvenience.

There is not a unique interpretation of time windows violations in the research community. Customer inconvenience for being visited too late and (possibly) too early with respect to the desired time window is typically quantified and the VRPSTW’s objective function is modelled as a weighted combination of routing costs and a measure of the customer inconvenience. However, how to measure the customer inconvenience and how to quantify the relative weight of routing and customer inconvenience are still open research questions.

VRPSTWs have been presented in the pioneering articles by Sexton and Bodin [16, 17] and Sexton and Choi [18]. In Chang and Russell [5] a Tabu Search is developed for the same problem studied in Balakrishnan [1]. Taillard et al. [19] also proposed a Tabu Search for a VRPSTW, in which linear penalizations are applied only to late visits. Calvete et al. [3] applies goal programming to the VRPSTW with linear penalizations for early and tardy visits. Ibaraki et al. [10] extend the concept of time window and measure customer’s inconvenience as a nonconvex, piecewise linear and time dependent function.

Fu et al. [9] acknowledge the need of a unified approach that model penalties associated to time windows. Figliozzi [8] proposed an iterative route construction and improvement algorithm for the same variant and compared its results with Balakrishnan [1], Fu et al. [9] and Chang and Russell [5].

Among the exact algorithms for VRPSTWs, we can mention Qureshi et al. [12], in which the authors solved by column generation a problem with semi soft time (tardy arrivals only). Bhusiri et al. [2] extend this algorithm to the variant in which both early and late arrival at a customer are penalizated, but the arrival time is bounded in an outer time window. Liberatore et al. [11] solves the VRPSTW with unbounded penalization of early and late arrival at the customers using a branch-and-cut-and-price technique.

Objective functions weighting routing costs and customer inconvenience suffer of typical drawbacks of weighted-sum multi objective optimization problems. As reported in Caramia and Dell’ Olmo [4], the planner is often not “aware of which weights are the most appropriate to retrieve a satisfactorily solution, he/she does not know in general how to change weights to consistently change the solution”.

In this paper, we model soft time windows constraints with in mind the needs of practitioners and their difficulties in comparing routing costs and customers inconvenience. Human planners accept time windows violations when the saving on routing costs is sufficiently big. We therefore compute a nominal solution in which hard time windows are imposed as a base of comparison for the planner. Then, the planner quantifies a desired saving on routing costs with respect to the nominal solution. The exact algorithm minimizes the time window violations to achieve this goal. We believe this variant will allow practitioners to make better use of VRPSTW software, because the parameter they are asked to define is just a measure of mileage saving and not a weight of routing cost and customer inconvenience. In the reminder, we propose two exact algorithms both based on branch-and-cut-and-price.

2 A Mathematical Model for Minimal Time Windows Violation

We recall the definition of the VRPHTW. A graph G(V, A) is given, where the set of vertices \(V = N \cup \{0\}\) is composed of a set of N vertices representing the customers and a special vertex 0 representing the depot. Non-negative weights \(t_{ij}\) and \(c_{ij}\) are associated with each arc \((i, j) \in A\); representing the traveling time and the transportation cost, respectively. Traveling times satisfy the triangle inequality. A positive integer demand \(d_i\) is associated with each vertex \(i \in N\) and a capacity Q is associated with each vehicle of a set K. A non-negative integer service time \(s_i\) and a time window \([a_i, b_i]\), defined by two non-negative integers, are also associated with each vertex \(i \in N\). The problem asks to find a set of routes with cardinality at most |K|, visiting all customers exactly once and respecting time windows and vehicles’ capacity constraints. The objective is to minimize the overall routing cost.

In the VRPHTW, the vehicle has to wait until the opening of the time window \(a_i\), in case of early arrival at customer’s i location. In the VRPSTW, constant or proportional penalties are incurred for early or late service. The service may start any time between the arrival and the opening of the time window. However, both in the VRPHTW and in the VRPSTW, vehicles are allowed to wait at no cost before servicing the customer.

In our variant of VRPSTW, we propose an alternative model. The model assumes that the optimal value of the underlying VRPHTW, \(z^*\), is known and is strictly positive. A cost saving is imposed by the planner as a maximum percentage \(\upbeta < 1\) of \(z^*\). The objective is to minimize the overall time windows violation. The model reads as follows:

$$\begin{aligned} g_{\Theta } = \textit{minimize}&\sum _{r \in \Theta } v^r x^r \end{aligned}$$
(1)
$$\begin{aligned} s.t.&\sum _{r \in \Theta } f^r_i x^r \ge 1 \qquad \forall i \in N \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{r \in \Theta } c^r x^r \le \upbeta \cdot z^* \end{aligned}$$
(3)
$$\begin{aligned}&\sum _{r \in \Theta } x^r \le |K| \end{aligned}$$
(4)
$$\begin{aligned}&x^r \in \{0,1\} \qquad \forall r \in \Theta \end{aligned}$$
(5)

where \(\Theta \) is the set of feasible routes in which the vehicle’s capacity is not exceeded and \(v^r\) is the overall time window violation of route r. Constraint (3) states that the routing cost must be not greater than a fraction of the cost of the optimal VRPHTW solution. Constraint (4) imposes that no more than |K| vehicles are used.

The routing cost improvement \(\upbeta \) is the only parameter required. Planners are likely to be comfortable defining parameter \(\upbeta \) as it directly relates to monetary savings.

3 Branch-and-Cut-and-Price Algorithm for the VRPSTW

Model (1)–(5) may contain a number of variables which grows exponentially with the size of the instance and cannot be dealt with explicitly. Therefore, to compute valid lower bounds, we solve the linear relaxation of the model recurring to a column generation procedure. To obtain feasible integer solutions we embed the column generation bounding procedure into an enumeration tree [7].

At each column generation iteration, the linear relaxation of the Restricted Master Problem (RMP, i.e., the model (1)–(5) where a subset of variables is considered) is solved. We search for new columns with negative reduced cost: \( \overline{v}^r = v^r - \sum _{i \in N} f^r_i \uppi _i - c^r \uprho - \upgamma \), where \(\uppi _i\) is the nonegative dual variable associated to the ith constraint of the set (2), \(\uprho \) is the nonpositive dual variable associated with the threshold constraint (3) and \(\upgamma \) is the nonpositive dual variable associated with constraint (4). The pricing problem can be modeled as a resource constrained elementary shortest path problem (RCESPP). In our implementation, we extend the algorithms presented in Righini and Salani [13, 14] and Liberatore et al. [11].

4 Alternative Formulation and Bisection Search

The algorithm reported in Sect. 3 is effective to identify infeasible instances and a feasible solution, when available. On the other hand, it shows slow convergence in proving the optimality of the master problem because the computation time required by the exact pricing problem is cumbersome.

In this section we propose an alternative formulation and an alternative exact solution algorithm based on bisection search. The model minimizes the overall routing costs subject to a maximal permitted time windows violation. The model is solved with branch-and-cut-and-price and reads as follows:

$$\begin{aligned} h_{\Theta } = \textit{minimiz}e&\sum _{r \in \Theta } c^r x^r \end{aligned}$$
(6)
$$\begin{aligned} s.t.&\sum _{r \in \Theta } f^r_i x^r \ge 1 \qquad \forall i \in N \end{aligned}$$
(7)
$$\begin{aligned}&\sum _{r \in \Theta } v^r x^r \le g_{\textit{max}} \end{aligned}$$
(8)
$$\begin{aligned}&\sum _{r \in \Theta } x^r \le |K| \end{aligned}$$
(9)
$$\begin{aligned}&x^r \in \{0,1\} \qquad \forall r \in \Theta \end{aligned}$$
(10)

The pricing problem searches for columns minimizing the following reduced cost: \(\overline{c}^r = c^r - \sum _{i \in N} f^r_i \uppi _i - v^r \uppsi - \upgamma \), where \(\uppi _i\) is the nonegative dual variable associated to the ith constraint of the set (7), \(\uppsi \) is the nonpositive dual variable associated with the time windows violation (8) and \(\upgamma \) is the nonpositive dual variable associated with constraint (9). The pricing problem associated to this formulation is equivalent to that studied by Liberatore et al. [11] where the linear penalty for earliness and tardiness is adjusted with the dual variable of constraint (8).

Our algorithm is based on a bisection search on the value of the permitted violation \(g_{\textit{max}}\). At each iteration of the algorithm \(g_{\textit{max}}\) represents either an upper or a lower bound to the optimal value of model (1)–(5), \(g^*_{\Theta }\).

Let \(h^*_{\Theta }(g_{\textit{max}})\) be the optimal solution of (6)–(10) for a given value of \(g_{max}\). The algorithm exploits the following two properties:

  1. 1.

    If \(h^*_{\Theta }(g_{\textit{max}}) > \upbeta \cdot z^*_{\Omega }\), then \(g_{max}\) is a valid lower bound to \(g^*_{\Theta }\).

  2. 2.

    If \(h^*_{\Theta }(g_{\textit{max}}) \le \upbeta \cdot z^*_{\Omega }\), then \(\sum _{r \in \Theta } v^r x^r\) is a valid upper bound to \(g^*_{\Theta }\).

The Algorithm requires the existence of a feasible solution and the value of an upper bound \(g_{\textit{UB}}\) to \(g^*_{\Theta }\). At each iteration, the range of possible values for the violation of time windows \((g^{it}_{\textit{LB},\Theta }, g^{it}_{\textit{UB},\Theta })\) is halved, as reported in algorithm 1; the value \(\upvarepsilon \) is strictly positive and is determined using the instance data.

We performed some preliminary computational experiments on the well known Solomon’s data set. From the original set we derived 54 instances from the R and RC data set by adding a performance constraint of 1, 5 and 10 % with respect to the optimal solution without time windows violation. The bisection algorithm converges to an optimal solution for all instances while the branch and price algorithm failed to converge on 12 instances within an our of computation.

We observe that the solution of the pricing problem benefits from the alternative formulation adopted in the bisection algorithm. We believe that in other contexts, where branch and price algorithms applied to combinatorial optimization exhibit slow convergence, it may be beneficial to devise alternative formulations.

figure a