The electric vehicle routing problem with synchronized mobile partial recharging and non-strict waiting strategy

Abstract

Many transportation activities have shifted to use electric vehicles (EVs) due to low-carbon and sustainability concerns. The main challenges faced by companies during the transition are the short range of EVs and the lack of recharging infrastructure. To cope with this situation, mobile charging vehicles (MCVs) are used in the system. However, this significantly increases the complexity of the electric vehicle routing problem (EVRP), as the routes for both EVs and MCVs should be optimized, and the two routes are highly interdependent. Moreover, most existing literature assumes that EVs need to be fully recharged or swapped, and EVs cannot wait for MCVs. This may lead to MCVs detour and increase scheduling difficulties, increasing the overall cost for both routes and reducing efficiency. Therefore, this paper proposes an EVRP model with synchronized mobile partial recharging and non-strict waiting strategy. The model relaxed the assumptions about full recharging and MCV waiting strategy, further increasing the complexity of the EVRP. To solve this model, we propose a two-stage dynamic programming and forward time slack algorithm based on the labeling algorithm, which is integrated into the framework of an improved adaptive large neighborhood search algorithm. Extensive numerical experiments are then conducted to demonstrate the efficiency of the algorithm and the benefits of the non-strict waiting strategy. Finally, the paper discusses some management insights based on the above analysis.

1 Introduction

Transportation plays a pivotal role in green logistics activities (Li et al., 2020a, 2020b), with road transportation standing out as a prominent contributor to energy consumption and carbon emissions (International Energy Agency, 2009). Approximately 50% of all diesel fuel is consumed by road freight transport, accounting for 80% of the net increase in global diesel use since 2000, emitting significant amounts of greenhouse gases (International Transport Forum, 2018). In response to environmental concerns, numerous studies and regulations have been proposed to bolster environmental protection. These include a focus on green manufacturing and emission reduction (Li et al., 2020a, 2020b; Sun et al., 2018). Additionally, European commissioners have set forth a vision to achieve near-zero carbon dioxide emissions in urban centers by 2030 (European Commission, 2011). Consequently, the adoption of new energy vehicles, projected to contribute approximately 45–50% to emissions reduction, is of significant interest (China Central Television, 2021). Notable examples include the effective implementation of electric taxis in Beijing, China leading to a reduction of 5,400 tons of carbon dioxide emissions between 2012 and 2015 (Ma et al., 2017). Similarly, the utilization of electric buses saved 626 tons of carbon dioxide between 2013 and 2015 (Ma et al., 2017). The remarkable emission reduction influences of electric vehicles (EVs) have prompted many companies, including major corporations like Amazon, SF Express, and JD, have transitioned from internal combustion engine vehicles to EVs, which has contributed significantly to reducing carbon emissions.

While the development of EVs promotes the greening of logistics, concerns about mileage anxiety due to battery technology limitations hamper the widespread application of EVs (Schneider et al., 2014; Xiao et al., 2023; Zang et al., 2022). To overcome this shortage, the common approach is to establish fixed charging stations (CS), enabling EVs to recharge while enroute to serve customers. However, the construction and operation costs of CSs are substantial (Schiffer & Walther, 2018), resulting in an uneven distribution of CSs, which cannot effectively meet the growing demand for EV recharging. For this reason, companies like Lightning eMotors in the US, EzUrja in India, and NIO and Huawei in China have initiated experimentation with mobile energy replenishment business mode. Meanwhile, some scholars have also turned their attention to the study of mobile energy replenishment mode in recent years (Çatay & Sadati, 2023; Raeesi & Zografos, 2020). In this mode, specialized vehicles move to customers to swap or recharge power for EVs, which addresses the inflexibility issue of CSs. Despite the benefits of the mobile mode, the model poses significant challenges for electric vehicle routing problem (EVRP) optimization. It requires to optimize the routes of EV and mobile charging vehicles (MCVs), which are closely related and interact with each other. Therefore, many scholars have studied EVRP in this mode, and the system consisting of two types of vehicles is referred to as the delivery-charging system.

Existing studies have primarily focused on the exploration of mobile swapping (Raeesi & Zografos, 2020, 2022), but the aforementioned studies usually assume the swapping of fully charged batteries, which equates to a full recharging of EVs. While swapping is faster than fully recharging, swapping may provide unnecessary power than is needed for subsequent service compared to partial charging. This may result in longer charging times for both MCVs and EVs, which delays subsequent tasks for these vehicles and reduces system efficiency. Moreover, mobile swapping has challenges such as battery ownership disputes and standardization of battery and swapping technologies (Arora et al., 2023; Setiawan et al., 2023). Mobile swapping operations also need specialized tools to replace batteries, which is more complex than mobile charging. Regarding waiting strategies, the mentioned studies typically prioritize EVs, which does not allow EVs to have additional waiting time beyond serving customers. This can lead to increased demands on mobile battery swapping vehicles (BSVs) or MCVs, requiring them to arrive earlier. The situation may force MCVs to prioritize service for tasks that are farther away but with more urgent charging demand, exacerbating vehicle scheduling challenges and increasing the cost of the overall delivery-charging system.

To overcome the aforementioned limitations, this study introduces an electric vehicle routing problem with synchronized mobile partial recharging and non-strict waiting strategy (EVRP-MPR&NSWS). The model relaxes the restriction that EVs must be full recharging and allows partial recharging, which is more practical in the real world due to the shorter recharging time. Unlike the previous models that MCVs must wait for EVs, this model introduces a non-strict waiting strategy that allows EVs to wait for MCVs to recharge after the service or even after the time window. Compared to fixed recharging and mobile swapping, the model introduces the decision of charging locations synchronization, charging levels, arrival times, and explores waiting scenarios for EVs and MCVs. EVRP-MPR&NSWS enhances the flexibility of EVs and MCVs while aiming at achieving a lower overall cost for the system. However, the model further increases the complexity of the solving due to the use of mobile partial charging with the non-strict waiting strategy. Therefore, this paper also proposes a two-stage dynamic programming and forward time slack (FTS) algorithm based on the labeling algorithm in the framework of Improved Adaptive Large Neighborhood Search (IALNS) to solve practically sized instances.

The main contributions of this study can be summarized as follows. (i) We introduce the innovative concept of mobile partial recharging. EVs can make use of partial recharging depending on the remaining service distance, increasing the charging time flexibility of EVs and MCVs. (ii) We propose a non-strict waiting strategy that does not require MCV to arrive earlier than the EV, which can optimize further the total cost of the delivery-charging system. (iii) This paper proposes an efficient algorithm and, in addition to the typical two-stage dynamic programming component for this problem, we innovatively adapted and improved the FTS based on the labeling algorithm to synchronized EVPR. These include considerations like delays in recharging service for EVs with sufficient service time in the route, aiming to enhance overall efficiency. As a result, the proposed algorithm component addresses the complexity produced by the non-strict waiting strategy and accurately evaluates solutions effectively and efficiently. (iv) The computational experiments provide a comprehensive analysis on the impact of these new ideas for logistics design and managerial insights into balancing vehicle utilization, overall efficiency, and vehicle characteristics.

The rest of the paper is organized as follows. Section 2 reviews related literature. Section 3 describes the problem and presents an EVRP-MPR&NSWS model. Section 4 describes the IALNS algorithm for solving the proposed model. Section 5 conducts several computational experiments to presents the advantages of our proposed model and algorithm. Section 6 summarizes the paper and discusses future research directions.

2 Literature review

This section reviews and discusses the existing literature related to the EVRP-MPR&NSWS problem. We first review EVRP and its variants. Then, we describe the main direction of research on fixed battery energy replenishment in EVRP over the past decade. Finally, we discuss the emerging mobile battery energy replenishment.

2.1 Electric vehicle routing problem with time windows

In recent years, growing concerns regarding carbon emissions in road freight transportation have prompted increased research into the green vehicle routing problem (GVRP). Erdoğan and Miller-Hooks (2012) introduced the GVRP with a focus on vehicles utilizing clean fuels. Building upon this, Zhang et al., (2018a, 2018b) considered the limited loading capacity of clean fuel vehicles within the context of GVRP. In addition to using clean fuel vehicles, considering the use of EVs is another increasingly important GVRP. Schneider et al. (2014) extended the GVRP by incorporating EVs and introducing energy and time constraints, leading to the development of the EVRP. Bruglieri et al. (2015) extended the EVRP by considering the battery state of charge (SoC) as a decision variable. However, unlike internal combustion engine vehicles, EVs are confronted with the challenge of a limited range (Aghalari et al., 2023). In the context of the EVRP, the efficiency of EV service is influenced by factors such as power and energy consumption. Therefore, it is necessary to find effective strategies to ensure that EVs have sufficient battery power to fulfill their freight transportation tasks efficiently (Erdelić & Carić, 2019).

