135 / 2023-07-15 18:09:28

基于TSP和遗传算法的应急巡逻车最优路线规划

应急巡逻车；旅行商问题；分支定界法；遗传算法

智能系统工程 > 1. 复杂系统智能需求工程

机场，作为现代最高效的长途交通工具飞机的起点与边界，通常是飞机安全的重要保障之一。车辆巡逻是机场空防的一种有力方式，可以有效解决部分机场监控系统摄像机无法覆盖区域发生应急情形的问题。机场占地面积大，内部结构复杂，安全需求极高。因此如何快速规划合理路线，实现应急巡逻车辆行驶路线对所有需求点位的全覆盖，成为了机场安全治理不可忽视的问题。“5G+4K”超高清视频直播信号传输系统主要由“5G+4K”广电级视频传输装置、互动接收器和集中管控平台这三部分组成，可实现正向4K超高清视频直播和反向低时延互动连线，从而使应急指挥具有更好的实时性、灵活性、精准性，有力巩固机场空防的安全保障。

为保障机场中每一个监控区域外场地的安全，应急巡逻车辆需要在一个整体巡逻任务中经停所有位点并最终返回起点。高效多次覆盖每个位置是应急巡逻体系的核心要点，故以单次巡逻过程中总耗时最短为目标，建立了基于分支定界法和遗传算法的TSP模型。对机场巡逻车巡逻线路进行分析，并最终找到在1和2辆巡逻车情景下的最优路线，结合已知条件中各点位的地理数据距离矩阵及示意图解决以下问题。问题一：以9号位点为一次巡逻的起点，请建立整体训练数学模型，找到能够完整经过14个位点的最优方案。问题二：假设存在两辆应急巡逻车辆，沿用上述条件中各位点的地理数据距离矩阵及示意图，根据所求的数学摸型找到两个合适的出发地点，使该次巡逻能够满足时间最优原则。

针对上述总耗时最短的最优目标，提出两点假设。假设一：应急巡逻车辆单次行驶过程中全程进行20km/h的匀速直线运动。解释：忽略因路况或者其他原因导致的车速变化以及车辆方向改变情况，利于宏观把控巡逻车整体运行趋势。假设二：不考虑应急巡逻车辆在每个经停地点停留所花费的时间。解释：忽略地点停留时间，突出路程运动时间，体现主次矛盾权衡。

针对问题一，基于旅行商问题(TSP)建立了基于分支定界法求解的单辆巡逻车的最优时间模型。首先，对不连通的路径进行长度极大值惩罚加权，并筛除必然构成回路的结点2、3、4。随后，基于运动学匀速情况下路径时间等效原理及TSP分析思想建立以总路程最短为目标的函数，以出入度、DFJ方程和破回路条件为约束的单目标0-1线性规划模型。采用分支定界法求得最优路线为：9-8-12-11-1-7-5-2-3-5-6-4-6-10-14-13，该路径总路程5820米，用时0.291小时，即17.46分钟。

针对问题二，探究多个起点的单程循环最短路径问题是经典的多旅行商(MTSP)问题。根据多旅行商问题建立基于遗传算法的双巡逻车的最优时间模型。基于问题一中模型预处理，以两辆巡逻车路径总和最短为目标函数，以出入度、DFJ方程即破回路为约束条件建立单目标0-1整数规划模型，针对模型求解本质即求解NP-Hard问题，通过遗传算法设定重要参数如下：染色体一分为二，通过部分映射交叉、顺序交叉、基于位置的交叉三种变异方式进行处理，建立了大小为m，断点为2的遗传族群。最终求得两辆车的起点分别为：6和11，对应的最优路程为：6-4-6-9-13-14-10-6和11-1-5-2-3-5-7-8-12-11，路径总和为5640米，用时0.282小时，即16.92分钟。

总结而言，针对应急巡逻车路径规划模型的建立由简入繁，层层递进，具有良好可扩展性。问题一结合原始矩阵维度通过分支定界求得精确解避免算法早熟问题，问题二合理设定参数求得局部最优解，问题二最短时间0.282小时明显优于问题一最短时间0.291小时，体现模型建立的准确性与方法选择的合理性。