CN109934405B - Multi-vehicle-type multi-train-number path planning method with time limit based on simulated annealing algorithm - Google Patents

Abstract

Translated fromChinese

本发明提供一种基于模拟退火算法的有时限的多车型多车次路径规划方法，属于路径规划技术。该方法包括如下步骤：(1)导入数据，初始化参数；(2)生成初始种群，计算个体的目标函数值；(3)选择最优个体进行模拟退火操作；(4)降温；(5)产生新解；(6)比较新解与当前解的适应值，判断是否接受新解为当前解；(7)内循环次数满足，返回(4)；(8)满足终止条件时，输出当前解为最优解，输出规划路线。本发明的优点是：能够考虑车辆的载重限制和工作时长限制，计算出要到达多个目的地的路径规划算法，且方法不只是规划一辆车的一趟路径，而是能规划多辆车的多次路径。

The invention provides a time-limited multi-vehicle and multi-vehicle path planning method based on a simulated annealing algorithm, which belongs to the path planning technology. The method includes the following steps: (1) importing data and initializing parameters; (2) generating an initial population and calculating the objective function value of an individual; (3) selecting an optimal individual to perform a simulated annealing operation; (4) cooling down; (5) generating (6) Compare the fitness value of the new solution and the current solution, and judge whether to accept the new solution as the current solution; (7) If the number of inner loops is satisfied, return to (4); (8) When the termination condition is satisfied, output the current solution as The optimal solution, output the planned route. The advantages of the present invention are: considering the load limitation of the vehicle and the limitation of the working time, the route planning algorithm to reach multiple destinations can be calculated, and the method is not only to plan a route for one vehicle, but also to plan multiple vehicles. multiple paths.

Description

Multi-vehicle-type multi-train-number path planning method with time limit based on simulated annealing algorithm

Technical Field

The invention relates to the technical field of path planning, in particular to a time-limited multi-vehicle-type multi-train-number path planning method based on a simulated annealing algorithm.

Background

In recent years, with the development of logistics, the Problem of Vehicle Routing Planning (VRP) has been gaining increasing social importance. The VRP problem generally refers to that under the condition that a starting point and an end point are determined, a vehicle route is divided, and the total route is optimized on the premise that the load limit of the vehicle is met and all points are visited once. However, in practice, the loads of the equipped vehicles in the parking lot are not exactly the same, and the vehicles need to consider the working time limit of the driver of the vehicle in addition to the load limit, and in some cases, the vehicles can be arranged to be transported in multiple times within the working time allowed range. The existing algorithm has high efficiency on the VRP problem of a single vehicle type, but still needs further research on the VRP problem of multiple vehicle types and multiple vehicle times considering the limitation of working time.

Simulated Annealing (SA) was derived from statistical physics, proposed by Metropolis in 1953. It simulates the temperature change of the actual solid annealing process, namely, the solid is heated to be sufficiently high and then is gradually cooled. When the temperature is increased, the particles in the solid are changed into a disordered state, and the internal energy is increased; and when the temperature is gradually reduced, the particles tend to be ordered, an equilibrium state is reached at each temperature, and finally a ground state is reached at normal temperature, so that the internal energy is reduced to the minimum. The simulated annealing algorithm (SA) is an extension of the local search algorithm, which differs from the local search in that it selects the optimal state in the domain with a certain probability. Simulated Annealing (SA) is an algorithm suitable for solving large-scale combinatorial optimization problems.

Disclosure of Invention

The invention aims to provide a time-limited multi-vehicle-type multi-vehicle-number path planning method based on a simulated annealing algorithm, which can effectively solve the path planning problem that vehicles of various vehicle types go out for multiple times and have working time limitation.

The method comprises the following steps:

(1) importing data and initializing parameters;

(2) generating an initial population, and calculating the objective function value of an individual;

(3) selecting an optimal individual s according to the objective function value in the step (2);

(4) cooling, the current temperature T is equal to alpha T₀And alpha is a cooling coefficient;

(5) generating a new solution S';

(6) comparing the new solution with the current solution, and judging whether to accept the new solution as the current solution: if the new solution is better than the current solution, accepting the new solution as the current solution; if the new solution is worse than the current solution, selectively accepting the new solution as the current solution according to the probability p;

(7) when the number of internal circulation times meets the initialization parameters in the step (1), returning to the step (4);

