1 Introduction

Globalization has fostered a prosperous climate for industrial growth. However, this growth is coupled with new challenges: a fiercer competition, broadened distribution networks, diversified supply chains, tighter profit margins, and more exigent clients. These latter are demanding lower prices, requiring higher quality levels, and imposing stricter deadlines. Consequently, the manufacturing, service, and transportation industries that are affected by this new order have to manage their activities judiciously while dealing with more complex, larger-scale, real-life systems. Managing these activities is equivalent to solving several inter-related industrial engineering problems. Because of the new global environment, industries can no longer address some abstract form of these problems or decompose them into independent subproblems. They have to model the problems as closely as possible to their true real-life context. Such models are important for three reasons. First, they offer a better reflection of the problem. Second, they account for more constraints, take into account the true nature of the variables, and build in intricate interdependencies. Third and last, they enhance the chances of direct real-life implementation of the resulting solutions without any modification and at no supplementary cost.

The optimization of the new complex problems that have emerged is difficult not only because of their compounded nature but most importantly because their components are themselves difficult to solve. This chapter considers one such problem: vehicle routing with multiple time windows (VRPMTW), a problem of substantial impact. Its good management alleviates environmental concerns caused by pollution, reduces costs, and offers better work conditions for drivers and higher satisfaction for clients. In VRPMTW, every client specifies more than one availability period for receiving delivery.

Unlike existing methods, which consider the routing and scheduling aspects of VRPMTW independently, this chapter addresses the problem as a single entity. It approximately solves VRPMTW in reasonable run times using an efficient search technique that takes advantage of the advances of computing technologies. Larger computer memories and faster processors allow the (near-)exact resolution of more realistic problems, an unimaginable phenomenon few years ago.

The proposed approach uses exact techniques as approximate ones. It substitutes difficult constraints with easier ones, and limits the search space to neighborhoods that contain the optimum. Most importantly, it explores the respective strengths of mixed integer programming, constraint programming, and search methods.

Section 19.2 reviews the literature. Section 19.3 defines and models the problem. Section 19.4 details the proposed approach. Section 19.5 presents some results. Section 19.6 discusses some practical considerations. Finally, Sect. 19.7 summarizes this research and presents future extensions.

2 Literature Review

Because they occur in most services and industries, vehicle routing problems (VRP) are continuously drawing the attention of researchers (Vidal et al. 2014). This is clearly reflected by the extensive literature and numerous review papers (Adewumi and Adeleke 2018; Braekers et al. 2016; Eksioglu et al. 2009, Gendreau et al. 2008, Koç et al. 2016; Vidal et al. 2013). These surveys classify the literature according to the problem constraints, mathematical models, and solution techniques. Most of them (e.g., Baldacci et al. 2012) single out cases where loads (Alba and Dorronsoro 2008; Gendreau et al. 1994; Minocha and Tripathi 2013; Nagata and Bräysy 2009; Toth and Vigo 2002) and delivery times (Cordeau et al. 2001; Favaretto et al. 2007; Fu et al. 2007; Figliozzi 2010; Moccia et al. 2012; Nagata et al. 2010; Nazif and Lee 2012; Solomon 1987) are constrained. These constraints fathom large parts of the search space and thus eliminate a large number of potential nodes of any tree-based procedure. However, they make finding feasible solutions much harder.

Hashimoto et al. (2006) and Ibaraki et al. (2005), to cite a few, consider VRP with general time windows (TW). They associate to each client more than one delivery window, but penalize the violation of these soft or flexible TWs, with penalties that are not necessarily linear. Beheshti et al. (2015) consider a variant where the multiple soft TWs are not specified by the clients but by the delivery company. Clients rank the TWs in decreasing order of their preference. This variant, which applies in rapid post deliveries, does not guarantee the suitability of the alternatives with the clients’ constraints.

Belhaiza et al. (2013) address VRPMTW via a tabu search variable neighborhood search (TSVNS) that minimizes the weighted sum of the trip duration and the penalties associated to the TWs and capacity constraints. Belhaiza and M’Hallah (2016) consider the multiple objective VRPMTW where the criteria are: drivers’ utility, total cost, and costumers’ utility. They speed their search by fathoming all dominated solutions and investigate the space of solutions that satisfy the Nash equilibrium conditions of a non-cooperative multiple-agent game. Finally, Belhaiza et al. (2017) extend the single objective VRPMTW to the multiple-depot heterogeneous fleet case with the objective of minimizing either the total travel time or the total traveled duration. They address the problem using a multiple-start hybrid genetic variable neighborhood search.

Unlike the techniques surveyed by Archetti and Speranza (2014), the proposed method combines random search with mathematical/constraint programming. This line of research is successfully applied in cutting and packing where the constraints are non-linear (M’Hallah et al. 2013; Al-Mudhahka et al. 2011) and in timetabling where the problem size is large and the planning horizon is long (M’Hallah and Alkhabbaz 2013). Similarly, it is applied in scheduling where a steepest descent heuristic (Laalaoui and M’Hallah 2016) calls iteratively a mixed integer program to insert a job on a machine (M’Hallah 2007; M’Hallah and Al-Khamis 2012) or to enhance an existing solution and assess its optimality gap (M’Hallah 2014) or to choose jobs that will be exchanged among agents (Polyakovskiy and M’Hallah 2014). Recently, it is extended to bin packing where mixed integer/constraint programs apply a look-ahead strategy that reserves areas in the bins for unpacked items (Polyakoskiy and M’Hallah 2018). In all aforementioned applications, the models are augmented with feasibility constraints and with bounds on the objective function values forcing the solvers to only investigate feasible improving directions. They are subject to runtime limits because in most cases, the incumbent is identified at an early stage of the search while most of the computational effort is devoted to proving optimality. Finally, they are fed with partial or complete initial solutions.

3 Problem Description and Formulation

Section 19.3.1 defines VRPMTW. Sections 19.3.2 and 19.3.3 model it as a mixed integer and as a constraint program. Finally, Sect. 19.3.4 discusses ways to enhance the performance of both models.

3.1 Problem Definition

