Irnich s 2023 vrp reviewed papers năm 2024

This study addresses a new electric vehicle routing problem with time windows and recharging strategies (EVRPTW-RS), where two recharging policies (i.e., full or partial recharging) and three recharging technologies (i.e., normal, rapid, and ultra-rapid) are considered. For this problem, we first develop a mixed-integer linear programming model defined in a series of vertices including a depot, a series of recharging stations, and a set of customers. Due to the strong NP-hardness of EVRPTW-RS, a tailored adaptive large neighborhood search heuristic (ALNS) which contains a number of advanced efficient procedures tailored to handle the proposed problem is developed. Numerical experiments for benchmark instances generated based on the Greater Toronto Area and Ontario in Canada are conducted to evaluate the performance of the proposed model and ALNS. Computational results demonstrate that the ALNS is highly effective in solving EVRPTW-RS and outperforms commercial solver CPLEX. Moreover, the advantages of the proposed recharging strategies are illustrated and some recommendations are provided for stakeholders when using electric vehicles for delivery.

1. Introduction

The red line that global temperatures must not exceed is the line that pushes our planet beyond the 1.5-degree temperature limit, according to the statement made at the 27th Conference of the Parties to the United Nations Framework Convention on Climate Change []. Global temperatures can rise as a result of a rise in CO2 emissions, which can also have an impact on climate change. However, CO2 emissions in 2021 increased by almost 2.1 Gt from 2020 levels. According to the International Energy Agency, if transportation activity had returned to prepandemic levels in 2021, the world’s CO2 emissions would have increased by 600 Mt. The overall CO2 emissions would have risen by 7.8% as a result, which would be the fastest pace of growth since the 1950s []. Considering this fact, electrifying conventional vehicles may significantly lower CO2 emissions. McKinnon et al. [] emphasized that one of the most important approaches to decarbonizing long-distance cargo transportation systems is through the electrification of road transportation vehicles.

Over the past decades, the parcel delivery service has increased dramatically due to population growth and urbanization. A huge increase in logistics has been seen since the early 2000s as a result of the rapid rise of lifestyles and the advent of electronic commerce. At the same time, environmental concerns [–] have begun to shape the logistics industry, with increasing competition among logistics service providers in order to meet the growing demand for green, faster, and cheaper deliveries. A rapid trend in the use of electric vehicles (EVs) has been observed. Logistics service providers and individuals are encouraged to use EVs, particularly to reduce CO2 emissions and fuel costs.

The adaption of alternative fuel vehicles (AFVs) in the fleet can achieve greener delivery and may help improve the competition among logistics service providers. Among these AFVs, EVs are among the most alluring. AFVs utilize alternatives and greener sources of fuel like methanol, ethanol, biodiesel, natural gas, electrical power, hydrogen, and propane. However, a systematic assessment of evidence is needed before these fleets become completely different. For example, Koc and Karaoglan [] pointed out that the use of AFVs has several impacts, including increased resource use, harm to ecosystems and people, increasing air pollution, noise pollution, and CO2 emissions’ effects on the climate.

As a last-mile service solution, the fleets of EVs have several advantages including the absence of CO2 emissions, positive impact on air quality in urban areas, and lower noise pollution in contrast to vehicles with internal combustion engines []. Moreover, in situations of high oil prices, such as the financial crisis, these EV system supply fleets play a lower cost role in protecting the logistics service providers from contact and ensuring the total cost of deliveries.

As a result, a fifth of automobiles sold in Norway today are electric, and 230 million electric bikes have replaced gasoline motorcycles in China’s largest cities []. Additionally, EV sales set a new high in 2021, growing by four times their market share from the previous year to account for nearly 10% of all new car sales globally. Compared to 2020, public and private spending on EVs has doubled. More and more nations make commitments to phase out internal combustion engines or set aggressive electrification goals [].

However, the greatest limitations are related to EV delivery, driving range, and long recharging times. Therefore, there is a growing interest [, ] in incorporating environmental factors and relative constraints in EVs into vehicle routing problems (VRPs). In the literature on operations research [], electric vehicle deliveries are generally modeled and studied as an electric vehicle routing problem. This problem is solved by placing multiple delivery EVs at the depot and building an EV route that serves all customer nodes to minimize travel distance or operational costs. The EVRP with time windows includes consumers who are only accessible within a specified timeframe.

The above background indicates that logistical transportation, particularly road transportation, can lead to high CO2 emissions, and therefore our study has chosen to use EVs for delivery. There are some limitations in current research into the recharging time of electric vehicle transportation. Moreover, existing studies on EVRP generally assume that EVs leave the distribution center at the same time every day, go immediately to the next node, and finish the fixed recharge energy of each recharging station at a certain recharging mode. Because each customer demand point has a time limit for the expected delivery time, this strategy can cause EV not to be delivered on a specified time frame, or the logistics company can use more efficient delivery methods to deliver goods within the customer demand point time limit. Additional vehicles increase the fixed fee. Therefore, after arriving at the recharging station, determining which recharging rate and how much to recharge is a valuable question worth examining.

To meet daily recharging needs, fast rechargers are becoming increasingly popular and drivers can choose recharging modes according to their needs. This study focuses on a new EVRP with time windows and multiple recharging strategies, which allows the partial recharge strategies using three recharging modes by determining recharge energy. It is naturally an extension of the EVRP with time windows and partial recharging (EVRPTW-PR) by deciding on the recharging energy and using alternative rechargers including three recharging modes (i.e., normal, rapid, and ultra-rapid).

The remainder of the paper is organized as follows. Section of this article reviews the pertinent literature. EVRPTW-RS is discussed in Section along with its mathematical model. The ALNS-SA is proposed in Section . The experimental study is fully described and the findings are discussed in Section . The work is concluded in Section with a final observation and recommendations for further study.

2. Literature Review