Numerous studies have explored various EVRP variants to improve EV service efficiency, including scenarios with mixed fleets. These works introduced mixed fleets comprising EVs and internal combustion engine vehicles (Dönmez et al., 2022; Goeke & Schneider, 2015; Sassi et al., 2015). Various recharging technologies have been considered, exploring different charging configurations, such as regular, fast, and ultra-fast recharging (Felipe et al., 2014; Keskin & Çatay, 2018). Additionally, distinct charging functions have also been examined. Some studies assumed linear charging functions (Bruglieri et al., 2015; Hiermann et al., 2016; Yu et al., 2021), while others considered nonlinear functions (Montoya et al., 2017; Pelletier et al., 2018). Furthermore, diverse energy consumption models have been investigated. Some studies treated EV energy consumption as a linear function linked to distance (Bruglieri et al., 2019; Paz et al., 2018; Schiffer & Walther, 2018), while others developed models that account for factors such as speed, vehicle mass, terrain, air resistance, and rolling resistance (Liu et al., 2017; Macrina et al., 2019; Rastani & Çatay, 2023).

In summary, scholars have explored the extension of GVRP and EVRP, mainly emphasizing the critical effect of batteries on EV operation. However, these studies focused on applying realistic technologies or designing more accurate formulas for calculating energy consumption and recharging rate in the model, with limited exploration on recharging modes. Therefore, this paper aims to further explore innovations in recharging mode with the expectation of completing the service with lower cost and higher efficiency.

2.2 Fixed battery energy replenishment

Selecting an appropriate recharging method is essential for improving the efficiency of EVs. Previous research has explored various recharging methods, including station replenishment, regenerative braking (Bhurse & Bhole, 2018), and wireless charging (Mouhrim et al., 2019). Among them, stationary battery swapping and stationary recharging have received significant attention.

Regarding the stationary battery swapping method, EVs can visit a battery swapping station to exchange their depleted batteries for fully charged ones (J.-Q. Li, 2014). The depleted batteries can then be recharged during nighttime hours, taking advantage of discounted tariffs and reducing charging expenses (United Nations Environment Programme, 2009). The battery swapping station has been widely studied in EVRP (Liao et al., 2016; Masmoudi et al., 2018). For example, Wang et al. (2018) set up battery swapping stations and constructed a low-carbon travel land-sea integrated network on Penghu Island. Ma et al. (2021) investigated a shared autonomous EVRP with battery swapping stations providing energy. Yang et al. (2023) introduced a battery swapping priority function based on battery health and the SoC of the batteries. They categorized the batteries into three banks, taking into account their health states.

Considering the stationary recharging method, EVs can travel to CSs for recharging, with the charging time dependent on the SoC upon arrival and the subsequent journey's charge requirements (Erdelić & Carić, 2019). Some studies assumed that EVs are fully recharged at CSs each time (Goeke & Schneider, 2015; Hiermann et al., 2016; Zhang et al., 2018a, 2018b). However, in practice, vehicles may not need full recharging to return, resulting in unnecessary charging time (Keskin & Çatay, 2016). Consequently, some studies allowed partial recharging (Desaulniers et al., 2016; Schiffer & Walther, 2018; Yu et al., 2021). Its advantages was demonstrated by Wang and Zhao (2023), who found that partial recharging reduces logistics costs compared to full recharging.

Existing literature has explored fixed battery energy replenishment in EVRP, mainly focusing on two methods, fixed battery swapping and fixed recharging, with few scholars focusing on the effect of mobile recharging on logistics cost and efficiency. In this paper, we will study the logistics design of mobile recharging and reveal the practical advantages from the perspective of mobility.

2.3 Mobile battery energy replenishment

Fixed battery energy replenishment involves significant investment costs and lacks flexibility due to the uneven distribution of CSs locations. In contrast, the mobile replenishment vehicles offer an efficient alternative by reducing the need for fixed facilities, eliminating detours for EVs, and minimizing response times. As such, mobile energy replenishment mode has gained significant traction in recent years.

Shao et al. (2017) established a scheduling model for mobile swapping, prioritizing service requests based on SoC and confirming the viability of mobile swapping. Raeesi and Zografos (2020) introduced the concept of the electric vehicle routing problem with time windows and synchronized mobile battery swapping (EVRPTW-SMBS), incorporating temporal and spatial synchronization. In their model, BSVs can provide swapping batteries for multiple EVs. Subsequently, Raeesi and Zografos (2022) extended the concept to enable EVs to recharge at CSs. Ren et al. (2023) innovatively integrated UAVs into EVRPTW-SMBS, employing a Q-learning-based large neighborhood search algorithm to solve the problem. Çatay and Sadati (2023) proposed the electric vehicle routing problem with time windows and mobile charging stations (EVRPTW-MCS). Their findings demonstrated that mobile recharging by MCVs can reduce costs by an average of 42% and save over 31% of the time compared to fixed recharging.

In summary, scholars believe that mobile battery energy replenishment is more flexible and convenient than fixed battery energy replenishment. Existing research primarily focuses on applying mobile swapping technology to smaller EVs. However, electric trucks have larger and heavier batteries, which pose challenges for battery swapping. Although only few literatures have investigated mobile partial recharging, it is becoming a trend. This research explores the underexplored realm of mobile partial recharging. In addition, the aforementioned studies commonly assume that BSVs or MCVs should arrive before EVs. This assumption could exacerbate the scheduling challenges for BSVs or MCVs, increase the frequency of additional BSVs or MCVs use, and raise overall costs. In contrast, this study relaxes the assumption and explores the use of MCVs for partial recharging of EVs. However, the interdependence between the two-tier routes of MCVs and EVs can potentially render the routes infeasible or significantly change solutions, posing challenges for solving EVRP (Drexl, 2012). This paper introduces the forward time slack algorithm to effectively solve the challenges of temporal synchronization and service delay.

Table 1 summarizes the research innovations of representative papers in EVRP and highlights our unique contribution.

Table 1 Research on related papers

3 The EVRP-MPR&NSWS description and formulation

In this section, we first provide a formal description of the electric vehicle routing problem with synchronized mobile partial recharging and non-strict waiting strategy (EVRP-MPR&NSWS). Next, we present a small illustrative example of the problem. Subsequently, we introduce an integer non-linear programming model and its linearization.

3.1 Problem description

In the EVRP-MPR&NSWS, a delivery-charging system comprising EVs and MCVs is defined. The MCVs and EVs have a limited range, where EVs serve a set of customers and MCVs are equipped with batteries to recharge EVs, effectively expanding the traveling range of the EVs. There is only one depot, and both EVs and MCVs start their routes from and return to that depot, initiating their journeys with fully recharged batteries. When recharging, both EVs and MCVs must meet at the same customer location, staying there until the recharge completes. While EVs can serve customers during recharging, MCVs leave after the recharging process finishes. It is important to note that EVs must serve customers within their specific time window, but the recharging process is not constrained by this time window. Furthermore, this paper considers mobile partial recharging and the non-strict waiting strategy (described in Sect. 3.2).

Similar to Raeesi and Zografos (2020), we assume that the EV and the MCV's energy consumption follows a linear function to distance, and the charging function is linear. EVs are exclusively tasked with delivery, whereas MCVs are solely dedicated to recharging EVs. However, the recharging process can only take place at customer locations, and MCVs can fully or partially recharge EVs. It is assumed that full recharging takes longer than battery swapping, which encourages the partial charging strategy.

To simplify the model, we assume that MCVs carry two different batteries, with one for traveling and the other for recharging. This simplification ignores the optimization of battery allocation. Moreover, since recharging does not hinder cargo handling, this model assumes it is possible to serve customers and recharge simultaneously. Note that while simplifying assumptions are employed to balance the complexity of the proposed problem and algorithms, in Sect. 5 we discuss further these assumptions.

Furthermore, in contrast to previous studies, this model introduces the notion that MCVs can arrive later than EVs, even outside the customers' time window. The recharging process can continue after the EV serves customers (non-strict waiting strategy), significantly augmenting the complexity of solving the model.

Figure 1 illustrates an example of the EVRP-MPR&NSWS, with solid lines representing EV routes, dashed lines depicting MCV routes, and nodes denoting customers. Three EVs serve fifteen customers, recharged by two MCVs. They converge for recharging at customers 5, 7, 9, 12, and 15, and all of these recharging nodes involve the non-strict waiting strategy.

Fig. 1

An illustrative example of the EVRP-MPR&NSWS

3.2 The description and practical significance of EVRP-MPR&NSWS model

Existing research on mobile battery energy replenishment takes EVs as a priority, assuming that MCVs must arrive first and wait for EVs (Çatay & Sadati, 2023; Raeesi & Zografos, 2020). The assumption increases the restrictions on EVs and MCVs, resulting in higher total costs for the delivery-charging system. Unlike previous studies, our model uses the non-strict waiting strategy, which leads to a more flexible scheduling space for EVs and MCVs and can effectively reduce the total cost. The application of partial recharging also plays a positive role in cost optimization.