Consider a set I = {1,  … , n} of n clients that are served, from a single depot d, by a set K = {1,  … , m} of m vehicles. The depot d, denoted also as client 0, is located in position \( \left({o}_0^h,{o}_0^v\right) \) of the Cartesian coordinate system. It is open during the time interval [ℓ0, u 0]; i.e., no vehicle leaves d prior to ℓ0 or returns to d later than u 0. A vehicle may wait at the depot or at a client’s site. Let δ i, j denote the travel times between i and j, i ∈ I ∗, j ∈ I ∗, i ≠ j, where I ∗ = I ∪ {0}.

Client i, i ∈ I, is characterized by its Cartesian coordinate system’s position \( \left({o}_i^h,{o}_i^v\right) \), positive demand q i delivered by a single vehicle, known positive service time s i, and ordered set \( {W}_i=\left\{{w}_{i,1},\dots, {w}_{i,{\overline{p}}_i}\right\} \) of \( {\overline{p}}_i \), \( {\overline{p}}_i\in {\mathrm{\mathbb{N}}}^{\ast } \), non-overlapping availability TWs. TW p, \( p=1,\dots, {\overline{p}}_i \), of client i, i ∈ I, is w i, p = [ℓi, p, u i, p], with \( 0<{\mathrm{\ell}}_{i,1}<{u}_{i,1}<\dots <{\mathrm{\ell}}_{i,p}<{u}_{i,p}<\dots <{\mathrm{\ell}}_{i,{\overline{p}}_i}<{u}_{i,{\overline{p}}_i}<\infty \).

Let I k ⊂ I be the ordered subset of clients assigned to k. The subsets are mutually exclusive; i.e., ∪k ∈ K I k = I, ∪k ∈ K I k = ∅. Thus, partial delivery is prohibited. Vehicle k, k ∈ K, has a limited capacity Q k > 0. Its time out of d, including its waiting time, should not exceed \( {\overline{D}}_k>0 \). Its travel duration D k is the sum of its travel and service time. It excludes any waiting time.

3.2 Mixed Integer Program

Herein, VRPMTW assigns the clients to the vehicles and schedules their respective deliveries with the objective of minimizing the total travel time over all vehicles. It can be formulated as a mixed integer program. The model is inspired from the mixed integer program (MIP) of Belhaiza et al. (2013). It uses three types of positive decision variables and three types of binary variables.

The first positive variable ω i, k denotes the waiting time of vehicle k, k ∈ K, at client i, i ∈ I ∗. A vehicle may have to wait prior to starting delivery to a specific client and may choose to wait at d in order to reduce its total time out of d. The second positive variable t i, k indicates the time k, k ∈ K, reaches i, i ∈ I ∗. Consequently, k starts delivery to i, i ∈ I, at t i, k + ω i, k. Finally, the third positive variable c i, k is the departure time of k, k ∈ K, from i, i ∈ I ∗. It follows that c 0, k is the departure time of k from d and t 0, k its return time to d.

The first binary variable z i, k = 1 if client i, i ∈ I, is assigned to vehicle k, k ∈ K, and 0 otherwise. The second binary variable x i, j, k = 1 if i, i ∈ I ∗, immediately precedes j, j ∈ I ∗, j ≠ i, and both j and i are served by vehicle k, k ∈ K, and 0 otherwise. Finally, the binary variable v i, p = 1 if client i, i ∈ I, is served during \( {w}_{i,p},\kern0.5em p=1,\dots, {\overline{p}}_i, \) and 0 otherwise.

Then, the VRPMTW using the above six types of decision variables follows.

$$ \operatorname{Min}\sum \limits_{k\in K}\sum \limits_{\left(i,j\right)\in {I}^{\ast}\times {I}^{\ast }}{\delta}_{i,j}{x}_{i,j,k} $$
(19.1)
$$ s.t.\ \ \ \sum \limits_{k\in K}{z}_{i,k}=1,\kern0.5em i\in I $$
(19.2)
$$ \sum \limits_{j\in {I}^{\ast }}{x}_{i,j,k}-\sum \limits_{j\in {I}^{\ast }}{x}_{j,i,k}=0,\kern0.5em i\in {I}^{\ast },k\in K $$
(19.3)
$$ 2{x}_{i,j,k}-{z}_{i,k}-{z}_{j,k}\le 0,\kern0.5em i\in I,j\in I,i\ne j,k\in K $$
(19.4)
$$ \sum \limits_{k\in K}\sum \limits_{i\in {I}^{\ast }}{x}_{i,j,k}=1,\kern0.5em j\in I $$
(19.5)
$$ \sum \limits_{k\in K}\sum \limits_{j\in {I}^{\ast }}{x}_{i,j,k}=1,\kern0.5em i\in I $$
(19.6)
$$ \sum \limits_{i\in I}{q}_i{z}_{i,k}={Q}_k,\kern0.5em k\in K $$
(19.7)
$$ {c}_{i,k}-{t}_{i,k}-{\omega}_{i,k}-{s}_i+M\left(1-{z}_{i,k}\right)\ge 0,\kern0.5em i\in I,k\in K $$
(19.8)
$$ {t}_{j,k}\,{-}\,{c}_{i,k}\,{-}\,{\delta}_{i,j}\,{-}\,M\left(1-{x}_{i,j,k}\right)\le 0,\kern0.5em i\in {I}^{\ast },j\in {I}^{\ast },i\ne j,k\,{\in}\,K $$
(19.9)
$$ {t}_{j,k}\,{-}\,{c}_{i,k}\,{-}\,{\delta}_{i,j}\,{+}\,M\left(1\,{-}\,{x}_{i,j,k}\right)\ge 0,\kern0.5em i\in {I}^{\ast },j\in {I}^{\ast },i\ne j,k\,{\in}\,K $$
(19.9′)
$$ {t}_{i,k}\,{+}\,{\omega}_{i,k}\,{-}\,{\mathrm{\ell}}_{i,p}\,{+}\,M\left(1{-}{z}_{i,k}\right)\,{+}\,M\left(1{-}{v}_{i,p}\right)\ge 0,\kern0.5em i\in I,p\in \left\{1,\dots, {\overline{p}}_i\right\},k\,{\in}\,K $$
(19.10)
$$ {t}_{i,k}\,{+}\,{\omega}_{i,k}\,{-}\,{u}_{i,p}\,{-}\,M\left(1{-}{z}_{i,k}\right)\,{-}\,M\left(1{-}{v}_{i,p}\right)\le 0,\kern0.5em i\in I,p\in \left\{1,\dots, {\overline{p}}_i\right\},k\,{\in}\,K $$
(19.11)
$$ \sum \limits_{p=1}^{{\overline{p}}_i}{v}_{i,p}=1,\kern0.5em i\in I $$
(19.12)
$$ {c}_{0,k}\ge {\mathrm{\ell}}_0,\kern0.5em k\in K $$
(19.13)
$$ {t}_{0,k}\le {u}_0,\kern0.5em k\in K $$
(19.14)
$$ {t}_{0,k}-{c}_{0,k}\le {\overline{D}}_k,\kern0.5em k\in K $$
(19.15)
$$ {\omega}_{i,k}\ge 0,{z}_{i,k}\in \left\{0,1\right\},\kern0.5em i\in I,k\in K $$
(19.16)
$$ {c}_{i,k}\ge 0,{t}_{i,k}\ge 0,\kern0.5em i\in {I}^{\ast },k\in K $$
(19.17)
$$ {v}_{i,p}\in \left\{0,1\right\},\kern0.5em i\in I,p\in \left\{1,\dots, {\overline{p}}_i\right\} $$
(19.18)
$$ {x}_{i,j,k}\in \left\{0,1\right\},\kern0.5em i\in {I}^{\ast },j\in {I}^{\ast },i\ne j,k\in K $$
(19.19)