Since the introduction of the truck delivery problem [], over the past few decades, VRPs and their various extensions and variants of traditional VRPs have been extensively developed with justification in applications in real life. The key objective of the vehicle routing problem (VRP) is to reduce the overall distance traveled by a group of customers during a visit by using several vehicle routes that begin and terminate at the depot while taking into account a variety of constraints. Many vehicle researchers [–] are primarily interested in the problem of capable vehicle routing problem (CVRP) and the heterogeneous fleet vehicle routing problem. In contrast, those [] who focus on customer-focused research have considered customer time windows and customer satisfaction.

EVRP is a typical VRP where delivery is performed by conventional vehicles. Compared to conventional vehicles, the use of EVs is limited by many restrictions, as the range of EVs is short, and there is a requirement of recharging activities along the route of the vehicle. However, they [, ] have several advantages, such as nonlocal greenhouse gas emissions, minimal noise, renewable energy source reliability, and the ability to operate independently of fluctuating oil prices. Currently, the EVRP extends the VRP mainly in four aspects:(i)Recharging stations (CSs) [–].(ii)Nonlinear charging functions [–].(iii)Recharge policy [–].(iv)Heterogeneous fleet of EVs [].

Schiffer and Walther [] presented the issue of positioning routes taking into account the positioning of EVs and the decision to position them at the charging stations. In this case, partial recharges are allowed. Finally, an ALNS was presented, which was enhanced through local search, labelling algorithms, and new penal functions for assessing neighborhoods. The location of the battery exchange station of the EV and the routing problem [] of the battery exchange station under the battery drive range limit are similar to CS locations. Keskin and Çatay [] developed an ALNS to efficiently solve the EVRPTW-PR. The interest in EVRPTW-PR is growing. Since the recharge profile is a linear time function and reaches 80% of the battery capacity [], the charge curve becomes concave. All vehicles recharge up to 80% of their batteries, and full recharging takes longer. They enhanced the ALNS algorithm to solve the problem. It was proposed [] to develop four variants on the basis of the allowed recharge times of each route and the recharge state of EVs at each CS.

In an EVRPTW-RS, a homogeneous EV fleet is shipped from a single library dispatch. Customers can specify additional time windows and delivery locations. The order is delivered to these locations strictly within the corresponding time window. Due to the limited autonomy of the EV, it may be necessary to recharge on the way to continue its journey. In contrast, most studies [, ] aim to reduce the total distance or travel time. These studies [–] consider reducing energy consumption and emissions of EVs or delays.

The objective of this function is to minimize the total cost of the delivery company by deciding on the delivery route, arrival time, recharging stations, recharging energy, and recharging technologies so that the delivery company uses the minimum number of vehicles in its fleet, including the cost of traveling and recharging. We first propose a 0-1 mixed-integer linear programming (MILP) model for this problem. It expands the EVRP-PR introduced by Schneider et al. [] in an alternative way as in Keskin and Çatay [], and this model also includes several realistic considerations. First, we consider the possibility of a partial recharge in a station. This means that we must determine not only where and when to recharge but also how much. This extension is driven by the potential cost savings resulting from using partial recharges, which could save recharge time and thus facilitate the achievement of maximum time constraints, reducing the number of vehicles needed and thereby reducing transportation costs. Since the problem is intractable for large-size instances, we develop an ALNS method that selects the operator to be used in the next iteration based on the historical performance of the operator with the number of uses and generates the neighborhood structure of the current solution by competing among operators. To avoid getting stuck in a local optimum, we incorporate the simulated annealing method (SA). Therefore, the proposed algorithm is called adaptive large neighborhood search-simulated annealing (ALNS-SA). In the local search phases, we use several problem-specific neighborhood structures. We conduct extensive experimental studies to investigate the performance of the ALNS-SA. Our contributions are summarized as follows:(i)We consider a new electric vehicle routing problem with time windows and recharging strategies and formulate it into a 0-1 MILP model.(ii)We develop an ALNS and SA hybrid approach by posing several new problems with specific neighborhood structures.(iii)Extensive computational experiments are conducted to verify the performance of the proposed approach.(iv)We present various trade-off analyses on key decision variables and provide insights from logistics companies when using electric vehicles for delivery.

3. Problem Definition and Formula of Model

This section studies the 0-1 MILP of the EVRPTW-RS.

3.1. Problem Definition

EVRPTW-RS refers to a group of customers with known time windows, demands, and service times. There are EVs with a fixed maximum battery and load capacity. During travel, the battery charge level decreases in proportion to the distance traveled, and EVs may have to visit recharge stations CSs to continue their travel. In contrast to EVRPTW, when the EV departs from the CS with a full battery, in EVRPTW-RS, the EV time of the recharging depends on the initial state of battery charge, the distance of the next depot, and the decided recharging rate.

Figure 1 shows an example involving 8 customers (1–8), 7 CSs (A–G), and the depot. The percentage value on the EV1 route shows the battery state of recharge when the vehicle arrives at the customer or CS and when it departs from the CS. EV2 visits CS D after servicing customer 5 and has its battery recharged before visiting customer 4. Servicing customers 8, 7, and 6, the EV3 returns to the depot with its initial charge. On the other hand, EV1 is recharged once in CS A and twice in CS B. Note that each CS is not necessarily visited (see charging stations C and E–G). In what follows, we provide the mathematical model for EVRPTW-RS.

Unlike traditional EVRPs, our aim is to propose a route plan to simultaneously deliver electric fleets that can meet constraints and provide charging strategies. Therefore, we propose the concept of a virtual distribution depot and provide a detailed explanation in Figure 2.

EVRPTW-RS is aimed at creating daily travel for logistics companies to provide services to customers. The objective function is to minimize the travel cost and recharging costs in order to effectively use available EVs by minimizing the EVs’ wasted time en route, and this reduces the number of vehicles in use. Each EV must visit each of the designated customers.

