1 Introduction

This article addresses the multi-depot open vehicle routing problem with time windows (MDOVRPTW). In this problem, a homogeneous fleet of vehicles must depart from a set of depots and serve a set of consumers within a time window for each one. Unlike traditional vehicle routing problems, the used vehicles are not required to return to the original depots after delivering goods to customers. MDOVRPTW consists of finding the shortest routes and, hence, the objective is to minimize the total distance covered by the vehicles [1, 2]. On the other hand, the current article also addresses a variant of MDOVRPTW, which we named MDOVRPTW*. This variant seeks first to minimize the number of used vehicles and, after, to minimize the total covered distance. Hence, MDOVRPTW* is a problem solved hierarchically, and this methodology considers the addition of a new vehicle as the primary cost to be minimized and, consequently, the total covered distance by these vehicles as the secondary cost. Therefore, it emulates the traditional methodology adopted for solving the vehicle routing problem with time windows (VRPTW). To our knowledge, this variant has not yet been addressed in the literature.

According to Brandão [3], Repoussis et al. [4] and Shen et al. [2], open vehicle routing problems are frequently encountered in the real-world. These problems appear when the companies do not have their own fleet of vehicles for the distribution of goods or, in some cases, the existing fleet is not enough to serve the customers and, therefore, some external vehicles must also be hired. These same characteristics are found in school bus routing problems and train or airplane route planning, as long as the routes start and end at different points. These are some examples that make it more suitable for describing various real-world problems. The number of depots involved is another important characteristic in this type of problem since it is common for companies to have several distribution centers. On the other hand, the time window maintains the adherence of this type of problem to the customers’ needs by defining their best service schedules. MDOVRPTW*, by its turn, is in line with the environmental concerns of lesser use of vehicles, especially in the case of contracted fleets and autonomous vehicles, where secondary costs arising from driver hiring and vehicle maintenance are not considered. However, to our knowledge, it has not yet been addressed in the literature. These characteristics make MDOVRPTW and MDOVRPTW* suitable for treating several real problems.

As pointed out by Cordeau et al. [5] and Brandão [3], MDOVRPTW and MDOVRPTW* are extensions of MDOVRP and OVRPTW, which are NP-Hard problems, and, therefore, they are also NP-hard ones. This claim justifies the application of metaheuristics for solving them. In the current article, we apply the smart general variable neighborhood search (SGVNS) developed by Rego and Souza [6] to treat these two problems. SGVNS is a general variable neighborhood search-based algorithm in which the basic variable neighborhood descent (BVND) [7] is the local search method. However, while Rego and Souza [6] used BVND as a local search method, we applied the randomized basic variable neighborhood descent (RBVND or RVND in the nomenclature of Subramanian et al. [8]). Unlike BVND, this procedure does not require a neighborhood order calibration. Furthermore, the best order of neighborhoods can be instance-dependent, requiring calibrating these orders for each instance [8, 9]. This local search strategy has been used successfully for solving various routing problems, as in [10,11,12]. Finally, Bezerra et al. [13] addressed the multi-depot vehicle routing problem with time windows (MDVRPTW), aiming to minimize the vehicle fleet. This problem is the closed-route version of MDOVRPTW. The authors proposed a smart general variable neighborhood search with adaptive local search (SGVNSALS) to solve this problem. The results showed that this algorithm provided a vehicle fleet average reduction of up to 23.32% of the evaluated instances.

The main contributions of this article are:

  1. (1)

    The proposition of MDOVRPTW* as a new variant of the class of multi-depot open vehicle routing problems;

  2. (2)

    The adaptation of the smart general variable neighborhood search (SGVNS) for treating both MDOVRPTW and MDOVRPTW*;

  3. (3)

    The development of an efficient local search method for SGVNS;

  4. (4)

    An extensive analysis of the results achieved by the proposed algorithm, comparing them with the results with and without fleet reduction.

The remainder of this article is organized as follows. Section 2 introduces MDOVRPTW and MDOVRPTW*. Section 3 presents a literature review on vehicle routing problems related to the ones addressed in this work. Section 4 presents the mathematical formulations for the addressed problems. Section 5 describes the proposed SGVNS-based algorithm for treating these two problems. Section 6 reports the computational results obtained with the SGVNS algorithm, and the statistical analysis of its performance are shown in Sect. 7. Section 8 concludes the article with a general analysis of the addressed problem.

2 Multi-depot open vehicle routing problem with time windows

The multi-depot open vehicle routing problem with time windows (MDOVRPTW) consists of determining a set of routes that minimize the total distance traveled, serving all customers, respecting the vehicle capacity, the maximum duration on the routes, and the time windows in which the customers must be served. The characteristics of this problem are:

  1. (1)

    The number of depots is greater than one;

  2. (2)

    Each vehicle starts its route in a depot;

  3. (3)

    The capacity of each vehicle is known;

  4. (4)

    The vehicle fleet is homogeneous;

  5. (5)

    Each customer is served by only one vehicle;

  6. (6)

    The total demand for each route cannot exceed the capacity of the vehicle that is on the route;

  7. (7)

    The customer time window must be met;

  8. (8)

    Each route has a maximum duration to be covered;

  9. (9)

    The vehicles do not return to the depot.

In this article, we also address a variant of this problem, named MDOVRPTW*. The solution strategy for this problem consists of building the solution hierarchically in such a way that, first, we seek to minimize the number of vehicles used and, in the sequel, to minimize the total distance traveled. This characteristic is added by the following formulation:

  1. (10)

    The total number of vehicles used must be minimized, and, after, the total distance traveled must be minimized.

