1 Introduction

Vehicle routing problem (VRP) determines a set of routes for a fleet of vehicles aiming to minimize, in general, the total distance traversed under a set of constraints such as capacity, time window (TW), visiting frequency, etc. VRP with time window (VRP-TW) imposes a constraint on the start of service time, thereby indicating that a customer must be visited by a vehicle within prescribed time interval. In order to encounter such real-life business scenarios, VRP-TW is observed to arise frequently in various context such as grocery distribution, oil and petroleum delivery, repairmen scheduling, school bus routing, industrial refuse collection, etc. (Cordeau et al [1]). The complexity involved in VRP-TW is much higher when the fleet is assumed to consist of a set of heterogeneous vehicles (having different capacities), which traverse through multiple depots over multiple periods. Yousefikhoshbakht et al [2] proposed a meta-heuristic algorithm called bone route algorithm combined with a modified tabu search (BRMTS) for solving the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP). The proposed research is intended to formulate a multi-depot multi-period vehicle routing problem with time window (MDMPVRP-TW), wherein a transportation company builds a set of replenishment depots to serve a set of customers located at different places. A fleet of heterogeneous vehicles are operated over a finite time horizon, the latter being segmented into several periods. The proposed MDMPVRP-TW is an extension of VRP-TW, and is therefore an NP-hard problem. To optimize the MDMPVRP-TW, we propose a hybrid meta-heuristic by combining tabu search (TS) with variable neighbourhood search (VNS) algorithm.

Over the last few decades, VRP-TW is being widely studied and is found to have many applications in the design and management of distribution systems. Several variants of VRP-TW are therefore put forward to encounter the real-life situations more closely. Besides the capacity constraint, it is now mandatory for each vehicle to visit a delivery location within a specified time frame. In literature two types of TWs are considered, namely soft and hard. The soft TW can be violated by incurring penalty cost whereas hard TW cannot be violated at any cost. The latter case is being considered in the present work. A heuristic TS algorithm was studied by Taillard et al [3] with soft TW. Cordeau et al [1] presented two important generalizations, namely the periodic and the multi-depot vehicle routing problems (MDVRPs) with TWs. Recently, Paul et al [4] investigated a two-echelon pollution routing problem with simultaneous pickup and delivery under multiple TWs constraint. Some other notable contributions on VRP-TW include the works of Solomon [5], Braysy and Gendreau [6], Chang et al [7], Miranda and Conceicao [8], Chu et al [9] and Hu et al [10].

In real-life VRP, routes are designed for a planning horizon that may consist of multiple periods and a customer may be served over a subset of these periods (Mancini [11]). Multi-period vehicle routing problem (MPVRP) is a profitable tour planning that allows vehicles to serve the customers based on their requirements so that every customer need not necessarily be visited daily. MPVRPs, capturing different situations, have been formulated by many researchers in the recent years. Dayarian et al [12] proposed partitioning-based two-stage MPVRP in which first stage corresponds to plan whereas second stage takes multi-period. Luo et al [13] investigated a mixed integer MPVRP with TW and limited visiting quota, and proposed three-stage heuristic approach to optimize it. Dayarian et al [14] formulated MPVRP by considering seasonal fluctuation in supply and designed an adaptive large neighbourhood search (ALNS)-based meta-heuristic to optimize the proposed model. Naccache et al [15] addressed a multi-pickup and delivery VRP with TW, and developed a hybrid ALNS via branch and bound heuristic. Similar to MPVRP, the literature of MDVRP is also very rich. An elaborative literature survey on MDVRP is carried out by Lahyani et al [16]. Michallet et al [17] addressed a real-world problem occurring in the transportation of valuable goods by considering a very hard periodic VRP with TWs and time spread constraints on services. The existing MDVRPs are mostly optimized by heuristics approach. One of the first algorithms is put forward by Tillman [18], which assigns every customer node to its nearest depot and thereby routes are constructed back and forth between the depots and the customers. Renaud et al [19] discussed a TS algorithm for the MDVRP with capacity and route length constraints, the algorithm being tested on a set of 23 benchmark instances.