This section uses the instances R102-10 and C202-10 (refer to Sect. 5 for the details of the instances) to illustrate the improvement of EVRP-MPR&NSWS compared with the EVRPTW-SMBS model. R102-10 and C202-10 consist of one warehouse and ten customers with different distributions, demands, and time windows. After using CPLEX to obtain the optimal solution for each of the two models, we found that using the non-strict waiting strategy effectively reduced the cost of the overall delivery-charging system. Figure 2a, b show the optimal solution of the R102-10 in the two models. In the EVRP-MPR&NSWS, since the EV at node 2 can wait for the MCV, the MCV can recharge the EV at node 2 instead of detouring to node 3. This changes EV routes and reduces the total cost from 564.57 to 554.07. Figure 2c, d show the optimal solution of the C202-10 in the two models. EV routes are consistent in the optimal solutions of both models, and MCVs visit the same customers. Nevertheless, in the EVRP-MPR&NSWS, EVs can wait for MCVs to recharge after the service at node 10, thereby leaving sufficient time for the MCV to charge the other vehicle at node 1 first. The optimal order of MCV visits is changed in the EVRP-MPR&NSWS, which reduces the total cost from 534.76 to 526.75.

Fig. 2

Comparison of optimal solutions between SMBS and MPR&NSWS

3.3 Mathematical model

The EVRP-MPR&NSWS model can be defined on a complete directed graph $G = \left( {N,A} \right)$, where N is the set of all nodes, and $A = \left\{ {\left( {i,j} \right)|i,j \in N,i \ne j} \right\}$ is the set of directed arcs. Each $\left( {i,j} \right) \in A$ has an associated distance $d_{ij}$ and a travel time $t_{ij}$. $N = N_{c} \cup N_{D}$, where $N_{c} \, = \, \left\{ {1,2 \ldots n} \right\}$ is the set of customers and $N_{D} = \left\{ {0,n + 1} \right\}$ is the set of depots, with n + 1 being the dummy node of the depot representing the end of the route. Each customer $i \in N_{c}$ has a known demand $q_{i}$, a service time $s_{i}$ and a time window $\left[ {e_{i} , \, l_{i} } \right]$ to be served. M refers to an arbitrary large constant number in the model. The set, parameters, and variables of EVRP-MPR&NSWS are summarized in Table 2.

Table 2 Notation for the EVRP-MPR&NSWS model

According to the above definitions, a mathematical model for EVRP-MPR&NSWS is formulated as follows

$$\begin{aligned} & min\;C_{e} \cdot \sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{k \in K} {x_{0jk} } } + C_{m} \cdot \sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{m \in M} {z_{0jm} } }\\ & + c_{e} \cdot \sum\limits_{{i \in N_{0} }} {\sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{k \in K} {d_{ij} \cdot x_{ijk} } } } + c_{m} \cdot \sum\limits_{{i \in N_{0} }} {\sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{m \in M} {d_{ij} \cdot z_{ijm} } } }\end{aligned}$$

(1)

subject to

$$ \sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{k \in K} {x_{ijk} } } = 1,\;\forall i \in N_{c} $$

(2)

$$ \sum\limits_{{j \in N_{0} }} {\sum\limits_{k \in K} {x_{jik} } } = \sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{k \in K} {x_{ijk} } } ,\;\forall i \in N_{c} $$

(3)

$$ \sum\limits_{{j \in N_{0} }} {\sum\limits_{m \in M} {z_{jim} } } = \sum\limits_{{j \in N_{n + 1} }} {\sum\limits_{m \in M} {z_{ijm} } } ,\;\forall i \in N_{c} $$

(4)

$$ \theta_{ik}^{EV} = max\left\{ {\tau_{ik}^{EV} ,e_{i} } \right\},\;\forall i \in N_{c} ,\;k \in K $$

(5)

$$ \theta_{im}^{MCV} = max\left\{ {\tau_{ik}^{EV} ,\tau_{im}^{MCV} } \right\},\;\forall i \in N_{c} ,\;k \in K,\;m \in M $$

(6)

$$ \xi_{ik}^{EV} = max\left\{ {\theta_{ik}^{EV} + s_{i} ,\theta_{im}^{MCV} + g \cdot (Y_{ik} - y_{ik} )} \right\},\;\forall i \in N_{c} ,\;k \in K,\;m \in M $$

(7)

$$ \xi_{ik}^{EV} + t_{ij} \cdot x_{ijk} - M \cdot \left( {1 - x_{ijk} } \right) \le \tau_{jk}^{EV} ,\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;k \in K $$

(8)

$$ e_{i} \le \theta_{ik}^{EV} \le l_{i} ,\;\forall i \in N,\;k \in K $$

(9)

$$\begin{aligned} & \theta_{im}^{MCV} + g \cdot (Y_{ik} - y_{ik} ) + t_{ij} \cdot z_{ijm} - M \cdot \left( {1 - z_{ijm} } \right)\\ & \le \tau_{jk}^{MCV} ,\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;k \in K,\;m \in M\end{aligned}$$

(10)

$$\begin{aligned} & 0 \le y_{jk} \le y_{ik} - r_{e} \cdot d_{ij} \cdot x_{ijk} + (Y_{ik} - y_{ik} ) \cdot \\ & \sum\limits_{{h \in N_{n + 1} }} {\sum\limits_{m \in M} {z_{ihm} } } + Q_{e} \cdot \left( {1 - x_{ij} } \right),\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;k \in K\end{aligned}$$

(11)

$$ {0} \le y_{ik} \le Y_{ik} \le Q_{e} ,\;\forall i \in N,\;k \in K $$

(12)

$$\begin{aligned}& {0} \le h_{jm} \le h_{im} - (Y_{ik} - y_{ik} ) + Q_{c} \cdot \left( {1 - z_{ijm} } \right),\\ & \quad \forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;k \in K,\;m \in M\end{aligned}$$

(13)

$$ 0 \le h_{im} \le Q_{c} ,\;\forall i \in N,\;m \in M $$

(14)

$$ 0 \le b_{jm} \le b_{im} - r_{m} \cdot d_{ij} \cdot z_{ijm} + Q_{b} \cdot \left( {1 - z_{ijm} } \right),\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;m \in M $$

(15)

$$ 0 \le b_{im} \le Q_{b} ,\;\forall i \in N,\;m \in M $$

(16)

$$ 0 \le u_{jk} \le u_{ik} - q_{i} \cdot x_{ijk} + U \cdot \left( {1 - x_{ijk} } \right),\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;k \in K $$

(17)

$$ 0 \le u_{0} \le U $$

(18)

$$ x_{ijk} \in \left\{ {0,1} \right\},\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;k \in K $$

(19)

$$ z_{ijm} \in \left\{ {0,1} \right\},\;\forall i \in N_{0} ,\;j \in N_{n + 1} {,}\;i \ne j,\;m \in M $$

(20)

The objective function (1) seeks to minimize the overall cost, including the travel and fixed costs for both EVs and MCVs. Constraint (2) ensures that EVs visit each customer once for delivery, while constraints (3) and (4) enforce routing balance for EVs and MCVs, respectively. Constraints (5) to (7) define EVs’ service start time, MCVs’ charging start time, and EVs’ departure time, which are also the scheduling and synchronization constraints for EVs and MCVs. Constraints (7) and (8) ensure that EVs satisfy the time constraints by determining MCVs’ charging completion time. Constraint (9) ensures that customer service commences within their time window. Constraint (10) specifies the potential arrival time for MCVs at the recharging node. Constraints (11) and (12) ensure the conservation of power after EVs partial recharging. Constraints (13) and (14) articulate MCVs’ battery level constraints, while constraints (15) and (16) safeguard against the MCVs' traveling battery falling below zero. Constraints (17) and (18) ensure customer demand satisfaction while respecting EVs capacity constraints. Constraints (19) and (20) are ranges of values for decision variables.

In the above model, the formulation incorporates nonlinear constraints, particularly the term $(Y_{ik} - y_{ik} ) \cdot \sum\nolimits_{{h \in N_{n + 1} }} {\sum\nolimits_{m \in M} {z_{ihm} } }$ in constraints (11). Solving such nonlinearities poses challenges for commercial solvers. Therefore, we define a new variable $\varpi_{i}$, as in Eq. (21), representing the amount of recharging at recharging nodes. Equations (22)–(25) are required to define $\varpi_{i}$ in a linear setting properly.

$$ \varpi_{i} = (Y_{ik} - y_{ik} ) \cdot \sum\limits_{{h \in N_{n + 1} }} {\sum\limits_{m \in M} {z_{ihm} } } $$

(21)

$$ \varpi_{i} \le Q_{e} \cdot \sum\limits_{{h \in N_{n + 1} }} {\sum\limits_{m \in M} {z_{ihm} } } $$

(22)

$$ \varpi_{i} \le Y_{ik} - y_{ik} $$

(23)

$$ \varpi_{i} \ge Y_{ik} - y_{ik} - Q_{e} \cdot \left( {1 - \sum\limits_{{h \in N_{n + 1} }} {\sum\limits_{m \in M} {z_{ihm} } } } \right) $$