where M is a large positive number. Equation (19.1) defines the objective, which minimizes the total travel time. Constraint (19.2) ensures that each client is assigned to a single vehicle. Constraint (19.3) is the classical flow conservation. Constraint (19.4) guarantees that client i may immediately precede client j if and only if both are assigned to the same vehicle k. Constraints (19.5) and (19.6) ensure that each client i is visited once: i has exactly one immediate predecessor and one immediate successor. Constraint (19.7) guarantees that the quantity delivered by a vehicle does not exceed the vehicle’s capacity. Constraint (19.8) defines the departure time of vehicle k from client i as the sum of its arrival, service, and waiting time. This equation holds when i is assigned to k, and is redundant otherwise. Constraints (19.9) and (19.9′) compute the arrival time of k to client j as the sum of the departure time of k from the immediately preceding client i and the travel time between i and j. Constraints (19.10) and (19.11) impose that vehicle k starts delivery to client i during TW p of i if and only if i is assigned to k and is served during p. They are redundant otherwise. Constraint (19.12) imposes that delivery to client i occurs during exactly one of the TWs of i. Constraints (19.13) and (19.14) impose that a vehicle k leaves and returns to d during the open time of d, whereas constraint (19.15) limits the time of k out of the depot to the maximal permissible threshold. Finally, constraints (19.16)–(19.19) define the variable types. Solving the above MIP is a challenge. Cplex fails to identify feasible solutions for instances with more than 20 clients when allocated 3 h of runtime.

3.3 Constraint Program

Alternatively, VRPMTW can be modeled as a constraint program. Let ζ i, k be an optional interval variable indicating the activity of visiting client i using vehicle k. Let the interval variable h i represent the activity of visiting client i. In addition, let x k denote the route of k; that is, x k is the sequence of interval variables ζ i, k. Then, the CP model follows.

$$ \operatorname{Min}\ \sum \limits_{k\in K}\sum \limits_{i\in {I}^{\ast }}{\delta}_{ij}:\mathrm{next}\left({\boldsymbol{x}}_k,i\right)=j $$
(19.20)
$$ \mathrm{s}.\mathrm{t}.\kern0.5em {u}_{i,1}\ge \mathrm{s}\mathrm{tartOf}\left({h}_i\right)\ge {\mathrm{\ell}}_{i,1}\left\Vert \dots \right.\left\Vert {u}_{i,{\overline{p}}_i}\right.\ge \mathrm{s}\mathrm{tartOf}\left({h}_i\right)\ge {\mathrm{\ell}}_{i,{\overline{p}}_i},\kern0.5em i\in I $$
(19.21)
$$ \mathrm{startOf}\left({\zeta}_{0,k}\right)\ge {l}_0\&\&{u}_0\ge \mathrm{startOf}\left({\zeta}_{n+1,k}\right),\kern0.5em k\in K $$
(19.22)
$$ \mathrm{noOverlap}\left({\boldsymbol{x}}_{\boldsymbol{k}},\boldsymbol{\delta} \right),\kern0.5em k\in K $$
(19.23)
$$ \mathrm{first}\left({\boldsymbol{x}}_{\boldsymbol{k}},{\zeta}_{0,k}\right),\kern0.5em k\in K $$
(19.24)
$$ \mathrm{last}\left({\boldsymbol{x}}_{\boldsymbol{k}},{\zeta}_{n+1,k}\right),\kern0.5em k\in K $$
(19.25)
$$ \sum \limits_{i\in I}{q}_i\kern0.5em \mathrm{presenceOf}\left({b}_i^k\right)\le {Q}_k,\kern0.5em k\in K $$
(19.26)
$$ \mathrm{endOf}\left({\zeta}_{n+1,k}\right)-\mathrm{startOf}\left({\zeta}_{0,k}\right)\le {\overline{D}}_k\kern0.5em k\in K $$
(19.27)
$$ \mathrm{alternative}\left({h}_i,{\zeta}_{i,k}\right),\kern0.5em k\in K,i\in I $$
(19.28)