These characteristics allow describing the problems under study. Table 1 summarizes the notations used in this description. These problems, in which N customers are served by M depots, are defined from a complete graph \({\mathcal{G}}=({\mathcal{V}},{\mathcal{A}})\), with \({\mathcal{V}}\) being a set of \((N+M)\) vertices and \({\mathcal{A}}\) a set of arcs. Therefore, the set \({\mathcal{V}}\) results from the union of two subsets, namely, the set of customers to be served, represented by \({\mathcal{C}}=\left\{ 1,2,\ldots ,N\right\}\), and the set of depots \({\mathcal{D}}=\left\{ N+1,N+2,\ldots ,N+M\right\}\), so that \({\mathcal{V}}={\mathcal{D}}\cup \, {\mathcal{C}}\) and \({\mathcal{D}}\cap \,{\mathcal{C}}=\oslash\). For the set \({\mathcal{K}}\) of vehicles, there is a subset \({\mathcal{K}}_{d} \subset {\mathcal{K}}\) for each depot \(d \in {\mathcal{D}}\), where \(\mid {\mathcal{K}}\mid =\mid {\mathcal{K}}_{N + 1}\mid + \mid {\mathcal{K}}_{N+2}\mid + \cdots + \mid {\mathcal{K}}_{N+M}\mid\). The vehicle fleet is homogeneous so that all vehicles \(k \in {\mathcal{K}}\) have the same capacity VC, maximum duration time of the route MT, and utilization cost \(\alpha\). For each consumer \(i \in {\mathcal{C}}\), there is a positive demand \(q_{i}\), which must be met in a time window \([e_{i},l_{i}]\). There is a service time \(h_{i}\) that starts at the arrival time for vehicle k in customer i, \(TS_{ki}\), such that \(e_{i} \le TS_{ki} \le l_{i}\). For any depot \(d \in {\mathcal{D}}\), both demand \(q_{d}\) and service time \(h_{d}\) have zero value, that is, \(q_{d} = h_{d} = 0\). Each arc \((i, j) \in {\mathcal{A}}\) is associated with a non-negative cost \(c_ {ij}\), which can represent both the distance between the respective nodes, or the travel time, or other measurement value.

Table 1 Notations used in the description of MDOVRPTW and MDOVRPTW*
Full size table

Figures 1a and 1b illustrate solutions for the MDOVRPTW and MDOVRPTW*, respectively. In these examples, the fleet of eight vehicles is divided equally among the depots. The approached instance has two depots, which serve eighteen customers. There is a homogeneous fleet of eight vehicles, each one with a capacity of \(VC= 8\). The en-route time of each vehicle cannot exceed \(MT=20\). Each arc has a cost \(c_{ij}\), given by the travel time between the node i and the node j. A tuple \((q_{i},\,h_{i},[e_{i}, l_{i}])\) is associated with the node i, being, respectively, \(q_{i}\) the demand, \(h_{i}\) the service time, and \([e_{i}, l_{i}]\) the time window for this node i.

Fig. 1
figure 1

Example of solutions to MDVRPTW and MDVRPTW*

Full size image

Table 2 presents the data for the examples shown in Fig. 1. For each vehicle k, the column “Routes” shows the routes created; the column \(c_{ij}\) represents the cost between the vertices i and j; \(h_{i}\) represents the service time spent on the customer i; \(WU_{k}\), the waiting time to unload the vehicle k; \(T_{k}\) represents the total time spent by the vehicle k on the route; \(Q_{k}\) represents the total cargo carried on the route k.

Table 2 Data for the examples shown in Fig. 1
Full size table

Note that the solution for MDOVRPTW shown in Fig. 1a has 7 routes, while the solution for MDOVRPTW*, shown in Fig. 1b, has 6 routes.

3 Literature review

The open vehicle routing problem (OVRP) was first addressed by Schrage [14]. Since then, much research has emerged into a variety of OVRPs. Table 3 reports some studies in open VRP. This table lists the problem, the author(s), and the algorithms or methods proposed in each study.

Table 3 Problems, authors and solution methods for open vehicle routing problems
Full size table

Brandão [15] developed a tabu search algorithm (TSA) to solve the OVRP. Hosseinabadi et al. [16] proposed the gravitational emulation local search algorithm (GELS) to solve the OVRP. In both studies [15, 16], the objective was to reduce the traveling time, distance, and the number of vehicles used.

The OVRP with Time Windows (OVRPTW) was addressed by Repoussis et al. [4]. The authors developed a heuristic to solve the OVRPTW by utilizing a greedy look-ahead solution framework for customer selection and route insertion. In Redi et al. [17], an improved variable neighborhood search (VNS) algorithm is proposed to solve the problem. The VNS features a route construction mechanism to ensure that customers with earlier time windows are served first. The proposed VNS was tested on 12 R1 and 8 RC1 datasets of classical VRPTW instances [22]. In recent work, Chen et al. [18] solved a real-life container transportation problem. They developed a variable neighborhood search algorithm with Reinforcement Learning (VNS-RLS). The algorithm was applied in 15 instances from the real-life Ningbo Port dataset.

The MDOVRP was introduced by Tarantilis et al. [23]. Soto et al. [19] proposed the multiple neighborhood search algorithm hybridized with a Tabu Search (MNS-TS) for solving this problem. The authors introduced some ejection chain techniques to reduce the size of the neighborhoods proposed. In Lahyani et al. [20], a hybrid algorithm based on a hybrid adaptive large neighborhood search (HALNS) heuristic was developed. The method combines the power of an ALNS algorithm to perform a diverse and thorough search of the solution space with local search improvement procedures to intensify the search for good and promising solutions. Brandão [3] presented the memory-based iterated local search algorithm (MBILSA). The moves performed during the local search are recalled, and this historical search information is then used to dene the moves executed inside the perturbation procedures. Lalla-Ruiz and Mes [1] proposed a two-index-based mathematical formulation for the MDOVRP. They also assessed the contribution of alternative constraints for handling flow conservation and sub-tours.

