CN114217607A - Takeout delivery path planning method, system and storage medium - Google Patents
Takeout delivery path planning method, system and storage mediumDownload PDFInfo
- Publication number
- CN114217607A CN114217607ACN202111395452.0ACN202111395452ACN114217607ACN 114217607 ACN114217607 ACN 114217607ACN 202111395452 ACN202111395452 ACN 202111395452ACN 114217607 ACN114217607 ACN 114217607A
- Authority
- CN
- China
- Prior art keywords
- path
- pheromone
- optimal
- ants
- ant
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034methodMethods0.000titleclaimsabstractdescription39
- 239000003016pheromoneSubstances0.000claimsabstractdescription107
- 241000257303HymenopteraSpecies0.000claimsabstractdescription52
- 238000004590computer programMethods0.000claimsdescription13
- 230000008569processEffects0.000claimsdescription13
- 230000009286beneficial effectEffects0.000description4
- 230000008901benefitEffects0.000description2
- 230000007613environmental effectEffects0.000description2
- 238000009499grossingMethods0.000description2
- 230000007812deficiencyEffects0.000description1
- 238000010586diagramMethods0.000description1
- 230000006870functionEffects0.000description1
- 230000006872improvementEffects0.000description1
- 230000007246mechanismEffects0.000description1
- 230000004048modificationEffects0.000description1
- 238000012986modificationMethods0.000description1
- 230000003287optical effectEffects0.000description1
- 238000005457optimizationMethods0.000description1
- 230000002028prematureEffects0.000description1
- 238000010845search algorithmMethods0.000description1
Images
Classifications
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
- G05D1/0221—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving a learning process
Landscapes
- Engineering & Computer Science (AREA)
- Aviation & Aerospace Engineering (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Automation & Control Theory (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
Description
Translated fromChinese技术领域technical field
本发明主要涉及路径规划技术领域，具体涉及一种外卖派送路径规划方法、系统及存储介质。The present invention mainly relates to the technical field of path planning, and in particular relates to a method, system and storage medium for path planning of food delivery.
背景技术Background technique
外卖是目前与人们生活息息相关的一个事物，有效的外卖派送路线规划对提高外卖小哥行程安排的合理性、点餐用户的时效性、外卖商户的效益最大化以及保证城市交通路径规划的科学性来说，具有重要的参考价值。路径规划问题是指，在给定的环境中，搜索出一条从起始点到目标点之间的总代价最小路径，这里的代价可以是距离最短、耗时最少、安全性最高或是费用最少等。目前外卖派送路径大都是工作人员通过经验规划，难以保证所选择的外卖派送路径是最佳的。Takeaway is a thing that is closely related to people's lives at present. Effective takeaway delivery route planning can improve the rationality of the takeaway brother's itinerary, the timeliness of ordering users, maximize the benefits of takeaway merchants, and ensure the scientific nature of urban traffic path planning. It has important reference value. The path planning problem refers to, in a given environment, to find a path with the minimum total cost from the starting point to the target point, where the cost can be the shortest distance, the least time-consuming, the highest security or the least cost, etc. . At present, most takeaway delivery routes are planned by staff through experience, and it is difficult to ensure that the selected takeaway delivery route is the best.
发明内容SUMMARY OF THE INVENTION
本发明所要解决的技术问题是针对现有技术的不足，提供一种外卖派送路径规划方法、系统及存储介质。The technical problem to be solved by the present invention is to provide a takeaway delivery path planning method, system and storage medium aiming at the deficiencies of the prior art.
本发明解决上述技术问题的技术方案如下：一种外卖派送路径规划方法，包括如下步骤：The technical solution of the present invention to solve the above-mentioned technical problems is as follows: a method for planning a delivery route for takeaways, comprising the following steps:
将外卖派送起点、外卖途径点和外卖派送终点作为路径节点，将外卖派送员作为蚂蚁，通过所述路径节点和所述蚂蚁建立外卖派送的路径轨迹模型；The takeaway delivery starting point, the takeaway route point, and the takeaway delivery end point are used as path nodes, and the takeaway delivery person is used as an ant, and a path trajectory model of the takeaway delivery is established through the path node and the ants;
基于最大最小蚂蚁算法MMAS在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，根据所述信息素对所述路径轨迹模型进行路径遍历，确定最优路径和最优路径蚂蚁；Based on the maximum and minimum ant algorithm MMAS, a pheromone for guiding the ants to move a path node is set on the path, and the path trajectory model is traversed according to the pheromone to determine the optimal path and the optimal path ants;
根据轮盘选择算法选择路径节点以更新所述信息素，并按照设置的迭代次数和更新后的信息素将所述最优路径蚂蚁在所述最优路径上进行路径遍历，当完成迭代次数时，输出最优目标规划路径。Select path nodes according to the roulette wheel selection algorithm to update the pheromone, and traverse the optimal path ants on the optimal path according to the set number of iterations and the updated pheromone. When the number of iterations is completed , and output the optimal target planning path.
本发明的有益效果是：将各个派送节点作为路径节点，外卖派送员作为蚂蚁，来构建路径轨迹模型，通过最大最小蚂蚁算法MMAS设置路径节点的信息素，以得到最优路径和最优路径蚂蚁，并结合轮盘选择算法选择路径节点以更新信息素，并进行多次迭代，输出最优目标规划路径，使外卖派送路径规划效率明显提升，并且相比于人工规划，其路径选择也更为优化。The beneficial effects of the invention are as follows: each delivery node is used as a path node, and the food delivery person is used as an ant to construct a path trajectory model, and the pheromone of the path node is set by the maximum and minimum ant algorithm MMAS, so as to obtain the optimal path and the optimal path ants , and combined with the roulette selection algorithm to select path nodes to update pheromone, and perform multiple iterations to output the optimal target planning path, which significantly improves the efficiency of takeaway delivery path planning. Compared with manual planning, its path selection is also more efficient. optimization.
在上述技术方案的基础上，本发明还可以做如下改进。On the basis of the above technical solutions, the present invention can also be improved as follows.
进一步，所述基于最大最小蚂蚁算法MMAS，在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，具体为：Further, based on the maximum and minimum ant algorithm MMAS, a pheromone for guiding the ants to move the path nodes is set on the path, specifically:
根据式(1)在路径遍历过程中在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，所述式(1)为：According to the formula (1), the pheromone used to guide the ants to move the path nodes is set on the path during the path traversal process, and the formula (1) is:
其中，τij为信息素，
采用上述进一步方案的有益效果是：通过设置的信息素来引导蚂蚁移动，来进行路径遍历，从而确定最优路径和最优路径蚂蚁。The beneficial effect of adopting the above-mentioned further scheme is that the ants are guided to move by the set pheromone to perform path traversal, so as to determine the optimal path and the optimal path ants.
进一步，所述根据轮盘选择算法选择路径节点以更新所述信息素，具体为：Further, selecting the path node according to the roulette wheel selection algorithm to update the pheromone, specifically:
在概率区间[0,1]设置随机数R，用随机数R减去第一预设值，若差值结果小于或等于0，则选择随机数R对应的路径节点作为下一个移动的路径节点，通过式(1)更新所述下一个移动的路径节点的信息素；Set a random number R in the probability interval [0, 1], subtract the first preset value from the random number R, if the difference result is less than or equal to 0, select the path node corresponding to the random number R as the next moving path node , the pheromone of the next moving path node is updated by formula (1);
若大于0，则用差值结果再减去第二预设值，直至差值结果小于或等于0，将最后一次减去第二预设值得到的差值结果所对应的路径节点作为下一个移动的路径节点，通过式(1)更新所述下一个移动的路径节点的信息素。If it is greater than 0, the second preset value is subtracted from the difference result until the difference result is less than or equal to 0, and the path node corresponding to the difference result obtained by the last subtraction of the second preset value is used as the next For the moving path node, the pheromone of the next moving path node is updated by formula (1).
采用上述进一步方案的有益效果是：通过轮盘选择算法来选择路径节点进行更新信息素，且尽量避免算法陷入停滞。The beneficial effect of adopting the above-mentioned further scheme is that the roulette wheel selection algorithm is used to select the path node to update the pheromone, and try to avoid the stagnation of the algorithm.
进一步，在更新所述信息素的过程中，还包括步骤：Further, in the process of updating the pheromone, it also includes the steps:
当最大最小蚂蚁算法MMAS停滞时，根据式(2)重新设置路径节点的信息素，所述式(2)为：When the maximum and minimum ant algorithm MMAS is stagnant, the pheromone of the path node is reset according to the formula (2), and the formula (2) is:
其中，
采用上述进一步方案的有益效果是：针对信息素平滑策略，在求解规模比较大的问题或者迭代次数比较多的时候，当算法陷入停滞的时候，可以重新设置环境信息素。The beneficial effect of adopting the above-mentioned further scheme is: for the pheromone smoothing strategy, when solving a relatively large-scale problem or when the number of iterations is relatively large, when the algorithm is stagnant, the environmental pheromone can be reset.
本发明解决上述技术问题的另一技术方案如下：一种外卖派送路径规划系统，包括：Another technical solution of the present invention to solve the above-mentioned technical problems is as follows: a takeaway delivery path planning system, comprising:
模型建立模块，用于将外卖派送起点、外卖途径点和外卖派送终点作为路径节点，将外卖派送员作为蚂蚁，通过所述路径节点和所述蚂蚁建立外卖派送的路径轨迹模型；The model building module is used to take the start of takeaway delivery, the takeaway route point and the takeaway delivery end point as path nodes, the takeaway delivery staff as ants, and the path trajectory model of takeaway delivery is established through the path nodes and the ants;
处理模块，用于基于最大最小蚂蚁算法MMAS在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，根据所述信息素对所述路径轨迹模型进行路径遍历，确定最优路径和最优路径蚂蚁；The processing module is used to set the pheromone used to guide the ants to move the path nodes on the path based on the maximum and minimum ant algorithm MMAS, and perform path traversal on the path trajectory model according to the pheromone, and determine the optimal path and the maximum path. optimal path ant;
按照设置的迭代次数将所述最优路径蚂蚁在所述最优路径上进行路径遍历，根据轮盘选择算法选择路径节点以更新所述信息素，当完成迭代次数时，输出最优目标规划路径。The optimal path ants are traversed on the optimal path according to the set number of iterations, the path node is selected according to the roulette selection algorithm to update the pheromone, and when the number of iterations is completed, the optimal target planning path is output .
本发明解决上述技术问题的另一技术方案如下：一种外卖派送路径规划系统，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，当所述处理器执行所述计算机程序时，实现如上所述的外卖派送路径规划方法。Another technical solution of the present invention to solve the above technical problem is as follows: a food delivery route planning system, comprising a memory, a processor, and a computer program stored in the memory and running on the processor, when the processing When the computer executes the computer program, the above-mentioned takeaway delivery path planning method is implemented.
本发明解决上述技术问题的另一技术方案如下：一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，当所述计算机程序被处理器执行时，实现如上所述的外卖派送路径规划方法。Another technical solution of the present invention to solve the above technical problem is as follows: a computer-readable storage medium, the computer-readable storage medium stores a computer program, when the computer program is executed by a processor, the above-mentioned takeout is realized Delivery route planning method.
附图说明Description of drawings
图1为本发明实施例提供的外卖派送路径规划方法的流程示意图；FIG. 1 is a schematic flowchart of a method for planning a food delivery path according to an embodiment of the present invention;
图2为本发明实施例提供的外卖派送路径规划系统的功能模块框图。FIG. 2 is a block diagram of functional modules of a food delivery route planning system provided by an embodiment of the present invention.
具体实施方式Detailed ways
以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于限定本发明的范围。The principles and features of the present invention will be described below with reference to the accompanying drawings. The examples are only used to explain the present invention, but not to limit the scope of the present invention.
实施例1：Example 1:
如图1所示，一种外卖派送路径规划方法，包括如下步骤：As shown in Figure 1, a method for planning a delivery route for food delivery includes the following steps:
将外卖派送起点、外卖途径点和外卖派送终点作为路径节点，将外卖派送员作为蚂蚁，通过所述路径节点和所述蚂蚁建立外卖派送的路径轨迹模型；The takeaway delivery starting point, the takeaway route point, and the takeaway delivery end point are used as path nodes, and the takeaway delivery person is used as an ant, and a path trajectory model of the takeaway delivery is established through the path node and the ants;
基于最大最小蚂蚁算法MMAS在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，根据所述信息素对所述路径轨迹模型进行路径遍历，确定最优路径和最优路径蚂蚁；Based on the maximum and minimum ant algorithm MMAS, a pheromone for guiding the ants to move a path node is set on the path, and the path trajectory model is traversed according to the pheromone to determine the optimal path and the optimal path ants;
根据轮盘选择算法选择路径节点以更新所述信息素，并按照设置的迭代次数和更新后的信息素将所述最优路径蚂蚁在所述最优路径上进行路径遍历，当完成迭代次数时，输出最优目标规划路径。Select path nodes according to the roulette wheel selection algorithm to update the pheromone, and traverse the optimal path ants on the optimal path according to the set number of iterations and the updated pheromone. When the number of iterations is completed , and output the optimal target planning path.
应理解地，在本发明实施例中，利用最大最小蚂蚁算法MMAS对外卖派送进行路径规划之前，需要预先建立全面真实的外卖派送路径轨迹模型。具体的，针对外卖派送模型，至少需要各个派送点的坐标，以及周边的道路环境。It should be understood that, in this embodiment of the present invention, before using the maximum-minimum ant algorithm MMAS to perform path planning for food delivery, a comprehensive and real food delivery path trajectory model needs to be established in advance. Specifically, for the takeaway delivery model, at least the coordinates of each delivery point and the surrounding road environment are required.
建立全面真实的外卖派送路径轨迹模型之后，在路径规划过程中，应在系统建立多个外卖派送节点、外卖派送起点、外卖派送终点；同理，在某一区域内，外卖派送员的数量也可以是多个，然后规划最优外卖路径。所有蚁群算法都会设置蚂蚁来进行路径遍历，同时蚂蚁会设置信息素，不同的蚁群算法对路径规划原则和信息素更新规则各有不同。最大最小蚁群算法的特点是：在每次循环之后，只有最优的蚂蚁可以进行信息素更新。最优解可以是迭代最优解，也可以是全局最优解，也可以是两者的混合策略，一般使用全局最优解。After establishing a comprehensive and real takeaway delivery path trajectory model, in the path planning process, multiple takeaway delivery nodes, takeaway delivery starting points, and takeaway delivery destinations should be established in the system; similarly, in a certain area, the number of takeaway delivery staff is also There can be multiple, and then plan the optimal delivery path. All ant colony algorithms will set ants to traverse paths, and ants will set pheromone. Different ant colony algorithms have different path planning principles and pheromone update rules. The characteristic of the max-min ant colony algorithm is that after each cycle, only the optimal ants can update the pheromone. The optimal solution can be an iterative optimal solution, a global optimal solution, or a hybrid strategy of the two. Generally, the global optimal solution is used.
当完成迭代次数时，输出最优目标规划路径，具体为：When the number of iterations is completed, the optimal target planning path is output, specifically:
每次迭代完成时(即路径遍历完成时)，判断是否完成预设的迭代次数，When each iteration is completed (that is, when the path traversal is completed), it is judged whether the preset number of iterations is completed.
若否，获取历史最优的从外卖派送起点经过多个外卖派送节点并到达外卖派送终点对应的节点顺序，以及根据最大最小蚁群算法计算得到的从外卖派送起点经过多个外卖派送节点并到达外卖派送终点对应的节点顺序；If not, obtain the historically optimal node sequence from the takeaway delivery starting point through multiple takeaway delivery nodes to the takeaway delivery end point, as well as the node sequence calculated according to the maximum and minimum ant colony algorithm from the takeaway delivery starting point through multiple takeaway delivery nodes and arrive at the takeaway delivery point The order of nodes corresponding to the takeaway delivery destination;
将两条外卖节点顺序派送路径中路径长度小的标记为历史最优；Mark the shortest path length in the sequential delivery paths of the two takeaway nodes as the historical optimal;
根据设置的信息素的量值，选取目标路径点；Select the target path point according to the set pheromone value;
根据所述目标路径点获得目标规划路径。The target planning path is obtained according to the target path point.
若是，则从多个目标规划路径中，选择路径长度最小的目标规划路径，作为最优目标规划路径，并输出最优目标规划路径。If so, select the target planning path with the smallest path length from the multiple target planning paths as the optimal target planning path, and output the optimal target planning path.
也就是说，每次迭代完成时会得到目标规划路径，并判断是否完成预设的迭代次数，若是，则输出所述目标规划路径，若否，则根据轮盘选择算法选择路径节点以更新所述信息素，并按照设置的迭代次数和更新后的信息素将所述最优路径蚂蚁在所述最优路径上进行路径遍历，从而得到目标规划路径，直至满足预设的迭代次数，从而输出最优目标规划路径。That is to say, when each iteration is completed, the target planning path will be obtained, and it will be judged whether the preset number of iterations is completed. If so, the target planning path will be output. If not, the path node will be selected according to the wheel selection algorithm to update all the the pheromone, and traverse the optimal path ants on the optimal path according to the set number of iterations and the updated pheromone, so as to obtain the target planning path until the preset number of iterations is satisfied, thereby outputting The optimal target planning path.
上述实施例中，将各个派送节点作为路径节点，外卖派送员作为蚂蚁，来构建路径轨迹模型，通过MMAS算法设置路径节点的信息素，以得到最优路径和最优路径蚂蚁，并结合轮盘选择算法选择路径节点以更新信息素，并进行多次迭代，输出最优目标规划路径，使外卖派送路径规划效率明显提升，并且相比于人工规划，其路径选择也更为优化。In the above-mentioned embodiment, each delivery node is used as a path node, and the delivery person is used as an ant to construct a path trajectory model, and the pheromone of the path node is set by the MMAS algorithm to obtain the optimal path and the optimal path ants, and combined with the roulette wheel. The selection algorithm selects path nodes to update pheromone, and performs multiple iterations to output the optimal target planning path, which significantly improves the efficiency of food delivery path planning. Compared with manual planning, the path selection is also more optimized.
具体地，所述基于最大最小蚂蚁算法MMAS，在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，具体为：Specifically, based on the maximum and minimum ant algorithm MMAS, a pheromone for guiding the ants to move the path nodes is set on the path, specifically:
根据式(1)在路径遍历过程中在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，所述式(1)为：According to the formula (1), the pheromone used to guide the ants to move the path nodes is set on the path during the path traversal process, and the formula (1) is:
其中，τij为信息素，
上述实施例中，通过设置的信息素来引导蚂蚁移动，来进行路径遍历，从而确定最优路径和最优路径蚂蚁。In the above embodiment, the ants are guided to move by the set pheromone to perform path traversal, so as to determine the optimal path and the optimal path ants.
具体地，所述根据轮盘选择算法选择路径节点以更新所述信息素，具体为：Specifically, the selecting a path node according to the roulette wheel selection algorithm to update the pheromone is specifically:
在概率区间设置随机数R，用随机数R减去第一预设值，若差值结果小于或等于0，则选择随机数R对应的路径节点作为下一个移动的路径节点，通过式(1)更新所述下一个移动的路径节点的信息素；A random number R is set in the probability interval, and the first preset value is subtracted from the random number R. If the difference result is less than or equal to 0, the path node corresponding to the random number R is selected as the next moving path node. By formula (1 ) update the pheromone of the next moving path node;
若大于0，则用差值结果再减去第二预设值，直至差值结果小于或等于0，将最后一次减去第二预设值得到的差值结果所对应的路径节点作为下一个移动的路径节点，通过式(1)更新所述下一个移动的路径节点的信息素。If it is greater than 0, the second preset value is subtracted from the difference result until the difference result is less than or equal to 0, and the path node corresponding to the difference result obtained by the last subtraction of the second preset value is used as the next For the moving path node, the pheromone of the next moving path node is updated by formula (1).
应理解地，应理解地，在MMAS算法每次路径在选择最佳蚂蚁时，引入了轮盘选择算法。现有的蚁群算法在路径选择时引入了轮盘选择的机制，以避免像贪心算法、爬山算法等算法过早陷入局部最优的问题，因为按照蚁群算法的特征，在经过一定次数的迭代搜索后，所有的蚂蚁在大概率上都会陷入同一解，也就是局部最优值。本发明针对这一思路，对于最大最小蚁群算法，在每次循环结束后，挑选最佳蚂蚁时，也引入了轮盘选择。核心思想是将最佳的蚂蚁数量设置一定的比例(比如：N/4)，轮盘选择这条只蚂蚁中的一只作为“最佳蚂蚁”，在这种情况下就不一定是路径最佳的蚂蚁。这一改进策略会增加最大最小蚂蚁算法MMAS中的随机性，避免算法过早陷入停滞。It should be understood that, when the MMAS algorithm selects the best ant for each path, a roulette wheel selection algorithm is introduced. The existing ant colony algorithm introduces the roulette selection mechanism in the path selection to avoid prematurely falling into the local optimal problem of algorithms such as the greedy algorithm and the hill-climbing algorithm, because according to the characteristics of the ant colony algorithm, after a certain number of After iterative search, all ants will fall into the same solution with high probability, that is, the local optimum. Aiming at this idea, the present invention also introduces roulette wheel selection when selecting the best ants after each cycle ends for the maximum and minimum ant colony algorithm. The core idea is to set a certain ratio of the optimal number of ants (for example: N/4), and the roulette wheel selects one of the ants as the "best ant". In this case, it is not necessarily the best path. Good ants. This improved strategy will increase the randomness in the max-min ant algorithm MMAS, and avoid premature stagnation of the algorithm.
在每次遍历完成后，根据最大最小蚁群算法选择得到最优路径的蚂蚁，然后根据该蚂蚁的信息素来更新各外卖节点的信息素。而在下一次遍历开始后，蚂蚁在到达一个外卖节点后，在选择下一个的外卖节点时，虽然下一站的外卖节点会有信息素的顺序排列，但根据轮盘赌在选择下一次的外卖节点。After each traversal is completed, the ant that obtains the optimal path is selected according to the maximum and minimum ant colony algorithm, and then the pheromone of each takeaway node is updated according to the pheromone of the ant. After the next traversal starts, after the ants arrive at a delivery node, when selecting the next delivery node, although the delivery node at the next stop will be arranged in the order of pheromone, according to the roulette, the next delivery node is selected. node.
蚁群算法是带有正反馈的随机搜索算法，随机性和正反馈是算法的核心，丢失任何一个都会使算法失去作用。正反馈是通过信息素来实现的，而随机性正是通过轮盘选择来实现的。轮盘选择，也称轮盘赌算法等。Ant colony algorithm is a random search algorithm with positive feedback. Randomness and positive feedback are the core of the algorithm. Losing any one of them will make the algorithm useless. Positive feedback is achieved through pheromones, and randomness is achieved through roulette selection. Roulette selection, also known as roulette algorithm, etc.
假设蚂蚁在D点，ABC为已经去过的点，EFG为没去过的点,现在蚂蚁要在EFG中选择一个点作为下一步要到达的点，已知表1中的信息。根据信息素除以距离，再比较整体的概率，可得D点前往这三个点的实际概率(表1第四列)，因此按照常理应该选F点为D点的下一个点。Suppose the ant is at point D, ABC is the point that has been visited, and EFG is the point that has not been visited. Now the ant needs to select a point in the EFG as the point to be reached in the next step, and the information in Table 1 is known. According to dividing the pheromone by the distance, and then comparing the overall probability, the actual probability of point D going to these three points can be obtained (the fourth column of Table 1). Therefore, according to common sense, point F should be selected as the next point of point D.
表1Table 1
但是如果每只蚂蚁到了D点都会选择F点作为下一个点，那样最终每只蚂蚁所走过的路径都是相同的，这样算法陷入停滞。为了避免这个问题，通常采用轮盘选择来决定下一个去往的路径节点，方法如下：However, if each ant reaches point D, it will select point F as the next point, then in the end, the path that each ant travels is the same, and the algorithm is stagnant. In order to avoid this problem, the roulette wheel selection is usually used to determine the next path node, the method is as follows:
在[0,1]之间取一个随机数R。然后用R减pE(D点前往E点的概率)，如果减去后的结果小于等于0就选E作为下一个去往的路径节点，如果减去后还大于0，就继续再减去pF(D点前往F点的概率)，直到减去后的结果小于等于0。然后用最后减去时的那个概率值对应的点作为下一个去往的路径节点。Take a random number R between [0,1]. Then subtract pE from R (the probability of point D going to point E). If the result of the subtraction is less than or equal to 0, select E as the next path node to go to. If it is still greater than 0 after subtraction, continue to subtract pF. (Probability of point D going to point F), until the result after subtraction is less than or equal to 0. Then use the point corresponding to the probability value at the last subtraction as the next path node.
上述实施例中，通过轮盘选择算法来选择路径节点进行更新信息素，且尽量避免算法陷入停滞。In the above embodiment, the roulette wheel selection algorithm is used to select the path node to update the pheromone, and try to avoid the algorithm from stagnant.
具体地，在更新所述信息素的过程中，还包括步骤：Specifically, in the process of updating the pheromone, it also includes the steps:
当算法停滞时，根据式(2)重新设置路径节点的信息素，所述式(2)为：When the algorithm is stagnant, the pheromone of the path node is reset according to the formula (2), the formula (2) is:
其中，
上述实施例中，针对信息素平滑策略，在求解规模比较大的问题或者迭代次数比较多的时候，当算法陷入停滞的时候，可以重新设置环境信息素。In the above embodiment, for the pheromone smoothing strategy, when solving a relatively large-scale problem or when the number of iterations is relatively large, when the algorithm is stagnant, the environmental pheromone can be reset.
本发明保留了MMAS算法的核心思想，继承了MMAS的优点，使得路径规划更为有效。The invention retains the core idea of the MMAS algorithm, inherits the advantages of the MMAS, and makes the path planning more effective.
实施例2：Example 2:
如图2所示，一种外卖派送路径规划系统，包括：As shown in Figure 2, a food delivery path planning system includes:
模型建立模块，用于将外卖派送起点、外卖途径点和外卖派送终点作为路径节点，将外卖派送员作为蚂蚁，通过所述路径节点和所述蚂蚁建立外卖派送的路径轨迹模型；The model building module is used to take the start of takeaway delivery, the takeaway route point and the takeaway delivery end point as path nodes, the takeaway delivery staff as ants, and the path trajectory model of takeaway delivery is established through the path nodes and the ants;
处理模块，用于基于最大最小蚂蚁算法MMAS在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，根据所述信息素对所述路径轨迹模型进行路径遍历，确定最优路径和最优路径蚂蚁；The processing module is used to set the pheromone used to guide the ants to move the path nodes on the path based on the maximum and minimum ant algorithm MMAS, and perform path traversal on the path trajectory model according to the pheromone, and determine the optimal path and the maximum path. optimal path ant;
按照设置的迭代次数将所述最优路径蚂蚁在所述最优路径上进行路径遍历，根据轮盘选择算法选择路径节点以更新所述信息素，当完成迭代次数时，输出最优目标规划路径。The optimal path ants are traversed on the optimal path according to the set number of iterations, the path node is selected according to the roulette selection algorithm to update the pheromone, and when the number of iterations is completed, the optimal target planning path is output .
具体地，所述处理模块中，所述基于最大最小蚂蚁算法MMAS，在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，具体为：Specifically, in the processing module, based on the maximum and minimum ant algorithm MMAS, a pheromone for guiding the ants to move the path nodes is set on the path, specifically:
根据式(1)在路径遍历过程中在路径上设置用于引导所述蚂蚁进行路径节点移动的信息素，所述式(1)为：According to the formula (1), the pheromone used to guide the ants to move the path nodes is set on the path during the path traversal process, and the formula (1) is:
其中，τij为信息素，
具体地，所述处理模块中，所述根据轮盘选择算法选择路径节点以更新所述信息素，具体为：Specifically, in the processing module, the path node is selected according to the roulette wheel selection algorithm to update the pheromone, specifically:
在概率区间设置随机数R，用随机数R减去第一预设值，若差值结果小于或等于0，则选择随机数R对应的路径节点作为下一个移动的路径节点，通过式(1)更新所述下一个移动的路径节点的信息素；A random number R is set in the probability interval, and the first preset value is subtracted from the random number R. If the difference result is less than or equal to 0, the path node corresponding to the random number R is selected as the next moving path node. By formula (1 ) update the pheromone of the next moving path node;
若大于0，则用差值结果再减去第二预设值，直至差值结果小于或等于0，将最后一次减去第二预设值得到的差值结果所对应的路径节点作为下一个移动的路径节点，通过式(1)更新所述下一个移动的路径节点的信息素。If it is greater than 0, the second preset value is subtracted from the difference result until the difference result is less than or equal to 0, and the path node corresponding to the difference result obtained by the last subtraction of the second preset value is used as the next For the moving path node, the pheromone of the next moving path node is updated by formula (1).
具体地，所述处理模块，还用于：Specifically, the processing module is also used for:
当MMAS算法停滞时，根据式(2)重新设置路径节点的信息素，所述式(2)为：When the MMAS algorithm is stagnant, the pheromone of the path node is reset according to the formula (2), and the formula (2) is:
其中，
实施例3：Example 3:
一种外卖派送路径规划系统，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，当所述处理器执行所述计算机程序时，实现如上所述的外卖派送路径规划方法。A food delivery route planning system, comprising a memory, a processor and a computer program stored in the memory and executable on the processor, when the processor executes the computer program, the above-mentioned Takeaway delivery route planning method.
实施例4：Example 4:
一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，当所述计算机程序被处理器执行时，实现如上所述的外卖派送路径规划方法。A computer-readable storage medium storing a computer program, when the computer program is executed by a processor, implements the above-mentioned method for planning a food delivery path.
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。It should be noted that, in this document, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply any relationship between these entities or operations. any such actual relationship or sequence exists. Moreover, the terms "comprising", "comprising" or any other variation thereof are intended to encompass a non-exclusive inclusion such that a process, method, article or device that includes a list of elements includes not only those elements, but also includes not explicitly listed or other elements inherent to such a process, method, article or apparatus.
所属领域的技术人员可以清楚地了解到，为了描述的方便和简洁，上述描述的系统和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。Those skilled in the art can clearly understand that, for the convenience and brevity of description, for the specific working process of the system and unit described above, reference may be made to the corresponding process in the foregoing method embodiments, which will not be repeated here.
在本申请所提供的几个实施例中，应该理解到，所揭露的系统和方法，可以通过其它的方式实现。例如，以上所描述的系统实施例仅仅是示意性的，例如，单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。In the several embodiments provided in this application, it should be understood that the disclosed system and method may be implemented in other manners. For example, the system embodiments described above are only illustrative. For example, the division of units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components may be combined or integrated. to another system, or some features can be ignored, or not implemented.
作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本发明实施例方案的目的。Units described as separate components may or may not be physically separated, and components shown as units may or may not be physical units, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solutions in the embodiments of the present invention.
另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以是两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。In addition, each functional unit in each embodiment of the present invention may be integrated into one processing unit, or each unit may exist physically alone, or two or more units may be integrated into one unit. The above-mentioned integrated units may be implemented in the form of hardware, or may be implemented in the form of software functional units.
集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分，或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。The integrated unit, if implemented as a software functional unit and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present invention is essentially or a part that contributes to the prior art, or all or part of the technical solution can be embodied in the form of a software product, and the computer software product is stored in a storage medium , including several instructions to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods of the various embodiments of the present invention. The aforementioned storage medium includes: U disk, removable hard disk, Read-Only Memory (ROM, Read-Only Memory), Random Access Memory (RAM, Random Access Memory), magnetic disk or optical disk and other media that can store program codes .
以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included in the protection of the present invention. within the range.
Claims (10)
Translated fromChinese
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111395452.0ACN114217607A (en) | 2021-11-23 | 2021-11-23 | Takeout delivery path planning method, system and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111395452.0ACN114217607A (en) | 2021-11-23 | 2021-11-23 | Takeout delivery path planning method, system and storage medium |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN114217607Atrue CN114217607A (en) | 2022-03-22 |
Family
ID=80697977
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111395452.0APendingCN114217607A (en) | 2021-11-23 | 2021-11-23 | Takeout delivery path planning method, system and storage medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114217607A (en) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116795108A (en)* | 2023-06-09 | 2023-09-22 | 西南交通大学 | Intelligent unmanned vehicle distribution method based on multi-source sensing signals |
| CN117217396A (en)* | 2023-09-12 | 2023-12-12 | 广西交科集团有限公司 | Multi-target dispatch path existence judging method and system based on road network |
| CN118940928A (en)* | 2024-10-12 | 2024-11-12 | 济南高品伟业信息科技有限公司 | A method and system for optimizing takeout delivery routes at campus delivery stations |
| CN119940669A (en)* | 2024-12-20 | 2025-05-06 | 南京信息工程大学 | A single-passenger travel route planning method based on the maximum-minimum ant system |
Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103345504A (en)* | 2013-07-03 | 2013-10-09 | 邢立宁 | Operator construction method of single-star scheduling |
| CN104700251A (en)* | 2015-03-16 | 2015-06-10 | 华南师范大学 | Maximum-minimum ant colony optimization method and maximum-minimum ant colony optimization system for solving vehicle scheduling problem |
| CN105589461A (en)* | 2015-11-18 | 2016-05-18 | 南通大学 | Parking system path planning method on the basis of improved ant colony algorithm |
| CN105868858A (en)* | 2016-03-31 | 2016-08-17 | 华南理工大学 | Method for optimizing track of engraving machine |
| CN106228265A (en)* | 2016-07-18 | 2016-12-14 | 中山大学 | Based on Modified particle swarm optimization always drag phase transport project dispatching algorithm |
| CN109800911A (en)* | 2019-01-10 | 2019-05-24 | 华南理工大学 | A method of part path unified navigation is sent for several couriers |
| CN111413932A (en)* | 2020-03-29 | 2020-07-14 | 河南工程学院 | Information management and scheduling system and method for unmanned electric cleaning vehicle |
| CN111857141A (en)* | 2020-07-13 | 2020-10-30 | 武汉理工大学 | A robot path planning method, device, equipment and storage medium |
| CN112161627A (en)* | 2020-09-23 | 2021-01-01 | 同济大学 | An intelligent path planning method for firefighting robots |
| CN113110472A (en)* | 2021-04-25 | 2021-07-13 | 深圳市跨越新科技有限公司 | Path planning method and device and terminal |
| CN113139669A (en)* | 2020-01-17 | 2021-07-20 | 北京京邦达贸易有限公司 | Multi-target route planning method and device, electronic equipment and storage medium |
- 2021
- 2021-11-23CNCN202111395452.0Apatent/CN114217607A/enactivePending
Patent Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103345504A (en)* | 2013-07-03 | 2013-10-09 | 邢立宁 | Operator construction method of single-star scheduling |
| CN104700251A (en)* | 2015-03-16 | 2015-06-10 | 华南师范大学 | Maximum-minimum ant colony optimization method and maximum-minimum ant colony optimization system for solving vehicle scheduling problem |
| CN105589461A (en)* | 2015-11-18 | 2016-05-18 | 南通大学 | Parking system path planning method on the basis of improved ant colony algorithm |
| CN105868858A (en)* | 2016-03-31 | 2016-08-17 | 华南理工大学 | Method for optimizing track of engraving machine |
| CN106228265A (en)* | 2016-07-18 | 2016-12-14 | 中山大学 | Based on Modified particle swarm optimization always drag phase transport project dispatching algorithm |
| CN109800911A (en)* | 2019-01-10 | 2019-05-24 | 华南理工大学 | A method of part path unified navigation is sent for several couriers |
| CN113139669A (en)* | 2020-01-17 | 2021-07-20 | 北京京邦达贸易有限公司 | Multi-target route planning method and device, electronic equipment and storage medium |
| CN111413932A (en)* | 2020-03-29 | 2020-07-14 | 河南工程学院 | Information management and scheduling system and method for unmanned electric cleaning vehicle |
| CN111857141A (en)* | 2020-07-13 | 2020-10-30 | 武汉理工大学 | A robot path planning method, device, equipment and storage medium |
| CN112161627A (en)* | 2020-09-23 | 2021-01-01 | 同济大学 | An intelligent path planning method for firefighting robots |
| CN113110472A (en)* | 2021-04-25 | 2021-07-13 | 深圳市跨越新科技有限公司 | Path planning method and device and terminal |
Non-Patent Citations (1)
| Title |
|---|
| 张元良: "移动机器人导航与控制算法设计", vol. 1, 华中科技大学出版社, pages: 57 - 76* |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116795108A (en)* | 2023-06-09 | 2023-09-22 | 西南交通大学 | Intelligent unmanned vehicle distribution method based on multi-source sensing signals |
| CN116795108B (en)* | 2023-06-09 | 2023-12-01 | 西南交通大学 | Intelligent unmanned vehicle distribution method based on multi-source sensing signals |
| CN117217396A (en)* | 2023-09-12 | 2023-12-12 | 广西交科集团有限公司 | Multi-target dispatch path existence judging method and system based on road network |
| CN117217396B (en)* | 2023-09-12 | 2024-06-11 | 广西交科集团有限公司 | A method and system for determining the existence of multi-target delivery paths based on road network |
| CN118940928A (en)* | 2024-10-12 | 2024-11-12 | 济南高品伟业信息科技有限公司 | A method and system for optimizing takeout delivery routes at campus delivery stations |
| CN118940928B (en)* | 2024-10-12 | 2025-02-14 | 济南高品伟业信息科技有限公司 | A method and system for optimizing takeout delivery routes at campus delivery stations |
| CN119940669A (en)* | 2024-12-20 | 2025-05-06 | 南京信息工程大学 | A single-passenger travel route planning method based on the maximum-minimum ant system |
| CN119940669B (en)* | 2024-12-20 | 2025-09-30 | 南京信息工程大学 | Single-passenger travel route planning method based on maximum and minimum ant system |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN114217607A (en) | Takeout delivery path planning method, system and storage medium | |
| CN111310999B (en) | A path planning method for warehouse mobile robot based on improved ant colony algorithm | |
| CN107272679B (en) | Path Planning Method Based on Improved Ant Colony Algorithm | |
| CN110160546B (en) | A mobile robot path planning method | |
| CN108564163B (en) | Improved ant colony method for solving multi-target multi-traveler problem | |
| CN106779212A (en) | A kind of city tour's route planning method based on improvement ant group algorithm | |
| CN102778229B (en) | Mobile Agent path planning method based on improved ant colony algorithm under unknown environment | |
| CN109974711A (en) | A kind of AGV multiple target point autonomous navigation method towards wisdom factory | |
| CN112327876B (en) | Robot path planning method based on terminal distance index | |
| CN112461240A (en) | Unmanned aerial vehicle obstacle avoidance path planning method and system | |
| CN110726408A (en) | A Path Planning Method for Mobile Robots Based on Improved Ant Colony Algorithm | |
| CN115373384B (en) | A vehicle dynamic path planning method and system based on improved RRT | |
| CN114721400A (en) | Ant colony algorithm-based path optimization method and water surface garbage collection path planning | |
| CN105429877A (en) | A Path Finding Method Based on Particle Swarm Optimization | |
| CN113468293A (en) | Road network Top-k path query method based on multi-keyword coverage | |
| CN110941267A (en) | Dynamic path planning method of ant colony algorithm in congestion environment | |
| CN110675004A (en) | Route planning method based on wolf algorithm | |
| CN117313967A (en) | Dangerous goods transportation path planning method based on improved ant colony algorithm | |
| CN112507047A (en) | Optimal ordered path query method based on interest point preference | |
| CN109840625A (en) | A kind of method of courier's group path navigation | |
| WO2023173831A1 (en) | Method and apparatus for updating associated information of guide points | |
| CN109800911A (en) | A method of part path unified navigation is sent for several couriers | |
| CN108627163B (en) | Weight table maintenance method and device and navigation route planning method and device | |
| CN112488358A (en) | Electric vehicle charging path planning method and storage medium | |
| CN113219994A (en) | Grid map optimal path planning method comprising traffic signal lamps |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication | Application publication date:20220322 |