CN111222705B

CN111222705B - Nonlinear charging vehicle path optimization method

Info

Publication number: CN111222705B
Application number: CN202010027852.5A
Authority: CN
Inventors: 李俊青; 邓佳文; 桑红燕; 段朋
Original assignee: Liaocheng University
Current assignee: Liaocheng University
Priority date: 2020-01-10
Filing date: 2020-01-10
Publication date: 2023-11-24
Anticipated expiration: 2040-01-10
Also published as: CN111222705A

Abstract

The present invention relates to the field of delivery path optimization. An object is to provide a method for optimizing an electric vehicle path with a time window and a nonlinear constraint, comprising: s1, expanding vehicle type parameters in the existing SOLOMON calculation example and reading the task of the calculation example according to the vehicle type problem of the electric vehicle; s2: determining an optimized target and constraint conditions; s3: providing a grading mode to determine customer satisfaction; s4: optimizing a path solution by adopting an improved differential evolution algorithm; s5: a charge amount adjustment strategy is proposed to optimize a path solution; s6: a negative workload restoration strategy is proposed to optimize the path solution; s7: and issuing the path optimization scheme to each delivery vehicle. The invention can improve the distribution efficiency and reduce the distribution cost.

Description

Nonlinear charging vehicle path optimization method

Technical Field

The invention relates to the field of distribution path optimization, in particular to a nonlinear charging vehicle path optimization method.

Background

Along with the rapid development of economy, the traffic industry also rapidly develops. But with the attendant serious environmental and resource problems. To solve these problems, the phenomenon that electric vehicles replace conventional fuel vehicles is becoming more and more common. The development of batteries and charging technology also promotes the rapid development of electric vehicles, and accelerates the construction work of charging infrastructure of the electric vehicles, thereby better promoting the popularization of the electric vehicles. In the logistics distribution process, the electric automobile is used for distribution, so that the environment can be protected, and the energy consumption can be effectively reduced.

In recent years, the vehicle path problem (vehicle routing problem, VRP) has been extensively studied since the first time it was proposed by Dantzig and Ramser in 1959. At present, a popular study on VRPs is a time windowed VRP (vehicle routing problem with time windows, VRPTW) which is a process whereby a group of vehicles can start from a warehouse to serve geographically dispersed customers at the lowest cost, eventually returning to the warehouse, while meeting customer time window and vehicle capacity constraints. VRPTW is typically an NP-hard problem. Thus, a variety of heuristic algorithms have been proposed to address this type of problem. Solomon (1987) considered a heuristic for solving VRP, where the insert heuristic showed excellent performance. Thereafter, various algorithms such as Tabu Search (TS), branch-and-place algorism (LS), local Search (LS), large neighborhood search (large neighborhood search, LNS) and iterative local search (iterated local search, ILS) have been proposed for such complex optimization problems.

In addition, electric vehicles (electric vehicles, EVs) are increasingly being combined with VRPs in a global energy-saving and environment-friendly large background. Some scholars have tried to combine VRP with environmental concepts and Bektas and Gilbert (2011) have proposed pollution-routing process (PRP) which takes into account the costs of greenhouse gas emissions, fuel, total travel time.And MilLer-Hooks (2012) propose a green vehicle path problem (green vehicle routing problems, GVRP) that can be overcome with alternative fuel stations (alternative fuel stations, AFS) to limit the range of vehicle service. Bruglieri et al (2019) propose a path-based algorithm to solve GVRP, zhang et al (2018) propose the use of Ant Colony (AC) to reduce the electric vehicle energy consumption problem. However, electric vehicles cannot provide a route that is too long unless charging stations are provided along the way. In summary, the electric vehicle path problem (electric vehicle routing problem, EVRP) has two core problems: one how to determine the location of the charging station and the other how to be electricThe car is charged.

In order to make EVRP more realistic, many students attempt to select the location of the charging station. Adderly et al (2018) propose measures such as: the number of charging stations of the main trunk line is increased to cope with emergency such as natural disasters. Breunig et al (2019) propose a two-stage EVRP that uses dynamic programming (dynamic programming, DP) to obtain the optimal location of charging stations on a two-stage line. A great deal of literature is devoted to the problem of how to charge electric vehicles. Desamtoniers et al (2016) propose to reduce the charge capacity of electric vehicles but increase the number of charges, and the experimental results show better than full charge. Keskin and bulent (2018) propose three different types of charging stations to solve the charging problem on the line, namely charging stations of normal, fast and ultra fast charging modes.The current, voltage, and charge level curves are typically plotted as a function of time, as described by et al (2012). Most scholars assume the charging process as a linear charging process. However, in real life, the charging process is actually a nonlinear charging process that varies with time, and a small proportion of the operators assume a nonlinear charging process. The EVRP of the nonlinear charging constraint should be more studied than the EVRP of the linear charging constraint.