The delivery network studied in this paper has one and only one depot, all EVs depart from the depot and return to the depot after completing their tasks. The EVs are fully charged when they leave the depot, and the EVs are partially recharged at the CS. The distribution vehicles are the same type of vehicle. The delivery goods studied in this paper are the same kind of general goods, and the vehicles only unload the goods when they reach the corresponding customer demand point. Each customer demand point can be visited once and only once by a single electric vehicle, and all of its delivery requirements are met. The location of the depot, the customer demand point, and the CS are known, and the demand at each customer demand point is known. EVs can be recharged without waiting when they arrive at the CS, and each vehicle can reach the CS an unlimited number of times for recharging, and the cost of recharging is proportional to the amount of recharging.

This paper considers multiple recharging technologies: normal, rapid, and ultra-rapid. This problem tracks the charge state of EVs and ensures that the energy of EVs is feasible rather than recharging to full capacity, , at the CS.

3.2. Model Formulation

3.2.1. Notation

The EVRPTW-RS is modeled as a 0-1 MILP program on a complete orientation graph , where the customer is modeled as a graphical vertice, and the route between customers is modeled as a graph arc [, ]. The symbol for the mathematical model developed to solve the variant of the EVRPTW-RS is shown in Tables 1–3. Let be a set of geographically scattered customers that need to be served, and let be a set of CSs. In order to allow multiple visits to the same CS, a virtual set of CSs is defined (). Vertices and denote the depot instances, and every route begins at vertex and ends at vertex (). Graph GRA is defined as , where is the set of arcs . The arc value indicates the distance of the arc, indicates the energy consumption to traverse the arc, and indicates the time required to cross the arc. The objective function includes firstly the total traveled distance’s cost minimization (equation ()) and then the recharging cost minimization (equation ()). EVs have a load capacity of and battery capacity of . Recharging time is computed as a linear function value of recharged capacity with each inverse recharge rate of , respectively, and the unit energy cost of using recharge technology is denoted by . Each customer has a service time , load demand , and time window . Besides the decision variable, eight more decision variables are used: 1 if the vehicle is recharged with normal charger at a recharging station, 0 otherwise, 1 if the vehicle is recharged with rapid charger at a recharging station 0 otherwise, 1 if 0 otherwise. is the amount of recharging energy received by the vehicle at a recharging station using the recharging type is the remaining load capacity when the vehicle arrives at the vertex, and is the remaining battery capacity when the vehicle arrives at the vertex.

3.2.2. Energy Consumption

Actually, the EVs’ energy consumption rate is influenced by the speed, the amount of load capacity, traveling speed, the amount of load, the traveling environment and other factors referenced [] to construct the driving speed, and dynamic load under the electric vehicle power consumption rate model as follows:

Equation () represents the calculation of the EVs’ energy consumption rate under dynamic load, where represents the energy consumption coefficient of vehicle during its journey from node to node ; is the vehicle weight; and indicate the weight of the load at nodes and , respectively; is the gravity constant; is the air density; is the windward area; is the air resistance coefficient; is the wheel rolling resistance coefficient; and is the electric vehicle rotation efficiency.

3.2.3. EVRPTW-RS

The minimized total cost of EV delivery is formed by equations () and (). Equations () and () represent the travel cost and the recharging cost, respectively.

Equations ()–() ensure arc connectivity. Constraint () enforces only one visit to each customer. By constraint (), a customer is restricted to be visited once at most. Constraint () indicates that the number of incoming arcs equals the number of outgoing arcs at each node. Constraints () and () guarantee a start and end vertex for each trip.

Equations () and () represent the load constraints. Constraint () guarantees that the maximum load of the vehicle is not exceeded, and constraint () ensures the load feasibility.

Equations ()–() denote the time window and the travel time constraints. Constraint () forces that the customer’s arrival time must be within the time range. Constraints () and () guarantee the timing requirements of adjacent customer nodes. Constraint () indicates the time requirement for visiting charging stations and customer nodes.

Constraints ()–() ensure arc battery. Constraint () forces the arrival remaining battery capacity of each node. Constraint () indicates that no power is consumed in each node. Constraint () shows the power relationship between two adjacent nodes. Constraint () guarantees the remaining battery capacity for each customer node.

The proposed model extends the MILP of EVRPTW-FR. A new decision variable is considered, which denotes the energy on the departure from CS , given by constraint (). After recharging, the rest of the energy is somewhere between the rest of the energy recharging in the previous CSs and the whole energy . Constraints () and () calculate the energy amount recharged and recharging duration of EV visits to CS, respectively. Constraints ()–() ensure that EV recharging at a CS is performed by the chosen recharger type. Constraint () guarantees the relationship between the battery capacity of the EV after visiting CS and when it arrives at the next node.

4. Adaptive Large Neighborhood Search

Since VRP is an NP-hard problem, commercial solvers have to wait long to solve mid-sized instance models, and they cannot solve large-scale instance models either. Furthermore, because the proposed problem is greater than traditional VRP, we develop ALNS using the SA method and efficiently solve the EVRPTW-RS. As seen in Table 4, the most common methods of solving EVRP are neighbor search algorithms [, , , , ] such as VNS and LNS variants. The main framework of the ALNS was developed by Ropke and Pisinger [], followed by the authors of [, ] who succeeded in solving a number of complex VRP variations. This method uses removal and insertion operators iteratively and accepts or rejects the candidate solution on the basis of the probability acceptance criterion. ALNS can generate up to 1000 clients and provide different versions of VRP []. The proposed EVRPTW-RS covers different types of VRPs, including CVRP [], vehicle routing problem with time windows (VRPTW) [], and EVRPTW-PR []. Recent research has highlighted how effectively the ALNS algorithm solves various VRP types. Some researches include [, ], which utilize ALNS to solve VRPTW and CVRP, respectively.