(24)

$$ 0 \le \varpi_{i} \le Q_{e} $$

(25)

4 Solution methodology

The non-strict waiting strategy and spatiotemporal synchronization pose a challenge in finding optimal solutions for large-scale problems since any small change may alter all EV and MCV routes, even for heuristic algorithms. To address the EVRP-MPR&NSWS model, this section introduces a two-stage dynamic programming (DP) and forward time slack (FTS) based on the labeling algorithm. The algorithm utilizes Improved Adaptive Large Neighborhood Search (IALNS) as its framework, initially generating an initial solution through greedy insertion. Subsequently, it employs removal and insertion operators to explore the neighborhood for constructing EV routes, where the operator selection relies on the roulette wheel mechanism. Then, a two-stage dynamic programming approach is used to tackle the coupling synchronization and partial recharging issues for EVs and MCVs, based on which FTS is employed to ensure the feasibility of the non-strict waiting strategy. Finally, a simulated annealing acceptance criterion is applied to improve the diversity of solutions. Algorithm 1 outlines the primary IALNS algorithm framework.

The procedure of IALNS

4.1 Roulette wheel mechanism and simulated annealing

The roulette wheel mechanism regulates the selection of operators. Let $\chi$ denote a given set of operators and let $\delta_{k}$ denote the weight of operator. Based on operator's performance at each iteration, the operator weight $\delta_{k}$ is computed, and the probability of the operator k being selected is $\pi_{k} = \delta_{k} /\sum\nolimits_{k \in \chi } {\delta_{k} }$.$\delta_{k}$ is calculated as $\delta_{k} = \delta_{k} \left( {1 - r_{p} } \right) + {{r_{p} \sigma_{k} } \mathord{\left/ {\vphantom {{r_{p} \sigma_{k} } {w_{k} }}} \right. \kern-0pt} {w_{k} }}$, where $r_{p}$ is the roulette wheel parameter, $w_{k}$ is the number of times it has been used in the most recent $N_{{{\text{update}}}}$ iterations, and $\sigma_{k}$ is the score of operator i before the update. If $c(S_{new} ) < c(S_{best} )$, the score is increased by $\sigma_{1}$. If $c(S_{new} ) < c(S_{current} )$, but $c(S_{new} ) > c(S_{best} )$, the score is increased by $\sigma_{2}$. If $c(S_{new} ) > c(S_{current} )$, but the solution is accepted, the score is increased by $\sigma_{3}$. To ensure the diversity of solutions, the algorithm adopts the simulated annealing acceptance mechanism, which always accepts $S_{new}$ if $c(S_{new} ) < c(S_{current} )$ and with probability $e^{{ - (c(S_{new} ) - c(S_{current} ))/T}}$ if $c(S_{new} ) > c(S_{current} )$, where T is the current temperature. The initial temperature is $c(S_{init} ) \cdot T_{init}$, and the initial solution is accepted with a fifty percent chance, where $c(S_{init} )$ is the objective function value of the initial solution $S_{init}$ and $T_{init}$ is the initialization constant. During the algorithm, the temperature is cooled at a fixed rate c, and the current temperature is reduced after each iteration to $c \cdot T$, where $0 < c < 1$ is a fixed parameter, and the algorithm returns the best solution found after a fixed number of iterations.

4.2 Removal operators

This section introduces three types of removal operators inspired by the works of Ropke and Pisinger (2006a, 2006b), Demir et al. (2012) and Hof and Schneider (2021), namely Route Remove, Segment Remove, and Vertex Remove.

4.2.1 Route remove

Route Remove operators remove the entire EV/MCV route, including four operators: (i) mixed-random route removal (MRR), (ii) cumulative maximum charge route removal (CRR), (iii) waiting time route removal (WRR), (iv) looseness route removal (LRR). The WRR operator is applied to MCV routes only, and the remaining removal operators are applied to both vehicle types. CRR is referred to the description of Hof and Schneider (2021). The explanations of the proposed MRR, WRR, and LRR are given as follows.

Mixed-random route removal For EV routes, the MRR operator uses the roulette wheel mechanism to select EV routes for removal. The selected probability is based on efficiency, which is calculated by $H_{r} = {{D_{r} } \mathord{\left/ {\vphantom {{D_{r} } {\sum {q_{r} } }}} \right. \kern-0pt} {\sum {q_{r} } }}$. $D_{r}$ is the distance of the route r, and $q_{r}$ is the customer demand. For MCV routes, the MRR operator uses the roulette wheel mechanism to select MCV routes for removal. The selected probability is based on distance.

Waiting time route removal The WRR operator removes the MCV route with the longest cumulative waiting time to eliminate poorly synchronicity of MCV and EV. The cumulative waiting time $\sum\nolimits_{i \in V} {\Delta_{i}^{wait} }$ is given by $\sum\nolimits_{i \in V} {\Delta_{i}^{wait} } = \sum\nolimits_{i \in V} {\left\{ {\left| {\tau_{ik}^{EV} - \tau_{im}^{MCV} } \right|} \right\}}$, where $\Delta_{i}^{wait}$ is waiting time at recharging node i in a feasible route.

Looseness route removal The LRR operator adapts the design of Dönmez et al. (2022) by removing the loosest routes, making the routes tighter and improving the efficiency of vehicle utilization. For EV routes, the tightness index is measured by the following equation,

$Tightness_{E} = w_{1} \left( {{{T_{r} } \mathord{\left/ {\vphantom {{T_{r} } {T_{\max } }}} \right. \kern-0pt} {T_{\max } }}} \right) + w_{2} \left( {{{C_{r} } \mathord{\left/ {\vphantom {{C_{r} } {C_{n} }}} \right. \kern-0pt} {C_{n} }}} \right) + w_{3} \left( {{{u_{r} } \mathord{\left/ {\vphantom {{u_{r} } U}} \right. \kern-0pt} U}} \right)$, where $T_{r}$ is the EV route duration, $T_{\max }$ is the maximum sustainable duration of the EV route, $C_{r}$ is the number of customers on the EV route, $C_{n}$ is the number of all customers, $u_{r}$ is the total customer demand on the EV route, and the weights $w_{i}$ between 0 and 1, satisfying $\sum {w_{i} } = 1,i \in \left\{ {1,2,3} \right\}$. For MCV routes, the tightness index is measured by $Tightness_{M} = w_{4} \left( {{{b_{r} } \mathord{\left/ {\vphantom {{b_{r} } {b_{\max } }}} \right. \kern-0pt} {b_{\max } }}} \right) + w_{5} \left( {{{l_{r} } \mathord{\left/ {\vphantom {{l_{r} } {l_{n} }}} \right. \kern-0pt} {l_{n} }}} \right)$, where $b_{r}$ is the MCV route duration, $b_{\max }$ is the maximum sustainable duration of all MCV routes, $l_{r}$ is the distance of MCV routes, $l_{n}$ is the cumulative distance traveled by all MCV routes, and the weights $w_{i}$ between 0 and 1, satisfying $\sum {w_{i} } = 1,i \in \left\{ {4,5} \right\}$.

4.2.2 Segment remove

Referring to Hof and Schneider (2021), Segment Remove operators remove a partial segment of the EV route, including four operators: (i) random segment removal (RSR), (ii) waiting time segment removal (WSR), (iii) looseness segment removal (LSR), and (iv) charging efficiency segment removal (CESR). RSR is random selection removal, and WSR and LSR are similar to the definitions in Route Remove operators, thus their descriptions are omitted. CESR is a newly designed operator, which is measured as follows.

Charging efficiency segment removal The CESR operator selects the EV route with the highest recharging volume and removes the segments with the lowest charging efficiency. This operator aims to improve the charging efficiency of the recharging nodes and take more significant advantage of partial recharging. The charging efficiency is measured by $H_{s} = C_{s} /Q_{s}$, where $C_{s}$ is the number of nodes contained in the segment, and $Q_{s}$ is the recharging volume of the recharging nodes in the segment.

4.2.3 Vertex remove

Vertex remove operators remove some customer/recharging nodes in the EV/MCV route nodes, consisting of the following operators: (i) random vertex removal (RVR), (ii) worst distance vertex removal (WDVR), (iii) relevance vertex removal (ReVR), and (iv) waiting time vertex removal (WVR). RVR and WDVR are referred to Demir et al. (2012) and their descriptions are ignored. ReVR and WVR are measured as follows.

Relevance vertex removal Referring to Hof and Schneider (2021), ReVR defines correlation based on the distance cost $c_{ij}$, the demand variance $\left| {u_{i} - u_{j} } \right|$, and the time variance $\left| {e_{i} - e_{j} } \right|$ between nodes as $R_{ij} = \chi^{c} \frac{{c_{ij} }}{{max\left( {c_{ij} } \right)}} + \chi^{d} \frac{{\left| {u_{i} - u_{j} } \right|}}{{max\left( {u_{i} } \right) - min\left( {u_{i} } \right)}} + \chi^{e} \frac{{\left| {e_{i} - e_{j} } \right|}}{{max\left( {e_{i} } \right) - min\left( {e_{i} } \right)}}$.