Furthermore, in the last few years, many scholars have proposed many types of heuristic algorithms to solve the real optimization problem. Such as: artificial bee colony algorithms (artificial bee colony, ABC), tabu search algorithms (tabu search, TS), genetic algorithms (genetic algorithm, GA) and differential evolution algorithms (differential evolution, DE). Among these heuristic algorithms, the differential evolution algorithm is considered a simple, reliable, robust and population-based algorithm that uses the differences between the current populations to search for globally optimal solutions. Many students have utilized differential evolutionary algorithms to solve many types of optimization problems, such as social learning, global numerical optimization on continuous space, parallel scheduling problems, scheduling raw milk transportation problems, linear optical response of photosynthetic pigments, multi-objective traveler problems (Traveling Salesman Problem, TSP), fuzzy demand and simultaneous pick-up and delivery vehicle path problems, open vehicle path problems with uncertainty in demand, capacity-limited vehicle path problems, multi-objective vehicle path problems, data-driven vehicle path analysis. Based on the above literature study on the differential evolution algorithm, it has been verified to be a type of efficient search capability, but few have applied the differential evolution algorithm to solve the electric vehicle path problem. Thus, in the present invention we propose an improved differential evolution algorithm (improved differential evolution, IDE) to solve the electric vehicle path problem with time window and non-linear constraints.

Comprehensive analysis of the above documents shows that students at home and abroad have conducted a great deal of research on the construction of VRPTW models and algorithm solving, and in the service process of electric vehicles, the charging process due to electric quantity consumption can be carried out by establishing models on the basis of VRPTW and solving, but related documents are still lacking at present, and a design algorithm is needed to solve. The invention adopts an improved differential evolution algorithm, aims at the electric vehicle path optimization problem with a time window and nonlinear charging constraint, and builds a model based on VRPTW and solves the model.

Disclosure of Invention

The invention aims to provide an electric vehicle path optimization method with a time window and nonlinear constraint, so as to improve the distribution efficiency, reduce the distribution cost and solve the problems in the background technology.

In order to achieve the aim of the invention, the invention adopts the following technical scheme: a method of non-linear charge vehicle path optimization, the method comprising the steps of:

s1, expanding parameters in the existing SOLOMON calculation example and reading the task of the calculation example according to the vehicle type problem of the electric vehicle;

s2: determining a target and constraint conditions of the distribution path optimization;

s3: providing a grading mode to determine customer satisfaction;

s4: optimizing a path solution by adopting an improved differential evolution algorithm;

s5: a charge amount adjustment strategy is proposed to optimize a path solution;

s6: a negative workload restoration strategy is proposed to optimize the path solution;

s7: and issuing the path optimization scheme to each delivery vehicle.

Preferably, in S1, the parameters extended in the existing SOLOMON calculation example include:

the system comprises V clients, one client i and the other client j, wherein i=any natural number from 1 to V, j=any natural number from 1 to V, and i is not equal to j;

the charging station comprises F charging stations, wherein y is any natural number from 1 to F;

the system comprises K vehicles, wherein a certain vehicle K, k=any natural number from 1 to K;

comprising x _ij ，x _ij As constraint variable, this value is 1 if the vehicle can go from client i to client j, otherwise 0;

comprises d _i ，d _i Representing the demand of customer i for goods.

Preferably, the objective of determining the optimization in S2 is f:

in the formula (1), alpha is the weight of travel time, alpha is more than or equal to 0, beta is the weight of customer satisfaction, beta is more than or equal to 0, and alpha+beta=1; t is t _ij Is the time it takes for the vehicle to travel from client i to client j; and (V) _y Is the charging time of the vehicle at the charging station y; gamma is the target coefficient; sv(s) _i Is the customer satisfaction level corresponding to customer i;

the constraint conditions in the S2 are as follows:

the total dispatch duration of the vehicle k cannot exceed the maximum working duration T of the vehicle _max ；

Wherein the total dispatch duration includes dispatch route elapsed time t _ij Service time s of customer _i And charging time of the vehicle at the charging station _y ；

Each customer can only be served by one vehicle, and the load of each vehicle cannot exceed the maximum load;

the vehicle providing the service must start and end at the distribution center while the vehicle is at the distribution center with no more than one node in front of and behind.

Preferably, said S3 is implemented as follows:

when the service vehicle is at t _i When arriving at client i there are three situations:

first kind: when the service vehicle arrives and services within a strict time window, i.e. E _ti ≤t _i ≤L _ti Customer satisfaction sv at the time of _i ＝1；

Second kind: when the service vehicle arrives within the early slack time window, i.e. EE _ti ≤t _i ≤E _ti Customer satisfaction when

Third kind: when the customer service vehicle arrives within the delayed relaxation time window, i.e. L _ti ≤t _i ≤LL _ti Customer satisfaction when