where || denotes the exclusive “or” operator, && the “and” operator, δ the travel matrix expressed in time units, and n + 1 the depot d. Equation (19.20) minimizes the total travel time. Constraint (19.21) ensures that service to client i starts within exactly one of the TWs of i while constraint (19.22) guarantees that a vehicle leaves and returns to d when d is open. Equation (19.23) makes the subsets of clients served by different vehicles mutually exclusive. Equations (19.24) and (19.25) force each vehicle to start and end its tour at d. Equation (19.26) imposes that the load of a vehicle be less than or equal to the vehicle’s capacity. Equation (19.27) limits the time out of d of vehicle k. Finally, Eq. (19.28) is the alternative constraint, which assigns every client to a single vehicle. CP obtains near-global optima for some benchmark instances, in particular, when the TWs are wide.

3.4 Enhancing MIP and CP

We use the above models as stand-alone heuristics by allocating fixed runtimes to their commercial solvers. To enhance their solvability, we couple them with some strategies.

  • First, we reduce the size of the problem by imposing logical assumptions that truck drivers adopt when constructing their solutions. A client j can’t immediately follow a client i on the route of vehicle k if the travel time δ ij is too large. Both MIP and CP formulations are augmented by the constraint x ijk = 0 if \( \left|{o}_i^h-{o}_j^h\right|>\frac{{\overline{o}}^h}{m} \) or \( \left|{o}_i^v-{o}_j^v\right|>\frac{{\overline{o}}^v}{m} \) or \( {\delta}_{ij}>\overline{\delta} \), where \( {\overline{o}}^h=\underset{\left(i,j\right)\in {I}^{\ast}\times {I}^{\ast }}{\max}\left\{{o}_i^h-{o}_j^h\right\} \), \( {\overline{o}}^v=\underset{\left(i,j\right)\in {I}^{\ast}\times {I}^{\ast }}{\max}\left\{{o}_i^v-{o}_j^v\right\} \), and \( \overline{\delta} \) is a maximal threshold time.

  • Second, we start the solvers from several feasible solutions. The multitude of starting points guards against the stagnation in local optima that are far from the global optimum.

  • Third, we iteratively fix clients to vehicles, deliveries to TWs, and solve the resulting problems. This avoids the need for disjunctive constraints and the sensitivity of solvers to the choice of M. At each iteration, we augment the model with the tightest known bounds. We obtain the lower bound by removing all TW-related constraints, thus reducing the problem to a series of single machine scheduling problems with sequence-dependent setup times and due date windows. The upper bound is updated every time a VRPMTW feasible solution is obtained.

  • Fourth, we iteratively divide the clients and vehicles into two or more disjoint subsets, solve the corresponding subproblems, merge their solutions, and compute the total travel time.

  • Fifth, we solve MIP with emphasis on constraint satisfaction rather than on optimization. This yields better quality solutions while tackling larger problems.

4 Solution Approach

To apply the above enhancements in a more systematic manner, we approximately solve VRPMTW via a two-stage approach. Stage 1 constructs a pool of initial solutions, where a solution assigns each client to a vehicle and sequences the clients of every vehicle. Stage 1 obtains solutions by one of nine constructive heuristics. These solutions are inspired from the way truck drivers construct their routes. They divide clients into sectors and choose the clients of a single vehicle from adjacent sectors. They construct the routes logically along the grid, a feature that enhances their chance of real-life implementation.

Stage 2 enhances the solutions of Stage 1 by perturbing the incumbent using a steepest descent neighborhood search. The search uses MIP to reassign clients to vehicles and CP to search for a feasible route of a vehicle. It embeds a look-ahead strategy that guards against infeasible/non-improving search directions. Sections 19.4.1 and 19.4.2 detail these two stages.

4.1 Stage 1

Because of the different distributions of the clients around the depot and of the varying number of vehicles and clients, it is difficult for a single heuristic to consistently generate good initial solutions. Therefore, we propose a panoply of constructive heuristics CH1, …, CH9. They all impose a maximal travel time \( \overline{\delta} \) between any (i ′, i +) when appending location i + to the current location i ′ of a vehicle. In addition to constraining the search space, this conforms to the way drivers plan their routes. Drivers prefer balanced routes; they would rather have equal stretches than a long haul followed/preceded by a series of small hauls. The constructive heuristics differ in the way they assign clients to trucks and how they route them. For example, CH1, CH7, and CH8 start from the closest client to the depot while CH2, …, CH6 select the first client randomly.

Some of the constructive heuristics (e.g., CH3 and CH4) use the notion of a sector. When the number of vehicles is large, the grid is divided into a series of radial sectors, where sector k, k = 1, … , m, is delimited by the angles \( \frac{2\left(k-1\right)\pi }{m} \) and \( \frac{2 k\pi}{m}, \) with sectors m + 1 and m + 2 coinciding with sectors k = 1 and k = 2, respectively. Client i, i ∈ I, is part of sector k if its polar coordinate \( {\theta}_i={\tan}^{-1}\left(\frac{o_i^v-{o}_0^v}{o_i^h-{o}_0^h}\right) \) falls in the sector of k. When the number of vehicles is small, the grid is split into m guillotine rectangular adjacent bands, with sector k corresponding to the band delimited by \( {o}^h=\frac{\left(k-1\right)\left({\overline{o}}^h-{\underline{o}}^h\right)}{m} \) and \( {o}^h=\frac{k\left({\overline{o}}^h-{\underline{o}}^h\right)}{m} \), where \( {\underline{o}}^h=\underset{\left(i,j\right)\in {I}^{\ast}\times {I}^{\ast }}{\min}\left\{{o}_i^h-{o}_j^h\right\} \).

Let F denote the set of free clients. Unless differently stated, F is initially set to I. In addition, let I k = {[1],  … , [n k]} denote the ordered set of n k=|I k| clients of k where \( {I}_k^{\ast }={I}_k\cup \left\{d\right\} \) with [n k + 1] = [0] = d signaling the end and the beginning of the tour at the depot. Using these definitions, we detail below each of the nine constructive heuristics.