Waiting time vertex removal The WVR operator operates on the recharging nodes in the EV routes and removes the recharging node with the longest EV waiting time. The waiting time at the recharging node i is given by $t_{i} = max\left( {\tau_{i}^{MCV} - \tau_{i}^{EV} ,0} \right)$, which eliminates the poorly synchronized recharging nodes as much as possible under the non-strict waiting strategy.

4.3 Insertion operators

This section introduces four insertion operators inspired by the works of Ropke and Pisinger (2006a, 2006b) and Demir et al. (2012).

Greedy insertion (GI) The GI operator inserts nodes at the best position greedily. The insertion cost $\Delta d_{i}$ at position i between j and k is calculated as $\Delta d_{i} = d_{ji} + d_{ik} - d_{jk}$. The operator iterates for all nodes in the removal list until $i^{*} = min\{ |\Delta d_{i} |\}$ is chosen. The node $i^{*}$ is inserted into the route and then removed from the removal list.

Regret insertion (RI) The RI operator applies a forward-looking mechanism using the 2-regret criterion. Let $i^{*} = argmax\{ \Delta d_{i2} - \Delta d_{i1} \}$, where $\Delta d_{i}$ refers to the cost in the GI operator,$\Delta d_{i1}$ is the best reinsertion, and $\Delta d_{i2}$ is the second-best reinsertion, then the customer with the highest regret value is inserted.

Greedy insertion with noise (GIN) The GIN operator uses randomness to select the optimal position of the nodes, so as to increase the diversity. The randomness is achieved by modifying the insertion cost of the nodes as $\Delta d_{i}^{noise} = \Delta d_{i} + \overline{d} \cdot \mu \cdot \varepsilon$, where $\Delta d_{i}$ is the cost, $\overline{d}$ is the maximum distance between the nodes, $\mu$ is the noise parameter set to 0.1, and $\varepsilon$ is a random number within [− 1,1].

Regret insertion with noise (RIN) The RIN operator is an extension of the RI operator but uses the same noise function as the GIN operator.

4.4 Two-stage dynamic programming procedure

In contrast to the traditional EVRP, this paper addresses a more complex problem involving EVs and MCVs. The interaction between EVs and MCVs poses more difficulties in synchronizing them when considering mobile partial charging and the non-strict waiting strategy. To tackle the challenge, the paper introduces a Two-Stage Dynamic Programming. Stage-I dynamic programming aims to identify all viable solutions, ensuring that the EV adheres to time, capacity, and energy constraints. Building upon Stage-I, Stage-II dynamic programming is employed to pinpoint the optimal insertion location for the recharging node on the MCV route and establish the optimal combination of EV and MCV routes. To facilitate partial recharging, the algorithm introduces a partial recharging enhancement procedure (Enhancement Procedure), referring to Dönmez et al. (2022). The Enhancement Procedure initiates by eliminating redundant recharging nodes from the current route. Subsequently, it adjusts the energy transmitted from these nodes to the minimum level required for the vehicle to reach the next recharging node.

In the Stage-I dynamic programming, nodes from the removal list are inserted into the corrupted EV route $ES_{destoryed}$ to ensure adherence to time and capacity constraints (lines 01–07). The battery state of charge (SoC) is defined as $SoC = Q_{e} + \varpi_{i} - D_{0,i}$, where $Q_{e}$ is the traveling power of the EV, $\varpi_{i}$ is the recharging amount, and $D_{0,i}$ is the distance from the warehouse to the node i. For routes that violate energy constraints, locations with route SoC < 0 are identified and stored in the charging list as potential recharging node insertion locations (lines 08–15). Then, recharging nodes are inserted into these positions to assess energy constraints. Some EV routes may require the insertion of multiple recharging nodes to meet energy constraints. The Enhancement Procedure is then executed to conduct partial recharging and verification, recording all feasible repair solutions in $\phi_{feasible}$ (lines 16–22). If none of the recharging node insertion scenarios enable the route to meet the time constraint, they are recorded in $\phi_{notfeasible}$ (lines 23–36). However, if any viable restoration scenario exists, $\phi_{notfeasible}$ remains empty. The pseudo-code for Stage-I dynamic programming is detailed in Algorithm 2.

The stage-I dynamic programming

The Stage-I dynamic programming outputs $\phi_{feasible}$ and $\phi_{unfeasible}$ to determine which customers can be inserted into the recharging nodes. Building upon the results of the Stage-I, the Stage-II dynamic programming determines optimal insertion locations to establish the best MCV routes, referred to as the mobile charging vehicle routing problem (MCVRP). In MCVRP, ${\mathbb{Z}}$ represents the set of nodes that can be inserted into the recharging nodes, and we define ${\mathbb{Z}}_{0} = {\mathbb{Z}} \cup \{ 0\}$, ${\mathbb{Z}}_{n + 1} = {\mathbb{Z}} \cup \{ n + 1\}$. $\varpi_{i}$ is the recharging amount, charging time is $g \cdot \varpi_{i}$,The mathematical formulation of the MCVRP is as follows.

$$ min \, C_{m} \cdot \sum\limits_{{j \in {\mathbb{Z}}_{n + 1} }} {\sum\limits_{m \in M} {z_{0jm} + c_{m} } } \cdot \sum\limits_{{i \in {\mathbb{Z}}_{0} }} {\sum\limits_{{{\text{j}} \in {\mathbb{Z}}_{n + 1} }} {\sum\limits_{m \in M} {d_{ij} \cdot z_{ijm} } } } $$

(26)

$$ \sum\limits_{{j \in {\mathbb{Z}}_{n + 1} }} {\sum\limits_{m \in M} {z_{ijm} } } \le 1,\;\forall i \in {\mathbb{Z}} $$

(27)

$$ \sum\limits_{{j \in {\mathbb{Z}}_{0} }} {\sum\limits_{m \in M} {z_{jim} } } - \sum\limits_{{j \in {\mathbb{Z}}_{n + 1} }} {\sum\limits_{m \in M} {z_{ijm} } } = 0,\;\forall i \in {\mathbb{Z}} $$

(28)

$$\begin{aligned} &\theta_{im}^{MCV} + g \cdot \varpi_{i} \cdot \sum\limits_{{h \in {\mathbb{Z}}_{n + 1} }} {\sum\limits_{o \in M} {z_{iho} } } + t_{ij} \cdot z_{ijm} - M \cdot \left( {1 - z_{ijm} } \right)\\ & \le \tau_{jm}^{MCV} ,\;\forall i \in {\mathbb{Z}}_{0} ,\;j \in {\mathbb{Z}}_{n + 1} {,}\;i \ne j,\;m \in M\end{aligned}$$

(29)

$$ {0} \le h_{jm} \le h_{im} - \varpi_{i} \cdot z_{ijm} + Q_{c} \cdot \left( {1 - z_{ijm} } \right),\;\forall i \in {\mathbb{Z}}_{0} ,\;j \in {\mathbb{Z}}_{n + 1} {,}\;i \ne j,\;m \in M $$

(30)

$$ 0 \le h_{im} \le Q_{c} ,\;\forall i \in {\mathbb{Z}}_{0} \cup \{ n + 1\} ,\;m \in M $$

(31)

$$ 0 \le b_{jm} \le b_{im} - r_{m} \cdot d_{ij} \cdot z_{ijm} + Q_{b} \cdot \left( {1 - z_{ijm} } \right),\;\forall i \in {\mathbb{Z}}_{0} ,\;j \in {\mathbb{Z}}_{n + 1} {,}\;i \ne j,\;m \in M $$

(32)

$$ 0 \le b_{im} \le Q_{b} ,\;\forall i \in {\mathbb{Z}}_{0} \cup \{ n + 1\} ,\;m \in M $$

(33)

$$ h_{0} = b_{0} = Q_{c} $$

(34)

Similar to the original problem, constraint (26) serves as the objective function to minimize MCV costs. Constraint (27) ensures that the MCV visits each node only once. Constraint (28) is the routing balance for MCV. Constraint (29) ensures the conservation of MCV energy. Constraints (30)-(31) represent MCV constraints related to the charging battery level. Constraints (32)-(34) pertain to MCV constraints regarding the traveling battery level. This paper solves the MCVRP by using the Stage-II dynamic programming.