[E _ti ，L _ti ]For the strict time window of client i, [ EE ] _ti ，LL _ti ]A slack time window for user client i.

Preferably, said S4 is implemented as follows:

step 1 according to the extended SOLOMON calculation example, generating X= (X) in a circulating way ¹ ,x ² ,...,x ^m ) M initial solutions are stored in a current solution set;

step 2, mutation operation;

step 3, performing cross operation;

and 4, selecting operation.

Preferably, step 1 in S4 is implemented as follows:

according to the extended SOLOMON calculation example, using an improved PFIH strategy (IPFIH), circularly generating Pn-1 initial solutions, using the PFIH strategy to generate an initial solution, and storing the initial solution into a current solution set; firstly, clients are allocated without considering battery capacity, and then the solution considers the factors of adding the battery capacity; as some vehicles reach the customer, the battery capacity may be negative; therefore, the charging operation needs to be considered by inserting the charging station, and the encoding strategy of the step 1 is as follows:

encoding a solution by adopting two-dimensional array modes, namely a vehicle allocation array and a charging operation array; the first dimension of the first two-dimensional array represents each vehicle, an array is created for each vehicle, the array comprises a client point sequence of the vehicle service, and the sequence of the client point sequence numbers represents the service sequence of the client points; the first dimension of the second two-dimensional array represents each vehicle, and for each vehicle an array is created comprising the charging station sequence for charging during servicing of the vehicle;

the specific charging station initialization strategy comprises the following steps:

step A: before inserting the charging station, firstly obtaining the sum of the condition that the battery capacity is negative when the vehicle reaches the customer and the current travel time;

and (B) step (B): if the battery capacity of the vehicle is negative, it is necessary to attempt to insert charging stations for charging in order to obtain an optimal solution, attempting to insert each charging station at each location;

step C: after the vehicle is charged, recalculating the total travel time and the total battery capacity reaching the customer as negative;

step D: recording the condition of the route after each charging station is inserted;

step E: after all charging stations at all positions are tested, the best charging station and the best position are selected for real insertion.

Preferably, the current solution x in the mutation operation in step S4 and step 2 ⁱ Is a generation strategy I:

step a, in order to generate a neighborhood solution, randomly selecting a vehicle, randomly selecting a client from the vehicle, and deleting the client from the selected vehicle;

step b: inserting the selected customer into another vehicle;

or (b)

Current solution x in mutation operation ⁱ Is generated by strategy II:

step a: to generate a neighborhood solution, as with strategy I, a vehicle is randomly selected, then a number of clients are randomly selected from the selected vehicles and deleted from the current vehicle;

step b: the selected customer is randomly plugged into the other vehicle.

Preferably, the step 3 cross operation in S4 specifically includes the following steps:

step (1): selecting a current solution x ⁱ Then select the optimal solution x ^best Combining the two parts;

step (2): from the current solution x ⁱ Randomly selecting one of the vehicles and then solving for x from the best ^best Finding a customer serviced by the vehicle;

step (3): deleting the corresponding clients from the best solution;

step (4) inserting the deleted clients into the best solution x ^best Other vehicles in (a).

Preferably, said S5 is implemented in such a way that in the current strategy, the battery capacity is fully charged each time, but there is still remaining battery capacity when the last customer is returned to the warehouse after the service is provided; from the standpoint of environmental protection, it is necessary to reduce the battery capacity during charging; according to the residual battery capacity when the battery is finally returned to the warehouse, the charge amount at the charging station is adjusted in the charging process, and then the charging time is calculated according to the nonlinear charging function, so that the total travel time is reduced;

the following conditions should be satisfied for adjusting the charging capacity at the charging station:

(1) If there is only one charging station on the route, it should be ensured that after the current charging station is charged, the vehicle returns to the warehouse with zero battery capacity;

(2) If there are two or more charging stations on the route, ensuring that the battery capacity from the current charging station to the next charging station is 0;

the method comprises the following specific steps:

step A: each vehicle is circulated, whether charging piles exist or not is checked, if so, a plurality of vehicles are checked, and the insertion position of each charging pile is recorded;

step B: for each vehicle, reversing the charge amount, and modifying the remaining power of each customer point of each vehicle;

step C: returning to the proper charging value at the charging station.

Preferably, said S6 is implemented as follows:

after mutation or crossover operation, the battery capacity reaching some customer points can appear as negative, and the current solution becomes an infeasible solution; therefore, the invention proposes a negative electricity repair strategy, which considers two strategies:

strategy (1):

to produce a viable solution, these negative level customer points can be deleted, and a vehicle can be added to service these customer points;

or (b)

Strategy (2):