(8) and (3) outputting the current solution as the optimal solution and outputting the planned route when the termination condition in the initialization parameters in the step (1) is met.

Wherein the data imported in the step (1) comprises weight information of each point, vehicle information and a distance matrix M_DTime matrix M_T。

The initialization parameters in the step (1) comprise setting an initial temperature T0 (ensuring enough) and a termination temperature T_endInner layer ofNumber of cycles L and initial population size N_p。

The initial population in the step (2) consists of a plurality of individuals, each individual consists of a plurality of arrays, and each array comprises a path which consists of a starting point, a passing point and an end point; the initial population generation method comprises the following steps:

s21: generating a random ordering of all collection points;

s22: randomly selecting a vehicle, and recording the load and the working time limit of the vehicle;

s23: considering the limitation of vehicle load and vehicle working time length, dividing paths for vehicles according to the collection point sequence, wherein the starting point of the path is the parking position of the vehicle, and performing greedy operation on the current path after the path division is completed: selecting a point closest to the current from a starting point as a next point, selecting a closest end point for the current route according to a greedy result and a last collection point, and performing intra-route neighborhood search on the route so as to enable the planned route to be more in line with the actual situation;

s24: if the working time of the current vehicle is remained, continuing to plan the route of the current vehicle, wherein the starting point of the route is the end point of the route on the current vehicle, and the rest is S23;

s25: returning to S22 when the current working time of the vehicle is used up;

s26: all collection points are divided into routes and the process ends.

The model used for calculating the objective function value in step (2) is as follows:

an objective function:

minimizing the total number of vehicles used:

minimizing the cost of using the vehicle:

minimizing the total path and the weighted sum of the balance values: min F;

wherein: f ═ β ═ L + γ ═ B;

by passing

To know

Restricting a point to be visited by one vehicle only once;

by passing

Ensuring the load limit of the vehicle;

by passing

Ensuring the limitation of the working time;

f is the value of the sum of the total distance and the balance index weight, and beta and gamma are the weight coefficients of the total distance and the balance target respectively and are determined according to the actual situation; l is the total route value, B is the balance index value; the number of vehicles is K, Q_kThe load of the kth vehicle, c_kIs the cost of the kth vehicle; the total number of collection points is N, and the collection amount per point is q_i(i＝1，2...N)，d_ijDistance of course between two points i, j, t_ijIs the time distance between two points i, j,x_kij1 means that k passes through point i to point j, y_kWith 1, the k-th vehicle is used and h is the operating time limit for all vehicles.

The generation mechanism of the new solution in the step (5) is as follows: and operating in the neighborhood of the current solution to generate a new solution, wherein the neighborhood has eight structures which are divided into an exchange neighborhood and a plug-in neighborhood, and under the conditions of full-load vehicle load and working time limit, exchanging a certain number of points (the number is more than or equal to 1 and less than or equal to 3) between two routes or inserting a certain number of points (the number is more than or equal to 1 and less than or equal to 5) of one route into the other route to generate the new solution.

