书畅云
English Version
中南大学出版社
无数据
高级检索
您当前的位置：
首页 >
文章列表页 >
面向大型工业仓库的多AGV综合优化调度方法
机械工程 • 控制科学与工程 | 更新时间：2023-06-20
|
面向大型工业仓库的多AGV综合优化调度方法
An integrated scheduling method of multi-AGV in large-scale industrial warehouses
- 中南大学学报(自然科学版)
- 作者机构：
1.中南大学 自动化学院，湖南 长沙，410083
- 作者简介：
贺建军，博士，教授，从事系统优化与调度研究；E-mail：jjhe@csu.edu.cn
贺
建
军
，
博
士
，
教
授
，
从
事
系
统
优
化
与
调
度
研
究
；
E
-
m
a
i
l
：
j
j
h
e
@
c
s
u
.
e
d
u
.
c
n
- 基金信息：国家自然科学基金资助项目(61873282)
DOI：10.11817/j.issn.1672-7207.2023.05.013
中图分类号： TP273纸质出版日期：2023-05-26，
收稿日期：2022-07-11，
修回日期：2022-08-20，
扫 描 看 全 文
引用本文
胡恩泽, 贺建军, 申帅, 等. 面向大型工业仓库的多AGV综合优化调度方法[J]. 中南大学学报(自然科学版), 2023, 54(5): 1779-1790.
HU Enze, HE Jianjun, SHEN Shuai, et al. An integrated scheduling method of multi-AGV in large-scale industrial warehouses[J]. Journal of Central South University(Science and Technology), 2023, 54(5): 1779-1790.
胡恩泽, 贺建军, 申帅, 等. 面向大型工业仓库的多AGV综合优化调度方法[J]. 中南大学学报(自然科学版), 2023, 54(5): 1779-1790. DOI： 10.11817/j.issn.1672-7207.2023.05.013.
HU Enze, HE Jianjun, SHEN Shuai, et al. An integrated scheduling method of multi-AGV in large-scale industrial warehouses[J]. Journal of Central South University(Science and Technology), 2023, 54(5): 1779-1790. DOI： 10.11817/j.issn.1672-7207.2023.05.013.
面向大型工业仓库的多AGV综合优化调度方法
面向大型工业仓库的多 AGV 综合优化调度方法 An integrated scheduling method of multi-AGV in large-scale industrial warehouses first-author corresp 贺建军，博士，教授，从事系统优化与调度研究；E-mail：jjhe@csu.edu.cn 贺建军，博士，教授，从事系统优化与调度研究；E-mail：jjhe@csu.edu.cn jjhe@csu.edu.cn 中南大学 自动化学院，湖南 长沙，410083 中南大学 自动化学院，湖南 长沙，410083 School of Automation, Central South University, Changsha 410083, China School of Automation, Central South University, Changsha 410083, China 陈灿华 针对大型工业仓库中自动引导车(AGV)集群执行大规模任务时效率低的问题，提出一种基于分层规划的综合优化调度方法，将调度问题分解为聚合的上层任务定序分配问题和下层路径规划问题。在上层问题中生成精英解集，将下层路径规划生成的禁忌列表作为碰撞冲突约束条件融入上层问题迭代寻优过程，并在迭代搜索中，将路径规划结果反馈给上层问题并更新约束条件，通过上下两层问题的综合计算得到整体性能最优的方案。进一步将路径搜索和禁忌列表融合，实现AGV调度中相互关联的多个问题的同步优化。通过大型工业仓库实例验证该方法的有效性。研究结果表明：相较于依次优化调度方法，基于分层规划的综合优化调度方法的平均任务完成时间减少10.56%，碰撞冲突造成的延迟时间减少74.53%；相较于混合自适应大邻域搜索算法和预先规划算法，基于混合离散状态转移算法的分层规划综合调度方法对于大规模问题任务完成时间分别减少9.73%和5.54%，计算时间分别减少84.19%和86.68%。 To address the inefficiency of automated guided vehicle(AGV) fleets in large-scale industrial warehouses, an integrated scheduling method based on hierarchical planning was proposed, which decomposed the scheduling problem into an aggregated upper-level task sequencing assignment problem and a lower-level path planning problem. An elite solution set was generated in the upper-level problem, and the tabu list generated by the lower-level path planning was integrated into the iteration search process as collision conflict constraints for upper-level problem. In iteration search processes, the elite solution of the upper-level problem with a large number of collision conflicts obtained by the path planning was continuously excluded by updating the upper-level elite solution set and the lower-level tabu list, to obtain the solution with the best overall performance. Further integrating path search and tabu lists to achieve simultaneous optimization of multiple interrelated problems in AGV scheduling, the effectiveness of the method was verified by a large-scale industrial warehouse case. The results show that, compared to the sequential optimization scheduling method, the completed time and delay time due to collision conflicts of an integrated scheduling method reduce 10.56% and 74.53%, respectivelty. For large-scale problems, compared to the hybrid adaptive large neighborhood search algorithm and the pre-planning algorithm, the task completion time of an integrated scheduling method reduce by 9.73% and 5.54%, respectively, and the computation time reduce by 84.19% and 86.68%, respectively. 自动引导车(AGV) 综合优化调度 任务定序分配 路径规划 碰撞冲突 automated guided vehicle(AGV) comprehensive optimization scheduling task sequencing assignment path planning collision conflicts http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705431&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705419&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705412&type= 14.66796875 14.66793823 随着仓储物流技术的发展，许多大型工业仓库采用大规模的自动引导车(AGV)编队来实现物料自动运输，其每天需要处理几千起搬运任务，如何优化调度使AGV更高效地执行任务成为当前提升物流效率和降低仓储成本的关键问题。AGV调度最重要的目标是最小化任务完成时间，其受到多项决策的影响 [ 1 1 ] ： 1) 任务定序分配。决定分配给每个AGV的任务及执行这些任务的顺序。 2) 路径规划。为AGV执行被分配的任务时选择最优路径，通常最优路径为耗时最少或距离最短的路径。 3) 冲突管理。解决各AGV之间可能发生的碰撞冲突。 以上3个问题是相互依存的 [ 2 2 ] ，确定AGV的任务分配是计算路径规划的先决条件，在选择AGV的执行路径后才能判断碰撞冲突是否会发生 [ 3 3 ] 。大多数研究针对调度优化的3个问题提出了求解的方法 [ 4 4 - 5 5 4-5 ] ： 首先，在不考虑碰撞冲突的情况下单独求解任务定序分配问题，得到最优方案 [ 6 6 ] ； 然后，为该方案选择最优的执行路径； 最后，考虑冲突管理问题，在发生冲突时建立“交通规则”等策略，指导AGV停车等待或绕行来避免碰撞 [ 7 7 ] 。 然而，AGV按照最优的任务定序分配方案生成的最佳路径去执行任务时，很可能存在大量的碰撞冲突情况 [ 8 8 ] ，频繁等待或绕行会降低AGV整体系统运行效率 [ 9 9 ] 。这些研究忽略了AGV避免冲突的规避操作，导致存在计算之外的“延迟时间” [ 10 10 ] ，无法实现系统整体的最优调度。综上分析，调度中的3个问题是内在关联的，任务定序分配结果会对路径规划中碰撞冲突情况造成直接影响 [ 11 11 ] 。因此，在AGV优化调度问题中，任务定序分配、路径规划和碰撞冲突问题需要经一体化综合处理，进而得到系统整体的最优调度方案 [ 12 12 ] 。 针对AGV综合调度问题，MAZA等 [ 13 13 ] 提出了预先规划算法和实时路由算法，在路径规划过程中生成无冲突路径。LIAN等 [ 14 14 ] 提出一种基于交通控制方法的综合调度方法，实现了基于时间窗的调度和冲突管理。然而，这些方法不能有效提高AGV整体系统效率。SINGH等 [ 15 15 ] 研究了电量约束下的异构AGV综合求解任务分配和路径规划问题，并提出了一种自适应大邻域搜索算法。然而，该方法没有考虑AGV之间的碰撞冲突。此外，一些基于精确算法的综合调度优化方法 [ 16 16 - 17 17 16-17 ] 被用于一体化求解任务定序分配和无冲突路径问题，但任务定序分配结果对路径规划中造成的碰撞冲突情况无法确定，这些方法对每一种情况进行分析时，需要消耗不合理的计算时间，无法应用于大型工业仓库实例。 针对以上问题，本文提出一种综合优化调度方法，体现在： 1) 建立一个混合整数线性规划模型来描述异构多AGV的综合调度问题，采用栅格法构建仓库地图，定义任务执行过程，提出路径专家库的概念，即所有候选路径的集合。针对现实工业仓库对于AGV在速度与物料搬运能力的异构性和AGV需要在适当时间充电等问题，制定相应的约束条件。 2) 提出一种基于分层规划的综合优化调度方法，将综合调度问题分解为聚合的上层任务定序分配问题和下层路径规划问题，在不考虑冲突的情况下生成上层问题的精英解集合，依次对集合中每个解在下层进行基于路径专家库的路径规划计算，记录碰撞冲突结果并生成禁忌列表，将禁忌列表作为碰撞冲突的约束条件融入上层问题寻优过程，最后通过迭代搜索得到满足整体性能最优的调度方案。 3) 提出一种混合离散状态转移算法(HDSTA)，设计一种精英种群生成方法，引入路径选择程序和禁忌列表，提升算法搜索过程的多样性能力与强化搜索能力。同时，为了在任务定序分配结果中合适的位置插入充电请求，提出2种插入算子。 1 调度模型 1 采用栅格法构建仓库地图，定义网格 <math id="M1"><mi>G</mi><mo>=</mo><mo stretchy="false">(</mo><mi>N</mi><mo>,</mo><mtext> </mtext><mi>E</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704317&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704325&type= 15.07066536 3.38666677 ，其中， <math id="M2"><mi>N</mi><mo>=</mo><mo stretchy="false">{</mo><mn mathvariant="normal">1</mn><mo>,</mo><mtext> </mtext><mn mathvariant="normal">2</mn><mo>,</mo><mtext> </mtext><mo>⋯</mo><mo>,</mo><mtext> </mtext><mi>n</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704326&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704336&type= 23.28333473 3.38666677 为节点的集合。节点集合 <math id="M3"><mi>N</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704348&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704327&type= 2.96333337 2.62466669 由充电站集合 <math id="M4"><mi>C</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704338&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704337&type= 2.62466669 2.62466669 、预分拣站集合 <math id="M5"><mi>X</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704329&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704349&type= 3.04800010 2.62466669 、AGV始发站 <math id="M6"><mi>s</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704351&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704350&type= 1.52400005 2.62466669 和AGV终点站 <math id="M7"><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704354&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704353&type= 1.69333339 2.62466669 组成。每对节点之间路径的集合表示为 <math id="M8"><mi>E</mi><mo>=</mo><mo stretchy="false">{</mo><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mtext> </mtext><mi>j</mi><mo>,</mo><mtext> </mtext><mi>p</mi><mo stretchy="false">)</mo><mo>:</mo><mi>i</mi><mo>,</mo><mtext> </mtext><mi>j</mi><mo>∈</mo><mi>N</mi><mo>,</mo><mtext> </mtext><mi>i</mi><mo>≠</mo><mi>j</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704341&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704366&type= 36.74533463 3.38666677 ，其中，连接节点 <math id="M9"><mi>i</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704368&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704342&type= 1.10066664 2.62466669 与节点 <math id="M10"><mi>j</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705272&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705285&type= 1.69333339 3.38666677 的路径 <math id="M11"><mi>p</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704346&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704370&type= 2.28600001 3.38666677 被定义为 <math id="M12"><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mtext> </mtext><mi>j</mi><mo>,</mo><mtext> </mtext><mi>p</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>E</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704362&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704361&type= 15.66333294 3.38666677 。定义所有候选路径的集合为路径专家库 <math id="M13"><msub><mrow><mi>N</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704379&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704393&type= 3.64066648 3.72533321 ，专家库在离线阶段构建。当一组运输任务 <math id="M14"><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704396&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704373&type= 2.45533323 2.62466669 由一组异构的AGV <math id="M15"><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704398&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704381&type= 2.79399991 2.62466669 完成时， <math id="M16"><mi>R</mi><mo>=</mo><mi>T</mi><mo>⋃</mo><mi>B</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704375&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704374&type= 13.71599960 3.21733332 表示所有请求的集合，其中， <math id="M17"><mi>B</mi><mo>=</mo><mo stretchy="false">{</mo><mn mathvariant="normal">1</mn><mo>,</mo><mtext> </mtext><mn mathvariant="normal">2</mn><mo>,</mo><mtext> </mtext><mo>⋯</mo><mo>,</mo><mtext> </mtext><mfenced open="" close="}" separators="|"><mrow><mfenced open="|" close="|" separators="|"><mrow><mi>B</mi></mrow></mfenced></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704376&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704400&type= 26.75466537 4.48733330 表示充电请求集合。将连接请求 <math id="M18"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704422&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704420&type= 1.52400005 2.62466669 拾取节点和请求 <math id="M19"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704422&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704420&type= 1.52400005 2.62466669 交付节点的路径集合记为 <math id="M20"><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704389&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704404&type= 3.38666677 3.72533321 ，而将连接请求 <math id="M21"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704422&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704420&type= 1.52400005 2.62466669 交付节点和请求 <math id="M22"><mi>r</mi><mi>'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704391&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704390&type= 2.45533323 2.62466669 拾取节点的路径集合记为 <math id="M23"><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704424&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704392&type= 4.82600021 3.72533321 。调度优化目标为最小化AGV使用总成本 <math id="M24"><mi>f</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704439&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704438&type= 2.37066650 3.38666677 ，AGV的使用成本与使用时长成正比，目标函数 <math id="M25"><mi>f</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704417&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704425&type= 2.37066650 3.38666677 为 <math display="block" id="M26"><mi>f</mi><mo>=</mo><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><munder><mo movablelimits="false">∑</mo><mrow><mi>k</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>r</mi><mo>∈</mo><mi>T</mi></mrow></munder><mrow><mo stretchy="false">[</mo><msub><mrow><mi>c</mi></mrow><mrow><mi>r</mi></mrow></msub><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>e</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>-</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>s</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo stretchy="false">)</mo><mo stretchy="false">]</mo></mrow></mrow></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704428&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704427&type= 39.79333496 6.77333355 式中： <math id="M27"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 为AGV的编号； <math id="M28"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704422&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704420&type= 1.52400005 2.62466669 为任务的编号； <math id="M29"><msub><mrow><mi>c</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704446&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704445&type= 2.70933342 3.72533321 为充电速率； <math id="M30"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>e</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704432&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704454&type= 3.72533321 4.06400013 为AGV <math id="M31"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 旅行终止时间； <math id="M32"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>s</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704434&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704456&type= 3.64066648 4.06400013 为AGV <math id="M33"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 的旅行开始时间。 保证每个运输请求都被分配给1个AGV并选择1个相关路径完成。 <math display="block" id="M34"><munder><mo movablelimits="false">∑</mo><mrow><mi>k</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>p</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></munder><mrow><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></mrow></mrow><mo>≤</mo><mn mathvariant="normal">1</mn><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704460&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704452&type= 32.08866501 7.45066643 式中： <math id="M35"><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704469&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704437&type= 3.80999994 4.06400013 为二元变量；当AGV <math id="M36"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704465&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704474&type= 1.86266661 2.62466669 按照路径 p 从任务 r 的拾取节点到交付节点时， <math id="M37"><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704472&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704463&type= 8.97466660 4.06400013 ，代表任务 <math id="M38"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704487&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704486&type= 1.52400005 2.62466669 由AGV <math id="M39"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704465&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704474&type= 1.86266661 2.62466669 完成；否则， <math id="M40"><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704489&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704476&type= 8.97466660 4.06400013 。 限定每个充电请求最多由1个AGV提出，每个充电请求 <math id="M41"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704605&type= 1.52400005 2.62466669 对应的路径集合 <math id="M42"><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704493&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704478&type= 3.38666677 3.72533321 仅包含1个路径。 <math display="block" id="M43"><munder><mo movablelimits="false">∑</mo><mrow><mi>k</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>p</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></munder><mrow><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></mrow></mrow><mo>≤</mo><mn mathvariant="normal">1</mn><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>B</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704480&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704494&type= 31.91933441 7.45066643 式中： <math id="M44"><mo stretchy="false">|</mo><mi>B</mi><mo stretchy="false">|</mo><mo>=</mo><mo stretchy="false">|</mo><mi>C</mi><mo stretchy="false">|</mo><mo>⋅</mo><mo stretchy="false">|</mo><mi>K</mi><mo stretchy="false">|</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704500&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704482&type= 17.10266685 3.38666677 ，为一个正整数。 AGV执行任务的能力与使用成本是异构的，限定每个运输任务只能被相匹配的AVG执行。 <math display="block" id="M45"><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">0</mn><mo>,</mo><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>,</mo><mo> </mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>T</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi><mo>,</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>r</mi></mrow><mrow><mi>T</mi></mrow></msubsup><mo>⊈</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>k</mi></mrow><mrow><mi>K</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704516&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704501&type= 60.36733627 5.41866684 式中： <math id="M46"><msubsup><mrow><mi>C</mi></mrow><mrow><mi>r</mi></mrow><mrow><mi>T</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704496&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704502&type= 4.23333359 4.06400013 为运输任务 <math id="M47"><mi>r</mi><mo>∈</mo><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704504&type= 7.78933382 2.62466669 要求的能力集合； <math id="M48"><msubsup><mrow><mi>C</mi></mrow><mrow><mi>k</mi></mrow><mrow><mi>K</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704520&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704530&type= 4.48733330 4.06400013 为AGV <math id="M49"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 的运输能力集合。 <math display="block" id="M50"><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">0</mn><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>R</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704507&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704533&type= 33.61266708 4.82600021 式中： <math id="M51"><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704535&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704522&type= 4.82600021 4.82600021 为二元变量； <math id="M52"><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704510&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704509&type= 9.99066734 4.82600021 表示连接任务 <math id="M53"><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704525&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704537&type= 8.63599968 3.72533321 的交付节点与任务 <math id="M54"><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704538&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704511&type= 8.80533314 3.72533321 的拾取节点的路径被禁止使用。 <math display="block" id="M55"><munder><mo movablelimits="false">∑</mo><mrow><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi mathvariant="normal">s</mi></mrow></msub></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>p</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub></mrow></munder><mrow><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></mrow></mrow><mo>=</mo><munder><mo movablelimits="false">∑</mo><mrow><mi>p</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>r</mi><mi>'</mi></mrow></msub></mrow></munder><mrow><msubsup><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi>'</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo>,</mo></mrow><mo>∀</mo><mi>r</mi><mi>'</mi><mo>∈</mo><mi>R</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704512&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704526&type= 57.74266815 7.70466709 式中： <math id="M56"><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704527&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704539&type= 5.41866684 4.82600021 为二元变量，当AGV <math id="M57"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704549&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704546&type= 1.86266661 2.62466669 按照路径 p 从任务 <math id="M58"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704558&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704541&type= 1.52400005 2.62466669 的交付节点到任务 <math id="M59"><mi>r</mi><mi>'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704545&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704542&type= 2.45533323 2.62466669 的拾取节点时， <math id="M60"><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704575&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704559&type= 10.49866676 4.82600021 表示AGV <math id="M61"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704549&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704546&type= 1.86266661 2.62466669 在完成任务 <math id="M62"><mi>r</mi><mi>'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704550&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704561&type= 2.45533323 2.62466669 之前刚执行完任务 <math id="M63"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704552&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704580&type= 1.52400005 2.62466669 ，在其他情况下 <math id="M64"><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo><mn mathvariant="normal">0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704582&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704553&type= 10.49866676 4.82600021 。 <math id="M65"><msub><mrow><mi>R</mi></mrow><mrow><mi mathvariant="normal">s</mi></mrow></msub><mo>=</mo><mi>R</mi><mo>⋃</mo><mo stretchy="false">{</mo><mi>s</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704555&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704554&type= 16.42533302 4.82600021 ； <math id="M66"><mo stretchy="false">{</mo><mi>s</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704584&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704568&type= 3.97933316 3.38666677 为始发站的集合。 <math display="block" id="M67"><munder><mo movablelimits="false">∑</mo><mrow><mi>p</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></munder><mrow><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>=</mo></mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>r</mi><mi mathvariant="normal">'</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>p</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub></mrow></munder><mrow><msubsup><mrow><mi>y</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup></mrow></mrow><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>R</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704570&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704557&type= 54.77933884 7.70466709 式中： <math id="M68"><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>=</mo><mi>R</mi><mo>⋃</mo><mo stretchy="false">{</mo><mi>e</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704588&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704587&type= 16.76399994 4.82600021 ； <math id="M69"><mo stretchy="false">{</mo><mi>e</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704619&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704572&type= 4.06400013 3.38666677 为终点站的集合。 式(6) 式(6) 和 式(7) 式(7) 保证了每个任务只被执行一次，其中，进入任务路径、任务执行路径和离开任务路径的数量相一致。 从运输任务 <math id="M70"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704605&type= 1.52400005 2.62466669 的拾取节点旅行到交付节点的时间为 <math display="block" id="M71"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>+</mo><msubsup><mrow><mi>h</mi></mrow><mrow><mi>r</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>+</mo><msubsup><mrow><mi>T</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>+</mo><munder><mo movablelimits="false">∑</mo><mrow><mi>g</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>m</mi><mo>∈</mo><mi>T</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>q</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>m</mi></mrow></msub></mrow></munder><mrow><mfenced open="[" close="]" separators="|"><mrow><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo stretchy="false">)</mo><msubsup><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">g</mi></mrow><mrow><mi mathvariant="normal">q</mi></mrow></msubsup></mrow></mfenced></mrow></mrow></mrow><mo>+</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704607&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704590&type= 69.17266846 7.95866632 <math display="block" id="M72"><munder><mo movablelimits="false">∑</mo><mrow><mi>g</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>m</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>m</mi><mi>'</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>q</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi></mrow></msub></mrow></munder><mrow><mfenced open="[" close="]" separators="|"><mrow><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo stretchy="false">)</mo></mrow></mfenced></mrow></mrow></mrow></mrow><mo> </mo><mi mathvariant="normal">*</mi><msub><mrow><msup><mrow><mi>y</mi></mrow><mrow><mi>q</mi></mrow></msup></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi><mi>g</mi></mrow></msub><mo>-</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704609&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704608&type= 64.43132782 8.21266651 <math display="block" id="M73"><mi>M</mi><mo stretchy="false">(</mo><mn mathvariant="normal">1</mn><mo>-</mo><msubsup><mrow><mi>x</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>≤</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>,</mo><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>,</mo><mo> </mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>T</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704623&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704593&type= 58.92800140 4.82600021 式中： <math id="M74"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704611&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704610&type= 3.64066648 4.06400013 为正实数变量，表示AGV <math id="M75"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 到达任务 <math id="M76"><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704835&type= 8.80533314 3.72533321 拾取节点 <math id="M77"><msub><mrow><mi>u</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704859&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704849&type= 2.96333337 3.72533321 的时间； <math id="M78"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>e</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704631&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704616&type= 3.72533321 4.06400013 为AGV <math id="M79"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 的旅途终止时间； <math id="M80"><msubsup><mrow><mi>h</mi></mrow><mrow><mi>r</mi></mrow><mrow><mi>u</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704634&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704648&type= 3.21733332 4.06400013 为装载时间； <math id="M81"><msubsup><mrow><mi>T</mi></mrow><mrow><mi>r</mi><mi>p</mi></mrow><mrow><mi>k</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704651&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704664&type= 4.23333359 4.06400013 为AGV <math id="M82"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 每个路径 <math id="M83"><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704689&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704688&type= 9.48266602 4.48733330 的旅行时间； <math id="M84"><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704667&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704655&type= 19.98133469 4.82600021 为AGV <math id="M85"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 在路径 <math id="M86"><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704689&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704688&type= 9.48266602 4.48733330 上的延迟时间； <math id="M87"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>u</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704661&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704672&type= 4.48733330 4.06400013 为AGV <math id="M88"><mi>g</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704711&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704709&type= 2.03200006 3.38666677 到达任务 <math id="M89"><mi>m</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705195&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705170&type= 2.70933342 2.62466669 拾取节点的时间； <math id="M90"><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704708&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704685&type= 22.01333237 4.82600021 为AGV <math id="M91"><mi>g</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704711&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704709&type= 2.03200006 3.38666677 在路径 <math id="M92"><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704689&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704688&type= 9.48266602 4.48733330 上由其引发的延迟时间； M 为一个正整数。 <math display="block" id="M93"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>+</mo><msubsup><mrow><mi>h</mi></mrow><mrow><mi>r</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>+</mo><msubsup><mrow><mi>T</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>p</mi></mrow></msubsup><mo>+</mo><munder><mo movablelimits="false">∑</mo><mrow><mi>g</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>m</mi><mo>∈</mo><mi>T</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>q</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>m</mi></mrow></msub></mrow></munder><mrow><mfenced open="[" close="]" separators="|"><mrow><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo stretchy="false">)</mo><msubsup><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">g</mi></mrow><mrow><mi mathvariant="normal">q</mi></mrow></msubsup></mrow></mfenced></mrow></mrow></mrow><mo>+</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704715&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704703&type= 71.12000275 7.95866632 <math display="block" id="M94"><munder><mo movablelimits="false">∑</mo><mrow><mi>g</mi><mo>∈</mo><mi>K</mi></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>m</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>m</mi><mi>'</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub></mrow></munder><mrow><munder><mo movablelimits="false">∑</mo><mrow><mi>q</mi><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi></mrow></msub></mrow></munder><mrow><mfenced open="[" close="]" separators="|"><mrow><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo stretchy="false">)</mo></mrow></mfenced></mrow></mrow></mrow></mrow><mi mathvariant="normal">*</mi><msubsup><mrow><mi>y</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi><mi>g</mi></mrow><mrow><mi>q</mi></mrow></msubsup><mo>-</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704707&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704692&type= 62.22999954 8.21266651 <math display="block" id="M95"><mi>M</mi><mo stretchy="false">(</mo><mn mathvariant="normal">1</mn><mo>-</mo><msubsup><mrow><mi>y</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">r</mi><mi>'</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>≤</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>,</mo><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mi>'</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704727&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704725&type= 76.11533356 4.82600021 式中： <math id="M96"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704729&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704740&type= 3.64066648 4.06400013 为正实数变量，表示AGV <math id="M97"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 到达任务 <math id="M98"><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704814&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704794&type= 8.63599968 3.72533321 交付节点 <math id="M99"><msub><mrow><mi>d</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704733&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704721&type= 2.96333337 3.80999994 的时间； <math id="M100"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>s</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704750&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704754&type= 3.64066648 4.06400013 为AGV <math id="M101"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 的旅途开始时间； <math id="M102"><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>g</mi><mi>q</mi></mrow></msubsup><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>,</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>m</mi><mi>g</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704769&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704760&type= 20.48933220 4.82600021 与 <math id="M103"><msubsup><mrow><mi>Φ</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi><mi>k</mi><mi>p</mi></mrow><mrow><mi>m</mi><mi>m</mi><mi>'</mi><mi>g</mi><mi>q</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704784&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704783&type= 8.89000034 4.06400013 为交通规则给出当AGV <math id="M104"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 使用路径 <math id="M105"><mi>q</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704798&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704767&type= 10.49866676 4.48733330 时的2种延迟时间。 式(8) 式(8) 反映了不同任务之间的行驶时间， 式(8) 式(8) 和 式(9) 式(9) 都包含了节点处理时间、路径旅行时间和交通规则给出的延迟时间。 每个请求拾取节点的放电量上界与下界为 <math display="block" id="M106"><msubsup><mrow><mi>b</mi></mrow><mrow><mi>l</mi></mrow><mrow><mi>k</mi></mrow></msubsup><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>≤</mo><msubsup><mrow><mi>b</mi></mrow><mrow><mi>h</mi></mrow><mrow><mi>k</mi></mrow></msubsup><mo>,</mo><mo> </mo><mo>∀</mo><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704790&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704799&type= 42.16400146 4.57200003 式中： <math id="M107"><msubsup><mrow><mi>b</mi></mrow><mrow><mi>l</mi></mrow><mrow><mi>k</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704778&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704791&type= 3.04800010 4.06400013 为最小电量水平； <math id="M108"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704807&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704806&type= 3.80999994 4.06400013 为AGV <math id="M109"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704809&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704792&type= 1.86266661 2.62466669 到达任务 <math id="M110"><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704814&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704794&type= 8.63599968 3.72533321 交付节点 <math id="M111"><msub><mrow><mi>d</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704817&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704815&type= 2.96333337 3.80999994 时，电池的放电量百分比； <math id="M112"><msubsup><mrow><mi>b</mi></mrow><mrow><mi>h</mi></mrow><mrow><mi>k</mi></mrow></msubsup><mo> </mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704818&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704829&type= 3.89466691 4.06400013 为最大电量。 每个任务的交付节点的放电量上界与下界为 <math display="block" id="M113"><msubsup><mrow><mi>b</mi></mrow><mrow><mi>l</mi></mrow><mrow><mi>k</mi></mrow></msubsup><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>≤</mo><msubsup><mrow><mi>b</mi></mrow><mrow><mi>h</mi></mrow><mrow><mi>k</mi></mrow></msubsup><mo> </mo><mo> </mo><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704822&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704820&type= 42.67200089 4.57200003 式中： <math id="M114"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704832&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704831&type= 3.80999994 4.06400013 为AGV <math id="M115"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 到达任务 <math id="M116"><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704835&type= 8.80533314 3.72533321 拾取节点 <math id="M117"><msub><mrow><mi>u</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704859&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704849&type= 2.96333337 3.72533321 时，电池的放电量百分比。 1个运输任务的拾取节点旅行到其交付节点的AGV放电量的变化为 <math display="block" id="M118"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>+</mo><msub><mrow><mi>d</mi></mrow><mrow><mi>k</mi></mrow></msub><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>-</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>-</mo><mi>M</mi><mo stretchy="false">(</mo><mn mathvariant="normal">1</mn><mo>-</mo><msubsup><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>,</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704861&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704851&type= 50.46133423 4.82600021 <math display="block" id="M119"><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>T</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi><mo> </mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704873&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704842&type= 35.56000137 4.48733330 AGV在充电站进行充电请求时放电量的变化为 <math display="block" id="M120"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>-</mo><msub><mrow><mi>c</mi></mrow><mrow><mi>k</mi></mrow></msub><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>-</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>-</mo><mi>M</mi><mo stretchy="false">(</mo><mn mathvariant="normal">1</mn><mo>-</mo><msubsup><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>,</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704874&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704864&type= 50.29199982 4.82600021 <math display="block" id="M121"><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>B</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi><mo> </mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704877&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704876&type= 35.81399918 4.48733330 从一个任务的交付节点旅行到另一个请求的拾取节点的AGV放电量变化为 <math display="block" id="M122"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>+</mo><msub><mrow><mi>d</mi></mrow><mrow><mi>k</mi></mrow></msub><mo stretchy="false">(</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>-</mo><msubsup><mrow><mi>z</mi></mrow><mrow><mi>r</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>-</mo><mi>M</mi><mo stretchy="false">(</mo><mn mathvariant="normal">1</mn><mo>-</mo><msubsup><mrow><mi>y</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">r</mi><mi>'</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>r</mi><mi>'</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>,</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704869&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704868&type= 53.00133133 4.82600021 <math display="block" id="M123"><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi mathvariant="normal">s</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mi>'</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704880&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704870&type= 52.49333191 4.48733330 二元变量的可行域为 <math display="block" id="M124"><msubsup><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo>∈</mo><mo stretchy="false">{</mo><mn mathvariant="normal">0,1</mn><mo stretchy="false">}</mo><mo>,</mo><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><mi>R</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704872&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704890&type= 51.64666748 4.82600021 <math display="block" id="M125"><msubsup><mrow><mi>y</mi></mrow><mrow><mi mathvariant="normal">r</mi><mi mathvariant="normal">r</mi><mi>'</mi><mi mathvariant="normal">k</mi></mrow><mrow><mi mathvariant="normal">p</mi></mrow></msubsup><mo>∈</mo><mo stretchy="false">{</mo><mn mathvariant="normal">0,1</mn><mo stretchy="false">}</mo><mo>,</mo><mtext> </mtext><mo>∀</mo><mi>p</mi><mo>∈</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>r</mi><mi>r</mi><mi>'</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>r</mi><mi>'</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi><mo> </mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704903&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704883&type= 70.78133392 4.82600021 时间相关变量的可行域为 <math display="block" id="M126"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>t</mi><mi>k</mi></mrow><mrow><mi>u</mi></mrow></msubsup><mo>≥</mo><mn mathvariant="normal">0</mn><mo> </mo><mo> </mo><mo>,</mo><mo>∀</mo><mi>t</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704893&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704885&type= 33.86666870 4.57200003 <math display="block" id="M127"><msubsup><mrow><mi>z</mi></mrow><mrow><mi>t</mi><mi>k</mi></mrow><mrow><mi>d</mi></mrow></msubsup><mo>≥</mo><mn mathvariant="normal">0</mn><mo>,</mo><mo>∀</mo><mi>t</mi><mo>∈</mo><msub><mrow><mi>R</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mo>∀</mo><mi>k</mi><mo>∈</mo><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704895&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704886&type= 33.18933105 4.57200003 2 基于分层规划的综合调度方法 1 本文提出一种基于分层规划的综合优化调度方法，将调度问题分解为聚合的上层主问题和下层子问题。上层问题决定AGV任务定序分配决策，下层子问题计算执行任务的最优路径，同时，在2层问题的计算过程中考虑碰撞冲突问题。综合优化调度方法首先在不考虑冲突的情况下生成上层问题的精英解集合；然后，依次对集合中的每个精英解在下层进行基于路径专家库的路径规划计算，计算碰撞冲突并生成禁忌列表；最后，将禁忌列表作为碰撞冲突的约束条件融入上层问题的寻优过程中，通过迭代搜索得到满足整体性能最优的调度方案。 AGV可以通过硬件和“交通规则”避免碰撞，因此，无冲突路径不是强制性的，但规避冲突造成的延迟时间(避免碰撞的等待或绕道时间)需要被量化，同时，在上层问题和下层问题求解过程中减少碰撞冲突，目标是最小化AGV运输时间，即最小化所有AGV执行任务时间和延迟时间(避免碰撞的等待或绕道时间)的总和。此外，为了避免死锁，不允许2辆以上AGV在同一位置发生冲突，存在这种情况的调度方案在计算过程中会被定义为不可行解。综合优化调度方法执行步骤如下。 步骤1：在上层主问题中去除碰撞约束条件，定义AGV每个任务的运输时间为从起始节点到交付节点的最短时间，计算任务定序分配最优解，并将最优解和计算过程中其他精英解放入1个集合 <math id="M128"><msub><mrow><mi>φ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704971&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704961&type= 2.87866688 4.48733330 中。 <math id="M129"><msub><mrow><mi>φ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704971&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704961&type= 2.87866688 4.48733330 中的每个解用 <math id="M130"><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705011&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705010&type= 3.55599999 4.48733330 表示，其中， <math id="M131"><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705011&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705010&type= 3.55599999 4.48733330 在集合 <math id="M132"><msub><mrow><mi>φ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704971&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704961&type= 2.87866688 4.48733330 中按照目标函数值升序排列。 步骤2：在下层问题中，对于 <math id="M133"><msub><mrow><mi>φ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704971&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704961&type= 2.87866688 4.48733330 中每一个解 <math id="M134"><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705011&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705010&type= 3.55599999 4.48733330 进行冲突约束下的路径规划，同时生成一个带有记忆的碰撞冲突约束列表，称为禁忌列表。若路径规划可以找到无冲突路径，则调度优化结束；否则，将碰撞冲突结果记录到禁忌列表中。在每一个 <math id="M135"><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705011&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705010&type= 3.55599999 4.48733330 计算碰撞冲突过程中，将具有最小目标函数值的解记为暂定最优解 <math id="M136"><msub><mrow><mi>p</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704927&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704949&type= 3.04800010 4.48733330 ，其碰撞冲突造成的延迟时间用 <math id="M137"><msub><mrow><mi>t</mi></mrow><mrow><mi>d</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704956&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704941&type= 2.37066650 3.72533321 表示。 步骤3：定义最大允许延迟时间为 <math id="M138"><mi>ε</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704945&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704944&type= 1.52400005 2.62466669 ，若步骤2中推导的 <math id="M139"><msub><mrow><mi>t</mi></mrow><mrow><mi>d</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704956&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704941&type= 2.37066650 3.72533321 小于 <math id="M140"><mi>ε</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704945&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704944&type= 1.52400005 2.62466669 ，则调度优化完成。 步骤4：重新求解上层主问题，在这过程中从 <math id="M141"><msub><mrow><mi>φ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704971&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704961&type= 2.87866688 4.48733330 中去除被记录在禁忌列表中的解。若 <math id="M142"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 次迭代后目标函数值没有降低，则调度优化结束。否则，更新精英集合 <math id="M143"><msub><mrow><mi>φ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704971&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704961&type= 2.87866688 4.48733330 并跳转到步骤2。 本文提出一种引入路径搜索和禁忌列表的混合状态转移算法(HDSTA)对任务定序分配、路径规划和碰撞冲突问题进行一体化求解，算法流程如 图1 图1 所示。首先，在考虑当前禁忌列表下，针对任务定序分配问题求解出候选精英解并添加到精英解集中，再依次对新生成的精英解执行基于路径专家库的路径规划计算。然后，通过碰撞检测程序确定冲突延迟时间并获得最终的任务完成时间。最后，更新禁忌列表，并将其作为冲突判断指导求解下一代候选精英解。 混合离散状态转移算法流程如 图1 图1 所示，其中， X best 代表当前最优解， f best 表示历史最优解， S E 为种群数量， n ， m a ， m b 和 m c 为0到1之间的小数。HDSTA的伪代码见 算法1 算法1 。算法开始于由不考虑冲突的DSTA(I)算法生成上层初始精英解集 <math id="M144"><msub><mrow><mi>Q</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705233&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705202&type= 3.97933316 4.48733330 ，对于其中每一个解 <math id="M145"><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705011&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705010&type= 3.55599999 4.48733330 ，通过路径选择程序(SP)生成下层路径解 <math id="M146"><mi>p</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704987&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705012&type= 2.28600001 3.38666677 ，计算运输时间 <math id="M147"><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705001&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705015&type= 2.45533323 2.62466669 、延迟时间 <math id="M148"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705263&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705245&type= 2.37066650 3.72533321 和冲突次数，并生成禁忌列表 <math id="M149"><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705023&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44704992&type= 4.99533367 3.72533321 。HDSTA设计了3个终止条件： 1) 精英解集中存在1个解，在路径规划中可以生成无冲突路径，算法结束，输出最优解； 2) 精英解集在路径规划中的最优解，其延迟时间 <math id="M150"><msub><mrow><mi>t</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705007&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705024&type= 4.82600021 3.72533321 小于目标值 <math id="M151"><mi>ε</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705053&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705026&type= 1.52400005 2.62466669 ，算法结束，输出最优解； 3) 迭代 <math id="M152"><mi>l</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705041&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705039&type= 1.18533325 2.62466669 次后目标函数值没有减少，算法结束，输出当前最优解。精英解集通过融合禁忌列表约束的DSTA(II)迭代过程进行更新，直到其中一个终止条件被满足，生成包含定序分配解 <math id="M153"><mi>D</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705031&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705030&type= 2.79399991 2.62466669 和执行路径解 <math id="M154"><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705277&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705288&type= 6.09600019 3.72533321 的综合调度解 <math id="M155"><mi>S</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705062&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705046&type= 2.03200006 2.62466669 。 算法1 ：HDSTA伪代码 输入：AGV <math id="M156"><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705208&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705221&type= 2.53999996 2.37066650 ，任务 <math id="M157"><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705222&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705236&type= 2.20133328 2.37066650 ，路径专家库 <math id="M158"><msub><mrow><mi>N</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705296&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705308&type= 3.38666677 3.38666677 输出： <math id="M159"><mi>S</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705099&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705098&type= 1.86266661 2.37066650 1：用DSTA(I)算法生成初始精英解集 <math id="M160"><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705237&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705209&type= 3.72533321 4.06400013 2：while <math id="M161"><mo stretchy="false">(</mo><msub><mrow><mi>y</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>=</mo><mn>1</mn><mtext> </mtext><mi mathvariant="normal">o</mi><mi mathvariant="normal">r</mi><mtext> </mtext><msub><mrow><mi>y</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>=</mo><mn>1</mn><mtext> </mtext><mi mathvariant="normal">o</mi><mi>r</mi><mtext> </mtext><msub><mrow><mi>y</mi></mrow><mrow><mn>3</mn></mrow></msub><mo>=</mo><mn>1</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705074&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705103&type= 32.51200104 4.06400013 3：for每一精英解 <math id="M162"><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∈</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705091&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705075&type= 10.49866676 4.06400013 4： <math id="M163"><mo stretchy="false">[</mo><mi>p</mi><mo>,</mo><mi>T</mi><mo>,</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>D</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>D</mi></mrow></msub><mo stretchy="false">]</mo><mo>←</mo><mi mathvariant="normal">S</mi><mi mathvariant="normal">P</mi><mo stretchy="false">(</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705106&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705077&type= 29.88733101 4.06400013 5：if <math id="M164"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub><mo>=</mo><mn>0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705095&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705107&type= 6.85799980 3.38666677 then 6： <math id="M165"><mi>D</mi><mo>←</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>;</mo><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mi>p</mi><mo>;</mo><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mi>T</mi><mo>;</mo><msub><mrow><mi>y</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>←</mo><mn>1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705109&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705079&type= 47.66733551 4.06400013 7：break for; 8：end if 9：if <math id="M166"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub><mo><</mo><msub><mrow><mi>t</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705113&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705097&type= 9.73666668 3.38666677 then 10： <math id="M167"><msub><mrow><mi>t</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub><mo>;</mo><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mi>p</mi><mo>;</mo><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mo stretchy="false">[</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>p</mi></mrow></msub><mo stretchy="false">]</mo><mo>;</mo><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705117&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705115&type= 59.09733200 4.06400013 11：end if 12：end for 13：if <math id="M168"><msub><mrow><mi>t</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo><</mo><mi>ε</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705119&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705118&type= 8.89000034 3.38666677 then 14： <math id="M169"><msub><mrow><mi>y</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>←</mo><mn>1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705131&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705144&type= 9.14400005 4.06400013 15：end if 16：if <math id="M170"><msub><mrow><mi>y</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>=</mo><mn>0</mn><mtext> </mtext><mi mathvariant="normal">o</mi><mi>r</mi><mtext> </mtext><msub><mrow><mi>y</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>=</mo><mn>0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705123&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705145&type= 21.50533485 4.06400013 then 17：采用DSTA(II)算法更新精英解集 <math id="M171"><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705237&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705209&type= 3.72533321 4.06400013 18：更新计数器 <math id="M172"><mi>l</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705136&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705135&type= 1.01600003 2.37066650 19：if <math id="M173"><mi>l</mi><mo>></mo><mn>5</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705149&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705148&type= 5.58799982 2.37066650 20： <math id="M174"><msub><mrow><mi>y</mi></mrow><mrow><mn>3</mn></mrow></msub><mo>←</mo><mn>1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705152&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705150&type= 9.14400005 4.06400013 21：end if 22：end if 23：end while 24： <math id="M175"><mi>S</mi><mo>←</mo><mo stretchy="false">(</mo><mi>D</mi><mo>,</mo><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705138&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705154&type= 17.94933319 4.06400013 2.1 生成精英解集 2 在搬运任务序列中插入定位充电请求对AGV调度问题至关重要。当AGV当前电量无法完成所有被分配的任务时，必须在中途充电，此时，需要在搬运任务序列中合理的位置插入充电请求，并规定AGV在距离先前服务任务位置最近的充电站进行充电 [ 18 18 ] 。针对AGV可能需要多次充电问题，定义AGV完成所有搬运任务需要的充电次数为 <math id="M176"><msub><mrow><mi>N</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705141&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705156&type= 3.80999994 3.72533321 ，设计临界插入算子和非临界插入算子。当决定了1个搬运任务定序分配解时，对 <math id="M177"><msub><mrow><mi>N</mi></mrow><mrow><mi>k</mi></mrow></msub><mo>></mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705173&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705157&type= 8.89000034 3.72533321 的AGV用临界插入算子插入充电请求，对 <math id="M178"><msub><mrow><mi>N</mi></mrow><mrow><mi>k</mi></mrow></msub><mo>=</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705188&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705176&type= 8.89000034 3.72533321 的AGV用非临界插入算子插入充电请求。 临界插入算子(CI)：按顺序确定AGV电量低于临界阈值 <math id="M179"><msub><mrow><mi>b</mi></mrow><mrow><mi>l</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705190&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705166&type= 2.70933342 3.72533321 的任务位置，并在该任务前插入充电请求。 非临界插入算子(NCI)：按顺序确定AGV电量低于临界阈值 <math id="M180"><msub><mrow><mi>b</mi></mrow><mrow><mi>l</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705190&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705166&type= 2.70933342 3.72533321 的任务位置。在该任务前找到离充电站最近且不会增加充电次数的位置，将充电请求插入该最佳位置，使AGV提前充电。 DSTA采用群体中的最优解在邻域内迭代搜索直到找到全局最优解。为了保证任务定序分配结果对路径规划过程具有多样选择性，需要生成包含多个精英解的集合。在DSTA迭代过程中，下一代种群的生成只与上一代的最优解相关，用于生成种群的3种特殊状态变换算子见文献[ 19 19 ]。每一代种群中的解具有高度相似性，其包含的解不满足精英性和多样性要求，因此，不能作为精英解集。针对上述问题提出一种精英解集 <math id="M181"><msub><mrow><mi>Q</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705233&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705202&type= 3.97933316 4.48733330 生成方法。初始化解集 <math id="M182"><msub><mrow><mi>Q</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705233&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705202&type= 3.97933316 4.48733330 并定义集合中解的数量上限为 <math id="M183"><mi>m</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705195&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705170&type= 2.70933342 2.62466669 ，按照目标函数值升序存放。在迭代过程中，将每一代搜索的所有精英解与 <math id="M184"><msub><mrow><mi>Q</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705233&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705202&type= 3.97933316 4.48733330 中存放的解进行比较，若存在更优的解则进行替换，从而保证精英解集 <math id="M185"><msub><mrow><mi>Q</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705233&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705202&type= 3.97933316 4.48733330 包含搜索过程中所有精英个体。引入插入算子的精英解集生成方法见 算法2 算法2 ，其中， <math id="M186"><msub><mrow><mi>S</mi></mrow><mrow><mi>e</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705200&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705203&type= 3.04800010 3.72533321 为种群数量， <math id="M187"><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705218&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705201&type= 5.67266655 3.72533321 为种群中最优解， <math id="M188"><msub><mrow><mi>Q</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705233&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705202&type= 3.97933316 4.48733330 为精英解集， <math id="M189"><msub><mrow><mi>C</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705207&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705220&type= 3.30200005 3.72533321 与 <math id="M190"><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705235&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705234&type= 3.38666677 3.72533321 分别为临界插入算子和非临界插入算子。 算法2 ：DSTA(II) 输入：AGV <math id="M191"><mi>K</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705208&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705221&type= 2.53999996 2.37066650 ，任务 <math id="M192"><mi>T</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705222&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705236&type= 2.20133328 2.37066650 输出： <math id="M193"><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705237&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705209&type= 3.72533321 4.06400013 1：随机生成初始化解Best 2： <math id="M194"><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mi mathvariant="normal">f</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">t</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">s</mi><mo stretchy="false">(</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705210&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705223&type= 26.16200066 4.06400013 3： <math id="M195"><mi>k</mi><mo>←</mo><mn>0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705224&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705211&type= 7.61999989 2.37066650 4：repeat 5： <math id="M196"><mo stretchy="false">[</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705242&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705216&type= 18.62666702 4.06400013 ←swap <math id="M197"><mo stretchy="false">(</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705217&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705230&type= 38.35400009 4.06400013 6： <math id="M198"><mo stretchy="false">[</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705242&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705216&type= 18.62666702 4.06400013 ←shift <math id="M199"><mo stretchy="false">(</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705217&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705230&type= 38.35400009 4.06400013 7： <math id="M200"><mo stretchy="false">[</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705242&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705216&type= 18.62666702 4.06400013 ←symmetry <math id="M201"><mo stretchy="false">(</mo><msub><mrow><mi>Q</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>e</mi></mrow></msub><mo>,</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705217&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705230&type= 38.35400009 4.06400013 8： <math id="M202"><mi>k</mi><mo>←</mo><mi>k</mi><mo>+</mo><mn>1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705231&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705243&type= 12.10733318 2.37066650 9：until达到最大迭代次数 2.2 路径选择 2 基于路径专家数据库的AGV路径选择程序SP，其伪代码见 算法3 算法3 。路径选择过程根据当前任务定序分配方案，从路径专家数据库中找到冲突最少的执行路径 <math id="M203"><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705277&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705288&type= 6.09600019 3.72533321 ，计算延迟时间 <math id="M204"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705263&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705245&type= 2.37066650 3.72533321 并记录冲突信息生成禁忌列表 <math id="M205"><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705246&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705250&type= 4.99533367 3.72533321 。为了求解路径规划方案 <math id="M206"><mi>P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705251&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705264&type= 2.37066650 2.62466669 ，定义 <math id="M207"><msub><mrow><mi>d</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705265&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705247&type= 3.04800010 3.80999994 为AGV <math id="M208"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705278&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705252&type= 1.86266661 2.62466669 被分配的所有搬运任务，其执行路径由 <math id="M209"><msub><mrow><mi>r</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705253&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705279&type= 2.62466669 3.72533321 表示。每个任务搬运任务 <math id="M210"><msub><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∈</mo><msub><mrow><mi>d</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705266&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705280&type= 9.22866726 3.80999994 由1个取货请求 <math id="M211"><msubsup><mrow><mi>o</mi></mrow><mrow><mi>u</mi></mrow><mrow><mi>t</mi></mrow></msubsup><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705281&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705254&type= 9.22866726 4.82600021 和1个送货请求 <math id="M212"><msubsup><mrow><mi>o</mi></mrow><mrow><mi>d</mi></mrow><mrow><mi>t</mi></mrow></msubsup><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705255&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705267&type= 9.22866726 4.82600021 组成， <math id="M213"><msub><mrow><mi>r</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">(</mo><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>:</mo><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi><mi mathvariant="normal">'</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705282&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705256&type= 13.46199989 4.82600021 代表执行任务 <math id="M214"><msub><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705257&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705268&type= 2.37066650 3.72533321 的路径，其中， <math id="M215"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>∈</mo><msub><mrow><mi>r</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705283&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705269&type= 9.65200043 4.06400013 和 <math id="M216"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi><mi mathvariant="normal">'</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>∈</mo><msub><mrow><mi>r</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705258&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705270&type= 9.82133293 4.06400013 分别表示取货路径和送货路径。此外，当任务为充电请求时，则只有1条路径 <math id="M217"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>b</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705259&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705284&type= 3.04800010 4.06400013 。在路径专家库中，从站点 <math id="M218"><mi>i</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705260&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705271&type= 1.10066664 2.62466669 到站点 <math id="M219"><mi>j</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705272&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705285&type= 1.69333339 3.38666677 的路线 <math id="M220"><msub><mrow><mi>r</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705273&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705261&type= 2.87866688 3.72533321 中第 <math id="M221"><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705286&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705262&type= 1.86266661 2.62466669 条路径用 <math id="M222"><mi>p</mi><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>n</mi><mo stretchy="false">)</mo><mo>∈</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705293&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705274&type= 17.52599907 4.48733330 表示。 在选择程序中，冲突检测程序(Con)是一个基于三维时空模型的冲突检测程序 [ 20 20 ] ，它能计算冲突路径位置 <math id="M223"><msub><mrow><mi>S</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705275&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705287&type= 3.21733332 3.72533321 与延时时间 <math id="M224"><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705294&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705276&type= 1.86266661 3.72533321 。当路径之间存在冲突时，替换程序(Replace)在路径专家数据库中用其他平行路径替换当前路径，替代方式是从路径候选解集中自上而下搜索，直到为每个AGV从路径库中找到延迟时间最少的路径。在找到无冲突执行路径后停止搜索，否则，替换程序将搜索路径专家库中冲突路线的替换路径，选择延迟时间最小的路径集合记为当前最优路径解 <math id="M225"><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705277&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705288&type= 6.09600019 3.72533321 。 算法3 ：路径选择程序 输入：任务定序分配方案 <math id="M226"><msub><mrow><mi>P</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705289&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705295&type= 3.38666677 3.38666677 ，路径专家库 <math id="M227"><msub><mrow><mi>N</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705296&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705308&type= 3.38666677 3.38666677 输出： <math id="M228"><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>,</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub><mo>,</mo><msub><mrow><mi>T</mi></mrow><mrow><mi>l</mi><mi>i</mi><mi>s</mi><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705309&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705290&type= 15.66333294 3.80999994 1： <math id="M229"><msub><mrow><mi>T</mi></mrow><mrow><mi>C</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705291&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705297&type= 3.47133350 3.38666677 ←0 2：for 每一个 <math id="M230"><msub><mrow><mi>d</mi></mrow><mrow><mi>k</mi></mrow></msub><mo>∈</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705298&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705310&type= 9.22866726 4.06400013 3：for 每一个 <math id="M231"><msub><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∈</mo><msub><mrow><mi>d</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705311&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705292&type= 8.55133343 3.38666677 4： <math id="M232"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705327&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705314&type= 2.79399991 3.64066648 ← P ( <math id="M233"><msubsup><mrow><mi>o</mi></mrow><mrow><mi>u</mi></mrow><mrow><mi>t</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705300&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705312&type= 2.96333337 3.64066648 ,1)； <math id="M234"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi><mi mathvariant="normal">'</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705313&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705324&type= 2.96333337 3.64066648 ← P ( <math id="M235"><msubsup><mrow><mi>o</mi></mrow><mrow><mi>d</mi></mrow><mrow><mi>t</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705325&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705301&type= 2.96333337 3.64066648 ,1) 5： <math id="M236"><msub><mrow><mi>r</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">(</mo><mn>1</mn><mo>:</mo><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705302&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705326&type= 7.11199999 4.06400013 ← <math id="M237"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705327&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705314&type= 2.79399991 3.64066648 ； <math id="M238"><msub><mrow><mi>r</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">(</mo><mn>1</mn><mo>:</mo><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705315&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705303&type= 7.11199999 4.06400013 ← <math id="M239"><msubsup><mrow><mi>r</mi></mrow><mrow><mi>u</mi><mi>'</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705304&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705328&type= 3.04800010 3.64066648 ； <math id="M240"><msub><mrow><mi>r</mi></mrow><mrow><mi>k</mi></mrow></msub><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705305&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705316&type= 6.51933336 4.06400013 ← <math id="M241"><msub><mrow><mi>r</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705329&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705317&type= 2.62466669 3.38666677 6：end for 7： <math id="M242"><mi>P</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705318&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705306&type= 5.84200001 3.04800010 ← <math id="M243"><msub><mrow><mi>r</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705307&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705330&type= 2.45533323 3.38666677 8：end for 9： <math id="M244"><mo stretchy="false">[</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>p</mi></mrow></msub><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705331&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705319&type= 8.21266651 4.06400013 ←Con( <math id="M245"><mi>P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705320&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705338&type= 2.20133328 2.37066650 ) 10：if <math id="M246"><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705333&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705332&type= 1.77800000 3.38666677 ≠ 0 11：for 每一个 <math id="M247"><msub><mrow><mi>S</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705340&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705339&type= 2.96333337 3.38666677 12：repeat 13： <math id="M248"><mi>P</mi><mi>'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705353&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705322&type= 2.96333337 2.37066650 ← Replace( <math id="M249"><msub><mrow><mi>S</mi></mrow><mrow><mi>P</mi></mrow></msub><mo>,</mo><mi>P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705335&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705341&type= 6.77333355 3.80999994 ) 14： <math id="M250"><msubsup><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705336&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705355&type= 1.86266661 3.64066648 ← Con( <math id="M251"><mi>P</mi><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705337&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705344&type= 2.79399991 2.37066650 ) 15：if <math id="M252"><msubsup><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msubsup><mo><</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705346&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705357&type= 6.51933336 3.64066648 16： <math id="M253"><msub><mrow><mi>S</mi></mrow><mrow><mi>p</mi><mi>'</mi></mrow></msub><mo>←</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705369&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705358&type= 10.75266743 3.38666677 <math id="M254"><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>←</mo><msubsup><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705350&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705360&type= 7.95866632 3.64066648 <math id="M255"><mi>P</mi><mo>←</mo><mi>P</mi><mi>'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705352&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705371&type= 9.48266602 2.37066650 17：end if 18：until 路径库中所有的路径都被查询 19：end for 20： <math id="M256"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub><mo>←</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705363&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705362&type= 8.38199997 3.38666677 21：else 22： <math id="M257"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub><mo>←</mo><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705384&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705373&type= 8.38199997 3.38666677 ； <math id="M258"><msub><mrow><mi>P</mi></mrow><mrow><mi mathvariant="normal">b</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mi>P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705375&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705365&type= 12.27666664 3.38666677 23：end if 24：if <math id="M259"><msub><mrow><mi>t</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705377&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705376&type= 2.20133328 3.38666677 满足被禁忌列表记录的条件 25： <math id="M260"><msub><mrow><mi>T</mi></mrow><mrow><mi mathvariant="normal">l</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mo>←</mo><mo stretchy="false">[</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>,</mo><msub><mrow><mi mathvariant="normal">S</mi></mrow><mrow><mi>p</mi></mrow></msub><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705367&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705387&type= 19.13466644 4.06400013 26：end if 禁忌列表在HDSTA中的作用是从搜索空间移除曾经访问的解，从而进行更广泛探索。在路径选择中，禁忌列表记录并更新存在冲突较多的任务定序分配精英解。HDSTA在迭代过程中更新精英解集时受到禁忌列表约束，并删除被记录的解，从而防止循环回到之前搜索过的解决方案。禁忌列表能存储解的数量上限为 <math id="M261"><mi>h</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705379&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705398&type= 1.86266661 2.62466669 ，当新的解延迟时间更大时，禁忌列表才会更新。需要强调的是，本文考虑的冲突问题具有时序性，优先被执行的任务不受靠后被执行任务的影响，禁忌列表中记录的信息对于任务分配结果的约束可以被扩展，如当AGV 1 被分配执行任务(2-1-3-5)且AGV 2 被分配行任务(8-7-6-4)时，若记录AGV 1 在执行任务1会与执行任务7的AGV 2 发生冲突，则冲突信息可以被扩展为AGV 1 (2-1- X - X )与AGV 2 (8-7- X - X )，其中， X 表示任意一个任务。 3 工业仓库实例验证 1 3.1 工业仓库案例 2 湖南长沙的某科技公司是本项研究的合作单位和实验应用场所，某仓库的布局如 图2 图2 所示，包括40个预分拣站和9个充电站。采用1个包含背负式AGV和托盘式AGV的异构车队集群，2种AGV的速度分别为0.8 m/s和1.0 m/s。根据从业者反馈，在1个时间段内，等待分配的平均任务数约为50个，繁忙期，等待分配的任务超过80个。 3.1.1 参数设定 3 在实验案例中对参数进行设定，首先确定种群数量、精英解集中解的数量和禁忌列表长度的上限分别为 <math id="M262"><mi>S</mi><mmultiscripts><mrow><mo>=</mo></mrow><mprescripts/><mrow><mi>e</mi></mrow><mrow/></mmultiscripts><mn mathvariant="normal">20</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705382&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705390&type= 10.83733368 3.72533321 ， <math id="M263"><mi>m</mi><mo>=</mo><mn mathvariant="normal">30</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705393&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705392&type= 9.73666668 2.62466669 ， <math id="M264"><mi>h</mi><mo>=</mo><mn mathvariant="normal">120</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705413&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705403&type= 10.75266743 2.62466669 。然后，确定算法的终止条件参数，允许的最大延迟时间 <math id="M265"><mi>ε</mi><mo>=</mo><mn mathvariant="normal">85</mn><mtext> </mtext><mi mathvariant="normal">s</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705404&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705394&type= 10.66800022 2.70933342 ，HDSTA迭代计数值为5次，DSTA最大迭代计数值为50次。路径专家库 <math id="M266"><msub><mrow><mi>N</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705406&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=44705405&type= 3.64066648 3.72533321 在离线阶段被提前预设，每一条站点之间的路线都包含10条以上优秀的候选路径。 3.1.2 案例分析 3 基于实际仓库案例的背景，通过处理不同规模的问题验证方法的有效性。在实验中，待调度的AGV数量分别6、9和15辆，案例中待分配的任务数分别为20、30、40、50、60、70和80个，每一个案例随机生成5组任务，并运行10次，共运行50次程序，取平均值作为结果。当前工业仓库中先进AGV系统普遍采用依次优化的调度方法，其中LIAN等 [ 14 14 ] 提出的方法最具有代表性，因此，在现实仓库案例分析中选择该方法进行对比验证。在案例分析中，综合优化调度方法和依次优化调度方法的任务完成时间和延迟时间的对比结果如 图3 图3 至 图5 图5 所示。 (a) 任务完成时间；(b) 延迟时间 (a) 任务完成时间；(b) 延迟时间 (a) 任务完成时间；(b) 延迟时间 案例分析结果表明，本文所提出的综合优化调度方法具有更好的性能，在所有案例中都找到了更优的解。具体表现为：相较于依次优化调度方法，综合优化调度方法的任务完成时间缩短了10.56%，延迟时间减少了74.53%。值得注意的是，这2种方法的延迟时间在任务数为20时任务完成时间仅相差42.63 s，但当任务数增大到80个时，其任务完成时间相差1 281.13 s。因此，随着任务规模增加，AGV之间发生冲突的可能性也越大，依次优化调度方法不能从任务分配过程中规避碰撞冲突的影响，而综合优化调度方法可以通过改变任务分配和具体执行路径，规避大多数冲突情况。 为了进一步验证综合优化调度方法在大规模任务案例中减少碰撞冲突的作用，使用30辆AGV将2种方法在任务数分别为110~150个的案例中对碰撞冲突次数进行对比。每一个案例随机生成10组任务，每组运行10次程序取平均值，结果如 图6 图6 所示。从 图6 图6 可以得到：综合优化调度方法能大幅度减少AGV之间的碰撞次数，与依次优化调度方法相比，平均碰撞次数降低73.3%。 3.2 对比验证分析 2 为了更全面地验证HDSTA的性能，需要建立更大规模的案例范本。将20~100个任务定义为小规模问题，待调度的AGV从5辆到15辆不等；将100个任务以上定义为大规模问题，待调度的AGV从15辆到30辆不等。在对比实验中，对于不同规模的每个案例随机生成10组任务，每组运行10次，共运行100次程序，对比任务完成的时间。在每个案例中，将HDSTA与自适应大邻域搜索算法(HALNS) [ 15 15 ] 、预先规划算法(PPA) [ 13 13 ] 和DS算法进行对比。其中，HALNS是一种混合了自适应大邻域搜索算法和线性规划的算法，用于求解带电量约束的异构AGV调度问题。但该方法没有考虑冲突和死锁问题，为了进行比较，对其最优解进行冲突检测并增加延迟时间。PPA是一种在路径规划过程生成无冲突最短路径的算法，本文将综合调度优化方法与无冲突路径策略进行比较。DS是基于离散状态转移算法的综合求解方法，用于与本文提出的基于HDSTA的综合求解方法作对比。算法的计算时间同样是重要的性能指标，因此，设定算法最大计算时间为120 s，对比结果如 表1 表1 和 表2 表2 所示。 2 编号 2 任务数/个 2 AGV数/辆 2 PPA 2 HALNS 2 DS 2 HDSTA 计算时间/s 任务完成时间/s 计算时间/s 任务完成时间/s 计算时间/s 任务完成时间/s 计算时间/s 任务完成时间/s 1 20 5 2.11 1 458 1.69 1 466 0.74 1 621 0.83 1 440 2 20 8 2.20 1 453 1.70 1 472 0.72 1 581 0.82 1 453 3 20 10 2.15 1 491 1.72 1 491 0.81 1 762 0.89 1 485 4 30 6 3.38 2 179 2.52 2 177 1.18 2 528 1.16 2 174 5 30 8 3.50 2 198 2.44 2 195 1.21 2 655 1.28 2 190 6 30 9 3.48 2 217 2.58 2 231 1.35 2 842 1.36 2 211 7 30 14 3.71 2 254 2.57 2 250 1.48 2 801 1.20 2 246 8 40 5 4.91 2 961 3.42 2 983 1.84 3 904 1.85 2 951 9 40 7 5.23 2 982 3.35 3 004 1.85 3 868 1.77 2 974 10 40 9 5.19 3 009 3.46 3 016 1.97 3 948 1.82 3 003 11 50 5 7.61 3 747 4.24 3 744 2.37 5 020 2.23 3 738 12 50 9 7.73 3 830 4.36 3 862 2.35 5 215 2.33 3 811 13 50 11 8.13 3 853 4.68 3 876 2.42 5 574 2.37 3 845 14 60 3 11.41 4 522 6.88 4 529 2.93 6 643 2.84 4 522 15 60 8 12.14 4 615 7.20 4 628 3.02 6 789 2.83 4 608 16 60 13 12.81 4 693 8.36 4 854 3.04 6 913 2.90 4 685 17 80 4 19.91 6 570 16.07 6 569 3.43 8 803 3.55 6 558 18 80 6 22.89 6 683 18.15 6 711 3.50 8 663 3.91 6 654 19 100 7 38.92 8 421 31.94 8 408 3.97 9 483 5.64 8 311 20 100 15 43.85 8 636 30.11 8 756 4.08 9 284 6.22 8 541 注： “—”表示算法在120 s内无法得到有效解。 2 编号 2 任务数/个 2 AGV数/辆 2 PPA 2 HALNS 2 DS 2 HDSTA 计算时间/s 任务完成时间/s 计算时间/s 任务完成时间/s 计算时间/s 任务完成时间/s 计算时间/s 任务完成时间/s 1 120 15 50.21 12 850 41.65 13 365 5.41 15 434 8.60 12 305 2 120 18 54.33 12 902 56.84 14 025 5.66 15 681 8.84 12 654 3 120 19 55.12 13 357 58.52 14 359 5.25 17 862 8.92 13 147 4 150 22 98.21 18 724 84.74 19 015 8.70 25 684 13.45 17 521 5 150 23 116.89 19 031 91.61 19 584 9.16 26 255 14.16 16 984 6 150 26 — — 92.84 21 283 9.32 25 743 15.10 18 125 7 200 20 — — 114.56 26 894 13.31 34 856 21.86 22 246 8 200 21 — — — — 14.42 36 481 23.65 24 821 9 200 27 — — — — 14.89 39 541 22.74 27 654 10 200 24 — — — — 15.51 38 942 25.28 25 246 任务完成时间与运行成本成正比，可以直观反映AGV协同运行效率，而计算时间是动态调度的重要指标，可以反映AGV系统的计算效率。从 表1 表1 可见：当任务数量为20个，AGV数量分别为5，8和10辆时，采用HDSTA算法优化调度计算得出的方案任务完成时间分别为1 440、1 453和1 485 s，计算时间分别为0.83、0.82和0.89 s；通过20个小规模案例类型的200组任务的结果分析发现，相较于PPA和HALNS，本文提出的HDSTA解的任务完成时间平均值分别缩短0.48%和1.16%，计算时间分别降低78.40%和69.74%。DS求解时间与其他3种综合调度方法相差较大；在小规模问题中，几种综合调度方法求解时间相差不大，而HDSTA的求解时间更少。从 表2 表2 可见：当任务数量为120个，AGV数量分别为15、18和19辆时，采用HDSTA算法优化调度计算后任务完成时间分别为12 305、12 654和13 147 s，计算时间分别为8.60、8.84和8.92 s；通过10个大规模案例类型的100组任务的结果分析发现，与PPA和HALNS相比，HDSTA可以在更短的时间内求得质量更高的解，任务完成时间分别缩短5.54%和9.73%，计算时间分别降低86.68%和84.19%。在大部分案例中，DS不能得到整体最优的结果，HDSTA虽然计算时间比DS的更长，但仍在一个合理的范围内。 4 结论 1 1) 本文提出的基于分层规划的综合优化调度方法比依次优化调度方法平均任务完成时间减少10.56%，碰撞冲突造成的延迟时间减少74.53%。 2) 在所有案例中，DS都不能得到整体最优的结果。在100个任务内的小规模问题中，本文提出的方法比HALNS和PPA任务完成时间分别减少1.16%和0.48%，计算时间分别减少69.74%和78.40%。在100个任务以上的大规模问题中，本文提出的方法比HALNS和PPA任务完成时间分别减少9.73%和5.54%，计算时间分别减少84.19%和86.68%。 参考文献 JIN Jian , ZHANG Xiaohua . Multi AGV scheduling problem in automated container terminal [J]. Journal of Marine Science and Technology , 2016 , 24 ( 1 ): 32 - 38 . Multi AGV scheduling problem in automated container terminal TAO Qiuyun , SANG Hongyan , GUO Hengwei , et al . Improved particle swarm optimization algorithm for AGV path planning [J]. IEEE Access , 2021 , 9 : 33522 - 33531 . Improved particle swarm optimization algorithm for AGV path planning CHIEW K , QIN Shaowen . Scheduling and routing of AMOs in an intelligent transport system [J]. IEEE Transactions on Intelligent Transportation Systems , 2009 , 10 ( 3 ): 547 - 552 . Scheduling and routing of AMOs in an intelligent transport system YU Dingding , HU Xianliang , LIANG Kewei , et al . A parallel algorithm for multi-AGV systems [J]. Journal of Ambient Intelligence and Humanized Computing , 2022 , 13 ( 4 ): 2309 - 2323 . A parallel algorithm for multi-AGV systems CORRÉA A I , LANGEVIN A , ROUSSEAU L M . Scheduling and routing of automated guided vehicles: a hybrid approach [J]. Computers & Operations Research , 2007 , 34 ( 6 ): 1688 - 1707 . Scheduling and routing of automated guided vehicles: a hybrid approach LI Guomin , LI Xinyu , GAO Liang , et al . Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm [J]. Journal of Ambient Intelligence and Humanized Computing , 2019 , 10 ( 11 ): 4533 - 4546 . Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm ZHANG Zheng , GUO Qing , CHEN Juan , et al . Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification [J]. IEEE Access , 2018 , 6 : 26022 - 26035 . Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification BAO Bizhen , DUAN Zhao , CHEN Wei . Mission scheduling of multi-AGV system with dynamic simulation [C]// 2020 International Symposium on Autonomous Systems (ISAS) . Guangzhou,China : IEEE , 2021 : 115 - 120 . Mission scheduling of multi-AGV system with dynamic simulation LIU Jian , WANG Zhongdong , XU Qing , et al . Path scheduling for multi-AGV system based on two-staged traffic scheduling scheme and genetic algorithm [J]. Journal of Computational Methods in Sciences and Engineering , 2015 , 15 ( 2 ): 163 - 169 . Path scheduling for multi-AGV system based on two-staged traffic scheduling scheme and genetic algorithm KIM C W , TANCHOCO J M A . Conflict-free shortest-time bidirectional AGV routeing [J]. International Journal of Production Research , 1991 , 29 ( 12 ): 2377 - 2391 . Conflict-free shortest-time bidirectional AGV routeing GUO Kunlun , ZHU Jin , SHEN Lei . An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals [J]. IEEE Access , 2020 , 9 : 3326 - 3338 . An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals TATSUSHI , NISHI . A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles [J]. Computers & Operations Research , 2011 , 38 ( 5 ): 876 - 888 . A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles MAZA S , CASTAGNA P . A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles [J]. Computers in industry , 2005 , 56 ( 7 ): 719 - 733 . A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles LIAN Yindong , YANG Qifan , XIE Wei , et al . Cyber-physical system-based heuristic planning and scheduling method for multiple automatic guided vehicles in logistics systems [J]. IEEE Transactions on Industrial Informatics , 2021 , 17 ( 11 ): 7882 - 7893 . Cyber-physical system-based heuristic planning and scheduling method for multiple automatic guided vehicles in logistics systems SINGH N , DANG Q V , AKCAY A , et al . A matheuristic for AGV scheduling with battery constraints [J]. European Journal of Operational Research , 2022 , 298 ( 3 ): 855 - 873 . A matheuristic for AGV scheduling with battery constraints BAE J , CHUNG W . A heuristic for path planning of multiple heterogeneous automated guided vehicles [J]. International Journal of Precision Engineering and Manufacturing , 2018 , 19 ( 12 ): 1765 - 1771 . A heuristic for path planning of multiple heterogeneous automated guided vehicles YANG Qifan , LIAN Yindong , XIE Wei . Hierarchical planning for multiple AGVs in warehouse based on global vision [J]. Simulation Modelling Practice and Theory , 2020 , 104 : 102124 . Hierarchical planning for multiple AGVs in warehouse based on global vision DANG Q V , SINGH N , ADAN I , et al . Scheduling heterogeneous multi-load AGVs with battery constraints [J]. Computers & Operations Research , 2021 , 136 : 105517 . Scheduling heterogeneous multi-load AGVs with battery constraints 阳春华 , 唐小林 , 周晓君 , 等 . 一种求解旅行商问题的离 散状态转移算法 [J]. 控制理论与应用 , 2013 , 30 ( 8 ): 1040 - 1046 . 一种求解旅行商问题的离 散状态转移算法 YANG Chunhua , TANG Xiaolin , ZHOU Xiaojun , et al . A discrete state transition algorithm for traveling salesman problem [J]. Control Theory & Applications , 2013 , 30 ( 8 ): 1040 - 1046 . A discrete state transition algorithm for traveling salesman problem FAZLOLLAHTABAR H , SAIDI-MEHRABAD M . Methodologies to optimize automated guided vehicle scheduling and routing problems: a review study [J]. Journal of Intelligent & Robotic Systems , 2015 , 77 ( 3 ): 525 - 545 . Methodologies to optimize automated guided vehicle scheduling and routing problems: a review study 10.11817/j.issn.1672-7207.2023.05.013 TP273 A 1672-7207（2023）05-1779-12 胡恩泽, 贺建军, 申帅, 等. 面向大型工业仓库的多AGV综合优化调度方法[J]. 中南大学学报(自然科学版), 2023, 54(5): 1779-1790. 胡恩泽, 贺建军, 申帅, 等. 面向大型工业仓库的多AGV综合优化调度方法[J]. 中南大学学报(自然科学版), 2023, 54(5): 1779-1790. HU Enze, HE Jianjun, SHEN Shuai, et al. An integrated scheduling method of multi-AGV in large-scale industrial warehouses[J]. Journal of Central South University(Science and Technology), 2023, 54(5): 1779-1790. HU Enze, HE Jianjun, SHEN Shuai, et al. An integrated scheduling method of multi-AGV in large-scale industrial warehouses[J]. Journal of Central South University(Science and Technology), 2023, 54(5): 1779-1790. 国家自然科学基金资助项目(61873282) Project(61873282) supported by the National Natural Science Foundation of China 2022-07-11 2022-08-20 2023-05-26 2023-06-20 38909961 中南大学学报(自然科学版) 5 54
查看原文
0
浏览量
0
下载量
0
CSCD
Alert me when the article has been cited
文章被引用时，请邮件提醒。
提交
工具集
下载
- 网络PDF下载
- WORD下载
- Meta-XML下载
参考文献导出
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
收藏
添加至我的专辑
关联资源
相关文章
障碍物条件下智能车辆换道路径规划的近优解
基于D-S理论和改进势场法的路径规划算法
动态环境下基于模糊逻辑算法的移动机器人路径规划
基于粒群行为与克隆的移动机器人进化路径规划
相关作者
李玮
段建民
龚建伟
王随平
桂卫华
潘天国
李擎
张超
相关机构
北京工业大学 电子信息与控制工程学院
北京理工大学 智能车辆研究所
中南大学信息科学与工程学院
北京科技大学自动化学院
唐山学院计算机科学与技术系
0
回到顶部