in addition to creating a viable solution in strategy I, these negative level customer points are deleted and plugged into other vehicles, but there is a difficulty here that other vehicles have already been serviced by arriving at the last customer and returned to the warehouse, and have had charge adjustment strategies set, so it is difficult to plug into other vehicles; therefore, it is difficult to add other vehicles to serve these customers; in order to meet this condition, the present invention proposes that the charge amount at the charging station can be increased, making it possible to serve these customer points.

The beneficial effects of the invention are concentrated in that: the distribution efficiency can be improved, and the distribution cost can be reduced.

Drawings

FIG. 1 is an illustration of the path optimization problem for an electric vehicle with time window and non-linear charging of the present invention.

Fig. 2 is a diagram of a classical example scenario of SOLOMN.

Fig. 3 is a schematic diagram of coding in the method of the present invention.

Fig. 4 is a schematic diagram of decoding in the method of the present invention.

FIG. 5 is a schematic diagram of a customer satisfaction level function according to the present invention.

Fig. 6 is a schematic view of a charging station insertion strategy in the present invention.

FIG. 7 is a current solution x in the present invention ⁱ Is a schematic of strategy II.

FIG. 8 is a schematic diagram of a cross strategy in the present invention.

Fig. 9 is a schematic diagram of a negative quantum repair strategy in accordance with the present invention.

FIG. 10 is a graph showing the comparative convergence curves of two-phase GA, ITSA and IDE examples according to the present invention.

FIG. 11 is a chart of the client point service time Gantt for an example of the method of the present invention.

Detailed Description

The invention will be fully illustrated by the following examples:

the invention is described in further detail below with reference to the attached drawing figures:

the invention provides a differential evolution algorithm for an electric vehicle path optimization problem with a time window and nonlinear charging constraint. In combination with the problem features, the algorithm adopts an improved differential evolution algorithm. The algorithm is divided into four stages of initialization, mutation, crossover and selection. The variation strategy and the crossing strategy in the improved differential evolution algorithm stage are improved, so that the population quantity is increased, and the probability of finding a better solution is increased. Meanwhile, a charge amount adjustment strategy and a negative charge amount restoration strategy are provided for optimization, so that the quality of a solution can be effectively improved. Experimental results verify the effectiveness of the proposed improved differential evolution algorithm. Meanwhile, a satisfaction degree grade strategy is adopted to be more practical, and the method has application value.

1. Description of electric vehicle path optimization problem with time window and nonlinear charging constraints.

In the present invention, a problem is defined as an extension of the EVRP with a time window, and the characteristics of the problem can be summarized as: (1) all types of electric vehicles are of the same type; (2) The battery capacity of the electric vehicle should always remain in a non-negative state; (3) Each customer has a time window constraint and service time; (4) The charging process of the vehicle is a nonlinear charging process; (5) The charging process of each charging station is divided into four different charging speeds.

In a real logistics distribution system, the charging process is a nonlinear charging process which changes with time. Most studies assume that electric vehicles are serviced from a warehouse in a full state, and that all charging stations can handle an unlimited number of electric vehicles at the same time, without waiting. From a benefit point of view, electric vehicles are more advantageous to charge at night. Meanwhile, under the strong market competition, customer satisfaction must be emphasized in the logistics distribution process, which is generally beneficial to improving distribution efficiency. For example, vehicles arriving within the customer's time window will reach a higher satisfaction. Thus, the present invention uses the service level to define customer satisfaction. If there is an advance or a delay, this results in a decrease in the level of satisfaction.

Furthermore, the ways in which customer satisfaction is calculated can be divided into two categories: one is based on the number of customers, which depends on the proportion of the number of customers offering service in advance or in delay to the total customers. Another is to use a time window to calculate satisfaction. When the time window is a hard window, then the customer satisfaction value is 0 or 1; when the time window is a fuzzy time window or a soft time window, the satisfaction of the customer is described by using a triangular fuzzy membership function. The present invention employs a service level method to determine customer satisfaction, unlike other studies in which the number of customers exceeding a time window is utilized to be added to a target value, which cannot reflect urgency of customers within a short time window. The manner in which customer satisfaction is calculated of the present invention has a number of advantages: first, the more important the customer, the tighter the time window; second, this ratio is calculated early or late with respect to the time interval to represent customer satisfaction and integrates the service level into the objective function. These advantages help to make the problem of investigation more realistic.

Thus, in the present invention, there are the following assumptions:

(1) Each route must start and end at the warehouse;

(2) The sum of the total service customer's demands cannot exceed the maximum capacity of the service vehicle provided;

(3) Each customer must be serviced by only one electric vehicle;

(4) Each customer has a time window constraint and service time;

(5) Each route considers the longest travel time limit and cannot exceed this maximum limit;

(6) The battery capacity of the electric automobile is always kept in a non-negative state;

(7) The charging process of the electric automobile is a nonlinear charging process;