In Stage-II dynamic programming, for each feasible solution in $\phi_{feasible}$, the recharging node is individually inserted into the MCV route. If inserting the recharging node causes a delay in the EV's arrival time, FTS Procedure based on the labeling algorithm (see Sect. 4.5) is employed to determine whether it renders the EV route infeasible in terms of time. If feasible, it identifies the optimal restoration scheme $ES_{repaired}$ for the EV route and the optimal insertion scheme $MS_{repaired}$ for the MCV route (lines 01–10). If $\phi_{feasible}$ consists entirely of time-infeasible repair schemes, the steps in lines 02–10 are repeated. Subsequently, the location in $ES_{repaired}$ that violates the time constraint is checked, denoted as p. If p corresponds to the depot, the node at route location (p-1) is removed; otherwise, the node at route location p is deleted. Removing the recharging node may lead to battery SoC feasibility issues, in which case, the recharging node must be reinserted at other nodes. The Enhancement procedure is repeated until the EV route complies with time and energy constraints (lines 13–30). Simultaneously, a new EV route needs construction to reinsert the deleted customer nodes, with the condition that it adheres to time, capacity, and energy constraints (lines 31–39). The pseudo-code for the Stage-II dynamic programming is provided in Algorithm 3.

The stage-II dynamic programming

4.5 Label algorithm and FTS procedure

The IALNS employs labeling algorithm as the core to construct a label $L_{\sigma }$ for each recharging node. The label evaluates the feasibility of partial recharging solutions with the non-strict waiting strategy by calculating the maximum EV waiting time. Suppose the EV route is denoted as $\left( {0, \ldots ,i,j \ldots ,k,n + 1} \right)$, where $i$ represents a recharging node. The label $L_{\sigma }$ consists of four components, denoted as $L_{\sigma } {\text{ = \{ }}\theta_{i} ,\beta_{i} ,\beta_{0} ,T_{i} \}$, where the first component stores the charging time at i, the second component stores the time of arrival of the MCV at i, the third component stores the latest time of arrival of the MCV when the EV's recharging completion time equals the end time of service at i, and the fourth component stores the delay maximum time provided the EV's route does not violate the constraint at i. If the EV arrives at recharging node i at time $\tau_{ik}^{EV}$, Eq. (35) gives $\beta_{i}$.

$$ \beta_{i} { = }max\left( {\tau_{ik}^{EV} ,\beta_{i - 1} } \right) + \theta_{i} + d_{i - 1,i} , $$

(35)

where $d_{i - 1,i}$ represents the distance of the MCV from the recharging node i-1 to the recharging node i. Since recharging and service are considered simultaneously, the EV’s recharging completion time $\xi_{ik}^{EV}$ at the recharging node is denoted as $\xi_{ik}^{EV} { = }max\left( {\tau_{ik}^{EV} ,\beta_{i} } \right) + \theta_{i}$. It is assumed that recharging must be completed before the end of service, and its service end time at the recharging node is also $\xi_{ik}^{EV*} { = }max\left( {\tau_{ik}^{EV} ,e_{i} } \right) + s_{i}$. The value $\beta_{0}$ can be computed using Eq. (36).

$$ \beta_{0} { = }max\left( {\tau_{ik}^{EV} ,e_{i} } \right) + s_{i} - \theta_{i} . $$

(36)

When altering the order of visiting the recharging nodes on an MCV route, the MCV’s arrival time at the recharging node changes. The change could delay the time when the EV visits the node following the corresponding recharging node on the respective route, which may lead to the EV violating the time window constraint. To avoid reorganizing the EV routes after each change in MCV routes, the FTS Procedure is designed based on Grangier et al. (2016). When a visit time deferral occurs, the FTS Procedure calculates the maximum delay time and compares it to the actual delay time. The operation does not violate the time window constraint if the delay time exceeds the maximum delay time.

The early arrival times of the vehicles from node j to k on the EV route before any deferrals occur can be calculated, the time at which the vehicles arrive before the start of the time window. Their cumulative early arrival times $ET$ are determined by Eq. (37).

$$ ET_{j,k} { = }\sum\limits_{w \in \Omega j,k} {max\left( {0,e_{w} - \tau_{wk}^{EV} } \right)} $$

(37)

Assuming that the end of the time window at the node is $l_{i}$, the delay time $T_{i}$ can be calculated as Eq. (38).

$$ T_{i} { = }min\left\{ {ET_{j,k} + l_{j,k} - \tau_{j,k}^{EV} } \right\} $$

(38)

After obtaining the label $L_{\sigma }$ for each recharging node on the EV route, if all the recharging nodes satisfy $\beta_{i} - \beta_{0} \le T_{i} ,\forall L_{\sigma } \in {\mathbb{R}}$ (where ${\mathbb{R}}$ is the set of all the labels on the EV route), it indicates that the EV route adheres to the time window constraints.

In FTS Procedure based on the labeling algorithm, the first step involves initializing the list of recharging nodes and the list of labels (line 01). Subsequently, the EV route is input, and recharging nodes are added (lines 02–06). Then, labels for different positions of each recharging node are calculated, including $\theta_{i}$, $\beta_{i}$, $\beta_{0}$, and $T_{i}$. Notably, if $T_{i} > 0$, the FTS Procedure is employed for computation (lines 07–15). After obtaining the label set for each recharging node, the EV route's time feasibility and permissible waiting time are determined using the values $\beta_{i}$, $\beta_{0}$, and $T_{i}$ from the labels. If $\beta_{i} - \beta_{0} \le T_{i} ,\forall L_{\sigma } \in {\mathbb{R}}$, the EV route complies with the time window constraints. In the case of $T_{i} \ge 0$, it is necessary to compute the delay times for all nodes following the EV route’s recharging nodes and calculate the actual arrival times for each node along the EV route (lines 16–30). The pseudo-code for the FTS Procedure is presented in Algorithm 4.

FTS Procedure

This section includes an example to illustrate the operation of the FTS Procedure. A virtual node is constructed at the recharging node's location for illustrative purposes. An EV route (0, 1, 2′, 2, 3, 4, 5, 0) is assumed, where 2' represents a virtual charging node. It should be noted that 2′ and 2 are located at the same customer location, and the time window of 2′ is the same as the time window of the depot. Furthermore, since recharging and service can be carried out simultaneously, their time windows will not affect each other. Figure 3 displays each node’s time windows, travel times, and arrival times. Cumulative early arrival times ET for reaching each node and slack times $l_{i} - \tau_{i}^{EV}$ are calculated according to Eq. (37), and $T_{i} = 10$ as per Eq. (38). Assuming service time $s_{i} = 30$ and charging time $\theta_{i} = 4$, we obtain $\beta_{0} = 96$. Assuming the MCV arrives at the recharging node at time $\beta_{i} = 106$, the label at recharging node 2' $L_{\sigma } = \left( {4,94,106,10} \right)$. Due to $\beta_{i} - \beta_{0} = T_{i}$, the route does not violate the time constraint. It is important to note that the delay of nodes following the EV route’s recharging node and the calculation of the deferred arrival time $\tau_{i}^{EV^{\prime}} = \max (0,\beta_{i} - \beta_{0} - ET_{i - 1} )$ are required after changing the MCV arrival time. The results are a deferred arrival time of 120 at node 3, 130 at node 4, and no deferral at node 5.

Fig. 3

Impact of different battery levels

5 Computational experiments

This section presents numerical experiments on the EVRP-MPR&NSWS model to evaluate the effectiveness of the proposed operator and solution algorithm. Comparisons are also made with different operational models, and some management insights are discussed.

5.1 Benchmark instances and experimental setting

The EVRP-MPR&NSWS model utilizes the EVRPTW-SMBS instances originally proposed by Raeesi and Zografos (2020), which include 36 small instances (5, 10, and 15 customers) and 112 large instances (25 and 100 customers). They are constructed based on the VRPTW benchmark introduced by Solomon (1987) and the EVRP instances presented by Schneider et al. (2014), which comprise six sets of test instances (C1, R1, RC1, C2, R2, and RC2). These instances are categorized according to the geographical location of the customer into clustered “C”, randomly distributed “R” and half clustered and half randomly distributed “RC”. Additionally, instances in the first group (R1, C1, and RC1) have a short scheduling horizon, whereas the second group instances (R2, C2, and RC2) have a longer one.

The EVs and MCVs also adopted the parameter characteristics and assumptions in Raeesi and Zografos (2020), including battery capacity and energy consumption. It was assumed that the MCV possesses a rechargeable battery five times larger than that of the EV, a traveling battery twice the size of the EV, and a similar energy consumption rate. The origination and unit traveling costs of EVs and MCVs are set to $C_{e} = 50$, $C_{b} = 60$, $c_{e} = c_{b} = 1$ with reference to Raeesi and Zografos (2020) and Shao et al. (2017). However, unlike the battery swapping time presented in EVRPTW-SMBS ($\zeta = 3$), this study assumes that EVs require 5 units to be fully recharged ($\zeta = 5$).

The parameters are divided into two sets. The first set refers to Ropke and Pisinger (2006a, 2006b) and defines the iteration parameters of the IALNS algorithm, including the roulette wheel mechanism, operator coefficients, and the simulated annealing acceptance framework, as detailed in Table 3, where n is the number of customers. The second set, encompassing vehicle and customer information, is outlined in the instances.

Table 3 Parameter settings