The calculation formula of the probability p in the step (6) is as follows: p ═ exp (- (F' -F) T/T₀) And F' is the third target value of the new solution.

The technical scheme of the invention has the following beneficial effects:

in the scheme, the load limit and the working time limit of the vehicle can be considered, the path planning algorithm for reaching multiple destinations can be calculated, and the algorithm can plan multiple paths of multiple vehicles instead of only one path of one vehicle. And various neighborhood structures are designed in the algorithm, so that the search space of the algorithm is enlarged. The algorithm is widely applied, and can be applied to the following scenes besides the application of truck delivery of logistics enterprises: (1) sharing the route planning of the single vehicle recovery; (2) planning the path of a maintenance worker; (3) planning the route of the school bus for picking up and delivering students; (4) path planning of multiple sightseeing points of a travel enterprise vehicle, and the like.

Drawings

FIG. 1 is a flow chart of a time-limited multi-vehicle type multi-pass path planning method based on a simulated annealing algorithm according to the present invention;

FIG. 2 is a diagram of a switching domain architecture in an embodiment of the present invention;

fig. 3 is a diagram showing a structure of an insertion field in the embodiment of the present invention.

Detailed Description

In order to make the technical problems, technical solutions and advantages of the present invention more apparent, the following detailed description is given with reference to the accompanying drawings and specific embodiments.

The invention provides a time-limited multi-vehicle-type multi-train-number path planning method based on a simulated annealing algorithm.

As shown in fig. 1, the method comprises the steps of:

(1) importing data and initializing parameters;

(2) generating an initial population, and calculating the objective function value of an individual;

(3) selecting an optimal individual s according to the objective function value in the step (2);

(4) cooling, the current temperature T is equal to alpha T₀And alpha is a cooling coefficient;

(5) generating a new solution S';

(6) comparing the new solution with the current solution, and judging whether to accept the new solution as the current solution: if the new solution is better than the current solution, accepting the new solution as the current solution; if the new solution is worse than the current solution, selectively accepting the new solution as the current solution according to the probability p;

(7) if the internal circulation times are met, returning to the step (4);

(8) and when the termination condition is met, outputting the current solution as the optimal solution and outputting the planned route.

The following description is given with reference to specific examples.

When the method is specifically applied, the method comprises the following steps:

step 1, considering the characteristics of the VRP problem of multiple vehicle types constrained by the working time length, generating an initial population, wherein the initial population is composed of a plurality of individuals, each individual is composed of a plurality of arrays, and each array comprises a path which is composed of a starting point, a passing point and a finishing point. The specific individual generation steps are as follows:

and 1.1, generating random sequencing of all the collection points.

And 1.2, randomly selecting a vehicle, and recording the load and the working time limit of the vehicle.

And step 1.3, considering the vehicle load and the vehicle working time limit, and dividing paths for the vehicles according to the collection point sequence, wherein the starting point of the route is the vehicle parking position. And after the path division is finished, performing greedy operation on the current route: and selecting the point closest to the current point from the starting point as the next point. And selecting the nearest end point for the current route according to the position of the last collection point of the greedy result. And performing neighborhood search in the route on the route to ensure reasonable internal planning of the route.

And 1.4, if the working time of the current vehicle is remained, continuing to plan the route of the current vehicle, wherein the starting point of the route is the end point of the last route of the vehicle, and the rest is the same as the step 1.2.

And step 1.5, returning to the step 1.1 when the current working time of the vehicle is used up.

And step 1.6, dividing all the collection points into routes, and ending the program.

And 2, calculating the adaptive value of the initial population. The adaptive value has three indexes which are respectively: the total distance value and the balance value are weighted to calculate the obtained value by using the number of vehicles and the vehicle cost. The specific calculation model is as follows:

an objective function:

min F (3)

and (3) constraint:

F＝(β*L+γ*B) (4)

equations (1) - (3) are the objective functions of the model, which are the sum of the minimum total number of vehicles used, the minimum cost of vehicles used, the minimum total route and the weight of the balance value; formula (4) is a formula for calculating the F value, formula (5) is a formula for calculating the total route, formula (6) is a formula for calculating the balance index, and the formula is obtained by subtracting the minimum working time from the maximum working time; equations (7) and (8) constrain that a point can only be visited once by one vehicle; equation (9) ensures vehicle load limiting; the formula (10) guarantees the working time limit; the symbols referred to in the above formula define the following meanings: f is the value of the sum of the total distance and the balance index weight, beta and gamma are the weight coefficients of the total distance and the balance target respectively, and the value is determined by a decision maker according to the preference; l is the total route value, B is the balance index value; the number of vehicles is K, Q_kThe load of the kth vehicle, c_kIs the cost of the kth vehicle; the total number of collection points is N, and the collection amount per point is q_i(i＝1，2...N),d_ijDistance of course between two points i, j, t_ijIs the time distance between two points i, j, x_kij1 means that k passes through point i to point j, y_kWith 1, the k-th vehicle is used and h is the operating time limit for all vehicles.

And selecting the optimal individual in the initial population according to the objective function value. When judging, selecting the individual with less vehicle number, selecting the individual with less vehicle cost, and finally selecting the minimum individual as the optimal individual of the current population from the total route value and the balance value according to the weight calculation. And performing simulated annealing operation by using the optimal individuals.

Step 3, beginningThe initialization algorithm parameters are: initial temperature T₀(ensure sufficiently large), termination temperature T_endAnd inner loop times L.

And 4, cooling. The cooling formula is adopted as follows: t ═ α T₀And alpha is a temperature reduction coefficient.

And 5, generating a new solution: a new solution is generated in the neighborhood of the current solution according to the rules. Eight kinds of neighborhood structures are set, and new solutions are generated in the eight kinds of neighborhood structures in sequence. The neighborhood structures are respectively exchange collection points among the lines, and as shown in fig. 2, 1 to 3 points are respectively exchanged between the two lines; the points of insertion between the routes, as shown in FIG. 3, are inserted from 1 to 5 points, respectively. Under the condition of meeting the limits of vehicle load and working time, new solutions are sequentially generated in eight neighborhoods.

Step 6, according to the metropolis criterion, if the new solution is superior to the current solution, accepting the new solution as the current solution; if the new solution is worse than the current solution, an acceptance probability is calculated, p ═ exp (- (F' -F) T/T₀) And F' is the third target value of the new solution. And generating a random number between 0 and 1, and if the number is less than p, accepting a new solution, otherwise, not accepting the new solution.

And 7, if the inner layer circulation times are met, returning to the step 4.

Step 8, the termination temperature is satisfied, namely T is less than T_endAnd then ending the program, outputting the current solution as the optimal solution, and outputting the vehicle division route.

While the foregoing is directed to the preferred embodiment of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention as defined in the appended claims.

Claims (7)

Translated fromChinese

1.一种基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：包括步骤如下：1. a time-limited multi-vehicle multi-vehicle path planning method based on simulated annealing algorithm, is characterized in that: comprise steps as follows:(1)导入数据，初始化参数；(1) Import data and initialize parameters;(2)生成初始种群，计算个体的目标函数值；(2) Generate the initial population and calculate the objective function value of the individual;(3)根据步骤(2)中的目标函数值，选择最优个体s；(3) According to the objective function value in step (2), select the optimal individual s;(4)降温，当前温度T＝αT₀，α为降温系数；(4) cooling, current temperature T=αT₀ , α is the cooling coefficient;(5)产生新解S′；(5) Generate a new solution S';(6)比较新解与当前解，判断是否接受新解为当前解：若新解优于当前解，接受新解为当前解；若新解差于当前解，根据概率p，选择性接受新解为当前解；(6) Compare the new solution with the current solution, and judge whether to accept the new solution as the current solution: if the new solution is better than the current solution, accept the new solution as the current solution; if the new solution is worse than the current solution, according to the probability p, selectively accept the new solution The solution is the current solution;(7)内循环次数满足步骤(1)中初始化参数要求，返回步骤(4)；(7) The number of inner loops meets the initialization parameter requirements in step (1), and returns to step (4);(8)满足步骤(1)中初始化参数中终止条件时，输出当前解为最优解，输出规划路线；(8) When the termination condition in the initialization parameter in step (1) is satisfied, output the current solution as the optimal solution, and output the planned route;所述步骤(2)中初始种群生成方法如下：The initial population generation method in the step (2) is as follows:S21：生成所有收集点的随机排序；S21: Generate a random order of all collection points;S22：随机选择车辆，记录车辆的载重和工作时长限制；S22: Randomly select a vehicle, and record the load and working time limit of the vehicle;S23：考虑车辆载重和车辆工作时长限制，按照收集点排序为车辆划分路径，路线起始点为车辆停放位置，路径划分完成后对当前路线进行贪婪操作：从起始点开始选择距离当前最近的点为下一点，根据贪婪结果最后一个收集点为当前路线选择最近终点，对路线进行路线内邻域搜索；S23: Considering the vehicle load and vehicle working time limit, the vehicle is divided into paths according to the order of collection points, the starting point of the route is the parking position of the vehicle, and the greedy operation is performed on the current route after the path division is completed: starting from the starting point, select the point closest to the current as The next point is to select the nearest end point for the current route according to the last collection point of the greedy result, and perform an intra-route neighborhood search on the route;S24：若当前车辆工作时长有剩余，继续规划当前车辆的路线，此时路线起始点为当前车辆上一路线的终点，其余同S23；S24: If there is remaining working time of the current vehicle, continue to plan the route of the current vehicle. At this time, the starting point of the route is the end point of the previous route of the current vehicle, and the rest are the same as S23;S25：当前车辆工作时长已用尽，返回S22；S25: The working hours of the current vehicle have been exhausted, and return to S22;S26：所有收集点均划分到路线内，程序结束。S26: All collection points are divided into the route, and the procedure ends.2.根据权利要求1所述的基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：所述步骤(1)中导入的数据包括各点重量信息、车辆信息、距离矩阵M_D、时间矩阵M_T。2. The time-limited multi-vehicle and multi-vehicle path planning method based on simulated annealing algorithm according to claim 1, wherein the data imported in the step (1) comprises weight information of each point, vehicle information, distance matrix_MD , time matrix_MT .3.根据权利要求1所述的基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：所述步骤(1)中初始化参数包括设置初始温度T₀、终止温度T_end、内层循环次数L和初始种群规模Np。3. The time-limited multi-vehicle and multi-vehicle path planning method based on a simulated annealing algorithm according to claim 1, wherein the initialization parameters in the step (1) include setting an initial temperature T₀ , an end temperature T_end , The number of inner loops L and the initial population size Np.4.根据权利要求1所述的基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：所述步骤(2)中计算目标函数值所用模型如下：4. the time-limited multi-vehicle and multi-vehicle path planning method based on simulated annealing algorithm according to claim 1, is characterized in that: in described step (2), the used model of calculating objective function value is as follows:目标函数：Objective function:最小化使用车辆总数：

Minimize the total number of vehicles used:

最小化使用车辆成本：

Minimize the cost of using the vehicle:

最小化总路程和平衡值权重加和：min F；Minimize the sum of the total distance and the balance value weight: min F;其中：F＝(β*L+γ*B)；Among them: F=(β*L+γ*B);

通过

和

约束一个点只能被一辆车访问一次；pass

and

Constraining that a point can only be visited once by one vehicle;通过

保证车辆载重限制；pass

Guaranteed vehicle load limit;通过

保证工作时长限制；pass

Guaranteed working hours limit;

F是总路程和平衡指标权重加和的值，β，γ分别是总路程和平衡目标的权重系数，根据实际决定；L是总路程值，B是平衡指标值；车辆数为K，Q_k为第k辆车的载重，c_k是第k辆车的成本；收集点总数为N，每点收集量为q_i(i＝1，2...N),d_ij为i，j两点之间的路程距离，t_ij为i，j两点之间的时间距离，x_kij＝1表示k车经过i点到达j点，y_k＝1表示使用第k辆车，h是所有车辆的工作时长限制。F is the sum of the weights of the total distance and the balance index, β, γ are the weight coefficients of the total distance and the balance target respectively, which are determined according to the actual situation; L is the total distance value, B is the balance index value; the number of vehicles is K, Q_k is the load of the k-th vehicle, c_k is the cost of the k-th vehicle; the total number of collection points is N, the collection amount of each point is q_i (i=1, 2...N), and d_ij is i, j two The distance between points, t_ij is the time distance between points i and j, x_kij = 1 means k vehicle passes through point i to point j, y_k = 1 means using the kth vehicle, h is all vehicles working hours limit.5.根据权利要求1所述的基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：所述步骤(5)中新解的产生机制如下：在当前解的邻域内操作产生新解，邻域结构共有八种，分为交换式邻域和插入式邻域，在满载车辆载重和工作时长限制的条件下，交换两条路线间一定数量的点或将其中一条路线一定数量的点插入到另一条路线之中以产生新解。5. The time-limited multi-vehicle and multi-vehicle path planning method based on simulated annealing algorithm according to claim 1, characterized in that: the generation mechanism of the new solution in the step (5) is as follows: operate in the neighborhood of the current solution Generate a new solution. There are eight types of neighborhood structures, which are divided into exchange neighborhoods and plug-in neighborhoods. Under the conditions of full vehicle load and working time limit, exchange a certain number of points between two routes or fix one of the routes. A number of points are inserted into another route to generate a new solution.6.根据权利要求1所述的基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：所述步骤(6)中概率p的计算公式为：p＝exp(-(F′-F)T/T₀)，F′是新解的第三个目标值。6. The time-limited multi-vehicle and multi-vehicle path planning method based on simulated annealing algorithm according to claim 1, characterized in that: the calculation formula of probability p in the step (6) is: p=exp(-(F '-F)T/T₀ ), F' is the third target value of the new solution.7.根据权利要求5所述的基于模拟退火算法的有时限的多车型多车次路径规划方法，其特征在于：所述两条线路间点的数量大于等于1且小于等于3；其中一条线路的点的数量大于等于1且小于等于5。7. The time-limited multi-vehicle and multi-vehicle path planning method based on a simulated annealing algorithm according to claim 5, wherein the number of points between the two lines is greater than or equal to 1 and less than or equal to 3; The number of points is greater than or equal to 1 and less than or equal to 5.

Images