(8) The goal is to minimize the weighted sum of total travel time and customer satisfaction.

When any electric vehicle arrives at the charging station, it selects a charging level according to the charging function based on the amount of power remaining in the electric vehicle, thereby affecting the charging time and thus the overall target value. A typical example describing this problem is given in fig. 1. In the figure there are 8 customers and 3 charging stations. Charging stations are of two types (conventional and fast charging). The battery capacities q and o are mapped to charging times s to d using piecewise linear functions corresponding to the charging stations, thereby estimating the time charged at the charging stations and representing the time difference between s and d with a. In this example, route 1 does not require access to any charging stations. Route 2 charges at charging station 9, and the electric vehicle arrives at the charging station with zero charge. And charges the battery capacity to an amount of o=5, and thus estimates the charging time by means of a piecewise linear function, so route 2 consumes 15.6 time units, where the total travel time is 14 time units and the charging time is 1.6 time units. Finally, route 3 consumes 2 and 6 charging time units, respectively.

1.1 modeling of electric vehicle Path optimization problem with time Window and nonlinear charging constraints

The parameters and symbols are represented as follows:

the objective function (1) is to minimize the weighted sum of two objectives, where the first term is the total travel time, including travel time and charge time, and the second term is customer satisfaction. Constraint (2) is to ensure that each customer is serviced only once. Constraint (3) defines the number of charges per charging station. The constraint (4) is a state that the electric automobile is fully charged when the electric automobile starts from a warehouse. Constraint (5) is a limitation on battery capacity when the electric vehicle arrives and departs from the charging station, ensuring that battery capacity is always non-negative and does not exceed maximum battery capacity. Constraint (6) represents t _si And t _di The time difference between them, i.e. the time at which charging is performed at the charging station. The constraint (7) is to ensure that the battery capacity of the electric vehicle is always a non-negative state and that the battery capacity can reach the next point. Constraint (8) represents the temporal relationship between two adjacent clients. Constraint (9) is that the time window for the vehicle to reach the customer point cannot exceed the slack time window limit. The constraint (10) ensures that the sum of the total travel times does not exceed the maximum travel time limit. The constraint (11) defines the constraint of the weights.

1.2 electric vehicle Path optimization problem with time Window and nonlinear charging constraint

Classical VRPTW examples, such as the SOLOMON example, include 56 examples, each containing 100 customer points, and the layout of the customer points is divided into three major categories, namely 17C (Clustering) series examples with higher aggregation, 23R (Random) series examples with scattered aggregation, and 16 RC series with intermediate aggregation. Fig. 2 shows customer point profiles for two different scenarios. The main characteristics of the C series calculation example include: (1) The aggregation degree of the client points is high, and a plurality of client points form a cluster; (2) The demand of the customer points is relatively large, so that the vehicle can only deliver limited customers; (3) the length of the time window of the client point is relatively large. The main characteristics of the R series calculation example include: (1) the client point dispersion degree is higher; (2) The demand of the customer points is small, so that the vehicle can deliver enough customer points; (3) the length of the time window of the client point is relatively small. The characteristics determine that the VRPTW problems with different structures have different problem characteristics, so that different heuristic rules are adopted for solving. A diagram of a classical example of a SOLOMON scene is shown in fig. 2.

The classical SOLOMON calculation example is not provided for a charging station, meanwhile, the consumption rate of the vehicle per unit is not noted, and in order to better consider practical constraints, the position of the charging station and the consumption rate of the vehicle per unit are increased on the basis of the classical SOLOMON calculation example. The location of the charging station is generated by using a clustering method, and 100 clients of the SOLOMON computing example are divided into a plurality of classes by calculating the distance between each client. Then, the position of the charging station is designed for each class by calculating the average value of the customer coordinates belonging to the same class.

The extended classical SOLOMON calculation example comprises 55 calculation examples, each calculation example comprises 100 client points, the layout of the client points is still divided into three main categories, namely a C (Clustering) series calculation example with higher aggregation degree, an R (Random) series calculation example with scattered aggregation degree and an RC series with intermediate aggregation degree.

2 solving electric vehicle path optimization algorithm with time window and nonlinear charging constraint

2.1 differential evolutionary Algorithm

The differential evolution (differential evolution, DE) algorithm was proposed by Storn and Price in 1995. In the basic differential evolution algorithm, several operations such as mutation, crossover and the like need to be performed iteratively, so that development and exploration tasks can be realized. The key process of the differential evolution algorithm is described as follows:

(1) Coding and initializing populations

For the continuous optimization problem, each solution is represented by a real number in the underlying DE. It should be noted that the elements in each solution must be x _ij ^(L) And x _ij ^(U) Within a range between.

x _ij (0)＝x _ij (L)+rnd[0,1]·(x _ij (U)-x _ij ^(L) )；i＝1,...,D.j＝1,....NP