CH1 considers the vehicles sequentially starting with k = 1. For the current vehicle k, it initializes the vehicle’s current capacity \( {Q}_k^{\mathrm{current}}=0 \) and the index of its current location i ′ = d. Iteratively, it assigns to k a free client i + ∈ F such that

  1. C1.

    i + is the closest client to i ′,

  2. C2.

    \( {Q}_k^{\mathrm{current}}+{q}_{i^{+}}\le {Q}_k \) —i.e., appending the demand of i + to the current load of k does not violate the load capacity of k,

  3. C3.

    delivery to i + may start during one of the TWs of i +, and upon completing delivery to i +, vehicle k may reach the depot

  4. C4.

    on-time (prior to u 0),

  5. C5.

    without exceeding its own maximal time out of the depot \( {\overline{D}}_k \).

Consequently, CH1 updates the vehicle’s current load: \( {Q}_k^{\mathrm{current}}={Q}_k^{\mathrm{current}}+{q}_{i^{+}} \), current location: i ′ = i + and the set of free clients: F = F ∖ {i +}. When CH1 fails to append any of the free clients to the current route of k, it considers the next vehicle: it sets k = k + 1.

Generally, CH1’s total travel distance is smaller than those of all other constructive heuristics; however, it may induce large waiting times. It is greedy and myopic by nature.

CH2 assigns all clients of a given sector to a same vehicle. Then, for each vehicle k, it applies CP to search for a feasible route; i.e., it applies Eqs. (19.20)–(19.25) and (19.27) of CP for K = {k}. When CP fails to identify a feasible route, we relax Eq. (19.25).

CH2 identifies good quality solutions when the sectors concord with the geographical clusters. CH2 offers balanced routes with every vehicle having to eventually serve those far away clients of its sector.

CH3 mimics CH2 except that it considers the clients of a sector sequentially. It assigns each vehicle k ∈ K to sector k. It then considers the vehicles sequentially starting with k = 1. For the current vehicle k, it initializes \( {Q}_k^{\mathrm{current}}=0 \) and the index of its current location i ′ = d. Iteratively, it assigns to vehicle k a free client i + from sector k such that \( {\delta}_{i^{\prime }{i}^{+}}<\overline{\delta} \), and constraints (C1)–(C5) hold. Consequently, it updates \( {Q}_k^{\mathrm{current}} \), i ′, and F.

When it fails to heuristically append any of the free clients of sector k to the current route, CH3 tries to insert a free client using an exact model. Let f ∈ F denote the free client to be inserted in the route of k. Let the binary decision variable χ [i] = 1, \( \left[i\right]\in {I}_k^{\ast } \), if client f is inserted immediately before client [i] on the route of k, and 0 otherwise. Let the positive decision variables t [i],  ω [i] , and c [i] denote, respectively, the time k reaches [i], waits before delivery, and ends delivery to [i], [i] ∈ I k, and (c 0, t 0) the time k leaves and returns to d. Finally, let parameter Δ[i] = δ [i − 1]f + δ f[i] − δ [i − 1][i] denote the net travel time change caused by inserting client f immediately before client [i]. In fact, k no longer travels between [i − 1] and [i]. Instead, it travels from [i − 1] to f to [i]. Using the above parameters and decision variables, MIP f tries to insert iteratively every free client f, f ∈ F, that satisfies C3 to the route of k using the following mixed integer program.

$$ \operatorname{Min}\ \sum \limits_{i\in {I}_k}{\Delta}_{\left[i\right]}{\chi}_{\left[i\right]} $$
(19.29)
$$ \mathrm{s}.\mathrm{t}.\sum \limits_{i\in {I}_k}{\chi}_{\left[i\right]}=1 $$
(19.30)
$$ {c}_{\left[i\right]}-{t}_{\left[i\right]}-{\omega}_{\left[i\right]}-{s}_{\left[i\right]}=0,\kern0.5em i\in {I}_k $$
(19.31)
$$ {t}_{\left[i+1\right]}-{c}_{\left[i\right]}-{\delta}_{\left[i\right]\left[i+1\right]}\left(1-{\chi}_{\left[i+1\right]}\right)+M{\chi}_{\left[i+1\right]}\ge 0,\kern0.5em i\in {I}_k $$
(19.32)
$$ {t}_{\left[i+1\right]}-{c}_f-{\delta}_{f\left[i+1\right]}{\chi}_{\left[i+1\right]}-M\left(1-{\chi}_{\left[i+1\right]}\right)\ge 0,\kern0.5em i\in {I}_k $$
(19.32′)
$$ {t}_{\left[i\right]}-{c}_f-{\delta}_{f\left[i\right]}{\chi}_{\left[i\right]}+M\left(1-{\chi}_{\left[i\right]}\right)\ge 0,\kern0.5em i\in {I}_k $$
(19.33)
$$ {t}_{\left[i\right]}+{\omega}_{\left[i\right]}-{\mathrm{\ell}}_{\left[i\right]p}+M\left(1-{v}_{\left[i\right]p}\right)\ge 0,\kern0.5em i\in {I}_k,p\in \left\{1,\dots, {\overline{p}}_{\left[i\right]}\right\} $$
(19.34)
$$ {t}_{\left[i\right]}+{\omega}_{\left[i\right]}-{u}_{\left[i\right]p}-M\left(1-{v}_{\left[i\right]p}\right)\le 0,\kern0.5em i\in {I}_k,p\in \left\{1,\dots, {\overline{p}}_{\left[i\right]}\right\} $$
(19.35)
$$ \sum \limits_{p=1}^{{\overline{p}}_{\left[i\right]}}{v}_{\left[i\right]p}=1,\kern0.5em i\in {I}_k $$
(19.36)
$$ {c}_0\ge {\mathrm{\ell}}_0 $$
(19.37)
$$ {t}_0\le {u}_0 $$
(19.38)
$$ {t}_0-{c}_0\le {\overline{D}}_k $$
(19.39)
$$ {\omega}_{\left[i\right]}\ge 0,\kern0.75em {c}_{\left[i\right]}\ge 0,\kern0.75em {t}_{\left[i\right]}\ge 0,\kern0.5em \left[i\right]\in {I}_k $$
(19.40)
$$ {v}_{\left[i\right]p}\in \left\{0,1\right\}\kern0.5em \left[i\right]\in {I}_k,p\in \left\{1,\dots, {\overline{p}}_{\left[i\right]}\right\} $$
(19.41)
$$ {\chi}_{\left[i\right]}\in \left\{0,1\right\}\kern0.5em i\in {I}_k^{\ast }. $$
(19.42)