Therefore, this paper develops metaheuristic algorithms to attain solutions within a feasible computation time. To solve our objective function model (cost minimization), we use the ALNS with the simulated annealing method. Algorithm 1 provides the overall framework of ALNS. The functions rem (.) and rep (.) show the removal operator and the insertion operator, respectively. The variables , , , and refer to the solutions of the initial, candidate, current, and best-found. The objective function values are expressed by R (), R (), and R ().

(1)Generate a and assign it to ;(2);(3);(4);(5) while the maximum number of iterations is not reached, i.e., do(6) if ≡ 0 (mod ) then(7) SNC (, ) (Algorithm 2) ⟶ ;(8) end if(9) Choose destroy operator s ∈ (customer, travel, station) based on ;(10) if travel is removed then(11) Select repair operator for the travel;(12) Update for the route operator;(13) else if a station is removed then(14) Select repair operator for stations;(15) Update for the station operator;(16) else if a customer is removed then(17) Select repair operator for customers;(18) Update for the customer operator;(19) else if a recharging technology is removed then(20) Select repair operator for charge technologies;(21) Update for the recharging technology operator;(22) end if(23) if the energy level shows that the solution is not possible then(24) Nearest CS Insertion operator;(25) end if(26) if ≤ then(27) Update ;(28) else(29) Generate a number randomly ;(30) ifthen(31) Update ;(32) Update and for each operator;(33) Update for each operator;(34) end if(35) end if(36) if < then(37) Update ;(38) Update ;(39) Update and for each operator;(40) Update for each operator;(41) else if compared to the previous iteration, it has enhanced then(42) Update ;(43) Update for each operator;(44) Update for each operator;(45) end if(46) if ≡ 0 (mod ) then(47) Update for operators using the adaptive weight adjustment;(48) end if(49);(50);(51) end while Output:

The proposed ALNS algorithm begins with the initial solution as described in Section , whereas using the SA framework, acceptance criteria are used. Initial temperatures are set to accept solutions with objective values equal to (1 + ξ), and initial objective values are accepted with 0.5 probability. The best, most current solutions and the iteration counter of the ALNS-SA, , have been initialized.

In each iteration, first select operators of the algorithm heuristics as mentioned in Section (i.e., the removal and insertion) that are used to attain . According to the acceptance criteria of SA, the candidate solution obtained by the algorithm through selected removal and insertion operators, will be decided whether to be accepted. That is, if R () < R (), then it is always accepted. If the is weaker than the , will replace the with a probability of . At the end of each iteration, the temperature will decrease, and the probability of accepting a bad solution will decrease. The set of removal and insertion operators is represented by and , respectively.

Once in every iterations, the continuous neighborhood change procedure, which is used as the reinforcement procedure for Hansen [], is used as a variable neighborhood search framework to improve the . Algorithm 2 shows this process. If the existing solution improves in one of the neighborhood structures, the search will resume in the first neighborhood structure of the updated or search for the next neighborhood.

(1) ;(2) whiledo(3) move ;(4) ifthen(5) ;(6) ;(7) else(8) ;(9) end if(10) end while Output: A global best solution

The removal operator has the selection probability and the insertion operator has the selection probability . The initial weight is and , respectively. The weight is updated on the basis of operator performance. The algorithm has the maximum number of iterations .

4.1. Initial Solution Construction

We develop a two-phase constructive heuristic for the procedure of generating an initial solution specific to a problem. The first phase is to assign customers to EVs, routing and scheduling; the second phase is to scan remaining unrouted customers and create the next route using other EVs.

The first is the customer-score, , calculated for every customer sorting the customers according to their latest distance. On the basis of a given customer-score, the further away customers have a higher customer-score. The order of the customer set is to increase the customer-scores and start the visit of the first customer in the order of the customer set. Second, each EV is built from the depot node with complete charging capacity, after which customers are visited one by one, plugging the nearest CS into the EV route (i.e., the charge capacity is insufficient to visit the next customer) and eventually returning to the depot node. At this stage, it is assumed that each CS will use the ultra-rapid recharging mode. Finally, the route schedules that are built in the first step are determined. If the time window of any customer is infringed, the corresponding customer will be removed from the EV route and, if it exists, inserted into the customer list of another EV, whose route has not yet been built. If such an EV does not exist, the customer will be inserted into the set of unrouted customers . And each CS visit will select the optimal recharging mode, the optimal recharging mode driver provides the lowest recharging energy, and the recharging energy ensures that the power supply will not be burned out until the next CS visit. represents the set of customers assigned to each EV, and represents the set of unrouted customers. The algorithm provides the construction process for the first phase.

At the end of the first phase, there may be an unrouted customer (i.e., ). In the second phase of the construction heuristic, all customers of the set must be added to another EV. If there are EVs satisfying various constraints that can access unrouted customers, then unrouted customers will be inserted into the corresponding EVs; otherwise, a new rout will be generated to access them.

4.2. Removal and Insertion Operators

ALNS searches the neighborhoods of the initial solution using different removal and insertion operators. Some of these operators [, ] are successfully proposed. However, the proposed ALNS must be modified on the basis of the presented problems, as the operators of removal and insertion are already used. In addition, we introduce several operators for specific problems, such as removal recharging technology, customers with worst distance removal, recharging technology insertion, and customers with optimal distance insertion.

One removal operator, “Random Route Removal,” is used to remove the routes, three removal station operators are named “Random Customer Removal,” “Worst Distance Removal,” and “Random Recharging Station Removal,” and one removal operator for deleting technologies is named “Recharging Technology Removal” in our ALNS.(i)Random Route Removal. The operator randomly selects an EV and removes the route traveled by that EV.(ii)Random Customer Removal. The operator randomly selects the customer for a route and removes it.(iii)Worst Distance Removal. The operator removes the customer, which increases the largest distance on the current tour.(iv)Random Recharging Station Removal. The operator randomly selects the CS visit in the and removes the CS from the tour that corresponds to it.(v)Recharging Technology Removal. The operator randomly removes the information on recharging technology from the CS visit selected in the solution. Figure 3 shows examples of applications of this action on delivery routes.