Where rnd 0,1 represents a number randomly generated within the range.

(2) Mutation operation

The mutation is used as a core operation of differential evolution and plays a vital role in the search process of differential evolution. The mutation operator uses the following formula:

v _ij (t+1) ^G+1 ＝x _ic (t) ^G +F*[x _ia (t) ^G -x _ib (t) ^G ] (12)

wherein a, b, c.epsilon.1, NP]And are different from each other, i.e. a +.b +.c +.j, F is the scaling factor, x _ia (t) ^G -x _ib (t) ^G Is a differential vector.

(1) Crossover operation

To increase the potential diversity, a crossover operation is performed after the mutation operation. The crossover operation is defined by the following equation:

where randn (i), which is a random integer in [1, n ], G represents the number of current iterations and CR ε [0,1] is the crossover probability.

() Estimation and selection operations

To determine v _ij (t+1) ^G+1 Whether it is the next generation, the estimation and selection operators are given below to ensure that the better adaptation values are preserved:

repeating the steps (2) to (4) until the number of iterations reaches a maximum. It should be noted that: this criterion is implemented by greedy selection.

2.2 problem encoding

In this section, the present invention encodes a solution, i.e., a vehicle allocation array and a charging operation array, in two-dimensional arrays, taking into account the constraints of the problem. The first dimension of the first two-dimensional array represents each vehicle, an array is created for each vehicle, comprising a sequence of customer points served by the vehicle, the order of the customer point numbers representing the order of service of the customer points. The first dimension of the second two-dimensional array represents each vehicle, creating an array for each vehicle containing the charging station sequence for charging during servicing of the vehicle. FIG. 3 (a) gives an illustrative example of a vehicle allocation array, where the first dimension represents all vehicles and the second dimension represents customers serviced by each vehicle. For example, there are three vehicles: the first vehicle serves three customers {5,1,2}, and the other two vehicles serve {4,7} and {6,8,3,9} respectively.

Fig. 3 (b) illustrates whether the vehicle is charged at each charging station, if the vehicle is charged at the corresponding charging station, the element is set to the charging station number, otherwise set to "-1". For example, the first vehicle will be charged at charging station number 0 and it will not visit other charging stations. The second vehicle will be charged at charging station number 2 and the last vehicle will be charged at charging stations number 3 and 4, respectively.

2.3 problem decoding

During decoding, the entire path taken by the vehicle can be found by means of the two-dimensional arrays mentioned above. Firstly, judging whether the vehicle is charged at a charging station or not by using the charging operation array, then determining that charging operations are carried out between clients or between the clients and a warehouse by combining the vehicle distribution array, and finally finding the whole path through which the vehicle passes. In fig. 4, two customers {5,2} are served by ev_a, and the second sequence { -1,0, -1} indicates that ev_a is to be charged at the charging station numbered "0". It can be seen that the charging operation occurs between clients numbered 2 and 5, so the entire path of EV_A is denoted as {0,5, '0',2,0}

2.4 calculation of customer satisfaction

In recent years, customer satisfaction levels have received increasing research attention, as customer satisfaction levels often represent service performance. A common method of calculating the customer satisfaction value is to directly add it to the target value. For example, afshar-bakesholoo (2016) proposes that the customer satisfaction value be considered a linear function between a strict time window and a slack time window. However, in a realistic application, the customer is generally unable to give an accurate value for each point in time. For example, in a dispatch stream, a customer will typically give several levels of service satisfaction values, which can be seen as a piecewise function. Fig. 5 depicts an example of such a piecewise function.

The method for calculating the customer satisfaction comprises the following specific steps:

when the service vehicle is at t _i When customer i is reached, there are three situations:

first kind: when the service vehicle arrives and services in a strict time window, i.e. E _ti ≤t _i ≤L _ti Customer satisfaction sv at the time of _i ＝1；

Second kind: when the service vehicle arrives in the early slack time window, EE _ti ≤t _i ≤E _ti Customer satisfaction when

2.5 initialization strategy for charging station

First, customers are allocated without taking battery capacity into account, and then add battery capacity factors are considered in the solution. The battery capacity may be negative as some vehicles arrive at the customer. Therefore, it is necessary to perform the charging operation in consideration of the insertion of the charging station. Fig. 6 depicts a process of inserting a charging station in a route.

In order to better describe the process of inserting the charging station, the specific steps are as follows:

step 1: before inserting the charging station, firstly obtaining the sum of the condition that the battery capacity is negative when the vehicle reaches the customer and the current travel time;

step 2: if the battery capacity of the vehicle is negative, it is necessary to attempt to insert charging stations for charging in order to obtain an optimal solution, attempting to insert each charging station at each location;

step 3: after the vehicle is charged, recalculating the total travel time and the total battery capacity reaching the customer as negative;

