An adaptive VNS algorithm for vehicle routing problems with intermediate stops

Abstract

There are numerous practical vehicle routing applications in which vehicles have to stop at certain facilities along their routes to be able to continue their service. At these stops, the vehicles replenish or unload their cargo or they stop to refuel. In this paper, we study the vehicle routing problem with intermediate stops (VRPIS), which considers stopping requirements at intermediate facilities. Service times occur at these stops and may depend on the load level or fuel level on arrival. This is incorporated into the routing model to respect route duration constraints. We develop an adaptive variable neighborhood search (AVNS) to solve the VRPIS. The adaptive mechanism guides the shaking step of the AVNS by favoring the route and vertex selection methods according to their success within the search. The performance of the AVNS is demonstrated on test instances for VRPIS variants available in the literature. Furthermore, we conduct tests on newly generated instances of the electric vehicle routing problem with recharging facilities, which can also be modeled as VRPIS variant. In this problem, battery electric vehicles need to recharge their battery en route at respective recharging facilities.

1 Introduction

Intermediate stops have to be considered in many practical vehicle routing applications, e.g., for (1) replenishment of the goods to be delivered, (2) refueling (or recharging in case of battery electric vehicles), or (3) unloading of collected goods or disposal of waste. These stops differ from regular customer stops in two aspects: first, they are optional, and second, they depend on the state of the vehicle with respect to load and fuel level (which decides the latest possible moment at which an intermediate stop has to occur). Contrary to optional customer stops, e.g., in vehicle routing problems with profits (Archetti et al. 2013), intermediate stops are not directly related to customer service or profit maximization, but aim at keeping the vehicle operational.

As mentioned above, major applications of intermediate stops are good replenishment, refueling, and waste disposal, which are detailed in the following. Intermediate replenishment stops are used in distribution systems with several facilities storing the products to be delivered (Angelelli and Speranza 2002; Crevier et al. 2007; Tarantilis et al. 2008). The aim is to avoid returning to a central depot to reload the delivery vehicle. Concrete applications can be found in the distribution of heating oil (Prescott-Gagnon et al. 2012), road maintenance (Amaya et al. 2007) or in city logistics, where city freighters may visit satellite facilities to be replenished (Crainic et al. 2009).

Intermediate stops for unloading operations are common in waste collection or snow ploughing. Here, intermediate disposal sites need to be visited, at the latest, when the maximal capacity of the vehicle is reached (see, e.g, Kim et al. 2006; Benjamin and Beasley 2010).

Intermediate refueling stops occur in several practical applications. For example, some companies keep contracts with gas station chains to get special rates at the respective stations, which makes it profitable to consider refueling stops in the route planning. Without such contracts, this is not the case because the network of gas stations is generally quite dense in developed countries. The refueling topic gains further relevance by the strong growth in alternative fuels, namely biodiesel, ethanol, hydrogen, methanol, natural gas or propane, for which only a sparse infrastructure is existent. Finally, battery electric vehicles (BEVs) need to stop to recharge during longer routes due to their limited driving range (Conrad and Figliozzi 2011; Schneider et al. 2014). BEV technologies have recently gained importance due to city logistics concepts, which aim at reducing the negative external effects of urban freight transportation. In this context, BEVs seem to be a very good choice as they have no local emissions, operate very efficiently at the stop-and-go level and have low noise levels (Wang and Lin 2013). Moreover, BEVs are defined to be emission free by EU regulation No 510/2011 and are, therefore, a major means to comply with laws and regulations on emissions.

This paper is the first to introduce the vehicle routing problem with intermediate stops (VRPIS), a routing model that considers visits to intermediate facilities to keep vehicles operational. The necessity to visit an intermediate facility depends on the fuel and/or the load level of a delivery vehicle. The time spent at a facility is defined as a function of the fuel and load level on arrival. By abstracting from the actual purpose of the intermediate stop, be it for replenishment, refueling or disposal, our problem definition comprises several problems with specific applications proposed in the literature. The objective of VRPIS is to minimize the total costs composed of travel costs and fixed costs for the deployment of vehicles.

VRPIS extends the NP-hard capacitated VRP (CVRP) by several combinatorial aspects, which makes exact methods unsuitable for solving large problem instances in fast computation time. We develop a heuristic solution approach, namely an adaptive variable neighborhood search (AVNS), which combines ideas of VNS (Hansen and Mladenović 2001) and adaptive large neighborhood search [ALNS, see (Pisinger and Ropke 2007)]. This method has been successfully applied to single- and multi-depot routing problems [see (Stenger et al. 2013a, b)]. To assess the performance of our AVNS, we perform computational studies on benchmark instances of VRPIS variants previously studied in the literature.

Moreover, we investigate the electric VRP with recharging facilities (EVRPRF) as a special case of VRPIS. EVRPRF models the routing decision of logistics service providers employing BEVs. The driving range of a vehicle is restricted by the maximum battery capacity and a distance-related energy consumption along the route, which determines the battery charge. We simplify several real-world characteristics and do not consider the influence of vehicle load, vehicle speed and grades on energy consumption. The battery can be recharged at any of the available recharging facilities. For this problem, we generate a set of small benchmark instances, which are used to assess the solution quality of our method in comparison to the commercial solver CPLEX. In addition, detailed results for a set of large instances are provided.

This paper is organized as follows. In Sect. 2, we review the related literature. Section 3 presents the problem description and the mathematical models of VRPIS and of the special case EVRPRF. The AVNS solution method is detailed in Sect. 4. Computational tests to assess the performance of the proposed method are described in Sect. 5. The paper is summarized and concluded in Sect. 6.

2 Literature review

This section gives short reviews of the following strands of literature related to VRPIS and EVRPRF: (1) VRP with intermediate replenishment or disposal stops, (2) VRP with refueling or recharging stops, and (3) refueling problems occurring in other application areas.

Crevier et al. (2007) introduce the multi-depot VRP with inter-depot routes (MDVRPI), which considers intermediate depots at which vehicles can be replenished with goods during the course of a route. The authors develop a heuristic procedure that combines ideas from adaptive memory programming (Rochat and Taillard 1995), tabu search (TS) and integer programming. Although the multi-depot case is described, all proposed benchmark instances consider only one depot at which the vehicle fleet is stationed. Therefore, Tarantilis et al. (2008) rename the problem to VRP with intermediate replenishment facilities (VRPIRF), and we adopt this acronym for the remainder of this paper. They propose a hybrid guided local search heuristic that follows a three-step procedure. First, an initial solution is constructed by means of a cost-savings heuristics. Second, a VNS algorithm is applied using a TS in the local search phase. Third, the solution is further improved by means of a guided local search.

