海域岛礁物资补给任务智能规划.pdf

第 卷 第 期 年 月指挥控制与仿真 文章编号：（）海域岛礁物资补给任务智能规划余昌仁，乔 涵，韩梦瑶，张国杰（陆军勤务学院，重庆）摘 要：综合考虑运输成本、存储成本、回收需求、运输容量等因素，利用多种运输工具为海域岛礁进行周期内的物资补给，是具有时间窗及容量限制的车辆路径规划问题。智能算法为解决这种复杂的不规则优化问题提供了较好的思路。建立了海域岛礁物资补给任务规划数学模型，探索了遗传算法的求解过程，并运用一个实例进行了计算，优化结果表明，方案能节约运输成本与储存成本，同时也满足了物资保障周期的需要，能为科学规划海域岛礁物资保障任务提供较好的参考。关键词：海域岛礁；物资补给；任务规划；智能算法中图分类号：文献标志码：，（，）：，：；收稿日期：修回日期：基金项目：陆军勤务学院青年科研资助项目（）作者简介：余昌仁（），男，博士，讲师，主要研究方向为系统仿真、国防经济。乔 涵（），男，硕士。岛礁是维护我国海洋权益的前哨，是我国领土不可分割的组成部分，派驻人员守卫岛礁对保障我国领土完整具有重要的意义。远海海域诸岛礁距离大陆较远，位置相对分散，岛上物资匮乏，为维持驻岛人员生存生活需要，需定期由陆上保障中心派出补给船对岛礁进行补给，制定科学的物资保障方案，提高保障的效益。岛礁物资补给有特定的保障目标和影响因素，主要解决物资补给任务规划问题。岛礁物资补给任务规划问题指在满足自然停泊环境、保障时间、运输工具装载量限制等条件下，使得保障目标达到最优，保障目标包括运输工具燃油经济性、物资储存成本等，所以其本质是 一 个 车 辆 路 径 规 划（，）问题，这类问题有精确算法与启发式算法等。精确算法主要运用线性规划、整数规划、非线性规划等严格的数学方法求解，比较适合特定的问题，而启发式算法适合解决一些不规则优化问题。问题常有容量约束或时间窗限制，也可能两者兼而有之，这类问题是（，多项式复杂程度的非确定性）难问题。智能算法作为启发式算法的一种，适合解决大规模的组合优化问题，能在解空间内高效率地寻找出极优解，典型的组合优化问 题 有 旅 行 商 问 题（，）、调度问题、背包问题、装箱问题等。优化目标是在可行解域内找到近似解来代替最优解，减少求解需要付出的代价。智能算法包括但不限于模拟退火、蚁群算法、遗传算法、禁忌搜索算法等。岛礁物资补给任务规划问题建模 模型考虑的因素岛礁物资补给由后勤补给中心运用各型补给舰船对海域岛礁实施运输补给。考虑补给时间、补给需求和补给效益，运输投送方案最优化受自然条件、经济成本和运输工具等多种因素影响。）自然地理条件。岛礁附近海底地貌、岸滩底质各不相同，靠泊条件各异，对于靠泊港口大的岛礁，补给舰可直接补给，对于靠泊港口小的岛礁，补给舰须在第 期指挥控制与仿真 距岛礁附近某处锚泊，通过配套小型补给艇进行转运实现间接补给，或采用某岛礁上的拖船完成物资倒运。）运输工具。可运用不同型号的大型补给舰，从特定的补给中心出发，补充一定数量的岛礁后再返回该补给中心。一条运输路线上仅有一艘大型补给舰。补给舰配备若干小型补给艇，拖船也可以用于短距离的物资转运。）运输成本。某海域领域广阔，岛礁位置相对分散，岛礁间距较远，距离是影响保障成本的主要因素。各型补给舰各有不同的燃油经济成本。规划不同的保障路径将产生不同的运输成本。拖船与小艇产生的短距离运输成本可忽略不计。）运输与装卸时间。各型补给舰航行速度已知，假设补给舰装有固体、液体两类物资，固体、液体的装卸也有不同的速度。各种运输工具（补给舰、小型补给艇、拖船）所载燃油能满足其去各岛补给的需要，即不考虑燃油耗尽需返回的问题。补给舰（艇）卸载固体物资和液体可同时进行，互不影响，回程时，需要从岛礁装载固体回收物。）储存成本。某海域岛礁大多属于热带、亚热带海洋性气候，具有高温、高湿、高盐的突出特点，各类物资易腐烂变质，长期存储需采取低温冷藏保鲜。物资储存成本也是物资补给应考虑的重要方面。固体、液体储存成本以储存天数和吨位数平均计算，单位为元吨 天。）补给要求。各岛礁存储空间有限，固体、液体物资均有最大储存量，各岛礁补给之前有一定的剩余储备量，固体、液体消耗速度以日均消耗量（吨）计量。需要补给一个时间周期内的物资需要，且要求在岛礁剩余物资消耗完毕之前进行补充。模型建立的变量模型建立的数学变量见表。表 变量说明 、分别表示岛礁 现有液体存储量、最大液体存储量、需补充的液体量、液体消耗速度、分别表示岛礁 现有固体存储量、最大固体存储量、需补充的固体量、固体消耗速度岛礁 固体回收需求量、个岛礁（用 表示，补给中心用 表示），表示补给航线上运输工具的数量、表示第 艘运输工具在岛礁 所补充物资最大装卸时间、液体装卸时间、固体装卸时间、分别表示岛礁 液体存储单位成本、固体存储单位成本（元 吨天）第 艘运输工具单位里程（海里）的燃油成本、分别表示第 艘运输工具液体最大装载容量、固体最大装载容量、第 艘运输工具装卸液体的速度、装卸固体的速度岛礁 与岛礁 之间的距离（海里）第 艘运输工具由补充中心 出发后，到达岛礁 的时间第 艘运输工具航行速度 目标函数与约束条件多艘补给舰从补给中心出发，遍历所有岛礁后返回当前补给中心，且多艘补给舰的路线不能重叠，总运输费用最小，这是典型的多旅行商（）问题。旅行商问题是车辆路径规划问题的一种，如表 所述，点 表示出发的地点：补给中心。点，表示 个旅行商（补给舰）要访问的地点（某海域的各个岛礁）。定义变量：旅行商 经地点 驶向 否则旅行商 经过地点 否则该问题的数学模型可表示为目标函数：()（）表示第 艘运输工具经过对应弧段（，）所花费用（距离与运输工具 单位运输成本的乘积）。目标函数 表示使所有旅行商的费用最小化。(（）（）（）（）)（）目标函数 表示所有岛礁剩余物资（固、液体）储存成本与补充后的物资储存成本和最小。余昌仁，等：海域岛礁物资补给任务智能规划第 卷约束条件：，（）（）（）约束条件（）表示从地点 出发，每个将被访问地点有且仅有一个旅行商经过；约束条件（）表示任一条弧的终点仅有一个起点地方与之相连；约束条件（）表示任一条弧的起点地方仅有一个终点地方与之相连。与此同时，还要考虑时间窗与各运输工具容量限制。各岛礁所需物资最早在其剩余物资刚消耗时进行补充，最晚于剩余物资耗尽时进行补充，再补充时可以按最大储存量进行补充。所以有以下约束条件：（）（）约束条件（）、（）分别表示岛礁 需补充的固体、液体的取值范围。因物资卸载时，固体、液体可同时进行，并回收固体垃圾。第艘运输工具运送的物资在岛礁 的装卸时间为 ，取装卸液体或装卸固体（含回收的固体）的时间最大值。因所运输物资最晚须于岛礁剩余物资消耗完毕之前进行补充，故有以下限制条件：，（）约束条件（）表示第艘运输工具到达岛礁的时刻加上物资装卸时间须小于岛礁 剩余物资消耗完毕所耗费的时间。因运输工具有容量限制，还有关系式：（）（）约束条件（）、（）分别表示第 艘运输工具所补充岛礁液体需求量小于其最大液体载重量、最大固体载重量。智能算法求解如前所述，问题可运用的算法有多种，但此问题有诸多的约束条件，可采用智能算法如模拟退火、禁忌算法、遗传算法（，）甚至是多种算法的结合进行求解。这些算法不存在对函数求导或连续性等限制，对多目标规划具有较好的全局搜索最优解能力。岛礁物资补给任务规划问题中若岛礁数量不太多时，可采用一种具有代表性的算法如 进行求解，是一种智能进化算法，通过把问题参数编码为“染色体”，利用迭代运算方式，设定适应度函数，使经选择、交叉和变异等操作后的“染色体”最终符合优化目标。）染色体编码。岛礁物资补给路径规划问题可采取实数编码方式，即补给中心为，各岛礁为，编码长度为 。如岛礁数量为、运输工具数量为时，若编码为，表示路径为 和 。按此编码方式生成一定规模的初始种群。）适应度函数。遗传算法是一个不断从种群中选择适应度高的个体的迭代优化过程，该任务规划问题中，目标函数取极小值，故以目标函数的倒数为适应度函数。）选择算子。从种群中选择优异的个体，使其以较高概率成为父代基因进入下一代种群中。采用轮盘赌法则，设种群规模为，个体被选中的概率计算公式为 。）交叉算子。采取部分映射杂交，对初始解中两个基因串中的随机片断进行交叉操作，还是以 ，为例，对下列两基因中的第、位中间数据进行交叉，交叉后有部分数据冲突，用 表示，再采用部分映射的方法消除重复，得到以下结果。：交叉映射 ）变异算子。在父代基因中随机选择两个断点，将断点之间的基因逆序排列或交换断点位置，从而产生一个新的个体。）重新插入初始种群得到更新后的新种群。进行迭代运算，以适应度函数为选择准则，不断把问题的可行解进行收敛，从而得到最优解。实例运用根据文献给出的实例，由补给中心点 为岛礁（）运送所需物资，由、两种型号补给舰执行物资补给任务，每条补给舰各配备 艘小艇。补给舰回程运回固体垃圾。补给方案应包括补给舰种类、第 期指挥控制与仿真 补给路线、补给数量、转运方式、物资装卸与回收材料的数量等。各岛礁（含补给中心）位置、储物情况、补给舰（艇）信息见该文献相关数据。问题中，目标函数与约束条件的处理较为复杂，总目标函数通常可取多个目标函数的加权平均，考虑约束条件时，遗传算法编码生成的初始种群及交叉（变异）后种群还要验证其是否满足约束条件，若是不可行解，需要一系列复杂的处理，总体计算量大，迭代较慢。在岛礁物资补给问题中，可以具体问题具体分析，灵活处理目标函数与约束条件。补给舰的燃油成本及各岛礁物资储存成本是一个多目标取优问题，通过计算，可发现物资储存成本远小于运输成本，故在目标函数上可以运输成本为主，为使储存成本最低，补给原则是在满足岛礁物资保障不间断的前提下尽量延长补给时间，待各岛礁剩余物资耗尽后再进行补充。与此同时，还要考虑运输工具的容量限制，基于上述分析，可运用分步优化的思路，运用智能算法先找出符合成本最低的运输路径，然后基于该路径做出微调以符合时间窗要求和为各岛礁分配物资数量。遗传算法仿真运行结果为任务规划的均衡性，可设定每条路线所经历的岛礁数量至少为 个以上。通过编程，使用 程序进行仿真，得出优化结果见图，遗传代数为。虚粗线表示 舰航行路径，实细线表示 舰航行路径。图 双舰补给路径规划图 优化方案的确定）最优路径顺序的选择使用、舰给岛礁实施物资保障时，要求使得各岛礁至少维持一个特定的供给周期。补给总的原则是：优先补给资源即将耗尽的岛屿，如、等；尽量使得补给在现有物资耗尽之后再补充，并且补充周期内所需最大库存，因为这样可以使储存成本减少；现有库存物资与后续补充的物资可用天数之和至少能满足一个补给周期所需。确定最优路径后，需要进一步安排、舰补给各岛的顺序，考虑、舰保障的各岛当前储存物资可消耗天数情况，在图 所示的路径基础上，应对此做出微调，舰先保障，再，尔后，再；由于 是小岛，应于小岛外抛锚，再由小艇倒送物资。由于 的可维持天数较长，而、保障时效要求更强，还应对 舰路径再做出微小调整，舰先保障，再，尔后，再；由于 需求量不大，时间又较为宽松，可利用 艘小艇同时由 向 运输物资。调整后的路线为 舰的，路径长 海里；舰为，路径长 海里，见图。图 调整后的优化路径 ）各岛礁物资补给的数量与时间在规划好、舰路径后，物资分配应按各岛礁能支持消耗一个补给周期的量分配，即按每天的消耗水平乘以补给周期再减去当前储存量，这样可以使得补给物资满足容量限制。进一步计算、舰到各岛的航行时间与装卸物资时间。需要注意的是、比较特殊，对于 舰来说，需要停靠 外某处，同时用 小艇倒运舰上物资保障 岛所需，计算出小艇运输与装卸总耗时为 小时。对于 舰来说，停靠于 后再保障 所需，由于 固体、液体的保障量较小，可以考虑运用 小艇来进行倒运物资，计算出总耗时为 小时。、舰 到达各岛的补给量与固体回收量、航行时间与物资装卸时间计算结果见表。通过计算，、两舰需装载补充的固体总量为 。舰固体量为 ，舰固体量为 。多出的 固体可以放小艇中。、两舰需装载补充的液体总量为 。液体量为 ，液体量为 。余昌仁，等：海域岛礁物资补给任务智能规划第 卷表 舰、到达各岛的补给量、航行时间与物资装卸时间 ，补给舰岛礁与前站点距离海里航行时间固体装卸时间液体装卸时间装卸时间固体补给量液体补给量固体回收量 舰（补给中心）舰（补给中心）最终方案成本分析各岛补充后的物资储存总成本为 元。加上补充前 的 当 前 已 有 物 资 储 存 成 本 ，共 元。根据前面的优化路径，的运输里程为 海里，的运输里程为 海里，总费用为 元。最终的运输成本加上储存成本合计为 元。结束语文章建立了岛礁物资补给任务规划模型，分析了智能算法的求解过程，结合一个实例，采用算法进行仿真运算，综合利用数据分析，得出了优化方案。方案从现实复杂问题出发，考虑保障任务较高的构成成本 岛礁物资运输成本，其次考虑储存成本、容量限制、补给周期等，分步进行优化调整，符合物资补给实际需要。当然，考虑模型的拓展性，还需要进一步结合实际情况中的多种条件如天气情况对物资保障的影响，考虑把某些岛礁作为中转站进行二次补给的情况进行规划，这些还需在未来的研究中进一步深化。参考文献：王诺，丁凯，吴迪，等面向远海岛礁群的双向物流网络规划运筹与管理，（）：，（）：孔德鑫，刘洋，赵金，等密集岛礁环境下的无人艇的路径规划信息通信，（）：，（）：郁磊 智能算法 个案例分析北京：北京航空航天大学出版社，：，：浮萍萍，叶春明，李佳桐物流配送车辆调度路径优化问题算法研究物流科技，（）：，（）：李珍萍，周文峰，张煜炜，等考虑卸载顺序约束的成品油二次配送车辆路径问题控制与决策，（）：，（）：刘云，张惠珍多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法公路交通科技，（）：，（）：，（）：孙翀翚利用光纤网络求解典型的 完全问题北京：北京交通大学，：，：第 期指挥控制与仿真 张硕航，郭改枝多旅行商模型及其应用研究综述计算机科学与探索，（）：，（）：邓南明，唐世轩，张迪基于模拟退火算法的岛礁补给路径规划兵工自动化，（）：，（）：鲍逸群基于类 模型和精英集策略遗传算法的多机器 人 任 务 分 配 研 究 武 汉：武 汉 科 技 大学，：，：，（）：刘天宇，叶军，曹欣芹，等基于动态网络图的兵力投送优化算法研究国防交通工程与技术，（）：，（）：李江成基于启发式遗传算法的岛礁物资补给任务规划军事运筹与系统工程，（）：，（）：皇甫尚乾改进罚函数分级遗传算法及其在结构优化设计中的应用广州：广州大学，：，刘晨生，宋士兵基于混合遗传算法的岛礁物资补给任务规划模型军事运筹与系统工程，（）：，（）：王梓行，姜大立，王丰，等战时单周期的远海岛礁战储物资供应保障任务规划模型军事交通学院学报，（）：，（）：李坦，肖晨，钟普查部分扩散与试错混合量子搜索算法的性能和最优参数分析信息工程大学学报，（）：，（）：张诗尧，曾子维，程子为无线传感器网络蚁群路由优化算法辽宁科技大学学报，（）：，（）：，（）：（责任编辑：许韦韦）