5.2 The performance of the operators

This section evaluates the performance of the removal and insertion operators in terms of solution quality. Following the approach of Franceschetti et al. (2017), %Usage, %Imp, and %IBest are performance metrics. %Usage represents the proportion of iterations in which this operator is used relative to the total number of iterations. A larger %Usage indicates a higher weight for the operator in the roulette wheel, illustrating a greater contribution of the operators in the iteration process. %IBest represents the percentage of the total number of iterations in which the operator is used and achieves the optimal solution. It indicates the operator's efficacy in reaching the global optimum. %Imp represents the percentage of the total number of iterations in which the operator is used and improves the existing solution, demonstrating the operator’s capacity for local optimization by obtaining a superior solution to the current one. We run algorithm ten times per instance, and the Table 4 shows the results.

Table 4 Relative performance of the operators

Table 4 illustrates the operators' performance, where the MRR and LRR operators perform the best with their high %Usage, %Improvement, and %IBest. This indicates that mixed random selection and route tightness measurements typically lead to improved solutions compared to existing ones. In contrast, the CESR operator exhibits the highest %Usage but underperforms, possibly due to the challenge of obtaining a better solution than the current one. Regarding %IBest, the WVR operator performs well and is employed efficiently. The WVR operator's performance improves with larger instance sizes indicating that removing more poorly synchronized recharging nodes through the WVR operator is more favorable for system optimization. Concerning insertion operators, those with noise achieve a higher %IBest than those without noise. The randomness introduced by noise enhances search diversity, resulting in a more effective discovery of optimal solutions.

5.3 Performance of the non-strict waiting strategy and the algorithm

In this section, we assess the performance of the proposed EVRP-MPR&NSWS algorithm by comparing its solutions with other waiting strategies and CPLEX. The evaluation is conducted on instances involving 5, 10, 15, and 100 customers, aiming to evaluate the effectiveness of both the algorithm and the non-strict waiting strategy.

5.3.1 Different waiting strategies and solution method

In this paper, the FTS Procedure based on the labeling algorithm serves as the core of IALNS to address the non-strict waiting strategy. In the development of the FTS, we progressively relax the constraints on waiting strategies for EVs and MCVs within delivery-charging systems. This relaxation results in three progressively less stringent waiting strategies, each allowing for varying degrees of flexibility. Waiting Strategy 1 (WS1) represents the most stringent waiting strategy, requiring the MCV arrives before the EV and waits for the EV to commence service. Waiting Strategy 2 (WS2) relaxes the waiting restriction imposed on the early arrival of MCVs, requiring that the MCV's charging end time precedes the EV's service completion time. Non-Strict Waiting Strategy 3 (NSWS3), presented in this paper, imposes no waiting constraints. The EV can wait for the MCV to complete charging after the end of its service or even beyond the designated time window, and the MCV can wait for the EV to recharge at its discretion.

To evaluate the effectiveness of the non-strict wait strategy and the efficiency of the algorithmic components, this section outlines the algorithmic components used to solve models with different waiting strategies, as detailed in Table 5.

Table 5 Algorithm component

5.3.2 Experiments with small-scale instances

This section evaluates the performance of the IALNS algorithm by solving small instances using CPLEX. TC represents the total cost, TV is the total number of vehicles, Δ% and Gap% indicate the gap between the WS1/WS2 and NSWS3, and the gap between the NSWS3 and CPLEX, respectively, with a CPLEX time limit of 7200 s. Table 6 reveals that CPLEX identifies the optimal solution in 33 instances, with NSWS3 matching CPLEX in these cases. In the remaining 3 instances, where CPLEX does not find the optimal solution within the specified time, NSWS3 outperforms with an average improvement of 3.36%. CPLEX exhibits an average runtime of 1958.57 s, while NSWS3 has an average runtime of only 13.74 s. These findings demonstrate that the algorithms in this paper efficiently handle small-scale instances. Additionally, to evaluate the algorithm components' contributions, the solutions of WS1, WS2, and NSWS3 are compared. Relative to NSWS3, the quality of WS1 and WS2 solutions, which lack specific components, decreases by an average of 2.90% and 0.46%, respectively, underscoring the effectiveness of incorporating FTS components into the ILANS algorithm.

Table 6 Comparison of the CPLEX and WS1/WS2/NSWS3 with 5, 10 and 15 customers

5.3.3 Experiments with large-scale instances

This section solves large-scale instances involving the three waiting strategies of EVRP-MPR&NSWS. Table 7 presents the results of these strategies with 100 customers, and the Gap% is computed as $gap = \left( {\frac{{z^{TS2/TS1} - z^{TS3} }}{{z^{TS3} }}} \right) \times 100\%$.

Table 7 Computational results for WS1/WS2/NSWS3

In Table 7, it can be observed that NSWS3 outperforms WS1 in 42 instances, while in 14 instances, their solutions coincide. Similarly, NSWS3 outperforms WS2 in 27 instances, with the remaining 29 solutions the same as NSWS3. On average, NSWS3 demonstrates improvements of 2.77% in total cost, 2.39% in total number of vehicles, and 2.58% in total distance compared to WS1. Compared to WS2, NSWS3 exhibits average improvements of 0.99%, 0.87%, and 0.66%, respectively. These indicate that the overall system optimization benefits from relaxing the assumption that MCVs must arrive earlier than EVs. Excessive emphasis on the priority of the EVs may affect the optimization of the system.

Table 8 provides the average results across various instances for the three strategies. De represents EVs’ travel distance, Dm represents MCVs’ travel distance, Ve denotes the number of EVs, and Vm represents the number of MCVs. NSWS3 outperforms all instances except where the total cost matches WS2 at C2. Specifically, for C2, R2, and RC2, the average total cost of NSWS3 is 1.29% lower than that of WS1, with only slight differences in fleet size. However, for R1 and RC1, the average total cost of NSWS3 is 4.39% lower than that of WS1 due to the shorter time windows. This underscores the significance of considering the non-strict waiting strategy, which can simultaneously benefit both EV and MCV routes in the delivery-charging system.

Table 8 Computational results for different instance collections

5.4 The added value of the EVRP-MPR&NSWS

By comparing with other classical models, this section explores the added value of the EVRP-MPR&NSWS mode in the context of various recharging modes and discusses in detail the specific advantages of the proposed mode.

The EVRP-MPR&NSWS is compared with other prominent modes, namely the EVRPTW-PR proposed by Keskin and Çatay (2016), the EVRPTW-MCS introduced by Çatay and Sadati (2023), and the EVRPTW-SMBS developed by Raeesi and Zografos (2020). It is essential to note that the mobile swapping proposed by Raeesi and Zografos (2020) cannot service customers when swapping. However, due to the convenience of recharging, the EVRP-MPR&NSWS can serve customers while recharging. To better demonstrate the advantages of the EVRP-MPR&NSWS, we introduce a mode where recharging and serving customers cannot be done simultaneously, called the separation model. Table 9 provides the results of these modes with 100 customers, where “PR” corresponds to the EVRPTW-PR, “SMBS” represents the EVRPTW-SMBS, “MPRS*” stands for the separation model, “MCS” denotes the EVRPTW-MCS, and “MPR&NSWS” refers to the EVRP-MPR&NSWS. Additionally, “S” indicates the number of recharging nodes, while “F” represents the total power of recharging or swapping.

Table 9 Computational results for different operation modes

As depicted in Table 9, all instances of MPR&NSWS exhibit lower costs than MPRS*, primarily because simultaneous recharging and service reduce overall time requirements. On average, MPR&NSWS leads to a 32.44% reduction in the total cost and a 13.74% decrease in fleet size compared to PR. PR's total cost includes factors such as total distance, vehicle fixed costs, and the cost of operating the CSs. Even without factoring in the fixed investment cost of constructing CSs, PR remains more expensive than MPR&NSWS. EVs face additional travel time and are more likely to miss time windows when detouring to CSs for recharging. The MCS mode, which prevents EVs from waiting for MCVs, is equivalent to the WS1. On average, MPR&NSWS outperforms the MCS mode regarding total cost, EV fleet size, MCV fleet size, number of recharging trips, and recharging volume. This demonstrates the outstanding results of the non-strict waiting strategy proposed in this paper.

Furthermore, the average cost of MPRS* is 4.22% lower compared to SMBS. The substantial 61.55% reduction in MCV recharging compared to BSVs emphasizes the considerable energy-saving potential of mobile partial recharging. In contrast, SMBS outperforms MPRS* for instances C102 and RC106, possibly due to the longer full recharging time, which makes partial recharging less advantageous. Although SMBS and MPRS* have similar fleet sizes, MCVs exhibit better energy replenishment efficiency, serving EVs 3.91 times on average compared to 3.49 times for BSVs. Moreover, for R101 and R111, BSVs require a minimum of 16 batteries, which imposes additional inventory costs for the company.