During serving the customers along a route, it may sometimes happen that the remaining cargo in the vehicle is not sufficient enough to fulfil the demand of the next customer. In such a situation there is a need of installation of some intermediate replenishment depots, which can be visited by the vehicles as and when required. Cordeau et al [1] presented a unified TS heuristic for the VRP-TW as well as for its two important generalizations, namely, PVRP-TW and MDVRP-TW. Allowable combination for serving the customers was also taken into consideration, which restricted the service time to be scheduled on certain specified time periods. Suppose a planning horizon of 5 days is considered, viz. Monday to Friday. Within this planning horizon a customer i is to be served twice, with the service being provided on Monday and Wednesday, or Monday and Friday or Tuesday and Friday (say). Therefore, in this case the customer i has 3 possible combinations of 2 days so that the set of allowable combinations can be represented as {{Monday, Wednesday}, {Monday, Friday}, {Tuesday, Friday}}. Polacek et al [20] proposed an algorithm based on the philosophy of the VNS for solving MDVRP-TW. An extension of MDVRP was suggested by Crevier et al [21] involving replenishment of vehicles at intermediate depots along the routes. A three-phase methodology was proposed by them based on adaptive memory, TS and integer programming. The algorithm was tested on randomly generated as well as on benchmark instances derived from those proposed for MDVRP by Cordeau et al [22]. A hybrid granular tabu search algorithm to solve the MDVRP under associated capacity and maximum duration constraints was proposed by Escobar et al [23].

Among the recent works, Mancini [11] introduced the multi-depot multi-period vehicle routing problem with a heterogeneous fleet (MDMPVRPHF). The authors proposed a mixed integer programming formulation and an ALNS-based meta-heuristic that defines several destroy operators. Salhi et al [24] solved an MDVRP with heterogeneous vehicle fleet by designing an efficient VNS-based algorithm. Kumar et al [25] developed a multi-objective multi-vehicle production and pollution routing problems with time window (MMPPRP-TW). They formalized a hybrid self-learning particle swarm optimization (SLPSO) algorithm in multi-objective framework for the solution methodology. A multi-depot open VRP was investigated by Soto et al [26], which is a well-known variant of VRP in which vehicles are not required to return to the depot at the end of their tour. Instead, each route ends at the last served customer. Recently, Zhou et al [27] introduced a new city logistics problem by considering a multi-depot two-echelon VRP with delivery options. For the solution methodology of the problem, the authors proposed a hybrid multi-population genetic algorithm.

With an overview of the related research works done so far, it is observed that a VRP-TW model with both multi-period and multi-depot facilities considering allowable combinations has not been examined yet in the literature. Therefore, in order to fill this research gap, a model with the said characteristics is presented here. The second novelty of this research is to propose a hybrid meta-heuristic by combining TS and VNS. The remainder of the paper is organized as follows. A detailed description of the examined situation with the formulation of the mathematical model is demonstrated in Section 2. The proposed hybrid VNS–TS algorithm is elaborately discussed in Section 3. In Section 4, the proposed model is illustrated with the help of numerical examples followed by relevant discussions. Lastly, Section 5 presents a brief conclusion along with future research opportunities.

2 Model formulation

In this section, we mathematically formulate the proposed MDMPVRP-TW. Before this, a detailed description of the model along with real-life application is presented.

2.1 Situation description

In real-life problems, a transportation company plans to design routes to serve customers over a planning horizon instead of a single period. We have considered, in our study, a finite planning horizon subdivided into a number of periods. For instance, a week may be regarded as a planning horizon with each of the seven days being considered as a period. A customer is served over a subset of this planning horizon. For example, one may be served on Monday, Wednesday and Friday, while another is served on Saturday and Wednesday and so on. Such a planning of routes also helps in minimization of total traversed distance. Every customer i has a constant demand and a fixed service time indicating that a vehicle must visit it within the specified TW, thereby taking care of the allowable combinations as discussed in Section 1. A set of d depots are installed at various locations, where a fleet of r heterogeneous vehicles are considered to be located. The journey of a vehicle in period t starts from the depot at which its journey ended in period \( (t-1) \). While serving the customers along the route, it may happen sometimes that a vehicle is out of cargo or the remaining cargo is not sufficient to serve the next customer node. In such a situation, it may visit any nearby replenishment depot for the purpose of refilling. However, the route duration covered by any vehicle is not allowed to exceed a given maximum time limit.