Equation (19.29) chooses the position of the free client f on the route of vehicle k. It minimizes the additional net travel time. Equation (19.30) imposes that f be inserted in exactly one position. It is possible that f can’t be inserted without violating the TWs of the already routed clients. In such a case, MIPf is infeasible. Equation (19.31) relates the arrival, waiting, service and departure times for client [i]. Equations (19.32) and (19.33) compute the arrival time to a client relative to the departure time of the vehicle from the preceding client. Constraints (19.34)–(19.36) ensure that any client’s service starts within exactly one of the client’s TWs. Equations (19.37)–(19.39) restrict the vehicle’s departure from, return to, and time out of d. Finally, constraints (19.40)–(19.42) define the variable types.

MIPf is much easier to solve than MIP. First, the clients’ sequence is fixed. Second, the number of alternative positions for inserting f is small. Third and last, for every client [i], [i] ∈ I k, many TWs can be removed from the model by preprocessing the data. For \( p\in \left\{1,\dots, {\overline{p}}_{\left[i\right]}\right\},\kern0.5em {v}_{\left[i\right]p}=0 \), if

$$ {u}_{\left[i\right]p}\le \sum \limits_{\left[j\right]=1}^{\left[i\right]}{\delta}_{\left[j-1\right]\left[j\right]}+\sum \limits_{\left[j\right]=1}^{\left[i-1\right]}{s}_{\left[j\right]}. $$
(19.43)

When the insertion of a free client of the current sector into the route of k deems impossible (i.e., MIPf is infeasible), CH3 appends it to sector k + 1.

CH3 is less sensitive to the physical limits imposed by the sectors while it yields good results when the clients are clustered. It maintains low traveled times per vehicle and makes the evolution of the route progress logically.

CH4 proceeds as CH3 does except that it considers clients from larger areas. It assigns to vehicle k a free client i + from sectors k − 1, k, and k + 1 such that \( {\delta}_{i^{\prime }{i}^{+}}<\overline{\delta} \) and C1–C5 hold. It generally obtains as good routes as CH3 or better, but may require more calls to MIPf (depending on the distribution of the clients on the grid and of the TWs) as it considers more free clients for each vehicle k, k ∈ K. CH4 is particularly useful in the presence of a mixture of clustered and randomly distributed clients.

CH5 and CH6 are similar to CH3 and CH4 except that they build a route from both ends: assigning simultaneously two clients to the route: the client that is closest to the previous position of the truck and a client that is closest to the next position in the return path of the truck.

CH7 assigns each client i, i ∈ I, to a vehicle k, k ∈ K, where k is randomly selected from the discrete uniform [1, m]. It then applies Eqs. (19.20)–(19.25) of CP to sequence the clients of each vehicle. CH7 is a blind random search. As such, it can’t be competitive when the clients are clustered. It can be used as part of a diversification strategy with a population-based meta-heuristic. Alternatively, it can be applied a fixed large number of times, and its best feasible solution is retained for further use. Obviously, it is useful when the clients are uniformly distributed.

CH8 balances the number of clients per truck. It considers the m trucks sequentially, assigning to each truck k, k ∈ K, the client that is closest to the previous location of k. It reiterates through the m trucks until all clients are assigned. When \( \frac{n}{m} \) is integer, all trucks have an equal number of clients; otherwise, the numbers of clients for any two trucks do not differ by more than one. It then reduces the violations of the TWs of the clients of each route by applying CP.

CH9 is inspired from CH8 in that it assigns an equal number of clients to each truck except that it only considers clients from the sector of vehicle k, k ∈ K. When it exhausts the clients of its sector, vehicle k chooses clients of sector k + 1. Any unassigned clients of a sector k are automatically appended to sector k + 1. CH9 uses MIPf to insert each client to the route of k.

CH3–CH9 apply a look-ahead search strategy that prohibits the search in infeasible directions. They abort constructing a solution if the demand of the free clients can’t be assigned to the residual capacities of the vehicles or the residual travel time can’t accommodate visiting them. This is guaranteed by solving a binary multiple choice multiple knapsack problem (MCKP) whose decision variables y f, k = 1 if the demand of free client f, f ∈ F, can be loaded to vehicle k, k ∈ K, during one of the next iterations. MCKP is also used to choose the subset of free clients that may potentially be appended to the current route of the vehicle k when applied with K = {k}. Let \( {c}_k^{\mathrm{current}} \) be the current total travel time of k and \( {\underline{\delta}}_i=\underset{i^{\prime}\in {I}^{\ast}\left\{i\right\}}{\min}\left\{{\delta}_{i{i}^{\prime }}\right\} \) be the smallest travel time from i, i ∈ I ∗, to any other client i ', i ' ∈ I ∗{i}. MCKP follows.

$$ \operatorname{Max}\ \sum \limits_{k\in K}\sum \limits_{f\in F}{y}_{f,k} $$
(19.44)
$$ \mathrm{s}.\mathrm{t}.\ \ \ \sum \limits_{k\in K}{q}_f{y}_{f,k}\le {Q}_k-{Q}_k^{\mathrm{current}},\kern0.5em k\in K $$
(19.45)
$$ {c}_k^{\mathrm{current}}+\sum \limits_{f\in F}\ \left({\underline{\delta}}_f+{s}_f\right)\ {y}_{f,k}+{\underline{\delta}}_0-{t}_0\le {\overline{D}}_k,\kern0.5em k\in K $$
(19.46)
$$ \sum \limits_{k\in K}\ {y}_{f,k}\leq 1,\kern0.5em f\in F $$
(19.47)
$$ {y}_{f,k}\;\mathrm{Binary},\kern0.5em f\in F,k\in K $$
(19.48)