Prescott-Gagnon et al. (2012) propose three metaheuristics to solve a VRP arising in heating oil distribution, considering intra-route replenishments, heterogeneous vehicles, optional customer visits and time windows. The authors design a TS, an LNS based on the TS and a column generation heuristic and report computational results obtained on test instances derived from a real-world dataset. Other problems similar to VRPIRF arise in the collection of waste (see, e.g., Angelelli and Speranza 2002; Kim et al. 2006; Coene et al. 2010; Benjamin and Beasley 2010), in snow clearance (Perrier et al. 2007), or in road maintenance and marking (Amaya et al. 2007; Salazar-Aguilar et al. 2013). A recent review of the literature on waste collection can be found in Beliën et al. (2014).

Hemmelmayr et al. (2013) study the periodic vehicle routing problem with intermediate facilities (PVRP-IF) in the context of waste collection. The authors introduce a hybrid solution approach consisting of a VNS using dynamic programming to insert intermediate facilities. The solution procedure is also applied to the VRPIRF problem instances provided by Crevier et al. (2007) and Tarantilis et al. (2008) and is able to outperform both approaches.

The literature on routing problems with refueling stops is still relatively scarce. Conrad and Figliozzi (2011) present the recharging VRP, in which vehicles with limited range have the possibility of recharging en route at certain customer locations. The recharging time is assumed to be fixed. The impact of maximum driving range, recharging time and time window existence is studied using a selection of the VRP with time windows (VRPTW) instances of Solomon (1987). Moreover, bounds are formulated to predict average tour lengths. Erdoğan and Miller-Hooks (2012) propose the green VRP (G-VRP), which considers a limited fuel capacity of the vehicles and the possibility of refueling at facilities along the route with a fixed refueling time. Neither capacity restrictions nor time window constraints are considered. The authors propose two heuristics to solve G-VRP. The first is a modified Clarke and Wright savings algorithm (MCWS) which creates routes by establishing feasibility through the insertion of refueling facilities, merging feasible routes according to savings and removing redundant facilities. The second heuristic is a density-based clustering algorithm (DBCA) designed as cluster-first and route-second approach.

Schneider et al. (2014) develop a hybrid heuristic approach that combines VNS with TS to address the electric vehicle routing problem with time windows and recharging stations (E-VRPTW). Contrary to the EVRPRF studied in this paper, their E-VRPTW includes time windows, but features no maximal route duration constraints. Moreover, their objective is hierarchical and inspired by the objective function used in heuristic methods for the VRPTW: they first minimize the number of employed vehicles and only minimize traveled distance second, whereas we follow the objective of minimizing total costs composed of travel costs and fixed vehicle costs. Their VNS/TS is able to significantly improve on the results of Erdoğan and Miller-Hooks (2012) on the G-VRP instances and achieves convincing results on the VRPIRF instances, although the method is not specifically designed for this type of problem.

Refueling problems are also investigated in other application areas, e.g., the refueling of aircraft or locomotives. In Barnes et al. (2004), tanker aircraft stationed at several bases have to be assigned to receiver aircraft to perform refueling in midair. Raviv and Kaspi (2012) deal with the optimal refueling schedule of locomotives pulling trains, i.e., the determination of the yards at which the locomotives have to be refueled.

3 Problem definition

This section presents a mixed-integer program of the VRPIS (Sect. 3.1) and derives the formulation of the special case EVRPRF (Sect. 3.2).

3.1 The vehicle routing problem with intermediate stops (VRPIS)

We start with the introduction of some necessary notation. Let $C = \{1, \ldots , n\}$ denote the set of $n$ customers and let $F$ denote the set of facilities. The set $F$ itself comprises the set of refueling facilities $F_F$, the set of replenishment or unloading/disposal facilities (in the following denoted as loading facilities) $F_L$, and the set $F_{ FL }$ of facilities where both refueling and loading are possible (from now on referred to as combined facilities), i.e., $F = F_F \cup F_L \cup F_{ FL }$. We use a set of dummy vertices $F'$ to allow several visits to the facilities in $F$ (see, e.g., Bard et al. 1998; Schneider et al. 2014). Further, let vertices 0 and $n+1$ denote instances of the same depot representing the start and end of each vehicle route. To indicate which depot instances are included in a fictive set $X$, the respective depot instances are used as indices, i.e., $X_0 = X \cup \{0\}$, $X_{n+1} = X \cup \{n+1\}$ and $X_{0,n+1} = X \cup \{0\} \cup \{n+1\}$. Finally, let $V' = C \cup F'$ denote the set of all customers and visits to facilities.

Then, VRPIS can be defined on the complete directed graph $G = (V'_{0,n+1}, A)$ with the set of arcs $A = \{(i,j): i, j \in V'_{0,n+1}, i \ne j\}$. Arcs $(i,j) \in A$ are associated with a cost $c_{ij}$, a distance $d_{ij}$ and a travel time $t_{ ij }$. A homogeneous fleet of $m$ vehicles with load capacity $q$, fuel capacity $p$ and fixed costs per use $c^{ fix }$ is stationed at the depot. Fuel capacity is expressed in distance units and denotes the distance that can be traveled with maximum fuel level.

Each customer $i \in C$ has a positive demand $u_i$ and service time $t^s_i$. Each facility visit $j \in F'$ is associated with a docking time $t^d_j$, which marks the time span between the arrival at the facility and the beginning of the actual refueling and/or loading process. The time span for the refueling and loading process is determined by functions $\Phi ^f(f_j)$ and $\Phi ^l(l_j)$, respectively. It may depend on the fuel level $f_j$ (the cargo level $l_j$) on arrival at the facility. Visiting a facility $j \in F_F$ completely refills the fuel tank of a vehicle and vehicles are fully replenished or unloaded at facilities in $F_L$. For combined facilities, we assume that vehicles are fully loaded and are simultaneously refueled during the time span occupied by the loading process. The increase in fuel during that time span is given by the function $\Theta (l_j)$, which depends on the loading time and thus on the load level $l_j$ on arrival at the facility. A refueling process at a combined facility that takes longer than the loading time is modeled by a visit to a refueling facility in $F_F$ with the same location as the combined facility. Each facility is assumed to have an unlimited fuel and cargo capacity, respectively, and can be simultaneously used by any number of vehicles. This assumption seems adequate for many real-world scenarios, but clearly represents a simplification for scenarios in which capacity and loading possibilities are constrained.

To represent working hour restrictions of real-world applications, we assume that the arrival time of all vehicles at depot instance $n+1$ may not exceed the maximum route duration $t^{ max }$. The following variables are used in the model: $a_j$ specifies the time on arrival at vertex $j$, $f_j$ the fuel level, and $l_j$ the load level. Binary decision variables $x_{ij}$ take value 1 if vertex $j$ is visited after vertex $i$ and 0 otherwise. Thus, the mixed-integer program of VRPIS is as follows (Table 1 summarizes the notation):