Three insertion operators for the insertion of customers, CS, and recharging technologies are “Random Customer Insertion,” “Nearest Recharging Station Insertion,” and “Recharging Technology Insertion.” These insertion operators are described as follows.(i)Random Customer Insertion. For every removed customer, the operator chooses a compatible EV and randomly assigns each removed customer to a route location.(ii)Least Distance-Based Customer Insertion. The operator selects an unrouted customer from a number of unrouted customers and an EV capable of serving that customer with a minimum distance. Then, the unrouted customer is assigned to the EV route. This procedure keeps going until all unrouted customers are given the EV route.(iii)Nearest Recharging Station Insertion. For EVs in each delivery route, the operator checks the recharging state of each visitor node, inserts the nearest CS at the corresponding location of the corresponding route every time a minimum SOC is detected, and determines the amount of recharging used in recharging and determines the technology used in recharging.(iv)Recharging Technology Insertion. For each CS the EV passes, the operator selects not to disturb the current EV schedule and provides the best recharging technology to minimize the recharge cost. If the removal of recharging technology is employed in an iteration as a removal heuristic, the introduction of recharging technology is chosen as an insertion heuristic. Figure 4 shows an example of the application of this action on the delivery route.

The ALNS-SA algorithm is employed after generating the initial solution . In the first iteration, the weights of all operators are initially equal to 1, and the operators are chosen randomly. These weights are adjusted once in each subsequent iteration and are calculated by equation () based on the performance of the operator.

represents the number of iterations that operator applied in the iterations, and roulette wheel parameter controls the historical performance of the heuristics. Apply a removal or insertion heuristic to the in an iteration and obtain a (such as heuristic pro). The score of the heuristic is improved by , which is calculated as

The increment amounts should be set to so as to carry out an appropriate score adjustment. The probability of selecting the operator is updated in iteration depending on the weights of equation (). is the weight of operator in iteration and is the total number of operators of each type.

4.3. Neighborhood Structures

The following four neighborhood structures (i.e., = 4) are used by the proposed ALNS-SA in the SNC process in the following order.(i)Horizontal Relocation. Randomly select nodes visited by the EV and insert them in random positions in the route of an EV.(ii)Horizontal Switch. Two nodes visited by the EV are randomly selected, and positions along the EV route are swapped.(iii)Vertical Relocation. Randomly select the node visited by the EV. Then, it is removed from the EV route and placed on another arbitrary EV route.(iv)Vertical Switch. Exchange the positions of two nodes that were chosen at random and visited by two separate EVs.

5. Computational Experiments

We employ CPLEX 12.10 solver in our experiments; however, any open-source or commercial solver can be utilized instead. The algorithm codes in the Python 3.8 environment and runs on a Core i5 3.40 GHz computer with 8 GB of RAM. The time limit for solving the instances is set to 7200 s. We first describe the data and parameter settings in Section . We then analyze the performance of the proposed ALNS-SA in Section to compare the difference between the proposed ALNS-SA and commercial solvers on small and medium-sized instances and the ALNS results of large-size instances in Section . We investigate the effect of multiple recharging strategies compared with a single strategy in Section .

5.1. Data and Experimental Settings

We conduct an extensive computational study to evaluate the performance of the proposed mathematical algorithm and the sensitivity of the solution to key parameter values. To do so, we generate a reasonable set of benchmark instances of three different scales from the GVRP instances in [] that are based on real-world settings: small size (including 5–10 customers), medium size (including 15–20 customers), and large size (including 100 customers).

Walmart in Canada aims to entirely use alternative fuel vehicles by 2028 []. However, due to their limited range, EVs need to be charged, and Walmart needs routing that takes into account both recharging methods and partially recharged EVs. Due to the many limitations of EVs, Walmart is somewhat similar to other logistics companies (such as UPS, Amazon, and JD) that wish to electrify their vehicle fleets. We will use them as an example to explore this problem in order to offer ideas for logistics organizations aiming to deploy electric fleets and improve delivery services.

In these cases, each node that corresponds to the exact locations of the Walmart supercenter’s depots and customers is relatively evenly dispersed within a region of the Greater Toronto Area measuring roughly 100 . All cases were evaluated considering a single depot. The travel distance of the two points is measured in km, and the distance affects how much energy is used.

Besides this, the EV’s cargo load capacity at vertex B of the depot is , and the EV cargo load capacity . Cost coefficients are derived for a real-world case study []; these are fixed as and . The battery capacity , the energy consumption per kilometer travel , and the average speed per vehicle . The full recharging of the EV battery takes 420 minutes for normal recharging, 180 minutes for fast recharging, and 30 minutes for super-fast recharging. Its cost [, ] is calculated in CNY per minute: , , and , respectively. To prevent battery degradation or total charging and maintain its lifespan [], and are defined to ensure that the SOC of each vehicle is between and of its capacity when it leaves the customers and recharging stations. The EV’s electric power consumption and the recharging cost parameters that the CS management established based on their marketing plan affect how long it takes to charge an EV.

The instance name indicates the volume of customers and recharge stations included in the case. For example, the case named 20-4-A has 20 customers and 4 CSs, and to distinguish the same consumers, identification is added to the end of the case name.

5.2. Results of Comparison of Small- and Mid-Sized Cases

The results of CPLEX implementation in small- and medium-sized mathematical models are presented in Table 5. After executing numerous several instances using different vertices, the overall number of vertices of a small-sized case is determined. Finally, cases with fewer than 15 vertices can be optimized using CPLEX. This section compares the CPLEX results with the proposed ALNS-SA on these test cases in order to assess the performance of the ALNS-SA algorithm because small-sized cases can be solved optimally using the CPLEX solver. The data table includes the total amount of EVs utilized in the best objective function, the optimal objective function value calculated using two different approaches, and the running time of the best result in seconds. The proposed ALNS algorithm is not very satisfactory in small-size instances, but it has a significantly longer running time than CPLEX and a significant effect in mid-sized cases.