A variant of the MDOVRPTW under shared depot resources was addressed by Li et al. [21] as the combination of MDVRPTW and OVRP. In this problem, the vehicles may end at the depot nearest to the last customer. The problem was solved with a hybrid genetic algorithm with an adaptive local search. In Shen et al. [2], the authors solved the MDOVRPTW, which considers low-carbon trading policies. The low-carbon MDOVRPTW model was constructed with minimum total costs, which include the driver’s salary, penalty costs, fuel costs, and carbon emissions trading costs. The solution was obtained through the particle swarm optimization (PSO) and tabu search (TS) algorithms.

In terms of techniques for the solution of routing-oriented problems, there are many in the literature; however, there is a large number of recent studies applying variable neighborhood search-based methods, as in studies of Smiti et al. [24], Bezerra et al. [25], Derbel et al. [26], Sanchez-Oro et al. [27], Ren et al. [28], Karakostas et al. [29], Barrero et al. [30], and Karakostas and Sifaleras [31]. The good performance of these methods in solving routing problems justifies our proposal to deal with the problems under study.

It is important to highlight that to the best of our knowledge, no research addresses the open VRP with multi-depots and time windows, with the primary objective to reduce the number of vehicles, as the proposed MDOVRPTW*.

4 Mathematical formulations

The mathematical formulations for MDOVRPTW and MDOVRPTW* are based on those presented in Li et al. [21], Brandão [3], and Repoussis et al. [4]. Table 1 shows the used notations in these formulations. Initially, the following decision variables are defined:

$$ x_{kij}= {} \left\{ \begin{array}{ll} 1, &{}\quad {\text{ if vehicle}}\; k\;{\text{visits consumer}}\; j\;{\text{after consumer}}\; i\\ 0, &{}\quad {\text{otherwise}} \end{array}\right. $$
(1)
$$\begin{aligned} y_{k}= & {} {\left\{ \begin{array}{ll} 1, &{}\quad {\text{if vehicle}}\; k\;{\text{is used;}}\\ 0, &{}\quad {\text{otherwise.}} \end{array}\right. } \end{aligned}$$
(2)
$$\begin{aligned} z_{jk}= & {} {\left\{ \begin{array}{ll} 1, &{}\quad {\text{if customer}}\;j~{\text{is the last customer to be visited by vehicle}}\;k{\text{;}}\\ 0, &{}\quad {\text{otherwise.}} \end{array}\right. } \end{aligned}$$
(3)

Considering that \(c_{id} = 0,\,\forall~i \in \mathcal{C},\,d \in \mathcal{D},\) i.e., the return distance of a vehicle to the depot is null, the formulation for MDOVRPTW is given by:

$$\begin{aligned} (MDOVRPTW){} & {} \min \sum _{k \in {\mathcal{K}}} \sum _{i \in {\mathcal{V}}} \sum _{j \in {\mathcal{V}}} c_{ij} x_{kij} ~~(4)\end{aligned}$$
(4)

subject to:

$$\begin{aligned}{} & {} \sum _{k\in {\mathcal{K}}} \sum _{j \in {\mathcal{V}}} x_{kji} = 1, \quad \forall i \in {\mathcal{C}}, \end{aligned} \\ $$
(5)
$$\begin{aligned}{} & {} \sum _{j \in {\mathcal{V}}} x_{kji} = \sum _{j \in {\mathcal{V}}} x_{kij} + z_{ik}, \quad \forall i \in {\mathcal{C}}, \forall k \in {\mathcal{K}}\end{aligned}$$
(6)
$$ \begin{aligned}{} & {} \sum _{j \in {\mathcal{C}}} x_{kdj} = \sum _{j \in {\mathcal{C}}} z_{jk}, \quad \forall k \in {\mathcal{K}}, \forall d \in {\mathcal{D}}\end{aligned}$$
(7)
$$\begin{aligned}{} & {} \sum _{d \in {\mathcal{D}}} \sum _{j \in {\mathcal{C}}} x_{kdj} \le 1, \quad \forall k \in {\mathcal{K}},\end{aligned}$$
(8)
$$\begin{aligned}{} & {} \sum _{d \in {\mathcal{D}}} \sum _{i \in {\mathcal{C}}} x_{kid} = 0, \quad \forall k \in {\mathcal{K}},\end{aligned}$$
(9)
$$\begin{aligned}{} & {} \sum _{i \in {\mathcal{L}}} \sum _{j \in {\mathcal{L}}} x_{kij} \le \mid {\mathcal{L}}\mid - 1, \quad \forall {\mathcal{L}} \subseteq {\mathcal{C}}, k \in {\mathcal{K}},\end{aligned}$$
(10)
$$\begin{aligned}{} & {} \sum _{i \in {\mathcal{D}}} \sum _{j \in {\mathcal{D}}} x_{kij} = 0, \quad \forall k \in {\mathcal{K}},\end{aligned}$$
(11)
$$\begin{aligned}{} & {} x_{kij}(TS_{ki} + h_{i} + c_{ij} - TS_{kj}) \le 0, \quad \forall k \in {\mathcal{K}}, \forall i, j \in {\mathcal{V}},\end{aligned}$$
(12)
$$\begin{aligned}{} & {} e_{i} \le TS_{ki} \le l_{i}, \quad \forall i \in {\mathcal{C}}, \forall k \in {\mathcal{K}}, \end{aligned}$$
(13)
$$\begin{aligned}{} & {} \sum _{i \in {\mathcal{V}}} \sum _{j \in {\mathcal{C}} } q_{j} x_{kij} \le VC, \quad \forall k \in {\mathcal{K}},\end{aligned}$$
(14)
$$\begin{aligned}{} & {} \sum _{i \in {\mathcal{V}}} \sum _{j \in {\mathcal{V}}} (c_{ij} + h_{j}) x_{kij} \le MT, \quad \forall k \in {\mathcal{K}},\end{aligned}$$
(15)
$$\begin{aligned}{} & {} x_{kij}, z_{ik} \in \{0, 1\}, \quad \forall \, i,j \in {\mathcal{V}}, \forall k \in {\mathcal{K}}.\end{aligned}$$
(16)

In turn, the mathematical formulation of MDOVRPTW* is given by:

$$\begin{aligned}{} & {} (MDOVRPTW^{*}) \quad \min \,\beta \sum _{k \in {\mathcal{K}}} \sum _{i \in {\mathcal{V}}} \sum _{j \in {\mathcal{V}}} c_{ij} x_{kij} + \alpha \sum _{k \in {\mathcal{K}}} y_{k}, \end{aligned}$$
(17)

subject to:

$$\begin{aligned}{} & {} \text{ Constraints } \text{(4)--(14) }\end{aligned}$$
(18)
$$\begin{aligned}{} & {} y_{k} \ge \displaystyle \frac{\sum _{i \in {\mathcal{V}}} \sum _{j \in {\mathcal{V}}} x_{kij}}{\mid N \mid ^{2}}, \quad \forall k \in {\mathcal{K}},\end{aligned}$$
(19)
$$\begin{aligned}{} & {} y_{k} \in \{0, 1\}, \quad \forall k \in {\mathcal{K}}. \end{aligned}$$
(20)

Constraints (5) ensure that each customer i is visited by exactly one vehicle k. Constraints (6) guarantee that if a vehicle k arrives at customer i, this vehicle must leave this customer or, then, this customer will be the last one on the route.  Constraints (7) assure that if a vehicle starts the route at a given depot, exactly one customer will be the last customer on the route. Constraints (8) guarantee that a vehicle will leave a depot, while constraints (9) assure that it will not return to it or another depot. These constraints define the routing condition as open. Constraints (10) assure that the graph is connected, as well as the sub-tours elimination. Constraints (11) establish that the vehicle cannot travel directly from depot i to depot j. Constraints (12) present the order of visits to the nodes, once if the vehicle k travels directly from the node i to the node j, then the moment of arrival \(TS_ {kj}\) at the node j must be equal to \((TS_{ki} + h_{i} + c_{ij})\). Constraints (13) guarantee the occurrence of the service on customer i within the time window \([e_{i}, l_{i}]\). Constraints (14) ensure that the load will not exceed the capacity of the vehicle k. Constraints (15) define that the total duration of the route is at most equal to MT. Constraints (19) show which vehicles will be used, and, finally, Constraints (16) and (20) define the binary domain of the decision variables x, z,  and y.

Expression (4) is the objective function of MDOVRPTW. This function represents the total covered distance, once \(c_{ij}\) is the distance between the customers i and j, and must be minimized. It is the focus of this problem. On the other hand, Expression (17) shows the objective function of MDOVRPTW*, also to be minimized. This objective function is given by the weighted sum between the cost associated with the distance between customers and the total number of used vehicles. The weighting factors \(\alpha\) and \(\beta\) show the relative importance of each of the two objectives to achieve the desired solution. The values that these weighting factors take for each problem are described in Sect. 5.2.

5 Smart general variable search algorithm

The general variable neighborhood search (GVNS) [7, 32] is a metaheuristic that performs perturbation and local search procedures based on systematic neighborhood changes until reaching a predefined stopping criterion. Perturbations are random moves gradually applied in a solution s to guide the search toward other basins of attraction. Each perturbed solution \(s'\) is refined through the Basic Variable Neighborhood Descent (BVND) [7] local search method, guiding the search to a local minimum. The method returns the best solution found after the repeated application of these two procedures.

In this paper, we propose an algorithm named SGVNS, an acronym for Smart GVNS. The SGVNS algorithm uses the smart version of the GVNS method developed in [6]. Reinsma et al. [33] introduced the adjective “smart” to refer to how to increase the level of perturbation in an iterated local search (ILS) algorithm. Traditionally, there is an increase in the perturbation level in a classic ILS algorithm whenever there is no improvement in the current solution. However, this way of changing the perturbation level can lead to a loss in the quality of the final solution due to the hasty way of leaving the current search region. As perturbation occurs randomly, other choices of perturbed solutions within the same current search region can lead to better solutions through local search. Based on this observation, the decision to increase the perturbation level in the smart strategy occurs only after a certain number of local search applications without improvement in the quality of the current solution. Thus, this strategy allows a better investigation to be carried out in a specific region of the solution space, enabling a more precise intensification during the algorithm’s execution. On the other hand, while Rego and Souza [6] apply the BVND as local search method, we use the randomized basic variable neighborhood descent (RBVND) method [8, 34].

To describe the proposed algorithm, we use throughout this section the notations described in Table 4 in addition to the notation introduced in Table 1.

Table 4 Notations used in the description of the SGVNS algorithm
Full size table

This section is organized as follows. In Sect. 5.1, we show how to represent a solution. Section 5.2 describes the function used for evaluating the solution of MDVRPTW and MDOVRPTW*. Section 5.3 presents the procedure for generating an initial solution to the problem. Section 5.4 shows the neighborhood structures used to explore the problem’s solution space. Section 5.5 details the perturbation procedure, and Sect. 5.6 describes the local search method. Finally, Sect. 5.7 presents the proposed SGVNS algorithm.

5.1 Solution representation

We represent a solution of the two problems through a set of lists \({\mathcal{R}} = \left\{ r_{1}^{N+1}, r_{2}^{N+1}, \ldots , r_{m}^{N+1}, r_{1}^{N+2}, r_{2}^{N+2}, \ldots , r_{n}^{N+2}, r_{1}^{N+{\mid {\mathcal{D}}\mid }}, r_{2}^{N+{\mid {\mathcal{D}}\mid }}, \ldots , r_{t}^{N+{\mid {\mathcal{D}}\mid }} \right\}\). In this set, \(r^{N+1}, r^{N+2},\) and \(r^{N+\mid {\mathcal{D}}\mid }\) refer to the set of routes of each depot (from \(N+1\) to \(N+\mid {\mathcal{D}}\mid\)). In turn, m, n, \(t \ge 1\) refer to the number of routes in each depot. For the example of Fig. 1a, \(r_{1}^{19} = \{19,\,1,\,2\}\), \(r_{2}^{19} = \{19, \,5, \,6, \, 7\}\), \(r_{3}^{19}=\{19, \, 3, \, 9, \, 11\}\) represent the routes of depot 19, and \(r_{1}^{20} = \{20, \,4, \, 8, \, 10\}\), \(r_{2}^{20}=\{20, 14, 17, 15\}\), \(r_{3}^{20}=\{20, 12, 18\}\), \(r_{4}^{20}=\{20, 16, 13\}\) the routes for depot 20.

5.2 Evaluation functions

As mentioned before, MDOVRPTW and MDOVRPTW* have different goals. In the case of MDOVRPTW, the objective is to reduce the total traveled distance using the total number of vehicles available. On the other hand, for MDOVRPTW*, the primary objective is to reduce the vehicle fleet, i.e., the number of used vehicles, and the secondary one is to reduce the total traveled distance. The evaluation functions of each problem are presented and discussed below. These evaluation functions add, to the objective functions of the mathematical formulations described in Sect. 4, a parcel of infeasibility to deal with the generation of infeasible solutions by the proposed algorithm during the exploration of the solution space of the problems.

5.2.1 Evaluation function to fleet reduction

As in Ombuki et al. [35], which addresses VRPTW, we evaluate a solution s for MDOVRPTW* by a evaluation function F(s) that represents a weighted sum of three objective functions to be minimized:

$$\begin{aligned} F(s) = \beta L + \alpha \mid {\mathcal{U}}\mid \,+\, \varphi\end{aligned}$$
(21)

The first objective function (L) seeks to reduce the total traveled distance by all used vehicles; the second objective function (\(\mid {\mathcal{U}}\mid \le \mid {\mathcal{K}}\mid\)) tries to reduce the number of used vehicles. The last objective function (\(\varphi\)) seeks to minimize the violations that may occur due to applying the moves to explore the problem’s solution space. These violations can occur due to the vehicle overload, customer service delays, and extrapolation of the route’s maximum duration.

The three objective functions of Eq. (21) are weighted by the values \(\beta\), \(\alpha\), and \(\varphi\), respectively, that reflect the relative importance of each objective function for reaching the solution of MDVRPTW*. As proposed in Ombuki et al. [35], we set \(\beta = 0.001\). The parameter \(\alpha\) is calculated by:

$$\begin{aligned} \alpha = \frac{1}{N} \sum \limits _{i \in {\mathcal{C}} } \sum \limits _{j \in {\mathcal{C}}} c_{ij}\end{aligned}$$
(22)

According to Eq. (22), the parameter \(\alpha\) represents the average distance between each pair of customers. Finally, the weighting factor \(\varphi\) is given by:

$$\begin{aligned} \varphi = \sum _{k \in {\mathcal{U}}} \phi (k) \end{aligned}$$
(23)

where \(\phi (k)\) represents the penalization by violating the constraints imposed on the route of each vehicle k, being calculated as:

$$\begin{aligned} \phi (k) = \omega ^{Q} \max \Big \{0, Q_{k} - VC \Big \} + \omega ^{T} \max \Big \{0, T_{k} - MT \Big \} + \omega ^{TW} TW_{k}\end{aligned}$$
(24)

In these expression, the parameter \(\omega ^{Q}\) penalizes the vehicle overload, the parameter \(\omega ^{T}\) penalizes the time exceeded in the route duration of vehicle k, and the parameter \(\omega ^{TW}\) penalizes delays in the delivery of products by vehicle k. The delay \(TW_{k}\) is the sum of the times that exceed the final time window of each customer belonging to the vehicle route k. In turn, the weighting values \(\omega ^{Q}\), \(\omega ^{T}\) and \(\omega ^{TW}\) are calculated from the parameter \(\alpha\), the average demands \(\bar{q}\), and the average service times \(\bar{h}\) for consumers, as defined below:

$$\begin{aligned} \omega ^{Q}=\, & {} \frac{\alpha }{\bar{q}}\end{aligned}$$
(25)
$$\begin{aligned} \omega ^{T}= \, & {} \omega ^{TW} = \frac{\alpha }{\bar{h}}\end{aligned}$$
(26)

The use of penalties for treating constraint violations is a strategy commonly used in the optimization literature due to the high degree of difficulty in exploring the solution space of problems like VRP and variants using only feasible solutions. The algorithms proposed by Polacek et al. [36] and Vidal et al. [37], for example, use this strategy.

5.2.2 Evaluation function to distance reduction

This section presents the evaluation function adopted for solving MDOVRPTW in order to reduce the total traveled distance by the used vehicles. This evaluation function for a solution s is given by:

$$\begin{aligned} F'(s) = \beta L + \alpha \Big ||{\mathcal{K}}|- |{\mathcal{U}}|\Big |+ \varphi\end{aligned}$$
(27)

As this evaluation function seeks to minimize the total traveled distance, the weighting factor \(\beta\) is set to \(\beta =1\). The second parcel of this evaluation function aims to stimulate the use of the whole vehicle fleet and, hence, the parameter \(\alpha\) is calculated according to Eq. (22). The third parcel \(\varphi\) of F(s) remains as described in Eq. (23), since the proposed algorithm also generates infeasible solutions.

5.3 Construction of the initial solution

The procedure for building the initial solution was inspired by the algorithm proposed by [38]. This algorithm first groups the customers for each depot and then generates the routes. This technique is performed here by Algorithms 1 and 2, respectively.

5.3.1 Procedure for generating clusters

This section describes Algorithm 1, which performs the clustering procedure. While customers are not associated with any route, the method finds a depot that can accept them. This is shown in Algorithm 1 in lines 3–47. In lines 8–18, we determine the two depots closest to each customer \(i \in {\mathcal{C}}'\). These depots were identified as d1 and d2 (lines 11 and 13). The distances between customer i and depots d1 and d2 were named \(c_{d1, i}\) and \(c_{d2, i}\), respectively. In line 15, the proximity ratio between each customer i and its depots d1 and d2 are calculated. The set of pairs \(\{i,c_{d1, i} / c_{d2, i}\}\), described in line 16, constitute the set \({\mathcal{H}\mathcal{R}}\). This set is sorted in ascending order from these ratios in line 19. Then, the customers are assigned to one of these depots. This procedure starts at line 22 and finishes in line 36. The distribution between depots occurs in a balanced way (lines 28–34). Therefore, in the order given by \({\mathcal{H}\mathcal{R}}\), each pair formed by the customer \(i \in {\mathcal{C}}'\), and its respective depot d1 (or d2), is assigned to the sets \({\mathcal{H}\mathcal{D}}\) and \({\mathcal{C}}''\). In the new composition of set \({\mathcal{C}}'\), all assigned customers are removed (line 37). In turn, the depots that have reached their capacity limit are also removed (lines 39–46). The algorithm returns the set \({\mathcal{H}\mathcal{D}}\) with pairs of customers and depots.

figure a

5.3.2 Algorithm for generating routes

Algorithm 2 shows the procedure to construct the routes. The routes are constructed respecting the vehicles’ capacity, the maximum route time, and the customers’ time windows. These routes are constructed in a partially greedy way. The customer i and the depot d, with \(\{i, d\} \in {\mathcal{H}\mathcal{D}}\), are chosen from a previously fixed value \(\lambda \in [0, 1]\). If a real random value is less than or equal to \(\lambda\) (line 4), then a customer j \(\in {\mathcal{H}\mathcal{D}}\) is chosen (line 5). Otherwise, the jth element is the first of the set \({\mathcal{H}\mathcal{D}}\) (line 3). From empirical tests, the value of \(\lambda\) was fixed in 0.6. In lines 7–8, the customer and depot are defined. The routes are represented in a subset \(r_{d} \subset {\mathcal{R}}\) that receives the customer i, as shown in line 10. In line 11, the pair \(\{i, d\}\) is dropped from \({\mathcal{H}\mathcal{D}}\). All customers must be served. This imposition can occur that the number of vehicles used can be greater than \(\mid {\mathcal{K}}\mid\). The algorithm is finalized in line 13, returning the set \({\mathcal{R}}\) of routes.

figure b

5.4 Neighborhoods

To explore the MDOVRPTW and MDOVRPTW* solution spaces, we use neighborhood operators that apply moves in the same depot on different routes (inter-routes), in the same route (intra-route), or between routes from different depots (inter-depots). These neighborhood operators are described in the following.

5.4.1 Perturbation operators

Three perturbation mechanisms \({\mathcal{P}\mathcal{O}} = \{{\mathcal{P}\mathcal{O}}_{1}, {\mathcal{P}\mathcal{O}}_{2}, {\mathcal{P}\mathcal{O}}_{3}\}\) were implemented:

  1. (1)

    \({\mathcal{P}\mathcal{O}}_{1}\) (Eliminates route) it consists of eliminating a route \(r^{d} \in {\mathcal{R}}\) from a depot d and transferring its customers to other routes from the same depot or to other depot \(d'\). All choices are made at random. All insertions of customers into routes need to be feasible.

  2. (2)

    \({\mathcal{P}\mathcal{O}}_{2}\) (ShiftDepot) a route of the set \(r^{d_{1}}\) of routes from the depot \(d_{1}\) is transferred to another depot \(d_{2}\), where \(d_{2} \ne d_{1}\). The depot \(d_{1}\) must have the greatest number of routes (at least two routes) and \(d_{2}\) the smallest one. If all depots have the same number of routes, \(d_{1}\) and \(d_{2}\) are randomly chosen.

  3. (3)

    \({\mathcal{P}\mathcal{O}}_{3}\) (SwapDepot) it consists of swapping a route of the set \(r^{d_{1}}\) of routes from the depot \(d_{1}\) with a route of the set \(r^{d_{2}}\) of routes of the depot \(d_{2}\).

5.4.2 Local search operators

We used Swap, Reinsertion, and Permutation operators, widely applied in the literature on VRP and variants [8, 25, 37, 39,40,41,42,43,44]. They are described below.

Intra-route operators:

  1. (1)

    \({\mathcal{LSO}}_{1}\) (Swap) it consists of swapping two customers in the same route.

  2. (2)

    \({\mathcal{LSO}}_{2}\) (Reinsertion) a customer is removed and reinserted in another position in the same route.

  3. (3)

    \({\mathcal{LSO}}_{3}\) (Or-opt2) two consecutive customers are removed and reinserted in another position in the same route.

  4. (4)

    \({\mathcal{LSO}}_{4}\) (2-Opt) two non-adjacent edges are deleted and two others are added to generate a new route.

  5. (5)

    \({\mathcal{LSO}}_{5}\) (3-Opt) three edges are excluded and all possibilities of exchange between them are tested to generate new routes.

Inter-routes operators:

  1. (1)

    \({\mathcal{LSO}}_{6}\) (Swap(1,1)) it consists of swapping a customer \(v_{j}\) from one route \(r_{k}\) with a customer \(v_{t}\) from another route \(r_{l}\) belonging to the same depot.

  2. (2)

    \({\mathcal{LSO}}_{7}\) (Shift(1,0)) it consists of transferring a customer \(v_{j}\) from a route \(r_{k}\) to another route \(r_{l}\) belonging to the same depot.

Inter-depots operators:

  1. (1)

    \({\mathcal{LSO}}_{8}\) (Swap(1,1)-InterDepot) it consists of swapping a customer \(v_{j}\) from one route \(r_{k}\) with a customer \(v_{t}\) from another route \(r_{l}\) belonging to another depot.

  2. (2)

    \({\mathcal{LSO}}_{9}\) (Shift(1,0)-InterDepot) it consists of transferring a customer \(v_{j}\) from a route \(r_{k}\) to another route \(r_{l}\) belonging to another depot.

The set of all local search operators is \({\mathcal{LSO}}\) = \(\{{\mathcal{LSO}}_{1}, \ldots , {\mathcal{LSO}}_{9}\}\).

5.5 Perturbation procedure

Algorithm 3 presents the perturbation procedure. In this algorithm, \({\mathcal{P}\mathcal{O}}\) is the set of perturbation operators described in Sect. 5.5, \({\mathcal{P}\mathcal{O}}_{v}\) is the vth operator that generates the perturbation solution, and p is the number of times that this operator is applied to the solution s. In line 6, the procedure returns the perturbed solution \(s_{p}\).

figure c

5.6 Local search

We used the randomized basic variable neighborhood descent (RBVND) algorithm [34] as the local search method. RBVND is a variation of the basic variable neighborhood descent (BVND) method [32]. Instead of using a predefined order of neighborhoods to explore the solution space, it uses a random order at each call of the local search method. More specifically, whenever it is not possible to improve the current solution in a specific neighborhood, RBVND randomly selects another neighborhood to continue the search in the problem’s solution space. At the end of the method, it returns a local optimum concerning all explored neighborhoods.

figure d

Algorithm 4 presents the pseudocode of RBVND. In this algorithm, the set \({\mathcal{LSO}}'\) defines the neighborhood structures that will be used, which are randomly ordered from the set \({\mathcal{LSO}}\) (line 1). At each iteration (lines 3–11), the neighborhood \({\mathcal{LSO}}'_{v} \in {\mathcal{LSO}}'\) is applied to the s solution, generating the neighbor \(s'\). In case of improvement of the current solution (line 5), it is updated, and the index v returns to the first neighborhood of \({\mathcal{LSO}}'\); otherwise, the search moves to the next neighborhood. The algorithm ends when it reaches the last neighborhood structure, and there is no improvement in the current solution. The refined solution is returned in line 12.

5.7 Proposed algorithm

Algorithm 5 shows the pseudo-code of the SGVNS algorithm proposed to solve MDOVRPTW and MDOVRPTW*. Lines 1 and 2 show that an initial solution is built using the procedures described in Algorithms 1 and 2, respectively. After the solution is created, the initial perturbation level, the index for the first neighborhood, the iteration counter without improvement, and the iteration counter for applying the local search procedure are set in 3, 4, 5, and 6, respectively. The main loop for SGVNS is between lines 7 and 27. The algorithm ends when the number of iterations without improvement reaches its maximum value or the run time meets its maximum duration. At each iteration, the solution s is perturbed according to Algorithm 3, generating a perturbed solution \(s'\) through perturbation operations described in Sect. 5.5. In line 9, the local search procedure is applied in \(s'\) according to Algorithm 9 described in Sect. 5.6, returning an improved solution \(s''\). If this solution \(s''\) is better than s, then we update the solution s, return to the first neighborhood and to the first perturbation level, and reset the iteration counter without improvement in lines 11–14, respectively. Otherwise, the perturbation level and the iteration counter are increased (lines 16–17). If the perturbation level meets its maximum level, i.e., maxLevel, the neighborhood is changed for the next. When it occurs, the perturbation level is changed to its minimum value, i.e., \(p=1\). If the last perturbation neighborhood is reached, it is necessary to return to the first perturbation neighborhood (line 24) and consequently to the first perturbation level (line 25). In line 28, the SGVNS algorithm returns the best solution s found during the search.

figure e

6 Computational results

The SGVNS algorithm was coded in C++ and executed on an Intel Xeon E5620 2.40 GHz \(\times\) 16 machine with 112 GB of RAM under the Linux operating system 64 bits.

We do not find test instances for MDOVRPTW and MDOVRPTW* in the literature. Hence, we decide to use the MDVRPTW instances from Cordeau et al. [45] and Vidal et al. [37] as test instances for these open routing problems. We named Group I the set described in Cordeau et al. [45], and Group II the instances proposed in Vidal et al. [37]. The first set is available at Networking and Emerging Optimization—NEO,Footnote 1 and the second one at Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation—CIRRELT.Footnote 2 The distance in Group I and Group II is the Euclidean distance, and it is supposed that the vehicle’s travel time between two nodes is equal to the Euclidean distance. The vehicle fleet is homogeneous in both groups.

The characteristics of instances of Group I and Group II are described in Tables 7 and 8, respectively. The first five columns of each table describe the characteristics of the instances, i.e., the number of customers, depots, vehicles per depot, and the total of available vehicles, respectively. Group I has 20 instances, such that the first ten instances have tight time windows, while the last ten ones have wide time windows. Group II contains 28 instances with a large number of customers and depots.

6.1 Parameter tuning

We used the iterated racing for automatic algorithm configuration (IRACE) [46] for tuning the SGVNS algorithm parameters. To calibrate the parameters iterMax and maxLevel, we selected 30% of the Group I instances. Table 5 shows the six chosen instances, and it is important to highlight that they contain different characteristics representative of the set of instances. We ordered them by the values of \(\rho = \mid {\mathcal{C}}\mid \cdot \mid {\mathcal{K}}_{d}\mid \cdot \mid {\mathcal{D}}\mid\) and grouped them by tight and wide time windows, respectively.

Table 5 Characteristics of the instances used for tuning SGVNS with IRACE
Full size table

Table 6 reports the range of the tested values and the returned values by IRACE. The parameter iterMax was set to 100; above this value, the algorithm required more computational time without significantly improving the results.

Table 6 Tested parameter values and results returned by IRACE
Full size table

6.2 Group I results

Table 7 reports the best results found by SGVNS in instances of Group I for MDOVRPTW and MDOVRPTW* and a comparison of its results with those shown in [37] for MDVRPTW. In this table, the first five columns show the MDVRPTW characteristics. The column “MDVRPTW” shows the best result for each instance from the literature. Column “SGVNS” shows the results found for the MDOVRPTW and MDOVRPTW*. For each instance, the distance, number of vehicles used, and spent time are shown in columns “Distance”, “\({\mathcal{K}}\)”, and “Time”, respectively. The differences concerning the distances and vehicles for both problems are shown in column “Difference between MDOVRPTW* and MDOVRPTW”. The line “Sum” of this table shows the total number of available vehicles and the total distance for the MDVRPTW; the total distance, the number of vehicles used, and spent times in all instances for the MDOVRPTW and MDOVRPTW*; the difference between the total distance and the total number of vehicles used for the MDOVRPTW* and MDOVRPTW. For Group I, the SGVNS algorithm was executed 30 runs per instance, and the value of the MaxTime parameter was set to 60 min.

Table 7 Results of the SGVNS algorithm applied to Group I instances for MDOVRPTW and MDVRPTW*
Full size table

The results show a reduction of approximately \(12.07\%\) in the total distance for MDOVPTW for all evaluated instances when compared with MDVRPTW. In all instances, there was a reduction in the distance traveled. The MDOVRPTW* results showed that the number of vehicles used was reduced by \(10.42\%\) on average compared to the total number of available vehicles. Among the 336 vehicles available in Group I, only 301 were used by the SGVNS solution. Even though it is not the aim associated with MDOVRPTW*, the total distance of Group I decreased by \(3.65\%\) on average compared with the MDVRPTW solution.

6.3 Group II results

Table 8 shows the best results generated by the SGVNSALS algorithm for Group II. The structure of this table is similar to that adopted for Table 7. As in Sect. 6.2, the results obtained by SGVNS for MDOVRPTW and MDOVRPTW* are compared to those of MDVRPTW shown in Vidal et al. [37]. For Group II, the algorithm was executed 20 runs per instance, and the value of the MaxTime parameter was set to 180 min.

For all instances of Group II, there was also a reduction in the distance and number of used vehicles. For MDOVRPTW, there was a reduction of \(10.43\%\) in the total traveled distance compared with the results from MDVRPTW shown in Vidal et al. [37]. Concerning MDOVRPTW*, there was a reduction of \(24.13\%\) in the number of used vehicles and \(6.14\%\) in the total traveled distance compared with the MDVRPTW results. Additionally, the results from MDOVRPTW* regarding MDOVRPTW achieved a reduction of \(23.59\%\) in the number of used vehicles, alongside an increase of \(4.79\%\) in the total distance traveled. These results, reached in a challenging set of instances, justify the definition and study of this variant.

Table 8 Results of the SGVNS algorithm applied to Group II instances for MDOVRPTW and MDVRPTW*
Full size table

7 Analysis of the proposed algorithm

In this section, the results of the SGVNS algorithm are statistically investigated. In Fig. 2a and 2b, the ordinate axis represents the gaps of the value of the median solutions concerning distances and number of vehicles, respectively. The gaps were calculated through:

$$\begin{aligned} gap\_{v}ehicle= & {} \, \frac{number \; of \; vehicles}{median \; of \; vehicles} \quad \quad (28)\end{aligned}$$
$$\begin{aligned} gap\_{d}istance= & {} \, \frac{distance}{median \;of \;distances} \quad \quad (29)\end{aligned}$$
Fig. 2
figure 2

Boxplots of the SGVNS algorithm results

Full size image

The results achieved by SGVNS concerning fleet reduction do not show significant variations in its behavior. Figure 2a shows that the distribution occurs around the median. There is no variation for \(50\%\) of results between the first and third quartile. The total amplitude was \(0.34\%\). These results show the stability of the SGVNS algorithm concerning fleet reduction.

Figure 2b shows the results for distance deviation. It is possible to verify the stability in the behavior of the proposed algorithm concerning the distances it found. For MDOVRPTW, there is a variation of \(4.27\%\) in \(50\%\) of the results around the median values, and for MDOVRPTW*, this variation is \(4.95\%\). The distances found by the SGVNS algorithm for MDOVRPTW* have a more significant number of outliers, which indicates the greater variation between these distances. Such variations are not atypical since distance reduction is not prioritized. When analyzing the distances through the errors related to the median values, it is concluded that there are no statistically significant differences between the two problems evaluated.

8 General discussions and conclusions

This article introduced a variant for the MDOVRPTW, called MDOVRPTW*. In the MDOVRPTW, the goal is to reduce the distance traveled, while in MDOVRPTW*, the priority is to reduce the fleet size. An algorithm based on the VNS heuristic, called SGVNS, was developed for treating them. The SGVNS algorithm uses nine neighborhood structures based on insertion, swap, and shift moves as local search operators to refine the incumbent solution and three neighborhood structures as perturbation operators to escape from each local optimum found. As there are no specific instances for the addressed problems, the current article adopted the instances from Cordeau et al. [45] (Group I) and those defined in Vidal et al. [37] (Group II), originally proposed for the MDVRPTW.

The results achieved by SGVNS for the two addressed problems were compared with the best-found results for the MDVRPTW. In Group I, there was a 12.07% reduction in the total distance traveled for the MDOVRPTW and a 10.42% reduction in fleet size for the MDOVRPTW*. In Group II, the algorithm achieved a 10.43% reduction in total distance traveled for the MDOVRPTW and a 24.13% reduction in fleet size for the MDOVRPTW*. Considering all instances (Groups I and II), there was a reduction in the total distance traveled for all of them and, besides, a fleet reduction in 92.65% of them. These results validate the proposition of MDOVRPTW as an important variant of vehicle routing problems and the proposed algorithm as a technique to solve these addressed problems.

In future work, we will address the challenge of including adaptive procedures in local search structures. Recently, several studies have shown high-quality results in the form of adaptation procedures in choosing neighborhoods like Derbel et al. [26], Karakostas et al. [29, 31], Ren et al. [28], Sanchez-Oro et al. [27], Smiti et al. [24] and in procedures involving machine learning techniques, like Sevaux et al. [47], Talbi [48], Karimi-Mamaghan et al. [49], and Silva et al. [50].