A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

Abstract

The multi-depot vehicle routing problem with inter-depot routes is studied in this paper, where vehicles may reset their capacity at any depot during the working day. Due to the complexity of this problem, exact approaches are limited to small-size applications. In order to overcome this limitation, we propose a matheuristic which integrates a mixed integer linear programming formulation with a set of relax-and-fix strategies. This solution approach is shown to be very efficient, and for the first time, large-size benchmarking instances are solved.

1 Introduction

Complex logistics systems often entail the use of several depots, where goods are stored and vehicles are allocated, from where they perform distribution activities. Such logistics networks also include storage facilities (like warehouses) that are not directly involved in distribution activities and therefore have no allocated vehicles. The major difference between a depot and a warehouse is that, by convention, the former serves as origin and final destination of vehicles, whereas the latter usually only serves as an intermediate facility within a vehicle’s routes. In a multi-facility scenario, this distinction leads to four different routing problems (see Table 1 and Fig. 1):

Table 1 Characteristics of five types of routing problems

Fig. 1

Schematic representation of four types of routing problems

• (1) the vehicle routing problem with intermediate facilities (VRPIFs) where one facility acts as depot and the remainder as warehouses,

• (2) the multi-depot vehicle routing problem (MDVRP) where all facilities act only as depots,

• (3) the multi-depot vehicle routing problem with intermediate facilities (MDVRPIFs) where some facilities act as depots and some as warehouses,

• (4) the multi-depot vehicle routing problem with inter-depot routes (MDVRPIs) where all facilities can act simultaneously as depots and as warehouses.

A VRP (see Table 1) is characterized by a logistics network with a single depot and no warehouses. The VRP has been extensively studied in the literature, and several algorithms have been proposed to solve it. Laporte (2009) and Toth and Vigo (2014) give a comprehensive overview of the problem. Due to its combinatorial nature, several heuristics have been developed to solve this problem, spanning from classical heuristics to metaheuristics and, more recently, matheuristics. Classical heuristics were classified by Laporte and Semet (2002) into three categories: constructive [e.g. Clarke and Wright (1964)]; two-phase [e.g. Gillet and Miller (1974), Renaud et al. (1996a)]; and improvement heuristics (e.g. Lin (1965), Lin and Kernighan (1973), Van Breedam (2001)]. Metaheuristics were classified by Laporte (2009) into three categories: local search (e.g. tabu search, simulated annealing and variable neighbourhood search); evolutionary algorithms (e.g. genetic algorithms and adaptive memory); and learning mechanisms (e.g. neural networks and ant colony optimization). Matheuristics are the result of a hybridization between heuristics and mathematical programming (Maniezzo et al. 2009), which exploit mathematical programming techniques within a heuristic framework.

Additionally, for the single-depot case (see Table 1 and Fig. 1), the existence of intermediate facilities allows drivers to reset the capacity of their vehicles during a shift without having to return to the central depot. In such logistics systems, a feasible route sequence starts at a central depot, visits a subset of customers, may refill at one of the intermediate facilities before visiting more customers, and returns to the depot. Refilling is allowed when required and vehicles only return to the original depot at the end of the route. The refill may occur at an intermediate facility or at the central depot. The same vehicle can perform multiple trips per day, which relates this problem with the Multi-Trip VRP. Several methods have been proposed in the literature for solving the Multi-Trip VRP. Brandao and Mercer (1997) developed a tabu search, Petch and Salhi (2003) developed a constructive heuristic, Mingozzi et al. (2013) developed an exact algorithm based on the set partitioning formulation, and Cattaruzza et al. (2014) proposed a memetic algorithm, just to name a few works.

The term “intermediate facilities” was first introduced by Angelelli and Speranza (2002); however, some years prior, Bard et al. (1998) used the term “satellite facilities”. Note that, “intermediate facilities” and “satellite facilities” are considered as having the same meaning in logistics. Bard et al. (1998) introduced the VRP with satellite facilities as a mixed integer linear programming formulation and developed a branch-and-cut algorithm to solve it. Angelelli and Speranza (2002) tackled the same problem, calling them intermediate facilities instead of satellite facilities, in a collection context. In this problem, a vehicle departs from the depot to collect goods from customers. When the vehicle is at full capacity, it heads towards an intermediate facility in order to unload the goods, after which it may start another collection route until the work shift ends, when it must return to the central depot. The authors develop a tabu search algorithm to solve the periodic VRP with intermediate facilities and present computational results on a set of instances. Similar collection problems have also been addressed by Kim et al. (2006), Benjamin and Beasley (2010), and Hemmelmayr et al. (2013). Tarantilis et al. (2008) also addressed the VRP with intermediate facilities and proposed a three-step algorithmic framework to solve the problem, which is based on a set of metaheuristic procedures. The developed approach was applied to a set of large-scale test instances.

Finally, the existence of multiple depots allows vehicles to be based at different depots (instead of at a central depot). In the classical MDVRP, routes start and end at the same depot, and only customers are visited in between. Stops at intermediate facilities are not allowed. Several works have been published addressing this problem, where mainly heuristic approaches have been developed [see Chao et al. (1993), Renaud et al. (1996b), Cordeau et al. (1997), Lim and Wang (2005), Dondo and Cerda (2009), Vidal et al. (2012), Tu et al. (2014)]. Using exact approaches, the works of Laporte et al. (1984, 1988) and Baldacci and Mingozzi (2009) also solved the MDVRP problem. The introduction of intermediate facilities can be considered an extension of the classical MDVRP. This problem has been modelled either as a MDVRP with intermediate facilities (where only warehouses act as intermediate points), or as a MDVRP with inter-depot routes (when depots, other than the vehicle’s home depot, also act as intermediate points). To the best of the authors’ knowledge, the MDVRP with intermediate facilities has only been addressed in the work of Markov et al. (2016), while the MDVRP with inter-depot routes was introduced by Crevier et al. (2007) and later studied by Muter et al. (2014).

Markov et al. (2016) addressed a real case of a complex recyclable waste collection system. In this problem, each vehicle route starts and ends at one of several depots, not necessarily the same for each vehicle. A sequence of collections followed by disposals at the available dumps (the intermediate facilities) was observed. In this case, since several depots are involved, the problem can be framed as a MDVRP instead of VRP. In addition, given that all routes must pass through a dump (intermediate facility) before returning to a depot, the problem is classified as a MDVRP with intermediate facilities. With the introduction of a flexible assignment of destination depots, it follows that a vehicle can start and end its route at different depots. A mathematical model based on the three-index formulation was developed, and as solution approach, a multiple neighbourhood search heuristic was designed and tested on literature instances, leading to the solution of a real case.