As an instance, water distribution to drought-affected areas can be considered as a suitable example for the proposed MDMPVRP-TW. All the vehicles that are used for transportation purpose are situated at a main station from where tours have to begin. The various sites away from the main station are affected by drought. In such a scenario, the more affected areas are supposed to be served frequently whereas the lesser affected regions have less frequent supply for water. Accordingly, each area will be specified with an allowable combinations set within a certain planning horizon in order to counteract the water scarcity in every region equally. Moreover, at any point of service, if the water supplying tank is found to lack sufficient water to serve further when there is already some pending demand, then in such a situation the vehicle (carrying storage tanks) can visit some nearby water reservoir, get refilled and resume the service further.

2.2 Assumptions

The model is built up under the following assumptions listed:

  1. 1.

    Heterogeneous fleet of vehicles is considered to serve the customer.

  2. 2.

    Demand rate at each customer node is fixed and known in advance. Shortages of item are not permissible to any node.

  3. 3.

    Intermediate replenishment is considered, which means any running vehicle can be replenished by a nearby depot if required.

  4. 4.

    Demand of any customer does not exceed the vehicle capacity.

  5. 5.

    Demand at each depot is assumed to be zero.

  6. 6.

    The journey of a vehicle in period t starts from the depot at which its journey ended in period \(t-1\).

  7. 7.

    Every depot is assumed to hold infinite inventory.

  8. 8.

    Each customer has a TW in each period within which it must be served by at most one vehicle.

  9. 9.

    Any route of a vehicle will get terminated as soon as it violates maximum time limit constraint.

  10. 10.

    A route is a path travelled by a vehicle in any particular period.

2.3 Mathematical model

Built upon the discussed situation, a constrained optimization problem is formulated with the objective function being represented as follows:

$$\begin{aligned} \text { minimize: }\sum _{i=1}^{n} \sum _{\begin{array}{c} j=1 \\ i \ne j \end{array}}^{n} \sum _{k=1}^{r} \sum _{t=1}^{p} d_{ij} x_{ijkt}. \end{aligned}$$
(1)

Equation (1) represents the total distance travelled by all the vehicles over the planning horizon. Hence our objective is to minimize it. The following constraints are enunciated by addressing time window, visiting frequency quota and vehicle routes:

$$\begin{aligned}&e_{it}\le ar_{ikt}\le l_{it}, \quad \forall i\in V, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(2)
$$\begin{aligned}&ar_{ikt}+s_{ikt}+t_{ij}x_{ijkt}\le ar_{jkt}x_{ijkt}+\Lambda (1-x_{ijkt}), \quad \forall i,j\in V, \nonumber \\& i \ne j, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(3)
$$\begin{aligned}&y_{ikt}\ge q_{it}, \quad \forall i\in V_1, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(4)
$$\begin{aligned}&0\le y_{jkt}\le (y_{ikt}-q_{it})x_{ijkt}+Q_k(1-x_{ijkt}), \quad \forall i\in V_1, \nonumber \\& \forall j\in V, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(5)
$$\begin{aligned}&0\le y_{jkt}\le Q_k-q_{it}x_{ijkt}, \quad \forall i\in V_2, \quad \forall j\in V, \quad \forall k\in K, \nonumber \\& \forall t\in T \end{aligned}$$
(6)
$$\begin{aligned}&\sum _{i \in V}\sum _{\begin{array}{c} j\in V \\ i \ne j \end{array}}q_{it}x_{ijkt}\le Q_k\left( \sum _{i\in V_2} E_{ikt}+1\right) , \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(7)
$$\begin{aligned}&t_{ij}=\dfrac{d_{ij}}{v}, \quad \forall i,j\in V \end{aligned}$$
(8)
$$\begin{aligned}&\sum _{i \in V}\sum _{\begin{array}{c} j\in V \\ i \ne j \end{array}}t_{ij}x_{ijkt}\le D_k, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(9)
$$\begin{aligned}&\sum _{\begin{array}{c} j\in V \\ i \ne j \end{array}}\sum _{k \in K}x_{ijkt}\le 1, \quad \forall i\in V_1, \quad \forall t\in T \end{aligned}$$
(10)
$$\begin{aligned}&\sum _{\begin{array}{c} j\in V \\ i \ne j \end{array}}\sum _{k \in K}x_{jikt}\le 1, \quad \forall i\in V_1, \quad \forall t\in T \end{aligned}$$
(11)
$$\begin{aligned}&\sum _{j\in V}x_{ijkt}=\sum _{j\in V}x_{jikt} \quad \forall i\in V_1, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(12)
$$\begin{aligned}&\sum _{j\in V}\sum _{k\in K}\sum _{t\in T} x_{ijkt}=f_i \quad \forall i \in V_1 \end{aligned}$$
(13)
$$\begin{aligned}&\sum _{j\in V}\sum _{k\in K}\sum _{t\in T} x_{jikt}=f_i \quad \forall i \in V_1 \end{aligned}$$
(14)
$$\begin{aligned}&\sum _{r\in C_i}w_{ir}=1, \quad \forall i\in V_1 \end{aligned}$$
(15)
$$\begin{aligned}&\sum _{\begin{array}{c} j\in V_1 \\ i \ne j \end{array}}\sum _{k\in K}x_{ijkt}-\sum _{r\in C_i}a_{rt}w_{ir}=0, \quad \forall i\in V_1, \quad \forall k\in K, \nonumber \\& \forall t\in T \end{aligned}$$
(16)
$$\begin{aligned}&\sum _{j\in V }\sum _{k \in K}x_{ijkt}=\sum _{k\in K}E_{ikt}, \quad \forall i\in V_2, \quad \forall t\in T \end{aligned}$$
(17)
$$\begin{aligned}&\sum _{j\in V }\sum _{k \in K}x_{jikt}=\sum _{k\in K}E_{ikt}, \quad \forall i\in V_2, \quad \forall t\in T \end{aligned}$$
(18)
$$\begin{aligned}&\sum _{k\in K} M_{ikt} \le r, \quad \forall i\in V_2, \forall t\in T \end{aligned}$$
(19)
$$\begin{aligned}&\sum _{k\in K} N_{ikt} \le r, \quad \forall i\in V_2, \forall t\in T \end{aligned}$$
(20)
$$\begin{aligned}&\sum _{i\in V_2}\sum _{k\in K} M_{ikt} = \sum _{i\in V_2}\sum _{k\in K} N_{ikt}, \quad \forall i\in V_2, \forall t\in T \end{aligned}$$
(21)
$$\begin{aligned}&\sum _{i\in V_2} M_{ikt}+\sum _{i\in V_2} E_{ikt}+\sum _{i\in V_2} N_{ikt}\ge 2, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(22)
$$\begin{aligned}&M_{ikt}=N_{ik,t-1}, \quad \forall i\in V_2, \quad \forall k\in K, \quad \forall t\in T\backslash \{1\} \end{aligned}$$
(23)
$$\begin{aligned}&\sum _{i\in S}\sum _{\begin{array}{c} j\in S \\ i \ne j \end{array}}x_{ijkt}\le \sum _{i\in S}\sum _{\begin{array}{c} j\in V_1 \\ i \ne j \end{array}}x_{ijkt}-\sum _{\begin{array}{c} j\in V_1 \\ e \ne j \end{array}}x_{ejkt}, \quad \forall S\subseteq V_1, \nonumber \\& |S|\ge 2, \quad \forall e\in S, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(24)
$$\begin{aligned}&ar_{ikt}\ge 0, \quad \forall i\in V, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(25)
$$\begin{aligned}&y_{ikt}\ge 0, \quad \forall i\in V, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(26)
$$\begin{aligned}&w_{ir}\in \{0,1\}, \quad \forall i\in V_1, \quad \forall r\in C_i \end{aligned}$$
(27)
$$\begin{aligned}&E_{ikt}\in \{0,1\}, \quad \forall i\in V_2, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(28)
$$\begin{aligned}&M_{ikt}\in \{0,1\}, \quad \forall i\in V_2, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(29)
$$\begin{aligned}&N_{ikt}\in \{0,1\}, \quad \forall i\in V_2, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(30)
$$\begin{aligned}&x_{ijkt}\in \{0,1\}, \quad \forall i,j\in V, \quad \forall k\in K, \quad \forall t\in T \end{aligned}$$
(31)
$$\begin{aligned}&x_{iikt}=0, \quad \forall i\in V, \quad \forall k\in K, \quad \forall t\in T. \end{aligned}$$
(32)