step 4: recording the condition of the route after each charging station is inserted;

step 5: after all charging stations at all positions are tested, the best charging station and the best position are selected for real insertion.

2.6 modified mutation operation:

current solution x in mutation operation ⁱ Is a generation strategy I:

step 1: to generate a neighborhood solution, a vehicle is randomly selected, then a client is randomly selected from the neighborhood solution, and the client is deleted from the selected vehicle;

step 2: the selected customer is plugged into another vehicle.

Current solution x in mutation operation ⁱ Generation strategy II (fig. 7):

step 1: to generate a neighborhood solution, as with strategy I, a vehicle is randomly selected, then a number of clients are randomly selected from the selected vehicles and deleted from the current vehicle;

step 2: the selected customer is randomly plugged into the other vehicle.

2.7 improved crossover operation is as follows:

the cross strategy is specifically as follows (fig. 8):

step 1: selecting a current solution x ⁱ Then select the optimal solution x ^best Combining the two parts;

step 2: from the current solutionx ⁱ Randomly selecting one of the vehicles and then solving for x from the best ^best Finding a customer serviced by the vehicle;

step 3: deleting the corresponding clients from the best solution;

step 4, inserting the deleted clients into the best solution x ^best Other vehicles in (a).

2.8 charge amount adjustment strategy

In the current strategy, the battery capacity is fully charged each time, but there is still remaining battery capacity when the last customer is serviced back to the warehouse. From the standpoint of environmental protection, it is necessary to reduce the charging capacity during charging. Accordingly, the present invention proposes a charge amount adjustment strategy. And adjusting the charging capacity at the charging station in the charging process according to the residual battery capacity when the battery is finally returned to the warehouse, and then calculating the charging time according to the nonlinear charging function, thereby reducing the total travel time.

(2) If there are two or more charging stations on the route, it is ensured that the battery capacity from the current charging station to the next charging station is 0.

The method comprises the following specific steps:

step 1: each vehicle is circulated, whether charging piles exist or not is checked, if so, a plurality of vehicles are checked, and the insertion position of each charging pile is recorded;

step 2: for each vehicle, reversing the charge amount, and modifying the remaining power of each customer point of each vehicle;

step 3: returning to the proper charging value at the charging station.

2.9 negative electric quantity repair strategy

After mutation or crossover operation, the battery capacity reaching some customer points is negative, and the current solution becomes an infeasible solution. Therefore, the invention proposes a negative electricity repair strategy, which considers two strategies:

strategy I:

strategy II:

in addition to creating a viable solution in policy I, these negative level customer points are deleted and plugged into other vehicles, but there is a difficulty here that other vehicles have already been serviced by reaching the last customer and returned to the warehouse with the battery capacity set to zero policy, so it is difficult to plug into other vehicles. Therefore, it is difficult to add other vehicles to serve these customers. To meet this condition, the amount of charge at the charging station may be increased, making it possible to serve these customer points.

Fig. 9 details this process. For example, the customer numbered 30 is deleted from the vehicle numbered 10. Now, suppose ten vehicles (i.e., vehicles numbered 0 through 9) are inserted, with vehicle numbered 7 servicing {1,2,5,7} customers, with a charging station numbered 8 between customer numbers 5 and 7, with a battery capacity of 100 during charging. We can increase this value to 150 to ensure that this vehicle can reach customer number 7 and then service customer number 30. The sequence obtained using the negative quantum repair strategy is {1,2,5,7, 30}.

3 experimental results and analysis

3.1 simulation experiment parameter set-up

The method specifically comprises the following steps: (1) Population size P _s I.e. the total number of individuals in the experiment. (2) Deletion ratio D _r The number of clients deleted on the vehicle of the current solution is determined. (3) Crossover probability P _c I.e. the likelihood of cross-operation of each individual is determined.

3.2 analysis of simulation results

In order to verify the effectiveness of the improved differential evolution algorithm (IDE), the invention selects a two-stage genetic algorithm (two-phase GA) and an Improved Tabu Search Algorithm (ITSA) as comparison algorithms, and solves the extended 55 VRPTW calculation examples.

Table 1 gives experimental comparisons of the algorithm for 55 VRPTW examples, the first column of the table gives the example names, the second column gives the best values obtained for all of the comparison algorithms in each algorithm, the next three columns show the best target values for each example obtained for the three comparison algorithms, and the last three columns show the mean square error obtained for the three comparison algorithms, with the following calculation formulas:

dev＝(f _c -f _b )/f _b ×100％ (15)

as can be seen from the table, the IDE algorithm proposed by the present invention is in solving the extended VRPTW algorithm: (1) 35 optimal solutions are obtained, and 2 and 19 optimal solutions are calculated by two-phase GA and ITSA respectively; (2) As can be seen by the mean square error 15, the IDE algorithm has significant effectiveness compared to other algorithms.