Table 1 Parameters and decision variables of the VRPIS model

$$\begin{aligned}&\min \sum \limits _{i \in V'_0} \sum \limits _{j \in V_{n+1}', i \ne j} c_{ij}x_{ij} + \sum \limits _{j \in V'} c^{ fix }x_{ 0j } \end{aligned}$$

(1)

$$\begin{aligned}&\sum \limits _{i \in V'_0, i \ne j} x_{ij} = 1 \qquad&\forall j \in C \end{aligned}$$

(2)

$$\begin{aligned}&\sum \limits _{i \in V'_0, i \ne j} x_{ij} \le 1 \qquad&\forall j \in F' \end{aligned}$$

(3)

$$\begin{aligned}&\sum \limits _{j \in V'} x_{0j} \le m&\end{aligned}$$

(4)

$$\begin{aligned}&\sum \limits _{i \in V'_0, i \ne j} x_{ij} - \sum \limits _{i \in V'_{n+1}, i \ne j} x_{ji} = 0 \qquad&\forall j \in V' \end{aligned}$$

(5)

$$\begin{aligned}&0 \le a_i \le t^{ max }&\forall i \in V'_{0,n+1} \end{aligned}$$

(6)

$$\begin{aligned}&a_i + (t_{ij} + t^s_i) x_{ij} - t^{ max } (1 - x_{ij}) \le a_j&\forall i \in C \cup \{0\}, j \in V'_{n+1}, i \ne j \end{aligned}$$

(7)

$$\begin{aligned}&a_i + (t_{ij} + t^d_i)x_{ij} + \Phi ^f(f_i) - t^{ max } (1 - x_{ij}) \le a_j&\forall i \in F'_F, j \in V'_{n+1}, i \ne j \end{aligned}$$

(8)

$$\begin{aligned}&a_i + (t_{ij} + t^d_i)x_{ij} + \Phi ^l(l_i) - t^{ max } (1 - x_{ij}) \le a_j&\forall i \in F'_L \cup F'_ FL , j \in V'_{n+1}, i \ne j \end{aligned}$$

(9)

$$\begin{aligned}&0 \le f_j \le f_i - d_{ij} x_{ij} + p(1 - x_{ij}) \qquad&\forall i \in C \cup F'_L, j \in V'_{n+1}, i \ne j \end{aligned}$$

(10)

$$\begin{aligned}&0 \le f_j \le p - d_{ij} x_{ij} \qquad&\forall i \in F'_F \cup \{0\}, j \in V'_{n+1}, i \ne j \end{aligned}$$

(11)

$$\begin{aligned}&0 \le f_j \le f_i + \Theta (l_i) - d_{ij}x_{ij} + p(1 - x_{ij}) \qquad&\forall i \in F'_{ FL }, j \in V'_{n+1}, i \ne j \end{aligned}$$

(12)

$$\begin{aligned}&f_i + \Theta (l_i) \le p \qquad&\forall i \in F'_{ FL } \end{aligned}$$

(13)

$$\begin{aligned}&0 \le l_j \le l_i - u_i x_{ij} + q(1 - x_{ij}) \qquad&\forall i \in C \cup F'_F, j \in V'_ n+1 , i \ne j \end{aligned}$$

(14)

$$\begin{aligned}&0 \le l_j \le q - u_i x_{ij} \qquad&\forall i \in \{0\} \cup F'_L \cup F'_{ FL }, j \in V'_{n+1}, i \ne j \qquad \end{aligned}$$

(15)

$$\begin{aligned}&x_{ij} \in \{0,1\} \qquad&\forall i \in V'_0,j \in V'_{n+1},i \ne j \end{aligned}$$

(16)

The goal of the VRPIS is to minimize the sum of the total travel cost and the fixed vehicle cost, expressed by the objective function (1). Constraints (2) ensure that every customer must be visited, while optional intermediate stops are ensured by Constraints (3). Constraints (4) guarantee that the number of routes does not exceed the number of available vehicles. Flow conservation is given by Constraints (5). Constraints (6) limit the arrival time at each vertex to the maximum route duration. Time feasibility for arcs leaving customers or the depot is defined by Constraints (7). The same is ensured for arcs leaving refueling facilities and loading facilities in Constraints (8) and (9). Constraints (10) control the fuel feasibility for arcs leaving customers or loading facilities and Constraints (11) guarantee that a refueling facility is left in a completely refueled state. The fuel increase during loading at combined facilities is defined in Constraints (12). Constraints (13) guarantee that no refueling beyond the maximal fuel capacity is possible at combined facilities. Constraints (14) control the load feasibility for arcs leaving customers or refueling facilities. Constraints (15) ensure that vehicles leave loading facilities and the depot in a fully loaded state. Binary decision variables are defined in Constraints (16).

3.2 New special VRPIS case: the electric vehicle routing problem with recharging facilities (EVRPRF)

As described above, we investigate the EVRPRF as a special case of the VRPIS. The VRPIS model is transformed into a formulation of the EVRPRF as follows:

• 1. No intermediate cargo loading takes place. Therefore, no loading facilities are present in the EVRPRF and sets $F_L$ and $F_{ FL }$ are empty and Constraints (9), (12) and (13) can be neglected. To allow for recharging at the depot, dummy instances of 0 are now contained in the set $F'_F.$

• 2. We assume a linear recharging process of the vehicle battery, depending on a given average recharging speed $g$. Since the fuel capacity is expressed as the maximum travel range without refueling, $g$ describes the increase of range per time unit. Thus, the function for the refueling time is defined as: $\Phi ^f(f_i) = \frac{p - f_i}{g}.$

3.3 Special cases from the literature: G-VRP and VRPIRF

To assess the performance of our AVNS, we conduct tests on instances of the special VRPIS cases G-VRP and VRPIRF and compare our results to those presented in the literature (see Sect. 5).

G-VRP can be addressed as special case of VRPIS as follows:

• As no loading at intermediate facilities is considered in G-VRP, all related constraints of VRPIS are omitted.

• $c^{ fix }$ is set to zero because no vehicle cost is considered in G-VRP.

• The refueling time $\Phi ^f(f_i)$ is set to zero and docking time $t^d_i$ is set to the fixed service time of the G-VRP instances.

VRPIRF can be addressed as special case of VRPIS as follows:

• Since the VRPIRF instances do not consider refueling possibilities, all refueling-related constraints of VRPIS are omitted.

• Loading time $\Phi ^l(l_i)$ is set to zero because only a fixed docking time $t^d_i$ occurs when visiting a loading facility.

• The maximum route duration $t^\mathrm{{max}}$ is reduced by $t^d_i$ to account for a docking operation at the depot at the end of a route, which is considered in the VRPIRF.

• No vehicle deployment costs are considered in the VRPIRF, so $c^{ fix }$ is set to zero.

Table 2 clarifies the relation between VRPIS and the special cases considered in this paper by comparing the properties of each problem.

Table 2 Relation between VRPIS, the introduced special case EVRPRF as well as the special cases from the literature VRPIRF and G-VRP

4 An adaptive variable neighborhood search algorithm for the VRPIS

In this section, we describe in detail our AVNS algorithm for solving VRPIS. AVNS follows the VNS diversification paradigm of searching in increasingly large neighborhoods [for a detailed introduction to standard VNS, see (Hansen and Mladenović 2001)]. However, routes and vertices involved in the shaking step of AVNS are not selected entirely at random, but are determined by problem-specific rules and the past search performance of these rules. AVNS has previously provided promising results for MDVRP, VRP with private fleet and common carriers (VRPPC), multi-depot VRPPC (Stenger et al. 2013a) and the prize collecting VRP with non-linear cost (Stenger et al. 2013b).

The choice of AVNS is motivated by two factors. First, the high complexity of VRPIS makes it necessary to use an algorithm with strong diversification possibilities. Pretests have shown that classical local-search-based algorithms, like TS, often get stuck in local traps from which they are not able to escape. By contrast, the shaking step of our AVNS modifies up to four routes and moves sequences of up to six nodes in one iteration, which proved to be of vital importance to find promising solutions. Moreover, VNS algorithms presented in the literature have previously shown convincing performance on VRPs with intermediate stops [see, e.g., (Tarantilis et al. 2008)]. Second, to ensure acceptable runtimes on large problem instances, a high efficiency of the search is required. The adaptive mechanism of AVNS takes into account the problem-specific characteristics of VRPIS and adapts based on the recent search performance. Thus, it efficiently guides the search to improving solutions. To sum up, combining the strong diversification of VNS with an adaptive mechanism results in a highly efficient heuristic, characterized by short computing times and high-quality results.

A pseudocode overview of the AVNS is given in Fig. 1. First, the set of neighborhood structures {$N_\kappa \ | \ \kappa = 1, \ldots , \kappa ^\mathrm{{max}}$} is defined. Next, an initial solution $S$ is constructed by means of a modified version of the savings algorithm by Clarke and Wright (1964), which considers the insertion of intermediate stops (Sect. 4.1), and the solution is subsequently improved by a local search (see Sect. 4.3).

Fig. 1

Pseudocode of the AVNS heuristic for solving VRPIS

In the AVNS component, a guided shaking step is used to diversify the search, producing a random solution $S'$ within the $\kappa$-th neighborhood of $S$ (Sect. 4.2.1). The adaptive mechanism is characterized by problem-specific selection methods for the routes and vertices to be shaken instead of an entirely random selection. Besides methods which have proven their effectiveness in previous works, we design specific methods which take the characteristics of intermediate stops into account (Sect.  4.2.2). Each of the selection methods is chosen according to a probability, which is dynamically updated during the search depending on the performance of the method (Sect. 4.2.3).

Subsequently, a greedy local search procedure is applied to obtain the local optimum $S''$ (Sect. 4.3). In this step, classical operators as well as operators which are able to rearrange intermediate stops are used. If $S''$ is accepted, it replaces $S$ and $\kappa$ is reset to one. Otherwise, $S''$ is discarded and $\kappa$ is increased by one, i.e, the next neighborhood is selected. We reset to the overall best solution after a certain number of iterations without improvement. The search is stopped after a given number of iterations without improvement of the best solution.

As described above, we adapt the algorithmic framework of AVNS to the specifics of VRPIS by incorporating problem-specific knowledge into the selection methods of our adaptive component and into the local search component. Numerical tests have proven the positive effects of these novel methods on the solution quality and runtime of our algorithm (see Appendix for details).

4.1 Initialization with modified savings algorithm

A modification of the savings algorithm, introduced by Clarke and Wright (1964), is used to quickly generate initial vehicle routes that include intermediate stops. We allow the initial solution to be infeasible with respect to fuel, load or duration constraints. The steps of our modified Savings Algorithm are the following:

• 1. Generate back-and-forth tours for all customers. If such a tour is already infeasible concerning fuel, perform the cost-optimal insertion of a refueling facility into the respective route (see Sect. 4.3 for details).

• 2. Evaluate potential cost savings for merging each pair of routes and sort the merge moves in decreasing order.

• 3. Out of the remaining merge moves, select the two routes with highest cost savings and merge them if the maximum route duration is not exceeded. If no merge with positive cost savings exists, stop.

• 4. Evaluate the resulting route:

  • (a) If fuel or load violations emerge in the resulting route, try to resolve them by adding intermediate facilities at the optimal position.

  • (b) If the facility insertion leads to a duration violation, cancel the previous merging and continue with Step 3.

  • (c) If the resulting route starts or ends with an intermediate facility, i.e., no merging according to customer-related cost savings can be performed at this position, try to connect the facility with one of the remaining routes such that the cost increase is minimized and all constraints are still met (see Fig. 2).

• 5. Continue with Step 3.

Fig. 2

Merging of routes that start or end with an intermediate facility. Removed arcs are shown with dashed lines, inserted arcs with dotted lines

The resulting number of routes may exceed the number of available vehicles. In this case, the route with the smallest cumulated customer demand is dissolved and its customers are inserted into the remaining routes at the cost-optimal position. Load capacity, fuel capacity and duration violations are handled by means of a penalizing cost function, see Sect. 4.4. The process of dissolving routes is repeated until the required number of vehicles is reached. Subsequently, the solution is improved by a local search step (see Sect. 4.3).

4.2 The adaptive shaking

In the shaking step of our AVNS, new solutions are generated according to predefined neighborhood structures (Sect. 4.2.1). Problem-specific methods are used for the selection of the routes and vertices to be involved in the shaking (Sect. 4.2.2). The algorithm guides the shaking step by adapting the selection probabilities of these methods according to their previous performance during the search (Sect. 4.2.3).

4.2.1 Shaking neighborhoods

Similar to Stenger et al. (2013a), two operators are employed to generate neighboring solutions: a sequence relocation and a cyclic exchange operator, originally introduced by Thompson and Orlin (1989). The cyclic exchange moves vertices between routes in a cyclic fashion. It is characterized by two parameters: the number of routes involved $\Omega$ and the maximum number of vertices to be exchanged $\Gamma ^\mathrm{{max}}.$

For each route $k$ the vertex sequence $\Psi ^k_{{j_k},{\Gamma _k}}$ with start vertex $j_k$ and length $\Gamma _k$ is transferred to route $k+1$ at the former position of sequence $\Psi ^{k+1}_{{j_{k+1}},{\Gamma _{k+1}}}$. In Figure 3, the cyclic exchange operator is depicted with $\Omega = 3$ routes, exchanging $\Gamma _1 = 1$, $\Gamma _2 = 2$ and $\Gamma _3 = 2$ vertices. Note that, if the total number of existing routes gets below the number of routes to cycle, $\Omega$ is reduced accordingly. Similarly, $\Gamma _k$ has to be adjusted if it exceeds the number of vertices of route $k$, denoted with $|V_k|.$

Fig. 3

Example of a cyclic exchange with three routes

Sequence relocation represents a restriction of the cyclic exchange operator. A vertex sequence is relocated from one route to another, and the latter keeps all of its former vertices. Thus, $\Gamma ^\mathrm{{max}} = 0$ applies for the second route.

Table 3 shows the neighborhood structures employed within the search. After six sequence relocation neighborhoods the search continues with 18 cyclic exchange neighborhoods, considering $\Omega = 2$ to $\Omega = 4$ routes between which up to $\Gamma ^\mathrm{{max}} = 6$ vertices can be transferred. Sequence lengths with up to $\Gamma ^\mathrm{{max}} = 4$ vertices are randomly chosen within the interval $[0, \min (\Gamma ^\mathrm{{max}}, |V_k|)]$. Sequence lengths with more than four customers are defined to be fixed.

4.2.2 Selection methods

Instead of determining the routes and vertices to be involved in the shaking entirely at random, the AVNS algorithm guides the shaking step to a certain extent. For this purpose, several methods are implemented which bias the route and vertex sequence selection. On the one hand, we use methods which have proven their effectiveness in previous works on routing problems. On the other hand, we design problem-specific methods which take into account the new characteristics of intermediate stops, e.g., the associated detours required. Each of the methods is chosen with a certain probability, which is dynamically updated during the search depending on the success of the method in former iterations. The selection methods and the adaptive mechanism are detailed in the following.

Route selection The first of the $\Omega _{\kappa }$ routes of the current neighborhood $N_{\kappa }$ is chosen according to one of the following five route selection methods:

• 1. Random The probability of being selected is equal for every route.

• 2. Route length The probability of a route for being selected is proportional to the associated travel distance. The intention is to remove vertices from long routes and reinsert them into shorter routes to reduce the total costs.

• 3. Route length per demand unit The selection probability of a route is proportional to the relation of the total distance and the cumulated demand of a route. This criterion shall lead to an improvement of inefficient routes.

• 4. Facility density The probability is proportional to the ratio of the number of intermediate stops to the number of customers within a route. The goal is to favor routes that possibly contain redundant facility visits.

• 5. Facility detour The probability is proportional to the total detour resulting from intermediate stops. This is intended to reduce the associated detours and thus the overall costs.

Table 3 Neighborhood structures examined within the shaking step of the AVNS

After choosing the first route by means of one of the procedures above, the other routes to be involved in the shaking are iteratively determined as follows: the next route is randomly chosen from the set of all remaining routes that are spatially closer than a predefined threshold $d^\mathrm{{max}}$ to the previously selected route [cp. (Stenger et al. 2013a)].

Vertex sequence selection Once the routes to be involved are determined, the vertex sequences to be removed from each route must be identified. The following three methods are used for this selection decision:

• 1. Random Each vertex sequence is chosen with the same probability.

• 2. Distance to next route The probability of selecting a vertex sequence is inversely proportional to the distance of the sequence to the route into which it will be inserted. This is measured by the sum of the vertex distances to the center of gravity of the target route.

• 3. Distance to neighboring vertices The probability of selecting a sequence is proportional to the distance of the sequence to the surrounding vertices. It is given by the sum of the distance between the first vertex and its predecessor and the distance between the last vertex and its successor. Removing a sequence which is far apart from the other vertices of the route can reduce the total costs.

4.2.3 Adaptive mechanism

At each shaking step, the choice of the route and vertex selection methods is based on probabilities. Each method is assigned the same probability at the beginning of the search. The probability of each method is then dynamically updated in the course of the search depending on its success in improving the current solution. To select the methods, we use the roulette wheel selection procedure as proposed by Pisinger and Ropke (2007) for ALNS. Given $h$ selection methods, each method $s$ is assigned a weight $w_s$. The probability of selecting method $s$ is then defined by $w_s / \sum _{i=1}^{h} w_i$. After $\gamma$ AVNS iterations, the weight of each method is updated based on its success during these iterations. The performance of a method is measured by a scoring system. A score of nine is added to the total score of a method whenever it achieved a new overall best solution, a score of three if the current solution was improved and a score of one if the solution is worse than the current one, but accepted according to the acceptance criterion. If $\phi _s$ denotes the current score of method $s$ and $\chi _s$ the number of applications of the method since the last weight update, then the new weight is calculated as $w_s = w_s(1-\rho )+\rho \frac{\phi _s}{\chi _s}$. The system parameter $\rho \in [0,1]$ allows to control to what extent the past value of the weight influences the new one. The values $\phi _s$ and $\chi _s$ are reset to zero after each update.

4.3 Local search

The solution generated within the shaking step is subsequently improved by several greedy local search procedures. All operators are implemented such that the first improving move is accepted.

First, potential fuel or load violations within a route are handled by adding visits to intermediate facilities. If the distance between two consecutive refueling facility visits exceeds the fuel capacity of the vehicle, the fuel level drops below zero at a certain point. Hence, at least one refueling facility must be visited before this point. Let $\phi$ denote the position of the last visited refueling facility and $\sigma$ that of the last vertex reachable from there. The best insertion position is, therefore, determined within the path $\{\phi +1, \ldots , \sigma +1\}$. For each possible position, the cost for inserting the closest refueling facility $i \in F_F$ is calculated. The insertion with the lowest cost increase is performed, but in this step insertions leading to feasible solutions are always preferred to infeasible solutions. The insertion of loading facilities is carried out in analogous fashion.

In a second step, we aim to improve the routing by means of the following operators, which are applied in random order. The 2-opt operator replaces two edges by two new ones (Lin 1965). A restricted variant of the Or-Opt exchange (Or 1976) replaces three existing edges by three new ones such that a sequence of three vertices is relocated (Stenger et al. 2013a). The intra-route relocate operator moves a customer to a different position within a route (Savelsbergh 1992). This operator is also defined for moving facilities. Finally, a facility replacement operator evaluates for each facility visit of each route whether replacing the facility visit with a visit to a different facility decreases the routing costs.

This block is followed by an application of a facility removal operator, which aims at removing redundant facility visits. In a final step, we apply two inter-route operators. The inter-route relocate operator moves a customer from its current route to another, and the exchange operator interchanges two customers between two routes (Savelsbergh 1992).

4.4 Penalty determination

Tightly constrained problems often let the local search get stuck in local optima quickly. It is, therefore, reasonable to temporarily allow constraint violations and impose penalty costs on infeasible solutions (see, e.g., Cordeau et al. 1997; Vidal et al. 2012). We define the total penalty costs of a solution as $\text {Cost}^\mathrm{{penalty}} = \delta ^{C} \cdot \upsilon ^{C} + \delta ^D \cdot \upsilon ^{D} + \delta ^{U} \cdot \upsilon ^{U}$, with $\delta ^C$ denoting the penalty factor for capacity violations, $\upsilon ^C$ the capacity violation of the solution, $\delta ^D$ the duration penalty factor, $\upsilon ^D$ the duration violation of the solution, $\delta ^U$ the fuel penalty factor, and $\upsilon ^U$ the fuel violation of the solution.

All penalty factors are initialized to $\delta ^0$ and dynamically varied within the interval $[\delta ^\mathrm{{min}}, \delta ^\mathrm{{max}}]$. After a given number of local search iterations $\eta ^+$ with a violation of the respective constraint, the penalty factor is increased by factor $\delta ^\mathrm{{update}}$. Analogously, after $\eta ^-$ feasible iterations, the penalty factor is reduced by factor $\delta ^\mathrm{{update}}$. Preliminary tests showed that choosing different values for $\eta ^+$ and $\eta ^-$ limits cycling of the local search, especially in small-sized problems.

4.5 Acceptance decision

The solution $S''$ obtained by the local search procedure is compared to the yet best solution $S$. If $S''$ is accepted, it replaces $S$ as initial solution and $\kappa$ is reset to one. Standard VNS implementations usually model the local search as a simple descent step, i.e., $S''$ is only accepted if it is improving on $S$. We use a criterion inspired by simulated annealing (SA) to control solution acceptance. This approach was originally proposed by Hemmelmayr et al. (2009) and also applied in Stenger et al. (2013a).

Improving solutions are always accepted, while non-improving ones are accepted with probability $e^{\frac{-(f(S'')-f(S))}{\vartheta }}$. The temperature parameter $\vartheta$ is decreased from its initial value $\vartheta ^0$ by factor $\vartheta ^-$ after every AVNS iteration. After $\epsilon$ non-improving main iterations, the current solution is reset to the best solution found so far. Solution diversification is increased by resetting $\vartheta$ to $\vartheta ^0$ after $\xi$ solution resets.

5 Computational studies

This section presents the computational studies to examine the effectiveness of the AVNS. We perform tests on available instances developed for the routing problems G-VRP (Erdoğan and Miller-Hooks 2012) and VRPIRF (Crevier et al. 2007; Tarantilis et al. 2008), which are both special cases of VRPIS. In addition, we design two sets of benchmark instances for the EVRPRF introduced in Sect. 3.2. A set of small instances is used to assess the quality of our solutions by comparing them to the solutions obtained with the commercial solver CPLEX. A set of large instances is used to prove the ability of our algorithm to deal with realistically sized problems in terms of computational effort. Detailed results are provided to enable a comparison with future methods developed for the EVRPRF. To the best of our knowledge, our numerical studies cover all special cases of the VRPIS investigated in the literature.

Section 5.1 describes the test environment and the parameter setting. The computational results obtained on the special cases of the VRPIS from the literature are presented in Sect. 5.2. Section 5.3 details the generation of EVRPRF instances and the results obtained on this benchmark.

5.1 Experimental environment and parameter settings

The AVNS is implemented as single-thread code in Java. Tests are conducted on a desktop computer with an Intel Core i5 2.67 GHz processor with 4 GB RAM, running Windows 7 Professional. All numerical tests are carried out with the same parameter setting, which was determined during the development and testing of our algorithm.

To determine this parameter setting, we follow the approach described in Ropke and Pisinger (2006). As test instances, we selected a reasonably large subset of the test instances of all VRPIS special cases. Then, we use the parameter setting that we have found during the development of our algorithm as basis for the tuning. Here, we stepwise refine the value of each parameter. In detail, we adjust the value of a single parameter while all remaining parameters are fixed. With every parameter setting, we perform 20 runs on the selected subset of test instances. The setting which produces the best average result is kept and the procedure is repeated with the next parameter. The resulting parameter setting is reported in Table 4.

In detail, the table shows the setting for the number of iterations after which the probabilities are updated ($\gamma$), the parameter $\rho$, which weighs the old weight and the new scores in the weight update of the selection methods within the adaptive mechanism, the initial ($\delta ^0$), minimal ($\delta ^\mathrm{{min}}$) and maximal ($\delta ^\mathrm{{max}}$) penalty factors, the penalty update factor ($\delta ^\mathrm{{update}}$), the numbers of iterations after which the penalty costs are decreased ($\eta ^-$) and increased ($\eta ^+$), the initial temperature ($\vartheta ^0$), the temperature reduction factor ($\vartheta ^-$), and the number of resets of the current solution to the best solution found after which the temperature is reset to its initial value ($\xi$).

Table 4 Overview of the final parameter setting of AVNS chosen for the numerical studies

To achieve reasonable runtimes on the investigated test instances, we set the maximum number of iterations without improvement ($\omega$) and the number of non-improving iterations after which the current solution is reset to the best solution found ($\epsilon$) as follows: for EVRPRF, we set $\omega$ equal to 2,000 and $\epsilon$ to 50, for VRPIRF, we use $\omega = 500, \epsilon =25.$ Additional tests on VRPIRF showed that a higher iteration number does not significantly improve the solution quality.

5.2 Experiments on problems with intermediate stops from the literature

To assess the performance of our AVNS, we conduct tests on instances of the special VRPIS cases G-VRP and VRPIRF and compare our results to those presented in the literature.

Table 5 Results of AVNS on the small-sized G-VRP instances by Erdoğan and Miller-Hooks (2012)

5.2.1 Green VRP

The benchmark instances designed for the G-VRP (see Sect. 2) consist of five sets. Four sets contain ten instances each comprising 20 customers (which are either uniformly distributed or clustered) and between two and ten refueling facilities. The fifth set represents a case study conducted by the authors and consists of twelve instances involving between 111 and 500 customers and 21 to 28 facilities. Note that, customers that either cannot be served within the maximum route duration or whose service requires visiting more than one refueling stop must be identified and removed from the test instances. The geographical coordinates given in the instances have to be converted to distances between vertices by means of the Haversine formula using an average earth radius of 4,182.45 miles.

Tables 5 and 6 show the results of AVNS on the small and, respectively, large G-VRP instances. We compare our results to those of the MCWS and DBCA heuristics of Erdoğan and Miller-Hooks (2012) and the VNS/TS of Schneider et al. (2014). For each problem instance, we report the problem name and the best-known solution (BKS) provided by either Erdoğan and Miller-Hooks (2012) or Schneider et al. (2014). For the MCWS and DBCA of Erdoğan and Miller-Hooks (2012), we give only the result of the better of the two algorithms for each instance. It was originally determined as the best of multiple runs ($L^\mathrm{{best}}$ in the table), but the exact number of runs is not given in the paper. For the VNS/TS of Schneider et al. (2014) and the AVNS, $L^\mathrm{{best}}$ corresponds to the best solution found in ten runs. For all algorithms, we further provide the gap of $L^\mathrm{{best}}$ to the BKS ($\Delta ^\mathrm{{best}}$) and the number of served customers ($n$). For VNS/TS and AVNS, we also display the average computing time of ten runs ($t^\mathrm{{avg}}$) in minutes, for the algorithms of Erdoğan and Miller-Hooks (2012), no runtimes were reported. The runtimes of VNS/TS and AVNS are directly comparable as both algorithms are coded in Java and executed on the same computer. Moreover, we report the average solution quality of the ten runs for the AVNS ($L^\mathrm{{avg}}$). Finally, averages of the runtimes and relative gaps to the BKS over the complete set of instances are given at the end of the table.

For the small G-VRP instances (Table 5), AVNS finds the best-known solution (BKS) for all instances. Thus, the AVNS is able to clearly outperform the methods of Erdoğan and Miller-Hooks (2012), even if for each instance only the best result provided by either MCWS or DBCA is considered. For the comparison with the VNS/TS of Schneider et al. (2014), note that the large gap of $-19.05~\%$ to the BKS for instance S2_10i6s is not meaningful because Schneider et al. (2014) identify one more customer to be reachable for this instance. However, even disregarding this instance, AVNS yields better solution quality than VNS/TS for one instance and is able to match the quality for all other instances. Moreover, compared to the VNS/TS approach, it runs nearly four times as fast on average. The results further prove the robustness of the developed algorithm: For the large majority of instances, the average solution quality of the ten runs $L^\mathrm{{avg}}$ is equal to the quality of the best run $L^\mathrm{{best}}$; for the remaining instances, the gap is quite small.

On the large-sized G-VRP instances (Table 6), the AVNS algorithm finds new best-known solution solutions for all instances and achieves an average gap to the previous BKS of more than 1 %. Moreover, the speed of the AVNS is remarkable, using approximately 4 % of the runtime of the VNS/TS of Schneider et al. (2014).

Table 6 Results of AVNS on the large-sized G-VRP instances by Erdoğan and Miller-Hooks (2012)

5.2.2 VRP with intermediate replenishment facilities

The VRPIRF (see Sect. 2) considers intermediate replenishment facilities for the goods to be delivered. We run tests on two instance sets. The set of Crevier et al. (2007) comprises 22 instances consisting of 48–216 customers, three to six intermediate facilities and four to six available vehicles. The customers are clustered around the facilities. The set of Tarantilis et al. (2008) contains 54 instances with 50–175 customers, three to eight facilities and two to eight vehicles.

Tables 7 and 8 show the results of our AVNS on the instances of Crevier et al. (2007), compared to the results of Crevier, Cordeau, and Laporte (2007) (CCL), those of Tarantilis, Zachariadis, and Kiranoudis (2008) (TZK), of the VNS/TS of Schneider et al. (2014), and the VNS of Hemmelmayr, Doerner, Hartl, and Rath (2013) (HDHR). For each instance, we report the instance name and the previously known BKS as determined by the four comparison methods. In Table 7, we report for all algorithms the average solution quality of ten runs ($L^\mathrm{{avg}}$), the gap of the average solution to the BKS ($\Delta ^\mathrm{{avg}}$) and the average computing time in minutes ($t^\mathrm{{avg}}$). Finally, averages of the runtimes and the gaps to the BKS over the complete set of instances are given at the end of the table. Note that, a direct comparison of runtimes is only valid for AVNS and VNS/TS. The other methods are partly coded in different programming languages and were run on different platforms to obtain the reported computation times. The best solution quality obtained by any of the methods on each instance is indicated in bold.

Table 7 Average solution quality of AVNS on the VRPIRF instances of Crevier et al. (2007)

Table 8 Comparison of the results on the VRPIRF instances of Crevier et al. (2007) to those of TZK, CCL, VNS/TS and HDHR based on the best run

In Table 8, we report the best solution found ($L^\mathrm{{best}}$) and the gap of the best solution to the BKS ($\Delta ^\mathrm{{best}}$). The best solutions reported by Crevier et al. (2007), Schneider et al. (2014), Hemmelmayr et al. (2013) and our AVNS are based on ten runs, those of Tarantilis et al. (2008) are the best solutions ever found with the final parameter setting, which we indicated with an asterisk. Finally, we report for our AVNS the best solutions found during the overall testing in column $\overline{\mathrm{AVNS}}$.

Concerning the entire instance set of Crevier et al. (2007), a comparison of AVNS is only possible with CCL, VNS/TS and HDHR because TZK only provide solutions for the first subset of the instances. AVNS is able to improve on the solution quality of CCL and VNS/TS concerning the best as well as the average quality. Moreover, the runtimes of AVNS are clearly faster than those of VNS/TS. AVNS is not able to match the solution quality of HDHR, which is superior to all comparison methods in terms of solution quality.

Table 9 Comparison of the AVNS results on the VRPIRF instances by Tarantilis et al. (2008) to those of TZK, VNS/TS and HDHR. BKS denotes the previously best-known solution

In Table 9, the results of AVNS on the test instances of Tarantilis et al. (2008) are compared to those of TZK, the VNS/TS of Schneider et al. (2014) and HDHR. The reported measures are the same as in Tables 7 and 8. Concerning the average gap to the BKS, the AVNS is able to improve on the results of TZK and VNS/TS based on average as well as best solution quality. AVNS is not able to match the solution quality of HDHR, which again outperforms all other methods concerning solution quality. AVNS is able to provide two new BKS during the ten test runs and four new BKS during the overall testing. Runtimes are observably faster than those of VNS/TS.

5.3 Experiments on EVRPRF instances

In this section, we conduct numerical studies on EVRPRF instances. Section 5.3.1 describes the generation of the EVRPRF instances in more detail. Section 5.3.2 presents the computational results of our AVNS on the new instances.

5.3.1 Generation of EVRPRF instances

Our EVRPRF instances are based on the benchmark instances for the CVRP introduced by Christofides and Eilon (1969) and Golden et al. (1998). To generate valid EVRPRF instances, the following adjustments are made: The service time $t^s_i$ of each customer $i \in C$ is set to ten time units. The battery capacity $p$ of each vehicle is equal to the amount of electricity required to travel 60 % of the average route length of a high-quality solution of the respective CVRP instance. The CVRP solutions are taken from the website http://neumann.hec.ca/chairedistributique/data/vrp/old/ for the instances of Christofides and Eilon (1969) and from the paper of Mester and Bräysy (2007) for the instances of Golden et al. (1998). The fixed costs per vehicle $c^{ fix }$ are calculated by dividing the objective function value of the respective high-quality CVRP solution by the number of vehicles employed in this solution (rounded up to the next multiple of 20). The recharging speed $g$ is set such that recharging the amount $p$ takes 30 time units. Due to the additional time-consumption of visiting recharging facilities, the maximum route durations given by Christofides and Eilon (1969) and Golden et al. (1998) are increased by $t^s_i$ multiplied with the average number of customers per route in the corresponding high-quality CVRP solution.

Further, each problem instance is complemented with eleven recharging facilities, of which one is located at the depot. The docking time $t^d_i$ of each recharging facility $i \in F_F$ is set to five time units. The procedure for locating the recharging facilities is illustrated in Fig. 4. First, we generate a circle around the depot with a radius that corresponds to the maximal distance $d^{ max }$ of any customer to the depot. From this circle, we create a circular ring using the radii $r_1 = 0.3 \cdot d^{ max }$ and $r_2=0.8 \cdot d^{ max }$ and divide this ring into ten sectors of identical size. Within each of this circle ring sectors, we iteratively draw possible locations for the recharging facility in a random fashion until the following two criteria are met: (1) the location does not coincide with a customer location and (2) the distance of the possible location to all previously placed recharging facilities exceeds a given threshold. This threshold is continuously decreased after a certain number of the generated random points have not met this criterion.

Fig. 4

Locating recharging facilities

In this way, we generate a total of 34 large EVRPRF instances, 14 based on the instances of Christofides and Eilon (1969) and 20 based on those of Golden et al. (1998). In addition, we create a set of small problem instances as follows: for each of the large EVRPRF instances of Christofides and Eilon (1969), we generate four small instances by (1) drawing 5, 10, 15 and 20 customers of the original instances and removing the remaining ones and (2) solving the thus generated instances with our AVNS and removing the recharging facilities that are not used in the produced solutions. In this way, 56 small instances are generated, which are denoted by the identifier of the underlying CVRP instance (CE plus instance number) followed by the number of customers (#C) and the number of facilities (#F) in the instance. For example, CE-01-05C2F denotes the instance obtained from the CVRP instance CE-01, containing five customers and two facilities.

5.3.2 Results on the EVRPRF instances

We solve the small EVRPRF instances by means of our AVNS and compare our results to those of the commercial solver CPLEX. Ten AVNS runs are conducted for each problem instance. CPLEX is given a time limit of 7,200 s for each instance and we generate three dummy vertices for each recharging facility to represent visits to the facility. The results are presented in Table 10. For CPLEX, we report the solution $L$ and the runtime $t$ in seconds. If CPLEX terminates before the end of the time limit, the given solution is optimal. Otherwise, the result corresponds to the best upper bound found within the time limit. For the AVNS, we give the best solution found in the ten runs ($L^{ best }$), the relative gap of this solution to the CPLEX solution ($\Delta ^{ best }$), the average solution ($L^{ avg }$), the gap of the average solution to CPLEX ($\Delta ^{ avg }$) and the average runtime in seconds ($t^{ avg }$).

Table 10 Comparison of the AVNS results on the generated small-sized EVRPRF instances with CPLEX

While CPLEX is only able to solve twelve out of 56 instances to optimality, AVNS is able to provide high-quality solutions with an average runtime of just above one second. Concerning the best solution, the quality of all optimal CPLEX solutions and all CPLEX upper bounds is matched or improved. The robustness of our AVNS is again proven by a negative average gap of the average AVNS solution on the CPLEX solution.

Finally, we provide the results of our AVNS on the large EVRPRF instances in Table 11. The instances are denoted by the identifier of the underlying CVRP instance (CE or G, respectively, plus instance number) followed by the number of customers (#C) in the instance. The same measures as for the AVNS results on the small instances are reported. Here, no results for comparison are available, however, we want to provide researchers tackling the EVRPRF in the future with the possibility to compare their results with those of our AVNS. Moreover, we can show that our AVNS is able to provide solutions to the large instances within reasonable runtimes.

Table 11 Results of AVNS on large EVRPRF instances

6 Conclusion

This paper presents an adaptive variable neighborhood search (AVNS) to address the vehicle routing problem with intermediate stops (VRPIS), in which vehicles are required to stop at certain facilities along their route to remain operational. The competitiveness of the proposed approach is demonstrated on benchmark instances from the literature designed for the green VRP and the VRP with intermediate replenishment facilities, which both represent special cases of VRPIS. Our AVNS algorithm shows a convincing performance compared to the methods from the literature and is able to obtain numerous new best solutions.

As a special case of the VRPIS, we additionally consider the electric vehicle routing problem with recharging facilities (EVRPRF). We design two sets of small and large EVRPRF instances based on well-known CVRP benchmarks. On the small instances, our AVNS, using a runtime of approximately one second, is able to match or improve all results obtained by the commercial solver CPLEX within a time limit of 2 h.

Appendix: Influence of problem-specific components

Table 12 shows a comparison of our AVNS to an AVNS without the problem-specific components addressing intermediate stops (denoted as $\text {AVNS-without}$) on the VRPIRF instances of Crevier et al. (2007). For each instance, we report the instance name and the BKS. Moreover, we provide the average solution found in the ten runs ($L^\mathrm{{avg}}$), the gap of the average solution to the BKS ($\Delta ^\mathrm{{avg}}$) and the average runtime in minutes ($t^\mathrm{{avg}}$) for both methods. Finally, averages of the runtimes and the gaps to the BKS over the complete set of instances are given at the end of the table. Results show that adding the problem-specific components clearly improves the solution quality while notably reducing runtimes.

Table 12 Comparison of the results of our final AVNS implementation to those obtained by our AVNS without the problem-specific methods explicitly addressing intermediate stops ($\text {AVNS-without}$) on the VRPIRF instances of Crevier et al. (2007)