TW constraints are given in (2) and (3), which indicate that a vehicle has to reach a particular customer node within a given time interval. Constraints (4) ensure that the remaining cargo in any vehicle on arrival at a node is greater than the customer demand at that node. It is specified by constraints (5) and (6) that the amount of cargo left in a vehicle can never fall below zero, i.e., whenever required, it may visit any nearby intermediate depot along the route for replenishment. Constraints (7) put a restriction on the total load carried by a vehicle, ensuring that it cannot exceed the vehicle capacity. Relation between time and velocity is given by (8). Constraints (9) restrict the duration of a route to its maximum limit. It is ensured by constraints (10) and (11) that in each time period, a customer can be served by at most one vehicle. Constraints (12) indicate that a vehicle arriving at a customer node will also get departed. Constraints (13) and (14) state that a customer i will be altogether served \( f_i \) times over the planning horizon. It is guaranteed by constraints (15) and (16) that each customer is visited only on the days corresponding to the assigned combination. Constraints represented by these two equations are directly adopted from the original research work of Cordeau et al [22]. Constraints (17) and (18) confirm the departure of a vehicle from an intermediate depot in case if it has visited one. A restriction upon the total number of vehicles is imposed by constraints (19) and (20). All vehicles departing from various depots in a particular period are bound to return back to the depots, which is ensured by constraints (21) and (22). Constraints (23) suggest that the journey of any vehicle in period t starts from the depot where it ended in period \( (t-1) \). For each vehicle the possibility of sub-tours is eliminated by constraints (24), as discussed in the work of Kumar et al [25]. Constraints (25)–(32) define the domain of the decision variables.

3 Solution methodology

As discussed in introduction section, the literature is laden with several algorithms for different variants of VRP and also with various ways to obtain the initial solution. The algorithm proposed in this paper, to obtain an optimal solution to the formulated MDMPVRP-TW, is a hybridization of TS and VNS. A detailed description of the adopted procedure is presented under the following headings.

3.1 Initial solution

The proposed approach to construct the initial solution is quite similar to that suggested by Cordeau et al [1], and is a very fast method. Step-by-step description of the procedure is listed as follows:

  1. 1.

    For each customer, an allowable combination from the given options is randomly selected and allotted.

  2. 2.

    Sets of customers having demand (need a service) in the respective periods are to be listed.

  3. 3.

    For every period:

  4. (a)

    Customers are sorted in ascending order of the mean value of their corresponding TW and the same is stored in a set U.

  5. (b)

    r empty routes are created, where empty route indicates a route containing two depots.

  6. (c)

    From the first \(\alpha \) customers of U, a customer i is randomly selected and inserted into any one of the r routes so that it is feasible with respect to TW and route duration. Then, i is removed from U.

  7. (d)

    Step (c) will be repeated until the remaining customers of U cannot be inserted into any route without violating TW and maximum duration constraints and then the remaining customers of U are inserted into the \(r^{th}\) route.

  8. (e)

    If the remaining cargo in a vehicle after serving a customer is not sufficient to serve the next customer along the route, then a depot is inserted in between these two customers in a way so as to minimize the total distance.

Thus, a set of r routes for each period is obtained where the first \( (r-1) \) routes are feasible with respect to demand (TW and route duration constraints may be violated because of late insertion of the intermediate depot in the routes). After completing this process we have an initial solution.

3.2 Generalized cost function

A solution is evaluated by means of the following generalized cost function:

$$\begin{aligned} f(s)=f_{dist}(s)+\alpha f_{dem}(s)+\beta f_{dur}(s)+\gamma f_{wait}(s)+\delta f_{late}(s). \end{aligned}$$
(33)

The terms used in the relation have the following significances: \(f_{dist}(s)\) denotes the total distance covered by all the routes in the entire planning horizon, \(f_{dem}(s)\) represents the demand penalty, \(f_{dur}(s)\) is the route duration penalty, \(f_{wait}(s)\) denotes the total waiting time penalty, \(f_{late}(s)\) is delayed time penalty and \(\alpha , \beta , \gamma , \delta \) are the penalty factors, which are considered to be constants (for details, see Schneider et al [28]).

If the remaining cargo is calculated to be negative at any node, then it implies that the demand of the previous node cannot be fulfilled by the available inventory on that vehicle. This will incur some demand penalty. Considering all routes in all the periods, the overall demand penalty is calculated as