To further verify the performance of the proposed algorithm in solving this problem, each algorithm was run 5 times on the same computer, randomly selecting 6 cases. Fig. 10 (a) - (f) illustrate the convergence curves of the examples.

Fig. 11 depicts a graph of customer service time and charging time for an example, in which each rectangle corresponds to a customer, the number "V1" represents the first vehicle, and the numbers within the rectangle represent the customer numbers. For example, the customer sequence for the vehicle service number 11 has {59, 58, 60, 38, 39, 19, 12, 100}, the total number of customers is 8, and the number to the right of each customer indicates the time the customer point has finished servicing. For example, the time to end service for customer 59 is 125. It should be noted that: the charging station between clients 60 and 38 is numbered 3.

Table 1 comparison of experimental results

Claims

1. A method of optimizing a path of a nonlinear electric vehicle, the method comprising the steps of:

s3: providing a grading mode to determine customer satisfaction;

s7: issuing a path optimization scheme to each delivery vehicle;

in S1, the parameters extended in the existing SOLOMON example include:

v clients, a certain client i, another client j, i=any natural number from 1 to V, j=any natural number from 1 to V, i not equal to j;

f charging stations, one charging station y, y=any natural number from 1 to F;

k vehicles, a certain vehicle K, k=any natural number from 1 to K;

x _ij ，x _ij as constraint variable, this value is 1 if the vehicle can go from client i to client j, otherwise 0;

d _i ，d _i representing the demand of customer i for goods;

the optimization target determined in S2 is f:

in the formula (1), alpha is the weight of travel time, alpha is more than or equal to 0, beta is the weight of customer satisfaction, beta is more than or equal to 0, and alpha+beta=1; t is t _ij Is the time it takes for the vehicle to travel from client i to client j; and (V) _y Is the charging time of the vehicle at the charging station y; gamma is the target coefficient; sv(s) _i Is taken as customer iA corresponding customer satisfaction level;

the constraint conditions in the S2 are as follows:

Wherein the total dispatch period includes the time t spent by the vehicle from client i to client j _ij Service time s of customer _i And charging time of the vehicle at the charging station _y ；

the vehicle providing the service must start and end at the distribution center, while the vehicle is at the distribution center with no more than one node in front of and behind;

the S3 is realized in the following way:

[E _ti ，L _ti ]For the strict time window of client i, [ EE ] _ti ，LL _ti ]A slack time window for user client i;

the S4 is realized in the following way:

step 1 according to the extended SOLOMON calculation example, generating X=x in a circulating way ¹ ,x ² ,...,x ^m Totally m initial solutionsStoring the current solution set;

step 2, mutation operation;

step 3, performing cross operation;

step 4, selecting operation;

step 1 in S4 is implemented as follows:

according to the extended SOLOMON calculation example, using an improved PFIH strategy to circularly generate Pn-1 initial solutions, then using the PFIH strategy to generate an initial solution, and storing the initial solution into a current solution set; firstly, clients are allocated without considering battery capacity, and then the solution considers the factors of adding the battery capacity; as some vehicles reach the customer, the battery capacity may be negative; therefore, the charging operation needs to be considered by inserting the charging station, and the encoding strategy of the step 1 is as follows:

step E: after testing all charging stations at all positions, selecting an optimal charging station and an optimal position for real insertion;

in the step S4 and step 2

Current solution x in mutation operation ⁱ Is a generation strategy I:

step b: inserting the selected customer into another vehicle;

or (b)

Current solution x in mutation operation ⁱ Is generated by strategy II:

step b: randomly inserting the selected customer into the other vehicle;

the step 3 crossing operation in the step S4 specifically comprises the following steps:

step (3): deleting the corresponding clients from the best solution;

2. The nonlinear charge vehicle path optimization method in accordance with claim 1, wherein: the step S5 is realized in such a way that in the current strategy, the battery capacity is fully charged each time, but the battery capacity remains when the service is returned to a warehouse after the last customer is provided; from the standpoint of environmental protection, it is necessary to reduce the battery capacity during charging; according to the residual battery capacity when the battery is finally returned to the warehouse, the charge amount at the charging station is adjusted in the charging process, and then the charging time is calculated according to the nonlinear charging function, so that the total travel time is reduced;

the method comprises the following specific steps:

step C: returning to the proper charging value at the charging station.

3. The nonlinear charge vehicle path optimization method in accordance with claim 2, wherein: the step S6 is realized in the following way:

after mutation or crossover operation, the battery capacity reaching some customer points can appear as negative, and the current solution becomes an infeasible solution; thus, a negative quantum repair strategy is proposed, taking into account a strategy:

strategy (1):

to create a viable solution, these negative level customer points are deleted and a vehicle is added to service these customer points.