Crevier et al. (2007) introduced the MDVRP with inter-depot routes and the concept of “rotation”. A rotation is defined as “the set of routes assigned to the same vehicle, which are constrained by a preset maximum duration”. A rotation has to start and end at the same depot and may include single-depot routes (a route starting and ending at the same depot), inter-depot routes (a route connecting two different depots) or a combination of the two. Crevier et al. (2007) proposed a set partitioning approach to solve the problem. This requires an a priori definition of all single-depot and inter-depot routes, a so-called herculean task. The solution method developed by the authors entailed the use of a tabu search heuristic, previously proposed by Cordeau et al. (1997), in order to select the set of routes to be considered in the partitioning formulation. Given the novelty of the work, new benchmark instances were generated to demonstrate the model’s adequacy. Under the assumption that it is rarely cost-effective to use inter-depot routes when vehicles are based at different depots, the authors considered, in the solved instances, that vehicles were solely located at the central depot and that all other depots were used only as intermediate replenishment facilities. In fact, Crevier et al. (2007) solved a problem that was later re-named as VRPIF by Tarantilis et al. (2008), to emphasize “both the replenishment role of the intermediate facilities and the use of a single central station for the fleet of vehicles”. Later, Muter et al. (2014) tackled the MDVRPI where vehicles could be based at multiple depots rather than at a single central depot. A branch-and-price algorithm with two different pricing strategies was proposed and tested on new instances based on the benchmarking instances developed by Crevier et al. (2007). These instances have 25 and 40 customers, and 4 and 6 vehicles, respectively. Summing up, Crevier et al. (2007) developed benchmarking instances for the MDVRPI but solved them as a VRPIF, while Muter et al. (2014) solved the MDVRPI but only for smaller instances (with 25 and 40 customers). Thus, the original benchmarking instances developed for the MDVRPI (with 48–288 customers) have not yet been solved as a MDVRPI, in which vehicles are based in multiple depots. This establishes a research opportunity.

In this paper, we aim to explore this research opportunity and our contribution is threefold: Firstly, we propose a new formulation for the MDVRPI through a flow formulation, where both routes and rotations are simultaneously defined by the model. Therefore, we overcome the need of generating routes beforehand. We define “rotation”, “single-depot route” and “inter-depot route” as defined by Crevier et al. (2007): “the set of all routes assigned to a vehicle is called a rotation whose total duration cannot exceed a preset value”, “a single-depot route starts and ends at the same depot while an inter-depot route connects two different depots”. Our model addresses tactical-operational decisions as the strategic decisions regarding the number and location of the facilities in the network were already defined, but the role of each facility (depot, intermediate facility or both), as well as the home depot for each vehicle, is to be defined while simultaneously defining the routing plan to be implemented for a medium-term period.

Secondly, to overcome the computational burden associated with the type of problem being studied, we develop a matheuristic procedure that explores a decomposition approach based on the relaxation of some constraints of the full proposed mathematical model. This matheuristic is capable of solving the majority of the instances used by Muter et al. (2014), in addition to the original MDVRPI instances with vehicles based at multiple depots which, to the best of our knowledge, were solved for the first time in this work. We choose this specific type of heuristic because we want to explore the mathematical formulation as much as possible, since this provides a generic form of structuring and formulating these problems, exploring the problem characteristics. The advantages of matheuristics are, on the one hand, granting to mathematical programming approaches the robustness and time effectiveness that characterize heuristics and, on the other hand, exploiting the mathematical programming model formulation in the customization of a heuristic for specific problems.

Lastly, and considering the applicability of the problem in hand, the economic benefit of stationing vehicles at multiple depots rather than at a central depot is assessed. The characteristics of a MDVRPI occur in real problems such as grocery distribution problems as addressed by Crevier et al. (2007); recyclable waste collection networks with multiple facilities, where trucks may unload the collected recyclable waste at any depot of the network; or the management of an electric fleet of vehicles, which have to recharge their batteries during a working day (Schneider et al. 2015).

The remainder of the paper is structured as follows: in Sect. 2, the mathematical formulation for the MDVRPI is presented, followed by the discussion of the solution methodology developed in Sect. 3. Computational results obtained for benchmark instances are reported in Sect. 4. Finally, Sect. 5 concludes the paper and proposes some suggestions for further research.

2 Problem formulation

The MDVRPI can be defined as the problem of designing a set of vehicle rotations which optimize a predetermined objective, such as the minimization of a total routing cost, while assuring that: (1) a rotation starts and ends at the same depot; (2) the duration of a rotation (including travel, service and loading times) does not exceed a preset limit; (3) a route starts at a certain facility but may end in a different one; (4) each customer is visited exactly once; and (5) the total demand covered by each route does not exceed the vehicle capacity. Note that, while a rotation must start and end at the depot where vehicles are parked, routes can start and/or end at any type of facility. Any facility may act as depot, as an intermediate facility or as both.

The MDVRPI problem is formulated in this work exploring the two-commodity flow formulation concepts (Baldacci et al. 2004). An undirected graph $G = \left( {V,E} \right)$ is considered, where $V = V_{c} \cup V_{f} \cup V_{g}$, being $V_{c} = \left\{ {1, \ldots ,n} \right\}$ a set of n customers, $V_{f} = \left\{ {n + 1, \ldots ,n + w} \right\}$ a set of w facilities, $V_{g} = \left\{ {n + w + 1, \ldots ,n + 2w} \right\}$ a replica of the facility set and $E = \left\{ {\left( {i,j} \right):i,j \in V_{c} \cup V_{f} \cup V_{g} ,i \ne j} \right\}$ the edge set. The facility replica set is needed because, in the two-commodity flow formulation, routes are defined by paths between the real facilities and the replica ones. To establish the routes, this formulation requires two flow variables that, in turn, define two flow paths for any route. One of the paths, from the real facilities to the replica ones, designed through the flow variable, represents the load of the vehicle, which decreases along the route in a distribution problem. The other path, from the replica facilities to the real ones, corresponds to the second flow variable and represents the empty space on the vehicle, which increases along the route.

Each customer is characterized by their demand $P_{i}$ and service time $S_{i}$. Each route $k$ of set $K = \left\{ {1, \ldots ,s} \right\}$ has a capacity of $Q$ units, and each rotation $r$ of set $R = \left\{ {1, \ldots ,m} \right\}$ has a maximum duration of $T$. Each edge $\left( {i,j} \right)$ has an associated cost $C_{ij}$ and a travel time $F_{ij}$. We also consider a loading time $L$ to account for the time it takes to fully load a vehicle at the start of each route.

The following decision variables are defined:

$$ x_{ijkr} \left\{ {\begin{array}{*{20}l} {1,{\text{if}}\,{\text{ edge}}\,(i,j)\,{\text{is}}\,{\text{ traversed}}\,{\text{on}}\,{\text{ route}}\,k\,{\text{that }}\,{\text{belongs}}\,{\text{to}}\,{\text{ rotation}}\,r} \hfill \\ {0,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

$y_{ijkr}$ :

Flow variable representing the vehicle load when travelling from nodes i to j on route k that belongs to rotation r. The flow $y_{jikr}$ represents the empty space on vehicle route k that belongs to rotation r

$$ z_{ikr} \left\{ {\begin{array}{*{20}l} {1,{\text{if}}\,{\text{ node}}\,i\,{\text{is }}\,{\text{visited }}\,{\text{by }}\,{\text{route}}\,k\,{\text{on}}\,{\text{ rotation}}\,r} \hfill \\ {0,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

$e_{ijkr}$ :

Exit time from node i to node j on route k on rotation r

$a_{ijkr}$ :

Arrival time at node j from node i on route k on rotation r

$$ g_{ikr} \left\{ {\begin{array}{*{20}l} {2,\,{\text{if}}\,{\text{ route}}\,k\,{\text{starts}}\,\underline{\text{and}} \,{\text{ends}}\,{\text{ at}}\,{\text{ depotion}}\,{\text{ rotation}}\,r} \hfill \\ {1,{\text{ if }}\,{\text{route}}\,k\,{\text{starts}}\,\underline{\text{or}} \,{\text{ends }}\,{\text{at}}\,{\text{ depotion}}\,{\text{ rotation}}\,r} \hfill \\ {0,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

The mathematical formulation also includes the following auxiliary variables:

$$ \alpha_{ikr} \left\{ {\begin{array}{*{20}l} {1,{\text{if}}\,{\text{ route}}\,k\,{\text{does}}\,{\text{ not }}\,{\text{start }}\,{\text{nor}}\,{\text{ ends}}\,{\text{ at}}\,{\text{ depotion}}\,{\text{ rotation}}\,r} \hfill \\ {0,\,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

$$ \beta_{ikr} \left\{ {\begin{array}{*{20}l} {1,{\text{if}}\,{\text{ route}}\,k\,{\text{starts}}\,\underline{\text{or}} \,{\text{ends}}\,{\text{ at }}\,{\text{depotion}}\,{\text{ rotation}}\,r} \hfill \\ {0,\,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

$$ \delta_{ikr} \left\{ {\begin{array}{*{20}l} {1,{\text{if}}\,{\text{ route}}\,k\,{\text{starts}}\,\underline{\text{and}} \,{\text{ends}}\,{\text{ at}}\,{\text{ depotion}}\,{\text{ rotation}}\,r} \hfill \\ {0,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

$$ \gamma_{ir} \left\{ {\begin{array}{*{20}l} {1,{\text{if}}\,{\text{ rotation}}\,r\,{\text{starts}}\,{\text{ at }}\,{\text{depot}}\,i} \hfill \\ {0,\,{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

The solution for the MDVRPI is a set of at most m constrained cycles (called rotations) on graph G which minimizes the total cost while ensuring that every customer is visited. The cycles are smaller than or equal to a maximum duration T, and each segment of the cycle (single-route or inter-depot route) is feasible with respect to the vehicle capacity Q. Figure 2 depicts a feasible solution for the MDVRPI, where three rotations are defined through eight routes. Rotation 1 includes three routes (one single-depot and two inter-depot routes—in blue), rotation 2 has two routes (all single-depot routes—in black) and rotation 3 has three routes (all inter-depot routes—in orange).

Fig. 2

Representation of a feasible solution for the MDVRPI (color figure online)

The MDVRPI formulation is then:

$$ {\text{minimize}}\;\frac{1}{2}\mathop \sum \limits_{i \in V} \mathop \sum \limits_{j \in V} \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} x_{ijkr} C_{ij} $$

(1)

$$ {\text{subject }}\,{\text{to }}\, \mathop \sum \limits_{j \in V} \left( {y_{jikr} - y_{ijkr} } \right) = 2P_{i} z_{ikr} ,\quad \forall i \in V_{c} ,k \in K,r \in R $$

(2)

$$ \mathop \sum \limits_{{i \in V_{f} }} \mathop \sum \limits_{{j \in V_{c} }} \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} y_{ijkr} = \mathop \sum \limits_{{j \in V_{c} }} P_{j} $$

(3)

$$ \mathop \sum \limits_{{i \in V_{f} }} \mathop \sum \limits_{{j \in V_{c} }} \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} y_{jikr} \le \left| K \right|Q - \mathop \sum \limits_{{j \in V_{c} }} P_{j} $$

(4)

$$ \mathop \sum \limits_{{j \in V_{c} }} y_{ijkr} \le Q, \quad \forall i \in V_{g} ,k \in K,r \in R $$

(5)

$$ y_{ijkr} + y_{jikr} = Qx_{ijkr} ,\quad \forall i,j \in V,k \in K,r \in R $$

(6)

$$ \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V} \\ {i \ne j} \\ \end{array} }} x_{ijkr} = 2z_{jkr} , \quad \forall j \in V_{c} ,k \in K,r \in R $$

(7)

$$ \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} z_{ikr} = 1, \quad \forall i \in V_{c} $$

(8)

$$ \mathop \sum \limits_{r \in R} z_{ikr} \le 1, \quad \forall i \in V_{c} ,k \in K $$

(9)

$$ \mathop \sum \limits_{k \in K} z_{ikr} \le 1, \quad \forall i \in V_{c} ,r \in R $$

(10)

$$ \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} x_{ijkr} \le 1, \quad \forall i,j \in V,i \ne j $$

(11)

$$ \mathop \sum \limits_{{i \in V_{f} }} \mathop \sum \limits_{j \in V} x_{ijkr} \le 1, \quad \forall k \in K,r \in R $$

(12)

$$ e_{ijkr} + F_{ij} x_{ijkr} = a_{ijkr} ,\quad \forall i,j \in V,i \ne j,\forall k \in K,r \in R $$

(13)

$$ \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V} \\ {i \ne j} \\ \end{array} }} \left( {e_{jikr} - a_{ijkr} } \right) = 2S_{j} z_{jkr} , \quad \forall j \in V_{c} ,k \in K,r \in R $$

(14)

$$ e_{ijkr} - \mathop \sum \limits_{{h \in V\backslash \left\{ {i,j} \right\}}} a_{hikr} \le S_{i} x_{ijkr} , \quad \forall i \in V_{c} ,\forall j \in V,i \ne j,\forall k \in K,r \in R $$

(15)

$$ e_{ijkr} \le Tx_{ijkr} ,\quad \forall i,j \in V,k \in K,r \in R $$

(16)

$$ a_{ijkr} \le Tx_{ijkr} ,\quad \forall i,j \in V,k \in K,r \in R $$

(17)

$$ \mathop \sum \limits_{j \in V} \mathop \sum \limits_{{i \in V_{g} }} \mathop \sum \limits_{k \in K} a_{jikr} + \mathop \sum \limits_{j \in V} \mathop \sum \limits_{{i \in V_{g} }} \mathop \sum \limits_{k \in K} x_{jikr} L \le T, \quad \forall r \in R $$

(18)

$$ \mathop \sum \limits_{j \in V} \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} x_{ijkr} + x_{jikr} = \mathop \sum \limits_{j \in V} \mathop \sum \limits_{k \in K} \mathop \sum \limits_{r \in R} x_{{\left( {i + w} \right)jkr}} + x_{{j\left( {i + w} \right)kr}} , \quad \forall i \in V_{f} $$

(19)

$$ g_{ikr} = \mathop \sum \limits_{{\begin{array}{*{20}c} {j \in V} \\ {j \ne i} \\ \end{array} }} x_{ijkr} + \mathop \sum \limits_{{\begin{array}{*{20}c} {j \in V} \\ {j \ne i} \\ \end{array} }} x_{{j\left( {i + w} \right)kr}} , \quad \forall i \in V_{f} ,k \in K,r \in R $$

(20)

$$ g_{ikr} = \beta_{ikr} + 2\delta_{ikr} ,\quad \forall i \in V_{f} ,k \in K,r \in R $$

(21)

$$ \alpha_{ikr} + \beta_{ikr} + \delta_{ikr} = 1,\quad \forall i \in V_{f} ,k \in K,r \in R $$

(22)

$$ g_{ikr} \le \mathop \sum \limits_{{\begin{array}{*{20}c} {k' \in K} \\ {k' \ne k} \\ \end{array} }} \beta_{k'ir} + 2\gamma_{ir} ,\quad \forall i \in V_{f} ,k \in K,r \in R $$

(23)

$$ \mathop \sum \limits_{{i \in V_{f} }} \gamma_{ir} \le 1,\quad \forall r \in R $$

(24)

$$ y_{ijkr} \ge 0,\quad \forall i,j \in V,k \in K,r \in R $$

(25)

$$ x_{ijkr} \in \left\{ {0,1} \right\},\quad \forall i,j \in V,k \in K,r \in R $$

(26)

$$ z_{ikr} \in \left\{ {0,1} \right\},\quad \forall i \in V_{c} ,k \in K,r \in R $$

(27)

$$ e_{ijkr} ,a_{ijkr} \ge 0,\quad \forall i,j \in V $$

(28)

$$ g_{ikr} \in \left\{ {0,1,2} \right\},\quad \forall i \in V_{f} ,k \in K,r \in R $$

(29)

$$ \alpha_{ikr} ,\beta_{ikr} ,\delta_{ikr} \in \left\{ {0,1} \right\},\quad \forall i \in V_{f} ,k \in K,r \in R $$

(30)

$$ \gamma_{ir} \in \left\{ {0,1} \right\},\quad \forall i \in V_{f} ,r \in R $$

(31)

The objective function (1) minimizes the total routing cost where, due to the two flow paths that define a route, each edge is counted twice. Therefore, the total routing cost has to be divided by two to translate the actual cost.

Constraints (2)–(6) model the flows that implicitly define the routes. Constraint (2) models the inflows and outflows for each customer, assuring that the inflow minus the outflow equals twice the demand, since two paths cross each customer. The total outflow of real facilities must equal the total demand [Constraint (3)], and the total inflow is less than or equal to the residual capacity of the used routes [Constraint (4)]. The cardinality of route set K must be sufficiently large not to constrain the solution. Route capacity must not be exceeded, and this is guaranteed by Constraints (5) and (6). Constraint (7) assures that any feasible solution contains two incident edges for each customer node due to the two paths that characterize each route. Constraint (8) ensures that all customers are visited.

Constraints (9)–(11) relate routes with rotations, ensuring that all routes belong to a rotation. Constraint (12) guarantees that each route starts, at most, at one of the real facilities.

Constraints (13)–(18) model the duration of routes and rotations. The arrival time at each node is equal to the exit time from the previous node plus the travel time $F_{ij}$ [Constraint (13)]. The difference between the exit time and the arrival time within each customer is equal to the service time [Constraint (14)]. Time continuity is ensured by Constraint (15). If edge (i, j) is not crossed, then the arrival and exit times of that edge are equal to zero [Constraints (16) and (17)]. Constraint (18) guarantees that the maximum time for a rotation is not exceeded.

Since inter-depot routes may be a part of the solution for this problem, Constraint (19) ensures route continuity among inter-depot routes by enabling a rotation in these cases. Therefore, the number of outbound edges at each real facility must equal the number of inbound edges at the corresponding replica facility.

Constraints (20)–(22) define the values for variables $g_{ikr}$, $\alpha_{ikr}$, $\beta_{ikr}$ and $\delta_{ikr}$. Variable $g_{ikr}$ assumes the value two if route k starts at facility i and ends at the same facility replica. If route k only starts or ends at facility i, $g_{ikr}$ takes value one [Constraint (20)]. Variable $g_{ikr}$ is also a function of binary variables $\alpha_{ikr}$, $\beta_{ikr}$ and $\delta_{ikr}$ [Constraint (21)], which act as discretization variables. Notice that variable $\alpha_{ikr}$ can be omitted since it models $g_{ikr}$ when it is equal to zero. Being discretization variables, only one of them can assume the value one [Constraint (22)]. Constraint (23) ensures that if a closed route belongs to the solution (whenever $g_{ikr} = 2$), either two inter-depot routes are part of the same rotation or the rotation starts at depot i. Each rotation must only start at one depot [Constraint (24)]. Finally, Constraints (25)–(31) define the variables’ domains.

3 Solution Methodology

To solve the MDVRPI, we develop a matheuristic approach, which adopts a relax-and-fix strategy supported by the previously presented formulation (see Fig. 3). First, the duration constraints and the number of vehicles available are relaxed, and then, if the solution satisfies the relaxed constraints, the corresponding variables are fixed. The main idea behind this relaxation step is to solve a less constrained problem, which is expectedly easier to solve. Moreover, the relaxed problem also provides a lower bound for the MDVRPI.

Fig. 3

Matheuristic solution methodology flowchart

The matheuristic is composed of four main modules, where a different mathematical formulation is solved in each one, plus a post-optimization module:

• (1) Module 1 solves a MDVRPI Relaxation I (MDVRPI without duration constraints and unlimited vehicle fleet). This module provides the lower bound;

• (2) Module 2 solves an Assignment Problem, where routes are assigned to rotations;

• (3) Module 3 solves a MDVRPI Relaxation II (MDVRPI with duration constraints and unlimited vehicle fleet);

• (4) Module 4 solves a MDVRPI Relaxation III (MDVRPI without duration constraints and single vehicle/rotation);

• (5) Module 5 applies 2-opt and 3-opt moves within and between rotations.

Analysing the matheuristic shown in Fig. 3, and starting with module 1, this takes the concept of rotation into account while relaxing the time limit for the vehicle to return to its original depot. The number of available vehicles is also relaxed (equivalent to the number of rotations). Single- and inter-depot routes are then designed without duration concerns, while guaranteeing that inter-depot routes are linked in order to enable rotations. Afterwards, the duration of each route is assessed, allowing the definition of vehicle rotations to take place in the next module. The maximum duration for a rotation (parameter Dur) is initially set to the value T. Module 2 is then run to define rotations. If there is a feasible solution with Dur = T, the procedure continues, and if not, then the maximum duration (Dur) is incremented by a value ∆ until a feasible solution is obtained. When such a solution is reached (with a duration for a rotation exceeding the predefined limit of T), module 3 is executed, imposing the duration constraints that were relaxed in module 1. This third module is executed considering both sites that belong to rotations exceeding the time limit, and the sites belonging to rotations have a low duration and capacity usage. After module 3, module 2 is executed once again, in order to re-define rotations considering all routes that were produced until then and the maximum time limit allowed (T). If the number of rotations obtained is smaller than or equal to the number of available rotations (i.e. the number of available vehicles), a feasible solution is reached, and therefore, the solution procedure moves to the final module, where some post-optimization moves are applied to each rotation and between rotations. Otherwise, module 4 merges two rotations into a single rotation until the number of rotations equals the number of available vehicles. All pairs of rotations that can be merged are listed (called Pair List), and after a pair is merged into one rotation, the duration is assessed. If the duration is higher than allowed (T), then the merge process is considered for the next pair of rotations. If all pairs have been submitted to module 4 (Pair List is empty) without complying with the duration limit, that means the matheuristic was not able to produce a feasible solution.

The mathematical formulations and details for each one of the five modules are provided below and in supplementary material: Appendix A.

3.1 MDVRPI Relaxation I

The relaxed version I of the MDVRPI can be formulated as follows: Let $G = \left( {V_{c} \cup V_{f} \cup V_{g} ,E} \right)$ be an undirected graph, where $V_{c} = \left\{ {1, \ldots ,n} \right\}$ is the set of customers, $V_{f} = \left\{ {n + 1, \ldots ,n + w} \right\}$ is the set of facilities, $V_{g} = \left\{ {n + w + 1, \ldots ,n + 2w} \right\}$ is the set of facility replicas and $E = \left\{ {\left( {i,j} \right):i,j \in V_{c} \cup V_{f} \cup V_{g} ,i \ne j} \right\}$ is the set of edges. A demand $P_{i}$ is associated with customer $i$ while a travel cost $C_{ij}$ with the edge $\left( {i,j} \right)$. An unlimited fleet of vehicles with capacity $Q$ is available, and each vehicle route has a fixed cost $H$. This formulation uses binary variables $x_{ij}$ equal to 1 if edge $\left( {i,j} \right)$ is traversed, a flow variable $y_{ij}$ representing the vehicle load when travelling from node i to node j and an integer decision variable k representing the number of vehicle routes in the solution. The feasible solution is a set of routes (single-depot routes and/or inter-depot routes) which minimize the total cost (travel cost plus a fixed cost for each vehicle route created), ensuring that every customer is visited and the capacity of the vehicles is not surpassed. The formulation is given below, whereas Constraints (33)–(39) correspond to Constraints (2)–(7) and (19) of the full model.

$$ {\text{minimize}}\;\frac{1}{2}\mathop \sum \limits_{i \in V} \mathop \sum \limits_{j \in V} x_{ij} C_{ij} + H.k $$

(32)

$$ {\text{subject}}\, {\text{to }}\, \mathop \sum \limits_{{\begin{array}{*{20}c} {j \in V} \\ {j \ne i} \\ \end{array} }} \left( {y_{ji} - y_{ij} } \right) = 2P_{i} ,\quad \forall i \in V_{c} $$

(33)

$$ \mathop \sum \limits_{{i \in V_{f} }} \mathop \sum \limits_{{j \in V_{c} }} y_{ij} = \mathop \sum \limits_{{j \in V_{c} }} P_{j} $$

(34)

$$ \mathop \sum \limits_{{i \in V_{f} }} \mathop \sum \limits_{{j \in V_{c} }} y_{ji} = k.Q - \mathop \sum \limits_{{j \in V_{c} }} P_{j} $$

(35)

$$ \mathop \sum \limits_{{i \in V_{g} }} \mathop \sum \limits_{{j \in V_{c} }} y_{ij} = k.Q\quad $$

(36)

$$ y_{ij} + y_{ji} = Qx_{ij} ,\quad \forall i,j \in V,i \ne j $$

(37)

$$ \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V} \\ {i \ne j} \\ \end{array} }} x_{ij} = 2,\quad \forall j \in V_{c} $$

(38)

$$ \mathop \sum \limits_{{j \in V_{c} }} x_{ij} + \mathop \sum \limits_{{j \in V_{c} }} x_{ji} = \mathop \sum \limits_{{j \in V_{c} }} x_{{\left( {i + w} \right)j}} + \mathop \sum \limits_{{j \in V_{c} }} x_{{j\left( {i + w} \right)}} , \quad \forall i \in V_{f} $$

(39)

$$ x_{ij} \in \left\{ {0,1} \right\},\quad \forall i,j \in V $$

(40)

$$ y_{ij} ,y_{ji} \ge 0,\quad \forall i,j \in V $$

(41)

$$ k\;{\text{integer}} $$

(42)

Since this formulation disregards the route durations, at a post-processing phase, the duration of each route is assessed.

3.2 Rotation Definition

Let $K$ denote the set of all routes defined in the previous module ($K = \left\{ {1, \ldots ,s} \right\}$), $V_{f}$ the set of depots ($V_{f} = \left\{ {1, \ldots ,w} \right\}$) and $R$ the set of rotations ($R = \left\{ {1, \ldots ,m} \right\}$). The goal of this second module is to assign each route $k$ to a rotation $r$. $SD_{ik}$ and $O_{ik}$ define a partition of set $K$, where $SD_{ik} \subseteq K$ is the set of routes starting and ending at depot i (single-depot routes) and $O_{ik} \subseteq K$ is the set of routes with one depot in i and the other depot outside i (inter-depot routes). Each route k is characterized by: (1) a duration $D_{k}$ (including travel, service and loading times) and (2) the definition of the start and end depot given by parameter $G_{ik}$. This parameter acts as the variable $g_{ikr}$ of the full model. Therefore, when $G_{ik} = 2$, route k starts and ends at depot i (single-depot route); when $G_{ik} = 1$, route k starts or ends at depot i (inter-depot route) and when $G_{ik} = 0$, route k neither starts nor ends at depot i. The maximum duration allowed for a rotation is given by parameter ${\text{Dur}}$.

As mentioned, this formulation assigns routes to rotations, where $\varepsilon_{kr}$ is a binary variable equal to 1 if route k is assigned to rotation r. If rotation r is in the solution, the binary variable $\pi_{r}$ equals 1. Otherwise, $\pi_{r} = 0$. Two auxiliary variables need to be defined: an integer variable $\mu_{ir}$ that models the number of times rotation r visits depot i in an inter-depot route and the binary variable $\gamma_{ir}$ which is equal to 1 if rotation r starts at depot i. Notice that the cardinality of set $R$ is sufficiently large not to constrain the solution, since an unlimited vehicle fleet is considered in this module. The solution is the minimum set of rotations which comply with the maximum duration allowed. The mathematical formulation to define rotations is as follows:

$$ {\text{minimize}}\, \mathop \sum \limits_{r \in R} \pi_{r} $$

(43)

$$ {\text{subject }}\,{\text{to}}\,\mathop \sum \limits_{{k \in O_{ik} }} G_{ik} \varepsilon_{kr} - 2\mu_{ir} = 0,\quad \forall r \in R,\forall i \in V_{f} $$

(44)

$$ \mathop \sum \limits_{{k \in C_{ki} }} \varepsilon_{kr} \le \left| {{\text{SD}}_{ik} } \right|\left( {\mathop \sum \limits_{{k \in O_{ki} }} \varepsilon_{kr} + \gamma_{ir} } \right),\quad \forall i \in V_{f} ,\forall r \in R $$

(45)

$$ \mathop \sum \limits_{k \in K} D_{k} \varepsilon_{kr} \le {\text{Dur}},\quad \forall r \in R $$

(46)

$$ \mathop \sum \limits_{r \in R} \varepsilon_{kr} = 1,\quad \forall k \in K $$

(47)

$$ \varepsilon_{kr} \le \pi_{r} ,\quad \forall k \in K,\forall r \in R $$

(48)

$$ \mathop \sum \limits_{{i \in V_{f} }} \gamma_{ir} \le \pi_{r} ,\quad \forall r \in R $$

(49)

$$ \varepsilon_{kr} ,\pi_{r} ,\gamma_{ir} \in \left\{ {0,1} \right\}\quad \forall k \in K,\forall r \in R,\forall i \in V_{f} $$

(50)

$$ \mu_{ir} \;{\text{integer}}\quad \forall r \in R,\forall i \in V_{f} $$

(51)

The objective function (43) minimizes the number of rotations, given that the number of rotations available is unlimited. Constraints (44)–(46) are based on the work of Crevier et al. (2007). Constraint (44) guarantees rotation continuity when inter-depot routes are in a rotation, while Constraint (45) ensures either rotation continuity or rotation starting when single-depot routes are in a rotation. Constraint (46) limits the total duration of a rotation. Constraint (47) guarantees that all routes are assigned to a rotation. Constraints (48) and (49) state that a rotation is used if a route is assigned to it or if a rotation starts at a depot.

The second module is solved through an iterative procedure concerning the total duration of a rotation (parameter Dur). The goal of this procedure is to have the maximum number of rotations which satisfy the maximum duration (T) in order to minimize the number of rotations to be worked out by module 3. Recall that, in the first module, no duration constraints were imposed, so solutions where the maximum duration for a rotation is exceeded might be generated. To deal with this situation, parameter Dur is initialized as T, and if there is no feasible solution within this time limit, then the value of Dur is iteratively increased by ∆ until a feasible solution is obtained. The value for ∆ should be the smallest possible in order to obtain rotations with a duration close to T. Since rotations are combinations of routes, we suggest the value ∆ to be the minimum duration of the routes (∆ = $\hbox{min} \left\{ {D_{k} :k \in K\} } \right.$), to allow the inclusion of, at least, one route in a rotation and, therefore, to reach a feasible solution.

3.3 MDVRPI Relaxation II

This module is activated if and only if rotations with a duration larger than T are produced in the previous module. The relaxed version II of the MDVRPI can be formulated as follows: Let $G = \left( {V'_{c} \cup V_{f} \cup V_{g} ,E} \right)$ be an undirected graph, where $V'_{c} \subseteq V_{c}$ is a subset of customers that belong to a rotation with ${\text{Dur}} > T$, $V_{f}$ is the set of facilities, $V_{g}$ is the set of facility replicas and $E = \left\{ {\left( {i,j} \right):i,j \in V'_{c} \cup V_{f} \cup V_{g} ,i \ne j} \right\}$ is the edge set. Let $K$ denote the set of routes to be created by this module. A demand $P_{i}$ and a service time $S_{i}$ are assigned to customer $i \in V'_{c}$, and a travel cost $C_{ij}$ and a travel time $F_{ij}$ are associated with the edge $\left( {i,j} \right)$. An unlimited fleet of vehicles with capacity $Q$ is available. Let $L$ be the fixed duration representing the time needed for a vehicle to dock at a depot and $T$ be the maximum duration for a rotation. This formulation uses binary variables $x_{ijk}$ equal to 1 if edge $\left( {i,j} \right)$ is traversed by route $k$, $z_{ik}$ equal to 1 if customer $i$ is visited by route $k$, a flow variable $y_{ijk}$ representing the vehicle load when travelling from nodes i to j on route $k$, and two positive variables $e_{ijk}$ and $a_{ijk}$ representing the exit time and the arrival time, respectively, from node i to node j on route $k$. The solution is a set of routes (single-depot routes and/or inter-depot route) which minimize the total cost (travel cost), ensuring that every customer is visited, the capacity of the vehicles is not surpassed and the duration of either single-depot routes and linked inter-depot routes (enabling a rotation) satisfies the maximum duration allowed (T).

This formulation is composed of Constraints (1)–(8) and (11)–(19) considering the decision variables mentioned (i.e. without index r). In order to guarantee that the sum of the duration of the linked inter-depot routes does not exceed the maximum duration for a rotation, Constraint (52) is added.

$$ \begin{aligned} & \mathop \sum \limits_{i \in V} \mathop \sum \limits_{j,j' \in \xi } \mathop \sum \limits_{k \in U} \left( {a_{ijk} - {\text{BigM}}\left( {1 - z_{{\left( {j' - w} \right)k}} } \right) + a_{{i\left( {j' - w} \right)k}} - {\text{BigM}}\left( {1 - z_{jk} } \right)} \right) \le 2\left( {T - \left| U \right|L} \right), \\ & \quad \xi \subseteq V_{g,} \;2 \le \left| \xi \right| \le w,U \subseteq K,\;2 \le \left| U \right| \le s \\ \end{aligned} $$

(52)

Constraint (52) is inspired by how the Dantzig–Fulkerson–Johnson constraints work to eliminate subtours (Dantzig et al. 1954). This type of constraints has the drawback of leading to an exponential number of additional constraints. However, it is often the case that not all inequalities need to be added to the formulation at the beginning. They can be generated only as required by a separation algorithm, meaning that the formulation solution can start without Constraint (52), and then, if a rotation with a duration larger than T occurs, a new cut is added to avoid that rotation.

At first, only the demand sites that belong to rotations exceeding T were considered. However, in preliminary tests, it was noted that better solutions were attained if the customers belonging to rotations with a low usage rate were also considered in this module. This is due to better rotations being defined by combining those which are overloaded with those which are under loaded. Therefore, the demand sites that belong to rotations with a usage rate smaller than B are also added. The usage rate accounts for duration and capacity simultaneously, i.e. only the rotations with both usage rates below B are included in this module. The value of B varies in the interval [0, 1]. A value near 1 will include all rotations in module three, which will have a negative impact on the computational results given the combinatorial complexity of the problem. A value near 0 implies no additional rotations for module three, which may result in a negative impact on the quality of the solution.

3.4 MDVRPI Relaxation III

As stated before, the previous modules have considered an unlimited vehicle fleet, which represents a relaxation of the original problem. Thus, if the number of rotations produced by the matheuristic exceeds the number of vehicles available, module four must be run in order to decrease that number. This is done by merging rotations: firstly, all pairs of rotations that could be merged are assessed according to their combined duration, and then, the feasible pairs are ordered regarding the travel distance (considering the customers and the depots involved), from the nearest rotations to the farthest rotations. In case of a similar distance, the second ordering criterion is the combined duration, from the lower duration rotations to the higher ones. The first pair of rotations on the list is chosen to be merged through the relaxed version III of the MDVRPI.

The relaxed version III of the MDVRPI can be formulated as follows: Let $G = \left( {V'_{c} \cup V'_{f} \cup V'_{g} ,E} \right)$ be an undirected graph, where $V'_{c} \subseteq V_{c}$ is a subset of customers that belong to the two rotations to be merged, $V'_{f} \subseteq V_{f}$ is the subset of facilities involved in the two rotations, $V'_{g} \subseteq V_{g}$ is the subset of facility replicas, and $E = \left\{ {\left( {i,j} \right):i,j \in V'_{c} \cup V'_{f} \cup V'_{g} ,i \ne j} \right\}$ is the edge set. Let $K$ denote the set of routes to be created at this module. Each route has a capacity $Q$. A demand $P_{i}$ is assigned to customer $i \in V'_{c}$, and a travel cost $C_{ij}$ is associated with the edge $\left( {i,j} \right)$. This formulation uses binary variables $x_{ijk}$ and $z_{ik}$, integer variables $g_{ik}$ equal to 2 if route k starts and ends at depot i, equal to 1 if route k starts or ends at depot i and equal to 0 otherwise. Three auxiliary binary variables are also introduced: $\delta_{ik} ,\beta_{ik} ,\alpha_{ik}$. $\delta_{ik}$ is equal to 1 if route k starts and ends at depot i, $\beta_{ik}$ is equal to 1 if route k starts or ends at depot i and $\alpha_{ik}$ is equal to 1 if route k does not start or end at depot i.

The solution is a set of routes (single-depot routes and/or inter-depot route) which minimize the total cost (travel cost), ensuring that every customer is visited, the capacity of the vehicles is not surpassed and all defined routes form a cycle enabling one single rotation. This formulation is composed by Constraints (1)–(8), (12), and (19)–(22) considering the decision variables without index r. Constraint (23) is rewritten as follows:

$$ g_{ik} \le \mathop \sum \limits_{{\begin{array}{*{20}c} {k' \in K} \\ {k' \ne k} \\ \end{array} }} \beta_{ik'} ,\quad \forall i \in V_{f} ,\forall k \in K $$

(53)

Constraint (53) guarantees that the defined routes are all linked in order to build a single rotation.

Since this formulation disregards the rotation’s duration, duration constraints are assessed afterwards. If Dur > T, then the solution is discarded and the next pair of rotations from the list is chosen. If Dur ≤ T, then the new rotation is part of the final solution. If the number of rotations is still larger than the number of vehicles available, module 4 is run again until the number of rotations is equal to the number of vehicles.

3.5 Post-Optimization

In this module, some post-optimization procedures are applied to the final solution. The 2-opt and 3-opt exchanges are applied within and between rotations, ensuring that an exchange is only accepted if the capacity and duration constraints are not violated. Since a rotation can include single- and/or inter-depot routes, exchanging edges of inter-depot routes might result in a single-depot route from another depot. Figure 4 illustrates this situation where rotation 4 (in red) is composed by two inter-depot routes and one single-depot route, with a vehicle based at depot 26. The two inter-depot routes have two crossing edges (27,20) and (13,21), and after applying the 2-opt operation, these routes turn into two single-depot routes: one from depot 27 [27-25-13-27] and the other from depot 26 [26-21-20-23-3-26]. This means that route [27-25-13-27] now belongs to rotation 1 (in blue), and the duration must be checked. In this case, including route [27-25-13-27] in rotation 1 makes it infeasible regarding the duration limit, and therefore, this move is not accepted, although it reduces the overall cost.

Fig. 4

Illustrative example of the post-optimization procedure (color figure online)

4 Computational results

In this section, the benchmark instances for the MDVRPI developed by Crevier et al. (2007) and Muter et al. (2014) are solved via the proposed methodology. Moreover, to show how the MDVRPI formulation scales, small instances are also solved through the full MDVRPI formulation using the branch-and-bound algorithm embedded in the CPLEX solver. Both MDVRPI full model and the first four modules of the solution methodology were implemented in GAMS 23.7 and solved through the CPLEX Optimizer 12.3.0, on an Intel Xeon CPU X5680 @ 3.33 GHz. The CPU time was limited to 4 h in each module. The fifth module was implemented in Python. Since the benchmark instances do not consider any fixed cost for routes, the fixed cost H is set to zero in module 1. In module 3, parameter B was set to 0.5 after performing some preliminary tests.

In the Muter et al. (2014) instances, the number of customers is limited to 25 and 40 and the number of vehicles is limited to four and six. In the Crevier et al. (2007) instances, the number of customers is between 48 and 288 and the number of vehicles is between three and six. To test the MDVRPI formulation, we create small instances based on the original ones, with the number of customers ranging from 10 to 18, and the number of vehicles between two and four. We selected the first instance “a1” and considered the first n customers for this test. The results are shown in Table 2. In the first column, each instance is coded as in the Muter et al.’s (2014) work: #–n–Q–T. The number of depots is shown in the second column and the number of vehicles in the third column. The following four columns present the results obtained when solving the MDVRPI formulation via CPLEX: lower bound (LB), upper bound (UP), gap between the upper and lower bound and the CPU time (in seconds). The last three columns are the results when solving the instances with the solution methodology: LB is the branch-and-bound lower bound of module 1 (solutions proven to be optimal for module 1 are asterisked in the LB column), UB is the final objective function value obtained after the whole procedure has been applied and the CPU time, in seconds, taken by running our method.

Table 2 Comparison between the MDVRPI formulation with the matheuristic for small-size instances

It can be observed from Table 2 that CPLEX is only capable of solving very-small-size instances of the MDVRPI (up to 14 customers) and takes much more CPU time to reach the same solution when compared to the proposed solution methodology. With 16 customers (a1-16-50-450), CPLEX failed to find a feasible solution after 4 CPU hours, while the proposed matheuristic found the optimal solution in 2.6 s.

Given the results of Table 2, the benchmarking instances of Crevier et al. (2007) and Muter et al. (2014) will be solved only by our solution methodology, and the results compared with the work of Muter et al. (2014)—see Table 3. The results are only compared with the work of Muter et al. (2014) since it is the only work that solved the instances as a MDVRPI (with vehicles based at multiple depots). Note that Crevier et al. (2007) solved the original instances as a VRPIF (with all vehicles based at a central depot) and not as a MDVRPI. Table 3 shows the results presented by Muter et al. (2014): lower bound (LB), upper bound (UB) and CPU time (in seconds), and the final three columns show our own results.

Table 3 Results for MDVRPI instances

When analysing the results, we observe that our solution method provides a lower bound for all 66 instances, while the approach proposed by Muter et al. (2014) was not able to provide a lower bound for i1-25-50-450 and k1-25-50-450, nor was it able to solve the original instances (those having more than 40 customers). Focusing on the 25 and 40 customers instances, our matheuristic improves the lower bound in 20 of the 42 instances and the same lower bound is obtained for 3 other instances (in bold). Also an upper bound for 13 instances, not reported in Muter et al.’s (2014) work, was obtained (in bold italic), four of them (c1-40-50-450, f1-40-50-450, c2-40-50-450 and f2-40-50-450) being proven to be optimal (in bold italic underlined). Furthermore, when analysing the results reported by Muter et al. (2014) we noticed some inconsistencies. For example, in instances b1-25-50-450 and c1-25-50-450, our lower bound corresponds to the upper bound presented by Muter et al. (2014). From our analysis, we conclude that the Muter et al. (2014) solutions are unfeasible, as they require five vehicles and the maximum number allowed for those instances is four vehicles. We were able to reach a feasible solution since our approach reduces the number of vehicles needed (by executing module 4). Additionally, for instance g2-25-50-450, we find a better feasible solution than Muter et al. (2014)—793.633 versus 794.243.

In total, our method solved 54 out of 66 instances, 22 of them from the original MDVRPI instances, which are solved, to our best knowledge, for the first time in this work, with vehicles located at different depots. The reasons behind why all larger instances were solved (original instances) but not all medium instances (25-customer and 40-customer) can be found by analysing the detailed results displayed in Tables 4, 5 and 6. For the 25-customer instances (Table 4), 10 out of 22 instances need to be worked out by module 3; for the 40-customer instances (Table 5), 15 out 22 instances need to go through module 3; while for the original and larger instances (Table 6), only 7 out of 22 instances go to module 3. The performance of module 3 depends on the number of routes involved in a rotation [set U cardinality at Constraint (52)]. As mentioned, Constraint (52) is implemented in a cutting-plane fashion, i.e. we start with $\left| U \right| = 2$; if a feasible solution is obtained (all rotations with Dur ≤ T), module 3 stops; otherwise, the cardinality of set U increases by one unit until a feasible solution is obtained. For example, when Constraint (52) is added with $\left| U \right| = 2$, it is guaranteed that a rotation with two inter-depot routes does not exceed the maximum duration allowed for any rotation. However, this does not prevent the appearance of a rotation with three or more inter-depot routes with a duration higher than T in the solution. In this case, we run module 3 again, now considering $\left| U \right| = 3$, and so on. We noticed that worse results were obtained as the cardinality of set U increases due to the exponential number of constraints generated. For the original (and larger) instances, the cardinality of set U was always, at most, two or three. For the smaller instances, given the location of the customers and the large number of depots (3–6 depots to serve only 25 or 40 customers), rotations with a higher number of inter-depot routes are created, linking several depots. Consequently, $\left| U \right|$ needed to be higher, and with $\left| U \right| \ge 5$ module 3 fails to provide a solution.

Table 4 Detailed results obtained on 25-customer MDVRPI instances

Table 5 Detailed results obtained on 40-customer MDVRPI instances

Table 6 Detailed results obtained on original MDVRPI instances

Given that the original MDVRPI had been solved in previous works as a VRPIF with all vehicles located at a central depot, we are able to assess the economic benefit of positioning vehicles at different depots by comparing our results with the best known solution (BKS) for each instance solved as a VRPIF. The BKS is available in the works of Crevier et al. (2007), Tarantilis et al. (2008) and Hemmelmayr et al. (2013). This comparison is shown in Table 7. We can observe that a potential benefit can reach values in the order of 10%. The potential benefit for the smaller instances, with fewer customers, is higher than that of larger instances. This fact is also observed in Markov et al. (2016), where the potential savings from a flexible assignment of destination depots and from home depot optimization are assessed. Comparing the average benefits gained: when vehicles are based at a central depot but are able to end their rotation at a different one, the average benefit is 1.77% (Markov et al. 2016); when vehicles can be based at different depots, but have to start and end their rotation at the same depot, the average benefit is 2.13% (Table 7); and finally, when vehicles may be based at different depots and can both start and end their route at different depots, the average benefit is 2.54% (Markov et al. 2016).

Table 7 Potential benefit from positioning vehicles at different depots

To illustrate the difference between a VRPIF and MDVRPI, instance a1 is analysed in further detail. Figure 5 presents both solutions for instance a1: the one obtained by solving the case as a MDVRPI (on the left) and as a VRPIF (on the right).

Fig. 5

Solution for instance a1 solved as a MDVRPI and a VRPIF

In the VRPIF solution, twelve routes are defined involving five vehicle rotations that must be based out of depot 49. In the MDVRPI, twelve routes are also defined and assigned to five vehicle rotations that are based out of the three depots (this solution involves two vehicles at depot 51, one vehicle at depot 49 and two vehicles at depot 50), representing a cost saving of 6.5%.

In order to illustrate how the solution method works, Figs. 6, 7, 8, 9 and 10 display the solutions generated by each module for instance a2. This instance was chosen since its resolution requires the execution of all modules of the solution method.

Fig. 6

Module 1 solution for instance a2

Fig. 7

Module 2 solution for instance a2

Fig. 8

Module 3 solution for instance a2

Fig. 9

Module 2 solution (after module 3) for instance a2

Fig. 10

Module 4 solution for instance a2 (and the final one)

The solution obtained by module 1 is comprised of seven routes as illustrated in Fig. 6.

These seven routes are the input for module 2 where the rotations are defined. In the first iteration, the total duration for a rotation (Dur) is set to 600 (T). Since no feasible solution was obtained, a second iteration was performed with Dur value reset to 650 (T + ∆) with ∆ as the minimum duration among the seven routes (i.e. 50 for route 5). A feasible solution was obtained in the fourth iteration, with Dur = 750, defining five rotations (see Fig. 7).

The total duration of rotation 1 is 721, rotation 2 is 54, rotation 3 is 299, rotation 4 is 478 and rotation 5 is 164. Since T = 600, rotation 1 needs to be re-worked by module 3, as it exceeds the operational time limit. Rotations 2, 3 and 5 have a duration lower than half of 600, meaning that they are possible candidates to be added to module 3 (since B = 0.5). However, the capacity usage of rotation 3 is 0.93 excluding this rotation from being re-worked by module 3, as it is above the assumed minimum capacity usage. The other two rotations (2 and 5) have a capacity usage lower than B = 0.5, and therefore, the customers in rotations 1, 2 and 5 (in this case, 27 customers) are considered as input for module 3. The solution obtained in module 3 for the 27 customers is shown in Fig. 8, where we obtained two single-depot and two inter-depot routes satisfying the duration limit.

After running module 3, module 2 is executed once more with the four new routes created by module 3 and the three previous routes from rotations 3 (with one route) and 4 (with two routes). Five rotations were obtained, meaning that the maximum number of vehicles available was exceeded (|R| = 4) (see Fig. 9). Therefore, module 4 was executed.

Firstly, module 4 elects the pair of rotations to be merged. Given the maximum duration for a rotation (T = 600), four pairs of rotation could be merged: [1; 2], [2; 3], [2; 4] and [2; 5]. For each pair, the minimum distance between each rotation is assessed considering both customers and depots and the pair with the lowest value is chosen. In instance a2, the pair with the minimum distance value is [2; 5]. The sixteen customers belonging to this pair are the input for the mathematical formulation of module 4 in order to define one single rotation. The solution obtained in module 4 is given in Fig. 10. The post-optimization procedures (module 5) were not able to improve the solution of instance a2, so the solution obtained at module 4 is the final one. This solution is to base the four vehicles out of facilities 49, 51, 52 and 53 (each represented by a different type of line). Therefore, these facilities act as depots and facility 50 remains unused.

All the details of the final solutions produced by our approach for the original MDVRPI instances are available in supplementary material: Appendix B.

5 Conclusions

This paper addresses the MDVRPI, a routing problem characterized by the existence of multiple depots, where vehicles can reset their capacity without having to return to their home depot. This problem, which is very important in real logistic networks with applications in grocery distribution, waste collection, or when an electric vehicle fleet is present, has received little attention from academia.

This gap is explored in this work where a generic MDVRPI is studied considering that vehicles are based at multiple depots. A new formulation, based on the two-commodity flow formulation, was developed, where routes and rotations are defined in order to minimize the total routing cost. The location of the available vehicle fleet as well as the role of each facility in the network (depot, intermediate facility, or both) is also decisions made by the model. Furthermore, to allow the solution of real instances and consequently potentiate model applicability to real cases, a matheuristic approach was developed. Literature instances were solved, namely those proposed by Muter et al. (2014) and Crevier et al. (2007)—two reference works in the field. For the instances proposed in the first work, some new and better solutions were achieved, whereas instances proposed in the latter were solved for the first time as a MDVRPI. When compared to the VRPIF solutions reported by Crevier et al. (2007), Tarantilis et al. (2008) and Hemmelmayr et al. (2013), economic savings up to 10% can be observed using the proposed approach.

Finally, although important results were achieved in the present work, future research directions can also be identified. Namely, further work on solution methods should be pursued, allowing the solution of all benchmarking instances published in the literature, as well as real problems. Moreover, other types of problems based on the MDVRPI should also be explored. One example is the problem that combines the MDVRPI characteristics with the inventory management aspects. Such studies will enable the consideration of multiple products’ availability at each facility. Also, holding costs could be accounted for into the MDVRPI problem together with routing costs, so as to model more realistic situations. Finally, the existence of uncertainty should also be explored within such problems.