Since the PR mode of fixed charging is significantly different from the other mobile modes, we focused on analyzing the results of the four mobile modes. Figure 4 presents route results for the C204 within the other four modes, where solid lines depict the EV, while dashed lines represent the MCV. In the SMBS mode, there are 5 EVs and 1 BSV, resulting in a total cost of 1095.98, while the MPRS*, MCS, and MPR&NSWS modes have 3 EVs and 1 MCV, with total costs of 957.86, 956.08, and 940.02, respectively. The lower cost in the MPR&NSWS mode compared to MPRS* and MCS modes is consistent with expectations. Compared to the SMBS mode, the number of EVs in the MPRS* mode was reduced from 5 to 3 vehicles, resulting in a cost reduction of 12.6%.

Fig. 4

Route diagrams under different modes of C204

Further analysis reveals that the total charging time for MCVs at the four recharging nodes is 10.25, while the total swapping time for BSVs is 12. It indicates that despite the full recharging taking longer compared to swapping, partial recharging offers greater time flexibility and ultimately shorter recharging time, which underscores the superior benefits of mobile partial recharging compared to mobile swapping.

Similarly, Fig. 5 presents route results for the R108. The SMBS mode encompasses 15 routes with a total cost of 2066.61, while the MPRS* mode includes 14 routes with a total cost of 1999.63. In contrast, the MCS and MPR&NSWS modes consist of 13 routes, with total costs of 1961.95 and 1913.11, respectively. Unlike the SMBS and MCS modes, the MPR&NSWS and MPRS* modes relax the waiting strategy at recharging nodes 8, 59, 61, and 100, which makes them cost less. The total costs of the MPR&NSWS mode and the MPRS* mode is 7.43% and 3.24% lower than the SMBS mode, respectively, due to the narrower time window of R108 and the application of a non-strict waiting strategy. Additionally, the total cost of the MPR&NSWS mode is 2.49% lower than that of the MCS mode, further demonstrating the effectiveness of the non-strict waiting strategy.

Fig. 5

Route diagrams under different modes of R108

5.5 Sensitivity analysis of different vehicle characteristics

This section focuses on the impact of various vehicle characteristics on the EVRP-MPR&NSWS solution. To examine these effects, 24 instances are selected for experimentation from 25 and 100 customer instances (selected from the first two instances of C1, R1, RC1, C2, R2, and RC2). Modifications to problem characteristics generate a set of new instances, which are then compared with the results of the original instances, offering insights into the application and operation of two types of vehicles.

5.5.1 Traveling battery

This section explores the influence of different EV and MCV traveling battery capacities on the solution. Low and high battery capacities are represented by 80% and 120% of the original battery, respectively. Figure 6 depicts the total cost, distance traveled, and the number of vehicles under varying battery capacities. Predictably, low battery capacity in EVs limits their travel distance, increasing the need for MCV deployments and recharging times. Similarly, MCVs with low battery capacity need more deployments to serve fewer EVs due to their limited range. An intuitive improvement is to deploy more EVs, reducing the energy demands on each delivery route. Consequently, whether EVs or MCVs, the larger the battery capacity, the lower the total cost.

Fig. 6

Impact of different battery levels

In summary, advancements in battery technology hold critical significance for MCV operators and the delivery-charging system, promising substantial cost and vehicle count reductions. Additionally, increasing the frequency of recharging cannot always reduce the cost when battery capacity is fixed. Deploying more EVs can decrease the recharging frequency, providing more relaxed time windows for MCVs and reducing the overall system cost.

5.5.2 Charging rate

The analysis in this section considers a slow charging rate, requiring ten units of time to reach full capacity, and an extra-fast charging rate, requiring three units of time. Figure 7 illustrates that the cost of the slow charging rate is generally higher due to the extended charging time. Interestingly, the improvement in ultra-fast charging is limited. This is because the saving in charging time is short and not enough to synchronize the EV and MCV better. Consequently, while increasing charging speed reduces the operator's costs, its effects diminish. Besides improving customer satisfaction and reducing waiting times, increasing charging speeds will unlikely reduce operating costs further.

Fig. 7

Impact of different charging rate

5.5.3 Shared batteries

This section investigates the impact of whether MCVs use the same battery to supply power for traveling and charging. “NS” denotes unshared batteries, while “S” represents shared batteries, with numbers indicating customer size. Shared batteries combine the energy of the original traveling and charging batteries. Figure 8 reveals that using shared batteries results in smaller MCV sizes, averaging 19.75% less. The reduction occurs because MCVs can balance traveling and charging energy, serving EVs more frequently and requiring fewer deployments to meet demand. Moreover, the total cost of shared batteries is, on average, 1.06% lower than that of unshared batteries. From a system optimization perspective, shared battery technology yields superior outcomes, as even the worst-case scenario remains the same, with most scenarios displaying improvements.

Fig. 8

Impact of shared battery

5.5.4 Deployment and operating costs

This section evaluates the impact of varying deployment and operating costs for MCVs on the overall system. A 50% and 100% increase in deployment and operational costs for MCVs is regarded as high and ultra-high, respectively. Figure 9 illustrates the impact of these cost changes. Generally, as costs increase, the total cost of the system rises. There are two scenarios for cost increases: one where delivery and charging routes remain unchanged, and the system cost increases solely due to elevated MCV costs. In contrast, altering existing routes leads to higher system costs. Another scenario is route changes due to changes in MCV deployment or operating costs. The cost changes in this scenario tend to be small, with the number of charges gradually decreasing as MCV costs rise. Eventually, all deliveries will use EVs without recharging.

Fig. 9

Impact of different cost

When MCVs are operated by third parties, deployment and operational costs become critical factors in MCV utilization. The higher the cost, the lower the MCV utilization rate. MCV costs are not the sole determining factor for the system, and advancements in battery technology can yield substantial cost savings. Surprisingly, optimizing MCV costs provides significant benefits. Nevertheless, the optimization is not limitless, as MCV costs decrease, the optimization of the system tends to plateau, with the number of recharges no longer increasing due to battery capacity constraints and time window limitations. Moreover, as MCV costs approach those of EVs, further optimization becomes less feasible in the real world.

6 Conclusion

This paper extends the EVRP model to EVRP-MPR&NSWS to explore mobile partial recharging decisions using the non-strict waiting strategy. EVs are employed for delivery tasks. MCVs can perform partial recharging on multiple EVs with low battery levels, resulting in a decrease in charging times and an increase in practicality. Unlike the traditional EVRP that takes EVs as a priority, the EVRP-MPR&NSWS model does not require MCVs to arrive immediately when EVs request recharging, and EVs can wait for recharging after servicing customers. This removes the time window restriction for MCVs and allows MCVs to serve EVs more efficiently, thereby reducing the total cost of the delivery-charging system.

While mobile partial recharging decisions with the non-strict waiting strategy offer an opportunity to save cost and improve time flexibility, challenges arise concerning recharging volume, waiting decisions, and the spatial and temporal coordination of MCVs and EVs. To address these complex problems, an improved ALNS algorithm is developed. The algorithm's core components include the labeling algorithm and FTS modules, designed to solve recharging amount and timing decisions. The instances for EVRP-MPR&NSWS were sourced from Solomon (1987) and Raeesi and Zografos (2020). Extensive numerical analysis of different waiting strategies shows that labeling algorithm and FTS achieve superior results across all instances, demonstrating the effectiveness of our algorithm. The results also underscore the competitiveness and efficacy of the non-strict waiting strategy in reducing the total cost of the delivery-charging system. Moreover, the advantages of the EVRP-MPR&NSWS model are showcased by demonstrating its competitiveness against relevant benchmark examples of EVRPTW, EVRPTW-SMBS, and EVRPTW-MCS. Our model reduces the total cost in these instances. Furthermore, we conducted a sensitivity analysis and provided operational suggestions and management insights. Based on the results of the computational experiments, we propose that companies, when designing their logistics plans, could innovatively consider additional waiting time of the EVs for MCVs to become available for recharging purposes. This approach would offer greater flexibility and efficiency in cargo distribution. Upon analyzing the various characteristics of vehicles, we show that companies could benefit from consolidating the traveling and recharging batteries of MCVs. This consolidation improves recharging flexibility and reduces operating costs, although it necessitates careful consideration of battery power allocation decisions. It is essential to note that we do not recommend companies overprice their MCVs. While this may result in higher profits, it could decrease the overall utilization of MCV across the system, potentially leading to increased costs.

Due to the current insufficient number of recharging infrastructures and their uneven distribution, MCVs will become an essential way to replenish the power of EVs. Future research may explore more application scenarios for MCVs. For instance, MCVs could set up temporary charging points at any location and serve multiple EVs at the same time, reducing MCV travel distances. EVs could also share power to reverse recharge the MCVs, which would enable the MCVs to service more EVs or travel longer distances. To enhance the model's realism, future studies may use nonlinear charging and energy consumption functions. Additionally, future research may delve into demand fluctuations, which may change in MCV charging locations and require further algorithmic advancements to coordinate EVs and MCVs effectively.