Equation (19.44) provides an upper bound to the number of free clients that can be inserted. Equation (19.45) ensures that the demand of the clients that could be assigned to a vehicle will not exceed the vehicle’s residual capacity. Equation (19.46) guarantees that the additional travel time caused by the assignment of free client to a vehicle will not exceed that vehicle’s residual travel time. Equation (19.47) reinforces that a free client is served by at most a single vehicle. Finally, Equation (19.48) defines the binary nature of the assignment variable; that is, no partial delivery to a client. When the objective function equals the number of free clients, it may be possible to find a feasible solution to VRPMTW, without any guarantee that such a solution exists. On the other hand, a zero upper bound signals an infeasible direction of the search and halts the construction process. As this problem is solved a large number of times, its integer programming form is only considered when its linear relaxation succeeds in packing all free items.

4.2 Stage 2

Stage 2 enhances each solution of Stage 1 by perturbing the incumbent using a steepest descent neighborhood search and using CP to define both feasible and infeasible directions of the search. Three perturbation mechanisms are used:

  • Merge I k and I k' for k and k ′ serving adjacent sectors and apply CP for |K| = 2 and \( I={I}_k\cup {I}_{k^{\prime }}, \)

  • Remove every client i,  i ∈ I k, and insert i into \( {I}_{k^{\prime }} \), k ≠ k ′, using MIPf

  • Remove i 1 and i 2 from I k and insert them, respectively, into \( {I}_{k^{\prime }} \) and \( {I}_{k^{{\prime\prime} }} \) using MIPf

Inserting client i into the route of vehicle k ′ is tested if (1) the residual capacity \( {Q}_{k^{\prime }}-{Q}_{k^{\prime}}^{\mathrm{current}} \) of k ′ exceeds demand q i, (2) the slack time of k ′ is less than the minimal additional travel and service times caused by the insertion of i, and (3) the minimal variation Δ of the travel time caused by the swap is negative. That is, CP and MIPf are only applied when the perturbation may lead to an improving solution. A neighbor is improving if it (1) reduces the fitness of the incumbent or (2) is feasible while the incumbent is not.

5 Results

We applied the resulting heuristic on benchmark instances, which have randomly distributed (rm) clients, clustered (cm) clients, randomly distributed clusters of clients (rcm), tight (1) and wide (2) TWs. The tighter the TWs, the larger the number of vehicles is. The heuristic was run on a laptop with a 2.90 GHz Intel Core i7 processor and a 16.0 GB RAM. It was allocated a maximal runtime of 9 min per initial solution per instance. All calls to CP and MIP were allocated 3 and 10 s of runtime with all travel times rounded to their nearest integer.

Table 19.1 illustrates the variation of the solution values obtained by the constructive heuristics for 24 benchmark instances. Columns 1–5 display the label of the instance, the minimal and maximal number of TWs \( \underline{p} \) and \( \overline{p} \), the minimal and maximal time gap \( \underline{\tau} \) and \( \overline{\tau} \) between two consecutive TWs, the minimal and maximal ranges \( \underline{w} \) and \( \overline{w} \) of the TWs, and the number of vehicles m. Columns 6 and 7 display \( \overline{z} \) and s, the average and standard deviation of CH1 to CH9 solution values. Column 7 reports \( \Delta =\frac{\left(\overline{z}-{z}^u\right)}{z^u}100\% \), the percent deviation of \( \overline{z} \) from the upper bound z u obtained by TSVNS while column 8 indicates the index of the CH yielding the best solution value.

Table 19.1 Variation of the solution values of Stage 1
Full size table

Table 19.1 suggests that none of the constructive heuristics obtains the best initial solution value consistently. Each of them is adapted to a particular class of TWs and tailored to a different distribution of clients on the grid. Table 19.1 further indicates that the initial solutions are reasonably good with a 3.96% average Δ from z u.

Table 19.2 assesses the heuristic’s performance. Columns 1–5 and 6–10 display the label of the instance, the number of vehicles m, the heuristic’s best solution value z ∗, the known bound z u, and \( {\Delta}^{\ast }=\frac{\left({z}^{\ast }-{z}^u\right)}{z^u}100\% \)the percent deviation of z ∗ from z u.

Table 19.2 Heuristic’s performance on benchmark instances
Full size table

None of the constructive heuristics makes stage 2 systematically obtain the best traveled time. This suggests that the nine local optima identified by stage 2 are not in the same vicinity. Indeed, their delivery plans differ in terms of routes and clients’ sequencing. Thus the importance of the multiple restart of the heuristic.

The nine constructive heuristics are fundamental to building good initial starting points. Stage 2 obtains consistently lower traveled distances when initiated from these nine solutions than when initiated randomly. The comparison of the solution values obtained in Tables 19.1 and 19.2 highlights the importance of stage 2 in identifying a near-global optimum.

The proposed heuristic lowers the travel time for 22 out of 48 benchmark instances with the reduction reaching 9.06% for rcm208. All the time reductions were recorded for rm and rcm classes. The analysis of the results further showed that the best known solutions z u correspond to solutions that are on the edge of feasibility. For instance, any slight increase of the travel time between pairs of clients may cause the violation of the TW constraints. This questions the validity of the best known solutions in a real-life context, as explained below.

6 Practical Considerations

Rincon-Garcia et al. (2018) discuss barriers to the implementation of VRP-related solutions in real-life contexts. Herein, we enumerate few such barriers and explain how the proposed model can handle them.

6.1 Single Versus Multiple Depots

Even though MIP and CP are given for a single depot, extending them to a multiple-depot case is straightforward. Two cases are possible: Subsets of vehicles are already allocated to each of the depots or the vehicles are allocated to the depots once an optimal solution to the problem is obtained. The former case is the more prevalent because vehicles are generally tagged to depots and goods are already stocked in specific depots. Such a case reduces to solving several single-depot problems. The latter case can be handled by defining I ∗ as the union of the set of depots and the set of clients. Then, Equations (19.9) and (19.9′) will apply to all i ∈ I ∗ while (19.12)–(19.14) will be defined for each of the depots d ∈ I ∗\I. The same applies to Equations (19.22)–(19.24) of CP.

6.2 Distances and Travel Times

