Research on the Operation Mode and Path Optimization of Mobile Charging Service for New Energy Vehicles ()
1. Introduction
The new energy vehicle mobile charging service industry refers to the industry that provides charging services for various types of new energy vehicles through movable intelligent charging robots (also referred to as mobile charging vehicles). This industry, together with the fixed charging service industry of new energy vehicles and the battery swap service industry of new energy vehicles (which can be subdivided into fixed battery swap service industry of new energy vehicles and mobile battery swap service industry of new energy vehicles), forms a new energy vehicle charging service industry in a broad sense, which is one of the indispensable key parts of the development process of the new energy vehicle industry.
At present, China’s new energy vehicle mobile charging service industry is still in the “blue ocean” stage in the market, although in recent years there have been more enterprises pouring into the new energy vehicle mobile charging service market, but compared with the traditional new energy vehicle fixed charging pile market, the mobile charging service market can still be considered in the early stage of development, the development potential is huge, in the mobile charging service industry of some leading enterprises (such as Fu Long Ma, Guo Xuan Hi-Tech, Dark Horse Force, Shitu Technology, etc.) is expected to occupy a larger market share of new energy vehicle charging in the future, and has good research value.
According to the existing research of domestic and foreign scholars on the mobile charging service of new energy vehicles, the academic community focuses more on the path optimization problem in the mobile charging service of new energy vehicles, and explores the mobile charging service scheme with the smallest cost or the largest benefit by considering the soft time window, cost and other factors, combined with the mileage and battery capacity of the mobile charging vehicle. As for the research on the operation model, the academic community focuses more on the exploration of the overall business model and operation process, and lacks the specific thinking chapter of a single enterprise or a type of enterprise. For the operation mode, this paper integrates and analyzes the current well-known or emerging mobile charging service operators of new energy vehicles at home and abroad through literature retrieval and enterprise research. In view of path planning, this paper uses heuristic algorithms to model, solve, and analyze the “multi-traveling salesman problem” of new energy vehicle mobile charging vehicles.
In general, through the study of the operation mode and path optimization of mobile charging services for new energy vehicles, we can deeply understand the advantages and challenges of the current supply of various mobile charging services in terms of commercial implementation. From the perspective of new energy vehicle mobile charging service operators, the research in this paper will promote enterprises to improve operational efficiency and optimize service quality. From the perspective of downstream user groups, the research in this paper will enhance the service experience of users and meet the growing charging needs of users.
2. Literature Review
2.1. Mobile Charging Service Operation Mode
At present, the operation mode of mobile charging services for new energy vehicles at home and abroad shows a situation of similar development in large dimensions and diversified development in small dimensions. The so-called large dimension refers to the fact that in the specific business practice process, the user (that is, the owner of the new energy vehicle that needs to be charged) places an order on the mobile phone APP or scans the code to enter a specific applet to make a charging appointment (in the case of roadside assistance, it can be through telephone call), and then the mobile charging robot in the specific scene realizes the subsequent charging operation of the new energy vehicle through the method of “pile looking for car/pile looking for person”. The small dimension refers to the different scenarios in which different enterprises operate mobile charging vehicles, the advantages of mobile charging vehicles are different, and the business focus of enterprises developing mobile charging vehicles is different.
In the process, Cui Shaohua believes that the mobile service is more flexible, and can provide services to customers at a designated location according to their request, or it can stay at a fixed location to provide services to customers nearby (Cui, 2019). In the original operation model, Qi Boshuo took into account the shortcomings of fixed charging piles, and believed that fixed charging stations could send “support” requests to mobile charging service providers, and recommend the optimal route to the fixed charging station for mobile charging vehicles after obtaining the geographic information and traffic information of the relevant road sections (Qi, 2018). In foreign countries, Hernandez-Moro has found that setting up multiple energy service stations can reduce logistics costs and improve service efficiency through the research on the operation mode of mobile charging services and the optimization of scheduling frameworks (Hernández-Moro & Martínez-Duart, 2013). And in recent years, Shahab Afshara et al. have found that MCS can be dispatched based on different scheduling strategies from MCS operators. The most popular strategies are first-come, first-served (FCFA), last next job (NJN), and earliest deadline first-served (EDFA) (Afshar, Macedo, Mohamed, & Disfani, 2021).
Starting from the specific new energy vehicle mobile charging service enterprises, according to the “2024 Mobile Charging Robot Research Report” released by Zuo Si Automotive Research Institute (the following company name is derived from the report), there will be more than 20 domestic enterprises operating new energy vehicle mobile charging vehicles in 2024 (Zuosi Automotive Research Institute, 2024).
From the perspective of enterprise scale, there are three listed companies (Guo Xuan Hi-Tech, Fu Long Ma, Yi Jia He) with R&D and operation of mobile charging robots as one of the main businesses, which support half of the R&D and operation of new energy vehicle mobile charging vehicles. In addition, there are many strong start-up companies/start-ups, although the scale of the enterprise is not large, but the group of such enterprises’ R & D technical team, operation and maintenance team are very professional, the development of mobile charging robot products in many regions of China in the specific scene has been successfully commercialized, for the new energy vehicle mobile charging service industry business practice has contributed a huge force, on behalf of the enterprise Dark Horse Force (Guo Guang Shun Neng), Zhong Neng Cong Cong, Shitu Technology, Pile Technology, Xiangyi Technology and so on.
From the perspective of enterprise types, the types of enterprises operating mobile charging services include OEMs (Zuosi Automotive Research Institute, 2024) (refer to the original intention of developing new energy vehicle mobile charging vehicles to cooperate with and improve their main product, new energy vehicles, which is equivalent to mobile charging vehicles as additional services provided by the enterprise for customers who purchase new energy vehicles) and energy enterprises (Zuosi Automotive Research Institute, 2024) (refer to its parent company or its own group or itself as an energy enterprise, and the excellent power technology and energy technology owned by the energy company will make the mobile charging vehicle products developed by the enterprise more advantageous than ordinary mobile charging vehicles in terms of reserve battery capacity, V2V maximum power, etc.), robot enterprises (Zuosi Automotive Research Institute, 2024) (this type of enterprise will focus on the research and development of robots, Therefore, the new energy vehicle mobile charging vehicle, which is also a robot, has good automation technology, system integration capabilities, etc., under the research and development of this type of enterprise), and technology companies (Zuosi Automotive Research Institute, 2024) (The technical R&D team is strong, and has deep insights and experience in the perception and navigation capabilities of mobile charging vehicles, data analysis and intelligent decision-making, human-computer interaction design, etc.), etc., and the products developed by different types of enterprises have different advantages, so they have different target customer groups. Starting from their own corporate characteristics and advantages, various types of enterprises have developed mobile charging robots for new energy vehicles that adapt to and meet different scenarios, which significantly expands the market size and market coverage of the new energy vehicle mobile charging service industry.
From the perspective of operation scenarios, the main operation scenarios of mobile charging services include high-speed service areas, parking lots of office buildings or shopping malls, parking lots of industrial parks, etc. (the scenario of roadside assistance services is in the roads of various cities). Specifically, as early as last year, Dark Horse Force had carried out a mobile charging operation pilot in the International Media Port on the west bank of the Xuhui Riverside River (the pilot product was G60 Xiao Hei, which is a mobile supercharging robot with integrated storage and charging (Dark Horse Force, 2023), and at the same time, another mobile charging product of the company, G30 Fubao has also been put into use in Shanghai K11 shopping center (Dark Horse Force, 2024). The mobile charging service “Tule Charging” has been carried out for new energy vehicles in some expressway service areas in Shandong, Zhejiang and other provinces and the new energy vehicle brands served include Tesla, BYD, NIO, Ideal, Xpeng, Zeekr, etc. (Shitu Technology, 2024). The FLMSD08XDY mobile charging robot of the Fu Long Ma brand can not only follow the large charging vehicle on the road to carry out emergency rescue work when new energy vehicles and various new energy vehicles lack power, but also make up for the lack of fixed charging piles in various parking lots, old communities and other venues (Fu, 2022). Guo Xuan High-Tech’s mobile charging robot has also been put into operation in Hefei, Anhui Province (Guo Xuan Hi-Tech, 2023). In addition, there are many companies with their own research and development of mobile charging robots, and are working hard or have successfully realized the commercial implementation of mobile charging products.
It should be added that when the upstream stakeholders of the new energy vehicle mobile charging service carry out the service, the general core business is to carry out the mobile charging of new energy vehicles in a fixed area (such as the parking lot of each scene mentioned above), and the operation business of the new energy vehicles (or new energy buses, new energy trucks, etc.) that dispatch mobile charging vehicles to various points in the city to exhaust the power on the road (or new energy buses, new energy trucks, etc.) only accounts for a small part of the mobile charging operators (even if they do not provide similar services, It is necessary for the owner of the new energy vehicle to call a tow truck to rescue by himself). At the same time, the number of enterprises specializing in the operation of new energy vehicle roadside assistance is relatively scarce among the many operating enterprises in the new energy vehicle mobile charging service industry, and the scale of the enterprise is relatively small, and there are more development prospects in the future.
2.2. Mobile Charging Service Path Planning
2.2.1. Path Planning Issues
Path planning problems are a classic combinatorial optimization problem whose main idea is how to arrange different vehicles (or other similarly moving objects) to visit different “customer points” in order to minimize the total distance traveled or consumption cost while the constraints are met. As far as the operation scenario of mobile charging service for new energy vehicles is concerned, whether it is the charging scenario of a fixed area or the charging scenario of roadside assistance, it is inseparable from the planning of the mobile charging path of the mobile charging vehicle.
In the academic research on path planning, Meng Ting introduced two types of customers with the same time window, proposed a model with the shortest driving path for electric vehicles in delivery services, and conducted sensitivity analysis on this basis (Meng, 2023). Mohd Kamarul Irwan Abdul Rahim et al. worked to determine the optimal solution of the single-cycle vehicle routing problem (SP-VRP), established an optimization model that accurately reflected the real-world problem, and simulated the transportation problem (Abdul Rahim, Radzuan, Nadarajan, Bolaji, & Ramli, 2024). Herman Mawengkang et al. focused on vehicle routing with relaxation time windows to determine the most cost-effective route for a fleet of vehicles with various constraints and nonlinear relationships (Mawengkang, Syahputra, Sutarman, & Salhi, 2024). Liu et al. cleverly integrated the simulated annealing algorithm into the Hybrid Variable Neighborhood Search (HVNS) algorithm, which enhanced the global search capability and innovatively solved the inventory path problem of customers with small volume-to-sales ratio (IRPSC) (Liu, Zuo, & Wu, 2024). Zhou Zhongbao et al. effectively avoided the impact of road damage on blood emergency distribution after the disaster and ensured the timely delivery of relief materials in the disaster environment by studying the problem of blood emergency distribution based on multi-UAV, which effectively solved the problem of solving the model under large-scale examples, significantly improved the solution efficiency, and provided a wake-up call for the improvement of the model in this paper, making the constraints of this paper more comprehensive, which is in line with the characteristics of emergency rescue, one of the key application modes of mobile charging vehicles (Zhou, Chen, Li, Sun, & Shi, 2024). In order to solve the problem of path planning of emergency rescue vehicles, Wu Jiabin incorporated safety factors into the path planning of vehicles, and proposed a timed collaborative planning method for emergency rescue vehicle paths under the dynamic road network, striving to take into account the driving safety of rescue vehicles (Wu, 2021).
In addition, Kassem Danach focused on the application of machine learning in VRP problems, exploring how to optimize routing strategies by predicting demand patterns, identifying valid paths in real time, and dynamically adjusting (Danach, 2024). Chen et al. abstracted the path optimization problem of new energy mobile charging vehicles into a team orientation problem with soft time windows and capacity constraints, and then solved the problem by designing a maximum and minimum ant colony optimization algorithm, which effectively avoided the defect of the traditional ant colony algorithm by introducing the maximum and minimum pheromone concentration limit, and improved the stability of the algorithm (Chen, Dong, & Yu, 2020). Yosephine et al. successfully solved the sensitivity of demand in the medical e-commerce field to price and lead time by combining transportation consolidation and vehicle routing problems (VRP) to establish a model that considers demand dynamics, and contributed to the optimization of corporate profitability (Yosephine, Shin, & Lee, 2024). Villamizar M A et al. successfully combined the Google Maps API with mathematical modeling to solve real-time VRP problems, in which the hybrid integer linear programming (MILP) model played a key role (Muñoz-Villamizar, Faulin, Reyes-Rubiano, Henriquez-Machado & Solano-Charris, 2024).
In general, the path planning problem has a complex theoretical background and application requirements. There are great flexibility and challenges in multi-objective optimization, multi-algorithm selection and optimization, real-time and authenticity requirements, etc. With the iterative upgrading of artificial intelligence technology and algorithms, the path planning problem will receive more extensive attention and in-depth research in the future, providing a good solution for practical application.
2.2.2. Related Algorithms
(1) Introduction to simulated annealing algorithm
Simulated annealing algorithm is an optimization algorithm inspired by the solid annealing process in physics, its principle is to achieve the lowest stable state of system energy by simulating the heating and then slow cooling process of solid substances, and so on to solve the optimization problem, by controlling the “temperature” parameter, so that the algorithm in the solution search process, with a certain probability to accept the solution worse than the current solution, so as to jump out of the local optimum, explore a larger solution space, the algorithm solution process is shown in Figure 1, often used to solve the engineering design of structural optimization, Image segmentation in computer image processing and path optimization in combinatorial optimization.
Figure 1. The solution process of the simulated annealing algorithm.
(2) Introduction to ant colony algorithm
The principle of ant colony algorithm is to simulate the behavior of ants releasing and perceiving pheromones when they are foraging, regard the potential solution in the optimization problem as ants, use the positive feedback mechanism of pheromones to guide ants to search in the solution space, and gradually accumulate the pheromone concentration on the excellent path, so as to attract more ants to choose the path, and finally realize the process of efficiently finding a near-optimal solution from a large number of candidate solutions, as shown in Figure 2. It is particularly suitable for solving optimization problems with complex search spaces and a large number of potential solutions, such as the traveling salesman problem and vehicle routing planning.
Figure 2. Ant colony algorithm solution process.
3. Mobile Charging Service Path Planning Analysis
3.1. Overview of Path Planning Scenarios
In fact, in the general mobile charging service operation mode of path planning, scheduling planning (the scheduling here refers to the situation of multiple types of mobile charging vehicles and multiple types of new energy vehicles, that is, in the case of considering the heterogeneity of both mobile charging vehicles and new energy vehicles, when a mobile charging vehicle will charge which new energy vehicle, whether it is necessary to return to supplement the electric energy after the charging is completed, and then charge which new energy vehicle, in order to flexibly arrange the way of mobile charging vehicles, There are many modeling factors that can or must be considered, including but not limited to the input/output charging power of each mobile charging vehicle), the reserve power of each mobile charging vehicle, the battery capacity of the new energy vehicle to be charged, and whether to carry out path planning for the path of the mobile charging vehicle to the new energy vehicle (i.e., the shortest path is solved by algorithms such as A*, if the shortest path is not actually solved, A way to reduce the complexity is to remove the straight-line distance between the two points of direct departure and arrival to the driving speed of the mobile charging vehicle, and then the arrival time can be obtained, and then the analysis of the subsequent charging and charging of the mobile charging vehicle can be carried out), whether to consider the time of the mobile charging vehicle itself to replenish the power, whether there is an influx of new charging demand when the mobile charging vehicle is charging service, whether to consider the soft and hard time windows, etc., and select different decision variables, constraints and objective functions (the potential goal can be to maximize the revenue, Shortening the path, maximizing the number of service vehicles, etc.), will make the final solution result show a relatively large difference. According to different research scenarios, different weights are given to each modeling factor, which determines whether the final solution of the path planning problem is practical and efficient.
After clarifying the importance and content of the path planning problem of mobile charging vehicles for new energy vehicles, it is a key part to improve the value of the solution results by selecting the specific operation mode in real life for exploration and solving. On the basis of the collation and analysis of the above operation mode and path planning, this paper selects mobile charging vehicles on the road to analyze the path planning problem of road rescue for new energy vehicles.
In the real new energy vehicle roadside assistance (road assistance in a broad sense includes not only the rescue of new energy vehicles that cannot be driven on the road, but also the rescue of new energy vehicles whose owners want to drive but find that the power is exhausted) in various locations, it is generally the customer who calls by phone or sends a message on the applet to enable the relevant enterprises with emergency charging services to rescue. After receiving an urgent need from a customer, enterprises often dispatch their own mobile charging robots to help. In this process, it is often a rescue vehicle composed of small mobile charging robots placed on top of ordinary medium and large vehicles. The mobile charging rescue vehicle in the simulated annealing algorithm/ant colony algorithm below is equivalent to the combination of these two vehicles, and the new energy private cars and medium and large vehicles (such as buses, medium and large trucks, sanitation vehicles, etc.) that have charging needs and want to accept the combination of large charging vehicles and small mobile charging robots above for charging services are the customers in the simulated annealing algorithm/ant colony algorithm below. Part of the reason for the establishment of this combination is that the driving speed of the small mobile charging vehicle itself is relatively slow, and it is difficult to quickly reach the customer who needs to be charged urgently compared with the situation of mobile charging in a fixed parking lot; Another part of the reason is that some large charging vehicles are difficult to enter underground garages, back streets and alleys and other areas, and small mobile charging robots can play their own flexibility after arriving near the target customer point with medium and large vehicles, and go to the customer point for rescue on their own, that is, the two play a complementary role.
In response to this situation, the team abstracted it into the “multi-travel salesman problem” (a variant of the traveling salesman problem), that is, how multiple mobile charging rescue vehicles can work together to run all customer points in the shortest distance from the initial location, so as to help enterprises optimize the quality of mobile charging services and improve the efficiency of actual operations. It should be noted that roadside assistance can be said to be a special existence in the mobile charging service of new energy vehicles, and the mobile charging vehicles under the ordinary fixed parking lot come by themselves for new energy vehicles. Compared with the situation of replenishing energy, returning to replenish energy by itself, and then repeating the cycle, after the mobile charging rescue vehicle arrives at the target customer point in the roadside rescue scenario, it often does not fully charge the new energy vehicle by the mobile charging vehicle and then leaves it like in the case of a fixed parking lot, but replenishes the energy of the new energy vehicle on the road or in other locations for about 5 - 10 minutes, ensuring that it can be driven to the nearby fixed charging pile area for follow-up energy replenishment. In addition, mobile charging robots in roadside assistance situations are often specially manufactured (usually carrying large-capacity storage and charging equipment), so they generally do not need to recharge themselves multiple times a day. Therefore, under the dual factors of short charging time and large capacity, the research and modeling of the “multi-traveling dealer problem” of roadside assistance can appropriately reduce or ignore the weight of the factors of self-charging and charging of mobile charging vehicles, and focus on the path planning from the starting point of mobile charging vehicles to the target customer points.
3.2. Path Planning Modeling
At present, we use the simulated annealing algorithm and ant colony algorithm to model and solve the multi-traveling salesman problem in the path planning of mobile charging vehicles. The multi-dealer problem is that in the case of multiple travel agents (i.e., multiple mobile charging rescue vehicles), each traveling dealer needs to complete the customer nodes assigned to it, and the sum of the customer nodes passed by each travel dealer should be the whole of all customer nodes. In other words, the scenario we use to simulate the algorithm is how each vehicle plans its own customer nodes to visit and the corresponding route when multiple mobile charging rescue vehicles are running at the same time, so that the overall path (i.e., from the starting point to all customer nodes and back to the starting point) is the shortest and the overall efficiency is optimal. It is important to emphasize that there are many types of multi-travel dealer problems, the most common of which are the following two situations: one is when multiple travel agents depart from the same location and return to a common initial location after running all the customer points together; The other is that multiple travel agents depart from different locations and return to their different starting locations after running through all the customer points together. In this article, we will choose to explore the first mode (which is more in line with the logic of the actual operation of the enterprise). In this scenario, let’s assume that there are 3 mobile charging rescue vehicles, 20 customers who need to be charged, and these 23 things are all in different locations in the city (the coordinates of each location are randomly generated using the PyCharm code, and of course the initial location of the 3 mobile charging rescue vehicles is the same).
Let’s do the modeling, first of all, we give the constants and decision variables under the multi-traveling salesman problem, as shown in Table 1:
Table 1. Modeling variables for the multi-traveling salesman problem.
symbol |
interpretation |
n |
The number of mobile charging rescue vehicles is set as a constant 3 in this article |
m |
The number of new energy vehicles that need to be charged is set as a
constant of 20 in this article |
djk |
Indicates the distance between customer J and customer K, J ∈ [1, m], K ∈ [1, m] |
d0j |
Indicates the distance between the departure position of the three mobile charging rescue vehicles and the customer j, j ∈ [1, m] |
xij |
The customer allocation variable, which is a 0 - 1 variable, indicates whether the mobile charging rescue vehicle i serves customer j, where i ∈ [1, n], j ∈ [1, m] |
yijk |
The path sequence variable, which is also a 0 - 1 variable, indicates whether the mobile charging rescue vehicle i drives straight from customer j to
customer k, where i ∈ [1, n], j ∈ [1, m], k ∈ [1, m], note j ≠ k |
first(i) |
The first customer point where the number i mobile charging rescue
vehicle arrived |
last(i) |
The last customer point where the number i mobile charging rescue
vehicle arrived |
This is followed by the objective function, in which the goal is to minimize the total distance traveled by all vehicles, noting that this total path distance includes the distance of the three traveling agents (i.e., the three mobile charging rescue vehicles) from the same location to their first customer point and the distance of the three traveling agents from their respective last customer points to a common starting location. Let the total path length be Z, then the objective function can be written as follows in the form of Equation (1) (where the second part of the sum equation represents the sum of the distances of all mobile charging rescue vehicles from the common starting position to the first customer point on their respective paths, and the third part represents the sum of the distances of all mobile charging rescue vehicles from the last customer point on their respective paths back to the common starting position, and according to the customer variable xij and the path sequence variable yijk information, it can be assigned to determine the first and last customer corresponding to each vehicle):
(1)
Then there is the constraint part, Equation (2) gives the constraint of the total number of service customers (the total number of customers served by all mobile charging and rescue vehicles should be equal to the total number of customers), Equation (3) gives the service constraint of only one mobile charging and rescue vehicle per customer, and Equation (4) to Equation (6) gives the constraint of vehicle path continuity (the in-in and out-of-customer degrees of customer points should be consistent, where the logic of the beginning and end customer points is slightly different, But the essence is the same), as shown in the following equation:
(2)
(3)
(4)
(5)
(6)
Of course, in order to simplify the scenario, the time for the mobile charging rescue vehicle to charge the customer and the time required to replenish its own power is not taken into account (the rationality of this operation has been demonstrated above), if these factors are taken into account, it will make the whole model more complex and uncertain.
Finally, some of the key parameters of the two heuristics used in the multi-traveling salesman problem scenario are introduced, which are as follows:
In the simulated annealing algorithm, we set the initial temperature to 1000, which determines the exploration range when the model starts to run, and the higher the initial temperature can make the simulated annealing algorithm accept more random solutions, so as to avoid falling into the local optimum. In addition, we also set the maximum number of iterations to 1000, which means that the algorithm will perform up to 1000 iterations to try to find the optimal solution in the given scenario. This parameter determines the maximum length of time the algorithm can run, and higher values usually increase the chance of finding the global optimal solution, but also increase the computation time. We set the cooling rate to 0.995, which refers to the rate at which the temperature decreases, which affects the speed at which the algorithm transitions from the exploration phase to the utilization phase. Table 2 summarizes the above information:
Table 2. Parameters of simulated annealing algorithm.
Simulate annealing algorithm
parameters |
Interpretation |
Init temperature |
Initial temperature, the exploration range at which the model starts running |
Max iteration |
Maximum number of iterations, the maximum
number of times the algorithm is executed |
Cooling rate |
Cooling rate, i.e., the rate at which the temperature decreases |
In the ant colony algorithm, the num ants represents the number of ants used in each iteration, which is set to 10, which determines the number of ants in the algorithm and affects the breadth of the search. Num iterations represent the number of iterations, which is set to 100, which controls the running time of the algorithm and the depth of the search; alpha represents the importance factor of pheromones, which is set to 1 here; beta represents the importance factor of the heuristic function, which is set to 2 here; alpha and beta adjust the influence of pheromones and heuristics on path selection, respectively. rho represents the volatility coefficient of pheromones, which is set to 0.1, which controls the rate of evaporation of pheromones, which affects the frequency of pheromone renewal, and Q, which is the increment factor of pheromones, which is set to 1, which affects the intensity of pheromone renewal. By adjusting different parameters, the results of the algorithm will also show relatively large differences. Table 3 lists the above information:
Table 3. Parameters of ant colony algorithm.
Ant colony algorithm parameters |
interpretation |
Num ants |
The number of ants used in each iteration |
Num iterations |
The number of iterations |
alpha |
The importance factor of pheromones |
beta |
The importance factor of the heuristic function |
rho |
The volatility coefficient of pheromones |
Q |
Pheromone increment factor |
3.3. Display of Path Planning Results
The results of the simulated annealing algorithm and the ant colony algorithm in the multi-traveling salesman problem are shown below.
The first is the demonstration of the results of the simulated annealing algorithm, where Figure 3 shows the position path diagram of different mobile charging rescue vehicles when charging all customers together:
Figure 3. Position path diagram of the simulated annealing algorithm.
Vehicle positions:
[[33.87125017 58.09157286]]
Customer positions:
[[93.8017599 60.44067342]
[93.7015287 18.83987041]
[70.9704665 64.88674622]
[79.36421558 13.45327923]
[8.6583173 14.52319336]
[63.06351672 25.34055693]
[59.85192517 72.63193706]
[2.31827281 29.42605074]
[30.88846813 66.80333431]
[89.06251341 46.74213269]
[59.24906421 73.80210307]
[98.98077778 78.7193138 ]
[93.10713922 15.73747427]
[91.66206498 7.51437211]
[19.91920396 41.9697912]
[60.44052081 82.10836865]
[93.94384037 76.00301703]
[21.69847498 30.22235652]
[7.43591025 48.2283341]
[69.79168959 77.68650454]]
Best solution (per vehicle): [[6, 7, 12, 4, 5, 14, 3], [19, 9, 20, 16, 15, 11, 10], [8, 17, 2, 13, 18, 1]]
Best cost (total distance): 749.2660293061824
The second is the result of the ant colony algorithm, and Figure 4 shows the initial position of different mobile charging rescue vehicles and customers, and the path trajectory of each mobile charging rescue vehicle from a common initial location, passing through a series of customer points, and returning to the initial common initial location:
Figure 4. Location diagram of ant colony algorithm.
Customer Coordinates:
Customer 1: [32.94262605 4.99866444]
Customer 2: [23.9607542 99.63901976]
Customer 3: [ 7.1929984 64.01668254]
Customer 4: [34.13773537 17.05283279]
Customer 5: [20.28779182 56.91204626]
Customer 6: [74.65360066 25.419215]
Customer 7: [17.19182586 69.04421416]
Customer 8: [20.63129817 86.38269555]
Customer 9: [42.44428481 60.32225488]
Customer 10: [48.11499221 54.82571012]
Customer 11: [54.90298123 2.54388616]
Customer 12: [26.53569162 57.38969745]
Customer 13: [91.11651403 55.5892018 ]
Customer 14: [28.21557451 71.57375146]
Customer 15: [66.54350322 79.23747933]
Customer 16: [12.39779204 75.42734804]
Customer 17: [28.96288439 89.50701021]
Customer 18: [73.27198809 66.58209314]
Customer 19: [69.0260771 1.56282346]
Customer 20: [58.6635478 40.60030945]
Vehicle Starting Position:
[51.09485603 33.81719162]
Path for Vehicle 1:
Customer 2 at [23.9607542 99.63901976]
Customer 18 at [73.27198809 66.58209314]
Customer 15 at [66.54350322 79.23747933]
Customer 17 at [28.96288439 89.50701021]
Customer 9 at [42.44428481 60.32225488]
Customer 19 at [69.0260771 1.56282346]
Total distance: 246.20167125004122
Path for Vehicle 2:
Customer 3 at [ 7.1929984 64.01668254]
Customer 7 at [17.19182586 69.04421416]
Customer 12 at [26.53569162 57.38969745]
Customer 16 at [12.39779204 75.42734804]
Customer 8 at [20.63129817 86.38269555]
Customer 13 at [91.11651403 55.5892018 ]
Customer 6 at [74.65360066 25.419215 ]
Total distance: 199.05017113279433
Path for Vehicle 3:
Customer 20 at [58.6635478 40.60030945]
Customer 10 at [48.11499221 54.82571012]
Customer 4 at [34.13773537 17.05283279]
Customer 1 at [32.94262605 4.99866444]
Customer 5 at [20.28779182 56.91204626]
Customer 14 at [28.21557451 71.57375146]
Customer 11 at [54.90298123 2.54388616]
Total distance: 245.71365997500274
Total distance for all vehicles combined: 690.9655023578383
As can be seen from the results of the above two algorithms, the two algorithms are established by different models, and the path diagram/coordinate diagram and the shortest path result display are given after running the program. Taking the simulated annealing algorithm as an example, the path that travel dealer 1 (mobile charging rescue vehicle 1, the same below) needs to walk is [6, 7, 12, 4, 5, 14, 3], travel dealer 2 is [19, 9, 20, 16, 15, 11, 10], and travel dealer 3 is [8, 17, 2, 13, 18, 1]. The sum of the shortest path is 749.2660293061824, which means that the three traveling merchants (three mobile charging rescue vehicles) will be charged according to their respective above paths, which will maximize the time and cost savings and improve operational efficiency (without considering the time required for charging and charging; In fact, if the amount of electricity that each customer needs to charge is the same, and the charging method of each mobile charging rescue vehicle and the time it takes to charge a customer are also the same, then the program operation results of the modeling of the above-mentioned multi-traveling salesman problem can also be used as a reference), helping the high-quality development of relevant mobile charging service operators.
In fact, the above-mentioned situation of using the simulated annealing algorithm and ant colony algorithm is based on the ideal situation, that is, ignoring the road obstacles that may be encountered during the driving process of the mobile charging vehicle, and also ignoring the time it takes for the mobile charging vehicle to charge the new energy vehicle and replenish its own power. From the perspective of algorithms, for the simulated annealing algorithm, because the structure of the algorithm is relatively simple, we can adjust the temperature and other parameters to meet different path optimization and response requirements when encountering dynamic data, unexpected situations, and temporary needs. Of course, when the simulated annealing algorithm processes dynamic data, there is a relatively high probability that the simulated annealing algorithm can adapt to the new traffic conditions through the frequent “annealing” process, which in turn leads to the increase of running time and the increase of computational overhead. For the ant colony algorithm, the structure and characteristics of the algorithm determine that it will take a long time to obtain a new optimal path in the face of sudden new requirements in path planning, and if new conditions continue to emerge/influx during this period, the solution speed of the algorithm will not be able to keep up with the speed of the emergence of requirements, resulting in the failure of the overall path planning. In addition, given the heterogeneity of the new energy vehicles that need to be charged, the end time for different mobile charging vehicles to complete the charging of the corresponding new energy vehicles is also different, so the algorithm will encounter greater challenges when studying larger and more complex problems such as the path planning of mobile charging vehicles in a day. Therefore, in the follow-up research, the particle swarm optimization algorithm and deep reinforcement learning methods are considered for analysis.
3.4. Solving Examples
After path planning, this paper performs a statistical analysis after multiple runs of the modeling solution of the above multi-traveling salesman problem (taking the simulated annealing algorithm as an example). Specifically, for each specific set of parameter combinations (consisting of different maximum iteration, initial temperature and cooling rate), perform a cycle which named “for _ in range (10)” in the program, ensuring that each parameter combination independently runs the simulated annealing algorithm 10 times, and then collects enough data to calculate the average cost and standard deviation for that parameter combination. The optional values for the maximum number of iterations are [500, 1000, 2000, 5000], the optional values for the initial temperature are [500, 1000, 2000], and the optional values for the cooling rate are [0.99, 0.995, 0.999].
Table 4 summarizes the average cost and standard deviation of each combination of parameters in the case analysis section.
Table 4. Analysis of the simulated annealing algorithm.
Maximum
iteration count |
Initial
temperature |
Cooling rate |
Average shortest path |
Standard deviation of cost |
500 |
500 |
0.99 |
725.4347517 |
42.70146154 |
500 |
500 |
0.995 |
847.297624 |
32.27637752 |
500 |
500 |
0.999 |
868.2971549 |
30.54879418 |
500 |
1000 |
0.99 |
758.241853 |
63.53347462 |
500 |
1000 |
0.995 |
883.9684024 |
41.49269855 |
500 |
1000 |
0.999 |
867.0883013 |
35.72874076 |
500 |
2000 |
0.99 |
788.3734698 |
49.23413909 |
500 |
2000 |
0.995 |
881.117345 |
40.78799264 |
500 |
2000 |
0.999 |
882.5105472 |
51.90677755 |
1000 |
500 |
0.99 |
693.2301814 |
61.75730718 |
1000 |
500 |
0.995 |
668.646896 |
71.15866095 |
1000 |
500 |
0.999 |
850.3284694 |
47.97474455 |
1000 |
1000 |
0.99 |
656.7123445 |
49.31433559 |
1000 |
1000 |
0.995 |
690.3013187 |
37.42626652 |
1000 |
1000 |
0.999 |
862.528858 |
44.88876202 |
1000 |
2000 |
0.99 |
685.4849418 |
82.60560665 |
1000 |
2000 |
0.995 |
743.6289012 |
68.98494233 |
1000 |
2000 |
0.999 |
873.0602822 |
33.92394415 |
2000 |
500 |
0.99 |
714.1604695 |
31.12133802 |
2000 |
500 |
0.995 |
671.0875065 |
64.42842634 |
2000 |
500 |
0.999 |
772.7477383 |
33.91880239 |
2000 |
1000 |
0.99 |
662.191588 |
65.29931341 |
2000 |
1000 |
0.995 |
676.8324676 |
33.6845098 |
2000 |
1000 |
0.999 |
830.2667395 |
20.45389734 |
2000 |
2000 |
0.99 |
674.1637213 |
45.38708872 |
2000 |
2000 |
0.995 |
658.105295 |
68.05125879 |
2000 |
2000 |
0.999 |
807.7119936 |
32.76934851 |
5000 |
500 |
0.99 |
686.954778 |
34.39527661 |
5000 |
500 |
0.995 |
643.9671385 |
43.1340493 |
5000 |
500 |
0.999 |
623.021368 |
43.62300355 |
5000 |
1000 |
0.99 |
634.9248702 |
67.93623125 |
5000 |
1000 |
0.995 |
670.2227134 |
56.6866003 |
5000 |
1000 |
0.999 |
638.6828019 |
28.3294308 |
5000 |
2000 |
0.99 |
692.0244901 |
67.2689553 |
5000 |
2000 |
0.995 |
661.1942836 |
44.11465777 |
5000 |
2000 |
0.999 |
658.2436893 |
47.94537923 |
Based on the results of the above examples, we analyze the following results:
1. The influence of preset parameters on the results
1) Maximum number of iterations: It can be seen from the data that when the maximum number of iterations increases from 500 to 5000, the length and standard deviation of the average shortest path show a certain downward trend in most cases, especially when the cooling rate is high (such as 0.999), which indicates that increasing the number of iterations helps the algorithm to explore the solution space more fully, so as to find a better solution.
2) Initial temperature: The setting of the initial temperature also has a significant impact on the results. In general, a higher initial temperature helps the algorithm jump out of the local optimal solution in the early stage, but may require more iterations to converge in the later stage. As can be seen from the example, when the initial temperature increases from 500 to 2000, the change of the length and standard deviation of the mean shortest path is not completely consistent, which indicates that the choice of initial temperature needs to be adjusted according to the specific problem.
3) Cooling rate: The cooling rate determines the rate at which the temperature drops. A lower cooling rate (e.g., 0.99) gives the algorithm more time to search at the current temperature during the cooling process, which may lead to a better solution, but it may also cause the algorithm to run for a longer time. A higher cooling rate (e.g., 0.999) accelerates the cooling process, which may make the algorithm converge to a solution faster, but it is not necessarily the global optimal solution.
2. Stability of results
The standard deviation reflects the difference between the results of multiple runs, and it can be seen from the data that the size of the standard deviation is closely related to the setting of the algorithm parameters, and under some combinations of parameters (such as the maximum number of iterations is 5000 and the cooling rate is 0.999), the standard deviation is relatively small, indicating that the stability of the algorithm results is high.
3. Satisfaction with the results
When the mean shortest path and standard deviation are taken together, no single combination of parameters performs optimally in all cases. However, for some specific problems or goals (e.g., pursuing a shorter average shortest path or a more stable solution), a combination of parameters can be chosen, e.g. if the goal is to find the shortest possible average shortest path, then a higher maximum number of iterations, a moderate initial temperature, and a lower cooling rate can be considered. In addition, the simulated annealing algorithm is a heuristic algorithm, and its results may be affected by the initial solution, so if possible, it is possible to try more different initial solutions to evaluate the algorithm.
It is important to note that the program on which the above run results depend, each time the simulated annealing algorithm is run, the customer location and the mobile charging rescue vehicle position are randomly generated once in the module that generates the sample data at the beginning, and are not regenerated throughout the process. Therefore, for multiple runs of different algorithm parameter combinations, the randomly generated positions of each mobile charging rescue vehicle and customer node are the same and will not change, which also makes the results of the above program run control the “variables”, and the conclusion analysis is more reliable.
4. Conclusion
On the basis of revealing the characteristics of different enterprise operation modes, the results show that the operation efficiency and user satisfaction of mobile charging services can be effectively improved by adopting advanced autonomous driving technology and mobile energy storage system, combined with intelligent path planning algorithm. In the analysis of the “multi-traveling dealer problem” in the roadside assistance scenario, this paper successfully uses the heuristic algorithm to solve the operation path of the mobile charging vehicle, and then solves the example by running the program several times, which affirms the effectiveness of finding a better solution and a better travel path by adjusting the algorithm parameters. The research also finds that although the mobile charging service market is still in the early stage of development, some companies have achieved commercialization and market recognition through technological innovation and optimized operation strategies. In addition, the introduction of vehicle-to-network interaction (V2G) mode provides a new growth point for mobile charging services, showing the great potential of new energy vehicles to integrate and interact with the power grid.
However, there are certain limitations to this paper. For example, the data in this article is mainly derived from public information and existing literature, which may not fully reflect the dynamic changes in the market. In addition, the path optimization model in this paper does not yet consider all variables in actual operation, such as charging time, user behavior, etc.
Future research can further explore the adaptability and sustainability of different operating models in different market environments, and how to promote the healthy development of the mobile charging service industry through policy support and technological innovation. At the same time, with the continuous expansion of the new energy vehicle market, the business model and operation strategy of mobile charging services also need to be continuously adjusted and optimized to meet the new needs of the market. In the problem of path planning of mobile charging vehicles, it is planned to apply the path planning algorithm to a wider range of real-world operation scenarios, and to collect data and solve the algorithm while considering more practical factors, so as to further verify and optimize the effectiveness of the algorithm. In addition, it is planned to explore the applicability and flexibility of algorithms in different scales and complexity of operation environments, and at the same time study how to combine path planning algorithms with other operation management decisions, in order to achieve more comprehensive operation optimization, and strive to make the research results closer to the current business practice and make better theoretical contributions to specific business practices.
In conclusion, this paper provides a useful reference and guidance for the high-quality development of the new energy vehicle mobile charging service industry, and provides decision-making support for relevant enterprises and policy makers.
Funding
This work was supported by the National Natural Science Foundation of China (No. 72074076).