5.3. Results for Large-Sized Cases

We evaluate the suggested ALNS-SA’s performance in large-sized cases. Table 6 displays specific findings. The best objective function values are shown in this table (i.e., the percentage contribution of the two objective function terms: travel cost and recharging cost), along with the average total cost value, the number of EVs utilized by the best solution, and the solution’s final execution time in seconds.

In large-sized instances, the total recharge cost is dominant, representing 64.30% of the total cost. This shows the importance of effective use of the recharging strategy. Similarly, we also note that the ALNS can deliver existing solutions to 100 customers in less than 50 minutes, which is acceptable for use in real-world scenarios.

5.4. The Impact of the Availability of Recharging Strategies for Different Recharging Methods

Several EVRP studies consider only fast recharging strategy []. Then, we examine the impact of accessibility to recharging strategies with numerous recharging modes on the entire cost. Furthermore, in the current case where there are recharging strategies with multiple recharging modes, we also consider the case where the recharging station has only normal, rapid, or ultra-rapid recharging technologies and conduct experiments for every case. Table 7 compares the average values for various recharging strategies and the best goal values of functions for each case’s divergence from the best objective values for all recharging strategies that used multiple recharging technologies.

It is clear from Table 7 that some recharging strategies have improved total costs. These savings are on average 3.30%, 0.16%, and 5.36% compared to the recharging strategy using a single recharge mode with normal, rapid, and ultra-rapid rechargers, respectively. If the recharge station only offers one recharging mode, for most of the instances, a fast recharger will provide the best results despite its higher recharge costs. Rapid recharging is crucial since it shortens the overall journey duration and increases the area that can be used in situations when time windows are a major constraint. The findings indicate that all technologies and rapid technology are equipped with the same solution for small- and mid-sized cases. However, compared to the accessibility of all recharger types, rapid rechargers result in poorer solutions in large-size situations.

To take into account the potential for partial recharge at the recharging station, we decide when and how much to charge at that charging station. Based on the possible savings from partial recharging, which can lower the total amount of vehicles required, recharging times, and costs of energy that cannot be recharged through depots, this result is shown in Table 8.

6. Conclusions

This paper examines the logistics and distribution of EVs. To improve the timeliness of the EVs, we propose the recharging strategies. When EVs are recharged at each recharging station, three recharging modes (i.e., normal, rapid, and ultra-rapid) and the recharging energy can be determined according to the need. To this end, we build the EVRPTW-RS model and consider constraints such as vehicle energy, vehicle load, and window time constraints. Since the established EVRPTW-RS model is an NP-hard problem, we design the ALNS algorithm according to the characteristics of the EVRPTW-RS model, which proposes more targeted operators of removal and insertion in the ALNS-SA algorithm.

Further analysis of the numerical results yields the following conclusions. Firstly, when solving the cases, the outcomes demonstrate that our ALNS algorithm outperforms CPLEX with regard to both time and solving quality. Secondly, the proposed EVRPTW-RS can reasonably determine the recharge mode and recharge energy at the recharge station in order to effectively reduce the overall cost. EVRPTW-RS performs mid-sized instance resolution (15.64%) better than CPLEX’s solutions, and it is able to resolve large-scale situations, which CPLEX is unable to do. Furthermore, the EVRPTW-RS solution time is shorter than the CPLEX solution time. Thirdly, the decision making of the three recharging technologies is compared, and the results show that the overall cost of the decision-making recharging technology is 3.3%, 0.16%, and 5.36% lower than that of only using normal, rapid, and ultra-rapid recharging technologies, respectively.

Our findings demonstrate the efficient use of multiple recharging technologies: normal, rapid, and ultra-rapid. As expected, the use of normal and ultra-rapid recharging technology at the recharging stations will increase the overall cost of operation of delivery companies. However, in some cases, recharging stations using only fast recharging technologies can also reduce overall costs. We have shown that, taking into account all recharging technologies (i.e., normal, rapid, and ultra-rapid), the overall cost will reduce in most cases. Furthermore, research shows that partial recharging at recharging stations through recharging energy decisions not only effectively saves each vehicle’s delivery time and reduces the number of vehicles used by delivery companies but also significantly reduces the total cost of recharging at the recharging station.

This finding may be of significant importance for stakeholders (i.e., delivery companies and governments) when investing in recharge infrastructure. If the government provides several recharge modes for some CSs, this finding can be important for delivery companies, which can significantly improve delivery efficiency and reduce delivery costs. Government action is not part of this study, but it may actually be the case.

There are several important directions to research in future work. Firstly, in the real world, the road is dynamic, such as vehicle accidents and severe weather events. Therefore, vehicle speeds may be connected to specific road segments in the network of roads. Secondly, from the perspective of model building, objective optimization under heterogeneous fleets and multiple delivery depots is also an attractive research direction. Finally, according to model characteristics, the ALNS algorithm can take into account more targeted removal and insertion operators and the parameters of the ALNS algorithm can be adjusted accurately in subsequent case analysis, further improving the algorithm’s performance. Although dealing with these problems is difficult, we believe that they have important implications for business.

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

The authors gratefully acknowledge the financial support from the Humanities and Social Science Foundation of the Chinese Ministry of Education under Grant 21YJA630096; the 2nd Fujian Young Eagle Program Youth Top Talent Program under Grant 0470-00472214; the General Program of National Natural Science Foundation of Fujian Province, China, under Grant 2022J01075; and the Natural Science Foundation of Fujian Province, under Grant 2020J05194, 2021J05226, and 2022J01938.

References