In MIP and CP, the time matrix δ may be the result of a transformation into time units of the Euclidean distances that separate any pair of locations (i, j) ∈ I ∗ × I. These distances are an accurate estimation of the true distances in the absence of natural or human made barriers or when locations are very far away, i.e., when the time needed to cover the travel distance is much larger than delays that may be caused by local traffic or the routing within the neighborhood of either i or j. In this case, transforming the distances into time units can be based on the average speed of the vehicle (on the highway). On the other hand, when the depot and clients are within the same city, a more relevant measure may be the actual distance the vehicles have to travel. For example, in newer cities, these distances could be estimated by the sum of the distances along the two axes because of the grid structure of the streets. In older cities, these distances should correspond to the true route that the vehicle will use. For instance, they can be approximated using Google Maps or similar software. Their transformation into time units should account for local traffic. The actual travel times are stochastic in nature because of traffic, weather conditions, road construction, unforeseen accidents, driver’s state of mind, time of day, etc. Consequently, the time estimates corresponding to the traveled distances should be worst case estimates. This will avoid generating solutions that are on the edge of feasibility and that will cause tardy deliveries.

In the proposed models, travel times are not necessarily symmetric. Even when distances are equal, travel times may differ. In this sense, the above models are general. Travel time can always be expressed as a polynomial relationship of trip time.

6.3 Time Windows

The TWs are herein defined as hard; i.e., they must be satisfied for any solution to be feasible. This may be the case for vehicles in cities with travel bans or for deliveries in downtown areas or for private households. To ensure that their deliveries be on-time, constructors tend to account for possible traffic delays and reduce the range of their TWs. That is, their declared TWs are much tighter than their true TWs. For businesses, TWs are either soft or slightly flexible. Businesses tend to wait few extra minutes hoping to receive a delivery rather than to have it postponed. Similarly, households give conservative/tighter TWs than their true availability. They may resort to the help of a neighbor or a family member to receive the delivery. All these factors can be easily accommodated by altering Equations (19.9)–(19.14) and (19.21)–(19.22), e.g., by adding a flexibility factor φ and studying the sensitivity of the solutions to the size of φ.

6.4 Collection Versus Distribution

Both models apply whether the goods are being delivered or collected. However, for a distribution problem, items requested by a customer could be in different depots. In this case, the problem can be divided into two steps: Collecting all goods into a single depot (or moving from a national depot to a local one), then distributing the cumulated goods (i.e., delivery from a local depot to customers). Both steps can be perceived as VRPMTW with the clustering solved as in the generalized traveling salesman problem.

6.5 Packing Constraints

Equations (19.7) and (19.22) are loading constraints, expressed in terms of the capacity of the vehicle. They assume that the loads are shapeless volumes. However, unless the goods are liquid (e.g., petroleum for gas stations, water), these constraints are a relaxation of three-dimensional non-overlap and envelopment constraints. In some instances, the packing has to also account for the accessibility of the items as a function of their order of delivery. Adding such constraints eliminates a large number of alternative solutions and reduces the search space.

6.6 Stochastic Travel Times and Time Windows

In MIP and CP, the travel times are deterministic. Yet, delays always occur. Travel times may vary according to time of day, traffic, weather conditions, etc. Even though delays are generally undesirable, they may be used in some circumstances to the advantage of the vehicle. When a vehicle is delayed on a route that doesn’t include enough slack time to compensate for it, deliveries may have to be postponed to a later TW for a particular client but may allow an earlier delivery to another client. In such circumstances, it is judicious to apply a dynamic rerouting of the non-served clients with the objective of minimizing the travel time and the violation of TW penalties. This is of course only possible in small cities where deliveries are within the same vicinity.

Because travel times are non-deterministic, the above models assume that travel times and TWs correspond to worst case scenarios rather than average or modal values. In real life, these bounds are fuzzy. Vehicles reaching clients early may be able to start service immediately. Similarly, those reaching few minutes late may still get a chance to serve their clients during the intended TWs. Again, clients are generally willing to wait few extra minutes for the arrival of a delivery and may be available prior to the TW; i.e., the TWs’ bounds are very conservative (i.e., tightest bounds).

When the average in lieu of the worst case performance is sought, a stochastic VRPMTW is at hand. It can be addressed via a stochastic program, which determines the routes that minimize the expected total travel time. The stochastic model can be tackled using a sample average approximation (Al-Khamis and M’Hallah, 2011) that iteratively determines the optimal routes of the vehicles for given samples of uncertain travel times and TWs. This method converges to the optimal travel time in the expected sense as the number of sampled scenarios increases. Each sample corresponds to a deterministic VRPMTW.

An alternative is to apply robust optimization (Mulvey et al. 1995). This method identifies solution robust (near-optimal) model robust (almost feasible) delivery plans. These plans are less sensitive to the uncertainty of the problem. They bound the infeasibility of the plans corresponding to the different scenarios and their distances from the optima by transforming the uncertain problem into a goal program. The weighted goal reflects the tradeoff between feasibility and optimality under all possible scenarios with the weights reflecting the likelihood of each scenario. Despite its attractiveness, robust optimization may become intractable for VRPMTW because of the very large number of possible scenarios, a number that increases with the number of clients, of TWs, and vehicles.

7 Conclusions

This chapter proposed a general framework for solving a complex compounded problem. This framework explores the complementary strengths of constraint and mixed integer programming. It builds and enhances solutions using constraint/mixed integer programming-based neighborhood search. The search is guided by feasibility constraints and look-ahead strategies that fathom large parts of the infeasible search space and focuses the search towards improving solutions. This framework was illustrated on the vehicle routing problem with multiple time windows. It can be extended to other compounded problems such as vehicle routing with packing constraints, bin packing with due dates, scheduling with cutting constraints or assembly limitations or resource unavailability.

This framework has several advantages. It requires no tuning and guarantees the reproducibility of the results. These two features can't be achieved by meta-heuristics that rely on seeds of random numbers. Such meta-heuristics include genetic algorithms, simulated annealing, ant colonies, swarm optimization, and bee colonies. Such techniques are generally assessed via their “average performance,” a practice that is not justifiable in the service industry.