$$\begin{aligned} f_{dem}(s)=\sum _{i,k,t}max\{-y_{ikt},0\}. \end{aligned}$$
(34)

The running time of vehicle k can never exceed a given maximum duration \(D_k\) time units, violating which will incur the duration penalty. The total duration penalty for all the periods can be given by

$$\begin{aligned} f_{dur}(s)=\sum _{k,t}max\{dur_{kt}-D_k,0\} \end{aligned}$$
(35)

where \(dur_{kt}\) denotes the duration of route k in period t.

If a vehicle arrives at a customer before the starting time of service then it will incur a wait penalty, whereas a late penalty will be incurred if it arrives after the end of TW of service; these two can be, respectively, expressed as follows:

$$\begin{aligned}&f_{wait}(s)=\sum _{i,k,t}max\{e_{it}-ar_{ikt},0\} ~\text { and } \end{aligned}$$
(36)
$$\begin{aligned}&f_{late}(s)=\sum _{i,k,t}max\{ar_{ikt}-l_{it},0\}. \end{aligned}$$
(37)

3.3 Proposed algorithm

The proposed MDMPVRP-TW is an NP-hard problem with heterogeneous vehicle, multiple depots and multiple periods, wherein a customer will be served (if served in a period) based on pre-specified allowable combination. Hence this is a very complex problem, and the existing meta-heuristic approaches are not so much suitable to optimize it. Here we propose a hybrid VNS algorithm by combining TS, and call it VNS–TS algorithm. The proposed VNS–TS algorithm strengthens the neighbourhood structure of classical VNS, which will be discussed in next and onward paragraphs. In VNS algorithm, a set of neighbourhood structures \({\mathcal {N}}_{\kappa }(S), \kappa =1,\ldots ,\kappa _{max}\) is generated for the current best solution S. A random point \(S'\) is selected from \({\mathcal {N}}_{\kappa }(S)\) on which local search is applied to obtain a new point \(S''\). If the obtained solution is found to be better than the incumbent, then S is replaced by \(S''\) and the search is thereby continued by setting \(\kappa =1\); otherwise \(\kappa \) is incremented by unity.

The proposed algorithm largely differs from those present in the literature in various aspects, mainly in the procedure of constructing the neighbourhood structures for a given solution. The neighbourhood structure of VNS is modified into a two-step procedure, and then local search is also utilized in the proposed VNS–TS. A brief sketch of the algorithm with detailed characteristics is presented here.

Algorithm: A hybrid meta-heuristic for MDMPVRP-TW

\( S \leftarrow \) Generate an initial solution()

set \( \kappa =1 \)

set \( TC(i)=0 \) for \( i=1,2,\ldots ,n \)

repeat

\(\rightarrow \)      generate \({\mathcal {N}}_{\kappa }(S)\), neighbourhood structure of S

\(\rightarrow \)      update TC(i)

\(\rightarrow \)      randomly select a set \({{{\mathcal {S}}}}\) of \(\theta \) solutions from \({\mathcal {N}}_{\kappa }(S)\)

\(\rightarrow \)      for each solution \( s \in {{\mathcal {S}}} \), generate \( {\mathcal {N}}'(s) \)

\(\rightarrow \)      from each \( {\mathcal {N}}'(s), s \in {\mathcal {S}} \), randomly select a solution \(s'\) and store it in \({\mathcal {S}}'\)

\(\rightarrow \)      apply local search on each \( s' \in {\mathcal {S}}' \)

\(\rightarrow \)      find the best solution \(S''\) from \({\mathcal {S}}'\)

\(\rightarrow \)      if \(f(S'')\) is better than f(S)

\(\rightarrow \)            \( S=S'' \)

\(\rightarrow \)            \( \kappa =1 \)

\(\rightarrow \)      else

\(\rightarrow \)            \( \kappa =\kappa +1 \)

\(\rightarrow \)      endif

until stopping criterion is met

The proposed \( \kappa \)-neighbourhood structure \( {\mathcal{N}}_{\kappa } (S) \) of S is generated as follows. To diversify the search, tabu counter TC(i) is set for each customer i whose value initially is taken to be zero. If a customer i participates in the nbd-structure then TC(i) will be set as \( \omega \), which implies it will not participate in nbd-structure for the next \( \omega \) iterations. Randomly select any \( \kappa \) customers from a set of those having more than one allowable combination and with TC(i) equal to zero. Consider all possible combinations \( \{r_1', r_2',\ldots , r_\kappa '\} \) of their corresponding visit combinations excluding the one \( \{r_1, r_2,\ldots , r_\kappa \} \) present in the current solution \( (\text {i.e., } \exists \text { at\;least\;one }~ i~ \text { for\;which }~ r_i\ne r_i') \). The composition of the neighbourhood structure is based upon the idea presented in the work of Cordeau et al [22]. It constitutes of a set of solutions that can be generated by the application of the following transformation:

  • For each time period l,

  • if \( a_{irl}=1 \) and \( a_{ir'l}=0 \) for every selected customer i in period l, then remove customer i from the routes in period l,

  • if \( a_{irl}=0 \) and \( a_{ir'l}=1 \) for every selected customer i in period l, then insert customer i into a route in period l so as to minimize the total function value as described in (33),

  • where \( a_{irl}=1 \) implies that, for \( r^{th} \) combination, customer i will be served on day l, and will not be served if \( a_{irl}=0 \).

The tabu counter for each of the selected customers is updated and that for each of the remaining nodes not participating in the nbd-structure is set as \( TC(i)=max\{0, TC(i)-1\} \). The new set of solutions obtained at the end of this procedure computed upon all the aforesaid combinations is said to form the neighbourhood structure \({\mathcal {N}}_{\kappa }(S)\) for the current solution S. From \({\mathcal {N}}_{\kappa }(S)\), a random set \({\mathcal {S}}\) of \( \theta \) solutions is chosen. For each solution \( s \in {\mathcal {S}} \), a neighbourhood structure \( {\mathcal {N}}'(s) \) is formulated using 2-opt* operator (Potvin and Rousseau [29]). It operates on two randomly chosen routes by breaking them at certain nodes (say i and j) so as to mutually divert the portions of the routes, i.e. node i of one route gets diverted to connect with the latter part of the second selected route cut at j.

For local search three operators are used, namely, Exchange and Relocate operators (Savelsbergh [30]) and a problem-specific operator DepotInOut. They are briefly discussed here.

Exchange: The exchange operator can be utilized to swap any two customers either within the same (intra) or two different (inter) routes. No depot is allowed to participate in this operation, i.e. swapping of a depot with a customer or any other depot is prohibited.

Relocate: The relocate operator selects a random customer, removes it from the route and then inserts it into either a different position along the same route (intra) or a different route (inter). Just like the exchange operator, the relocate operator also cannot be performed on depots other than the customers.

DepotInOut: This operator finds out the first customer node at which remaining cargo becomes negative and thereby inserts a depot along the route before reaching that customer so as to minimize f(s) . If even after removing an intermediate depot from a route the remaining cargo in a vehicle is found to be sufficient to serve all the upcoming customers along the route without the incur of any demand penalty, then this operator removes the said depot.

For better exploration of the solution space the dynamic diversification process was adopted for the penalty factor as introduced by Cordeau et al [1], which was further modified by Schneider et al [28]. The diversification method involves updating the initial penalty factors \( (\alpha _0, \beta _0, \gamma _0, \delta _0) \) with the help of a penalty updating factor \( \lambda \) within a permissible range of their corresponding minimum \( (\alpha _{min}, \beta _{min}, \gamma _{min}, \delta _{min}) \) and maximum \( (\alpha _{max}, \beta _{max}, \gamma _{max}, \delta _{max}) \) values.

4 Computational results

The proposed MDMPVRP-TW and hybrid VNS–TS algorithms are here tested on a set of 20 benchmark instances varying from small to large scale as presented in table 1. All the test instances are taken from Cordeau et al [1] after some modifications. We change the co-ordinates of the customer nodes, service time and demand parameters, and install replenishment depots randomly. All data are created in a way so that the total demand of all the customers in all the periods is greater than the total capacity of all the vehicles considered over all the periods. Therefore, the vehicles have to visit intermediate depots in order to fulfil the complete demand of the customers. In table 1, \( n= \) the number of customers, \( d= \) number of replenishment depots, \( m= \) number of available vehicles, \( p= \) total number of periods, \( \sum Q_k= \) fleet capacity and \( \sum q_{it}= \) total demand of all the customers for all the periods.

Table 1 Details of instances.
Full size table

The parameters involved in the proposed algorithm need to be empirically selected with utmost care. This is because the choice of these parameters has a significant effect on the execution of the algorithm. The exploration and exploitation rates are observed to be influenced greatly by the selection of the parameters. Table 2 presents the parameter values set best attained for the proposed algorithm, which is obtained by trial and error method. Although the provided set need not be optimal, the algorithm is observed to perform much better with it as compared with other parameter values.

Table 2 Parameter set.
Full size table

4.1 Discussion on numerical examples

In this section, a complete illustration of the obtained numerical results for the formulated MDMPVRP-TW as well as the proposed hybrid algorithm is presented through small as well as large instances discussed earlier. All the computational experiments are performed on a DELL PC (Intel Core i5 3.2 GHz) with 4 GB RAM and Windows 7 Operating System. The program codes are written in MATLAB R2017a.

In order to clearly delineate the vehicle route-schedule over the periods, a detailed solution of the first instance with 48 customer nodes is presented in table 3 and figure 1. The first column of the table shows the route number expressed in the form of an ordered pair, wherein the first element indicates the period number and the second one is the vehicle number. From this table, it can be clearly interpreted that every customer node from 1 to 12 is served in all the periods; each of customers 13 to 24 is served twice in the time horizon whereas each of the customers 25 to 48 is served only once. All the routes except (2, 2) and (3, 2) are observed to have demand that is higher than the vehicle capacity, thereby forcing them to visit an intermediate replenishment depot along their routes. Also every vehicle starts from the depot where it ends in the previous period. The scheduling plan of each vehicle over the periods is depicted in figure 1.

Table 3 Optimal routes of vehicles for instance of 48 customers.
Full size table
Figure 1
figure 1

Optimal routes of vehicles over the periods.

Full size image

We have tried existing VNS algorithms to optimize the proposed MDMPVRP-TW but, perhaps due to high complexity, none of the algorithms got any success. However, performance of the hybrid VNS–TS algorithm with respect to the operators exchange and relocate is tested in each of the three ways: firstly, without the exchange operator; secondly, without the relocate operator and finally with both the exchange and relocate operators. Comparisons between the developed algorithm and the well-known PSO are also studied. The parameters involved in the proposed algorithm contain several random components as well. Therefore for more accurate results, the algorithm is run for 10 times for 100 iterations in each run. The best obtained results of the conducted comparative study are then reported partly in table 4 and partly in table 5.

Table 4 Comparisons between the operators and PSO.
Full size table
Table 5 Comparisons between the operators and PSO.
Full size table

Comparisons from the tabulated results indicate that the best solution with minimum distance is obtained for the third case when the algorithm is tested with both the relocate and exchange operators in comparison with the other two situations. While being compared with PSO also, better outcomes are observed for the case of simultaneous incorporation of relocate and exchange operators in our proposed methodology.

5 Conclusion and future work

The aim of this paper is two-fold. First, to develop a more practical VRP that is mostly used in real life such as school bus routing, grocery distribution, oil and petroleum delivery, repairmen scheduling, etc. In this process, we propose a multi-depot multi-period vehicle routing problem with time window (MDMPVRP-TW) by considering allowable combination. A particular customer may appear along several routes and can be served by many vehicles over the period. However, all these routes and vehicle may not be feasible for the customer. Out of these routes and vehicles, we first select the feasible one and then make all possible combinations. Our objective is to find the most suitable combination for each customer in such a way that the total traversed distance or cost is minimum. The second objective of this paper is to propose a hybrid VNS–TS algorithm to optimize the mathematical model of MDMPVRP-TW. In this process, three operators for hybrid VNS–TS algorithm are considered in order to construct the neighbourhood structures for a solution. In order to find the initial solution, TS is modified and used. The efficiency and robustness are believed to be the strengths of the proposed algorithm. It is observed from the experimental results that the algorithm holds good for the proposed problem and is found to be preferably stable in obtaining the optimal solution.

Both the proposed model and algorithm can be further extended in several directions. One possible extension is that instead of a single visit to a customer by a vehicle within a period, multiple visits can be considered. Furthermore, soft TW in place of hard TW can also be considered as an extension of this work that will further strengthen the model because it will tackle an even more realistic situation.