1. Cop, “The 27th conference of the Parties to the united nations framework convention on climate change,” 2022, https://www.un.org/en/climatechange/cop27. View at: Google Scholar
2. IEA, “Global energy review: CO2 emissions in 2022,” 2022, https://www.iea.org/reports/co2-emissions-in-2022. View at: Google Scholar
3. A. McKinnon, J. Allen, and A. Woodburn, “Development of greener vehicles, aircraft and ships,” in Green Logistics. Improving the Environmental Sustainability of logistics.Reprinted, A. C. McKinnon, Ed., pp. 140–166, Kogan Page, London, UK, 2011. View at: Google Scholar
4. Y. Wang, X. Ma, Z. Li, Y. Liu, M. Xu, and Y. Wang, “Profit distribution in collaborative multiple centers vehicle routing problem,” Journal of Cleaner Production, vol. 144, pp. 203–219, 2017. View at: Publisher Site | Google Scholar
5. Y. Wang, X. Ma, M. Liu et al., “Cooperation and profit allocation in two-echelon logistics joint distribution network optimization,” Applied Soft Computing, vol. 56, pp. 143–157, 2017. View at: Publisher Site | Google Scholar
6. D. Kannan, A. Diabat, M. Alrefaei, K. Govindan, and G. Yong, “A carbon footprint-based reverse logistics network design model,” Resources, Conservation and Recycling, vol. 67, pp. 75–79, 2012. View at: Publisher Site | Google Scholar
7. C. Koc, “A unified-adaptive large neighborhood search metaheuristic for periodic location-routing problems,” Transportation Research Part C, vol. 68, pp. 265–284, 2016. View at: Google Scholar
8. I. Malmgren, “Quantifying the societal benefits of electric vehicles,” World Electric Vehicle Journal, vol. 8, no. 4, pp. 996–1007, 2016. View at: Publisher Site | Google Scholar
9. T. Bektaş, J. F. Ehmke, H. N. Psaraftis, and J. Puchinger, “The role of operational research in green freight transportation,” European Journal of Operational Research, vol. 274, no. 3, pp. 807–823, 2019. View at: Publisher Site | Google Scholar
10. H. Dündar, M. Ömürgönülşen, and M. Soysal, “A review on sustainable urban vehicle routing,” Journal of Cleaner Production, vol. 285, Article ID 125444, 2021. View at: Publisher Site | Google Scholar
11. M. Schneider, A. Stenger, and D. Goeke, “The electric vehicle-routing problem with time windows and recharging stations,” Transportation Science, vol. 48, no. 4, pp. 500–520, 2014. View at: Publisher Site | Google Scholar
12. G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management Science, vol. 6, no. 1, pp. 80–91, 1959. View at: Publisher Site | Google Scholar
13. V. R. Máximo and M. C. Nascimento, “A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem,” European Journal of Operational Research, vol. 294, no. 3, pp. 1108–1119, 2021. View at: Publisher Site | Google Scholar
14. V. R. Máximo, J. F. Cordeau, and M. C. Nascimento, “An adaptive iterated local search heuristic for the Heterogeneous Fleet Vehicle Routing Problem,” Computers & Operations Research, vol. 148, Article ID 105954, 2022. View at: Publisher Site | Google Scholar
15. M. Eskandarpour, D. Ouelhadj, S. Hatami, A. A. Juan, and B. Khosravi, “Enhanced multidirectional local search for the bi-objective heterogeneous vehicle routing problem with multiple driving ranges,” European Journal of Operational Research, vol. 277, no. 2, pp. 479–491, 2019. View at: Publisher Site | Google Scholar
16. E. H. Sadati, V. Akbari, and B. Çatay, “Electric vehicle routing problem with flexible deliveries,” International Journal of Production Research, vol. 60, no. 13, pp. 4268–4294, 2022. View at: Publisher Site | Google Scholar
17. S. Moon and D. J. Lee, “An optimal electric vehicle investment model for consumers using total cost of ownership: a real option approach,” Applied Energy, vol. 253, Article ID 113494, 2019. View at: Publisher Site | Google Scholar
18. J. Yang and H. Sun, “Battery swap station location-routing problem with capacitated electric vehicles,” Computers & Operations Research, vol. 55, pp. 217–232, 2015. View at: Publisher Site | Google Scholar
19. M. Schiffer and G. Walther, “The electric location routing problem with time windows and partial recharging,” European Journal of Operational Research, vol. 260, no. 3, pp. 995–1013, 2017. View at: Publisher Site | Google Scholar
20. S. Zhang, M. Chen, and W. Zhang, “A novel location-routing problem in electric vehicle transportation with stochastic demands,” Journal of Cleaner Production, vol. 221, pp. 567–581, 2019. View at: Publisher Site | Google Scholar
21. A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas, “The electric vehicle routing problem with nonlinear charging function,” Transportation Research Part B: Methodological, vol. 103, pp. 87–110, 2017. View at: Publisher Site | Google Scholar
22. A. Froger, J. E. Mendoza, O. Jabali, and G. Laporte, “Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions,” Computers & Operations Research, vol. 104, pp. 256–294, 2019. View at: Publisher Site | Google Scholar
23. X. Zuo, Y. Xiao, M. You, I. Kaku, and Y. Xu, “A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function,” Journal of Cleaner Production, vol. 236, Article ID 117687, 2019. View at: Publisher Site | Google Scholar
24. M. Keskin and B. Çatay, “Partial recharge strategies for the electric vehicle routing problem with time windows,” Transportation Research Part C: Emerging Technologies, vol. 65, pp. 111–127, 2016. View at: Publisher Site | Google Scholar
25. T. M. Sweda, I. S. Dolinskaya, and D. Klabjan, “Adaptive routing and recharging policies for electric vehicles,” Transportation Science, vol. 51, no. 4, pp. 1326–1348, 2017. View at: Publisher Site | Google Scholar
26. T. M. Sweda, I. S. Dolinskaya, and D. Klabjan, “Optimal recharging policies for electric vehicles,” Transportation Science, vol. 51, no. 2, pp. 457–479, 2017. View at: Publisher Site | Google Scholar
27. G. Macrina, L. Di Puglia Pugliese, F. Guerriero, and G. Laporte, “The green mixed fleet vehicle routing problem with partial battery recharging and time windows,” Computers & Operations Research, vol. 101, pp. 183–199, 2019. View at: Publisher Site | Google Scholar
28. G. Macrina, G. Laporte, F. Guerriero, and L. Di Puglia Pugliese, “An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows,” European Journal of Operational Research, vol. 276, no. 3, pp. 971–982, 2019. View at: Publisher Site | Google Scholar
29. P. Zhao, F. Liu, Y. Guo, X. Duan, and Y. Zhang, “Bi-objective optimization for vehicle routing problems with a mixed fleet of conventional and electric vehicles and soft time windows,” Journal of Advanced Transportation, vol. 2021, Article ID 9086229, 11 pages, 2021. View at: Publisher Site | Google Scholar
30. G. Desaulniers, F. Errico, S. Irnich, and M. Schneider, “Exact algorithms for electric vehicle-routing problems with time windows,” Operations Research, vol. 64, no. 6, pp. 1388–1405, 2016. View at: Publisher Site | Google Scholar
31. D. Goeke and M. Schneider, “Routing a mixed-fleet of electric and conventional vehicles,” European Journal of Operational Research, vol. 245, no. 1, pp. 81–99, 2015. View at: Publisher Site | Google Scholar
32. M. Keskin and B. Catay, “A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,” Computers & Operations Research, vol. 100, pp. 172–188, 2018. View at: Publisher Site | Google Scholar
33. V. Leggieri and M. Haouari, “A practical solution approach for the green vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 104, pp. 97–112, 2017. View at: Publisher Site | Google Scholar
34. S. Zhang, Y. Gajpal, S. S. Appadoo, and M. M. S. Abdulkader, “Electric vehicle routing problem with recharging stations for minimizing energy consumption,” International Journal of Production Economics, vol. 203, pp. 404–413, 2018. View at: Publisher Site | Google Scholar
35. X. Ren, H. Huang, S. Feng, and G. Liang, “An improved variable neighborhood search for bi-objective mixed-energy fleet vehicle routing problem,” Journal of Cleaner Production, vol. 275, Article ID 124155, 2020. View at: Publisher Site | Google Scholar
36. A. Amiri, S. Amin, and H. Zolfagharinia, “A bi-objective green vehicle routing problem with a mixed fleet of conventional and electric trucks: considering charging power and density of stations,” Expert Systems with Applications, vol. 213, Article ID 119228, 2023. View at: Publisher Site | Google Scholar
37. M. Bruglieri, F. Pezzella, O. Pisacane, and S. Suraci, “A variable neighborhood search branching for the electric vehicle routing problem with time windows,” Electronic Notes in Discrete Mathematics, vol. 47, pp. 221–228, 2015. View at: Publisher Site | Google Scholar
38. S. Ropke and D. Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows,” Transportation Science, vol. 40, no. 4, pp. 455–472, 2006. View at: Publisher Site | Google Scholar
39. C. Koc, “A unified-adaptive large neighborhood search metaheuristic for periodic location-routing problems,” Transportation Research Part C: Emerging Technologies, vol. 68, pp. 265–284, 2016. View at: Publisher Site | Google Scholar
40. D. Pisinger and S. Ropke, “A general heuristic for vehicle routing problems,” Computers & Operations Research, vol. 34, no. 8, pp. 2403–2435, 2007. View at: Publisher Site | Google Scholar
41. N. A. Kyriakakis, I. Sevastopoulos, M. Marinaki, and Y. Marinakis, “A hybrid Tabu search–Variable neighborhood descent algorithm for the cumulative capacitated vehicle routing problem with time windows in humanitarian applications,” Computers & Industrial Engineering, vol. 164, Article ID 107868, 2022. View at: Publisher Site | Google Scholar
42. C. Chen, E. Demir, and Y. Huang, “An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots,” European Journal of Operational Research, vol. 294, no. 3, pp. 1164–1180, 2021. View at: Publisher Site | Google Scholar
43. S. Voigt, M. Frank, P. Fontaine, and H. Kuhn, Hybrid Large Neighborhood Search For The Capacitated Vehicle Routing Problem And The Vehicle Routing Problem With Time Windows, SSRN, Rochester, NY, USA, 2022.
44. P. Hansen, N. Mladenovi´c, J. Brimberg, and J. A. M. Pérez, “Variable neighborhood search,” in Handbook of Metaheuristics, M. Gendreau and J.-Y. Potvin, Eds., pp. 57–97, Springer, Cham, Switzerland, 2019. View at: Google Scholar
45. C. Koc, O. Jabali, J. E. Mendoza, and G. Laporte, “The electric vehicle routing problem with shared charging stations,” International Transactions in Operational Research, vol. 26, no. 4, pp. 1211–1243, 2019. View at: Publisher Site | Google Scholar
46. M. Schiffer, S. Stütz, and G. Walther, “Are ECVs breaking even?—competitiveness of electric commercial vehicles in medium—duty logistics networks,” 2016, https://www.om.rwth-aachen.de/data/uploads/om-022016.pdf. View at: Google Scholar
47. Expert Systems with Applications and Ev Database, “Newest electric vehicles,” 2018, https://ev-database.org/. View at: Google Scholar
48. R. Xiong, Y. Zhang, J. Wang, H. He, S. Peng, and M. Pecht, “Lithium-ion battery health prognosis based on a real battery management system used in electric vehicles,” IEEE Transactions on Vehicular Technology, vol. 68, no. 5, pp. 4110–4121, 2019. View at: Publisher Site | Google Scholar

Copyright © 2023 Ya-ru Duan et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.