2023年7月27日发(作者：)

第２５卷第１期２０１０年。３月湖南科技大学学报（自然科学版）ＪｏｕｍａｌＶ０１．２５Ｎｏ．１Ｍａｔ．２０１０ｏｆＨｕｎａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）多约束最短路径模型与求解胡耀民１’２，刘伟铭２（１．广州番禺职业技术学院信息工程学院，广东广州５１１４８３；２．华南理工大学土木与交通学院，广东广州５１０６４０）摘要：提供满足驾驶贞多个心理期望的路径是导航系统该解决的关键问题，其本质是资源约束最短路径问题，属于ＮＰ难问题，无法使用传统的最短路径算法解决．提供了多约束路径规划的数学模型，并使用了蚁群算法对其求解，在算法中针对问题重新设计了信息素更新规更Ｉｊ和启发因子．实验证明算法具备良好的寻优能力。能准确找出路网中满足多种属性约束的路径．关键词：多约束；路径规划；蚁群算法中圉分类号：ＴＰ３ｌｌ文献标识码：Ａ文章编号：ｔ６７２－ｇｔ０２（２０１０）０１－００８７－０４驾驶员在使用导航系统进行路径规划时都希望得到的路径最短以达到节省时间和费用。但同时又希多约束最短路径，并在基本蚁群算法的基础上重新设计信息素更新规则，引入信息素更新算子。动态增加负荷约束的路径上信息素；为提高算法效率，算法中改进能见度启发因子．望路径是容易驾驶、安全性很高、风景迷人的，这就要求路径满足多种路径质量的约束条件．这个问题的实质就是在最短路径（ｓｈｏｒｔｅｓｔｐａｔｈ：ＳＰ）的基础上添加另外的约束条件而构成带约束最短路径问题（ｃｏｎｓｔｒａｉｎｅｄｓｈｏｒｔｅｓｔ１数学模型多约束最短路径是求解路网中能够同时满足多ｐａｔｈ：ｃｓＰ）．ＣＳＰ问题有多种形式，如要求路径必须经过某个节点、必须经过某条弧、路径资源限制等，文中使用的是资源约束的ＣＳＰ定义ｎ－习：求解满足路径上某种或某几种属性之和小于设定的上限值的最短路径．众所周知，ＳＰ问题的时间复杂度为ｎ：（ｎ为节点个数），然而不幸的是ＣＳＰ问题已经被证明为ＮＰ难问题１６－７１，无法采用ｄｉｊｓｔｒａ或Ａ宰来解决．对于ＣＳＰ问题的个路径属性约束（如到达时间限制、安全性限制、距离限制、费用限制、路的等级限制等），且距离最短的路径，下面对多约束最短路径建模．交叉１３对应结点，两交叉口之间的路段对应弧，路段的属性使用多元组来表示．有向图满足了导航需要的路网表达方法和存储结构应满足的要求，如存储量小，便于路线优化算法对其进行操作，充分考虑路冈作为网络的特殊性，能够表达路网要素及拓扑结求解，也是学术界一直在探讨的问题，Ｈａｎｄｌｅｒ，Ｇ．Ｙ．，Ｚａｎｇ昀中使用了Ｋ一最短路径和拉格朗日松弛的方式进行求解，成为ＣＳＰ问题的经典解法，但求解的时间构，能够表达单向交通、交叉ＩＺｌ转向限制等交通管制措施，能够表达路网的各种特殊结构，要考虑结点权重如何存储．路网有向图的可以表示为式（１）：复杂度并不令人满意．蚁群算法模拟生物界群体觅食的能力，能够在实际的路径搜索过程中对外界的影响做出动态的响应，是一种具有分布计算、信息正反馈和启发式搜索等特征的优化工具旧，因而在交通最优路径选择中具有极大的可能性和适应性．作者先给出多约束路径的数学模型，采用改进型蚁群算法来寻找收稿日期：２００９—１０－２２基金项目：国家自然科学基金资助项目（５０９７８１０６）Ｉ％＝（Ｖ，昱），｝ｙ＝ｆ１，２，３，４，…），ＩＥ＝（（ｕ，矿，Ｑ。）ｌｕ，ｙ∈ｙ１．式中，Ｑ。是道路的属性集用多元组表示，如（长度、平（Ｉ）通信作者：胡耀民（１９７５－），男．湖南宁乡人，博士生，讲师。主要从事智能交通及数据挖掘研究．ＥＬｍａｉｌ：ｈｙｍｓｅｕｔ＠１６３．咖万方数据均时速、收费金额、道路等级）等．为了表示方便本文引入了其他一些符号定义：Ｃ：路网有向图矩阵；０：表示起始点；ｄ：表示终点；ｃｆ：从节点ｉ到节点＿『的弧，ｃＦ∈Ｃ；西：路段ｃ＃的长度；石：路段ｃＦ的通行费金额（不包括燃油耗费），按不同车辆类型有不同数据；≈：行驶在ｃｉ时每公里的耗时，参考历史的平均时段统计数据；５ｆ：发生在ｃｆ上的交通事故率，参考历史的平均时段统计数据．在行车时间、通行费、安全性等方面施加了质量约束的多约束最短路径数学模型：Ｍｉｎ（ｃ）刊ｎ（磊磊（西‘略），（２）磊磊（蜀’蚺）≤珥，乏乏（西听）＜乃，ＪＥｙｎ（１也·ｓ，）≥Ｓ，ｉＥｙＪＥｙＸｏ∈｛０，１），ｉ，ｊ∈Ｅ西，如果ｃ＃弧在连接０和ｄ的出行路径ｐ上为１，否则为０；Ｇ表示路径Ｐ上的距离：Ｇ＝荟荟（蜀’西）．Ｇ＝乞乞（蜀’西）．（３）到达时间约束：乏三（蜀·西·巧）≤Ｂ．（４）安全性约束：（５）ｎ（１《一ｉ）≥ｓ，ｙＪＥ通行费用约束：磊磊（墨＂ｆＯ＜ｏ．。（６）式中ＤＰ为所选路径ｐ＿Ｉｚｔ拘Ｙｔ许时间开销上限，Ｓ为所选路径Ｐ上安全系数下限，Ｃ为所选路径上的通行费用上限．２算法设计蚁群算法就是受蚂蚁觅食行为的启发，以人工蚂万方数据蚁模拟真实蚂蚁行为来求解组合优化问题的方法．在２０世纪９０年代初期，由意大利学者ＤｏｆｉｇｏＭａｃｒｏ等首先提出１９１．其原理在于【肛瑚，蚂蚁在所经过的路径上留下一种称为信息素的挥发性分泌物，在觅食过程中蚂蚁能够感知这种物质的存在及其强度，并以此来指导己的运动方向，同时它们倾向于朝着信息素浓度高的方向移动．信息素浓度越高的路径，被选择的机会就越多，蚂蚁在其上留下的信息素就更多，而更多的信息素又能吸引更多的蚂蚁，从而形成一种正反馈．通过这种正反馈，大部分的蚂蚁最终都会走上同一条最优路径．为了求解多约束高质量路径模型（Ｉ号模型），要改进解决ＴＳＰ问题的基本蚁群算法哩２．１蚂蚁转移规则为模拟蚂蚁的行为引入如下记号叨：设１７ｌ是蚁群中蚂蚁的数量，也（ｉ。７，…，霸）表示节点ｉ和节点．『之间的距离，％（￡）表示ｔ时刻在节点ｉ和节点歹连线信息素．初始时刻，各条路径上信息素的浓度相同，设％（ｏ）＝ｃ（ｃ为常数）．蚂蚁尼（ｋ＝ｌ，２，…，ｎ）在运动过程中，根据各条路径上的信息素的浓度决定转移方向，Ｐ：（１）表示在ｔ时刻蚂蚁ｋ从节点ｉ转移到节点－『的概率；％为能见度启发因子，表示目标点的能见度；ｄ为信息启发因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间协作性越强；口为期望启发因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发式因子在蚂蚁选择路径中的受重视程度，其值越大，则该转移概率越接近于贪心规则．蚂蚁ｋ从ｉ节点转移至节点，转移规则按如下公式进行：如果：Ｐ：（１）印。，转移概率按式（７）来求解，其中Ｐ。是转移概率门槛值，式（７）可加速算法收敛：ｐ＃Ｌ‘Ｊ２Ｉｎ否刚ｌ，、ｆｍａｘ（ｒｉ－（ｔ））Ｊ∈ａｌｌｏｗｅｄ＋，Ｌ，Ｊ否则按式（８）来求解：ｊ！迎必蛆Ｊ∈ａｕ。ｗｅｄＩ，ｐ：（￡）＝∑ｈ（ｆ）ｒ·ｍｆ（１）】Ｂ（８）Ｏ，否则．式（８）中啊不能使用基本蚁群算法中的１慨，因为这样会导致蚂蚁贪图单步快捷而偏离行进方向．为了改进算法的收敛速度，７７Ｆ的取值按照式（９）规则：，７，：ｆ：，ｄ黧Ｐｉ即不等于ｏ，’７＃２Ｉｌ，否妣（９）Ｌ９Ｊ式（９）中ｄｉ啄为＿『点到目标点ｄ的直线距离，这样可以启发蚂蚁以较高概率向最终目标点行进，而不贪婪当前最小一步．２．２信息素更新规则为了诱导蚂蚁以较大几率向满足条件的路径靠拢，在所有蚂蚁都找到一条路径后（也即一个循环结束）后，要对路网上信息素按照式（１０）更薪：拍川＝陀黝０嚣慧茹篇驴。，式（１０）中Ｐ为全局信息素挥发因子，Ｐ为本轮循环找到的最优路径，Ｆ是一个函数，可表示为肚一·ＦＩ＋Ｂ·胁Ｃ·凡＋Ｄ·Ｒ（１１）式（１１）中，只表示路径Ｐ上的距离；最表示路径能够满足时间限制；玛表示路径期望满足安全性限制；只表示路径期望满足通行费限制．冗，易，最，只可分别用式（１２），式（１３），式（１４），式（１５）来表示：一＝善磊（墨’西）．（１２）缉一善；（墨’由‘。’当畛磊；（墨’鸯‘每）时，（１３）６，当咏ｉ∑ｅＶｊ∑ｅＶ（鼍。西。≈）时．即ｎ（１也·ｓ＃），当ｐＨ（１也·ｓｉ）时，ｏ，当昂＜‘１７（１矗ｌ·ｓｆ）时．印磊磊（墨皤）’当ｐ善磊（西西埘’（１５）ｏ，当水篙磊（墨嘎）时·式（１１）中，Ａ，Ｂ，Ｃ，Ｄ是４个系数，都是正实数，分别表示距离限制、时间限制、安全性限制、通行费限制的相对重要性，在如果算法中要强调哪个因素的限制，就可以把系数取一个较大正实数．通过上述定义可知，如果所选路径的总路径距离越短，同时又满足时间限制要求、安全性限制要求、通行费限制要求，则该路径上信息素相应要增加更多，这就启发更多蚂蚁向这些路径上的边汇聚．多约束高质量路径的蚁群算法具体步骤如下：１）初始化网络拓扑中各边的信息素；２）放置ｍ只蚂蚁在出发节点，各蚂蚁通过转移规则来选择各自路径，当某只成功完成路由选择之后，万方数据该蚂蚁所选路径上各边的信息素根据信息素更新规则进行更新；３）对所有蚂蚁重复第２）步，直到ｍ只蚂蚁都完成了第２）步；４）选择在本次循环中费用最小。且满足时间限制、安全性限制的路由的蚂蚁，然后使用全局更新规则对该蚂蚁所选的路径各边上的信息素进行更新；５）重复第２）ｏ）步，直到获得满意的结果．３算例３．１试验为了验证算法的寻优能力。作者在ｗｉｎｄｏｗｓＸＰ下，使用Ｊｂｕｉｌｄｅｒ２００６编程实现了算法，对多约束最短路径模型进行求解．图１是是仿真所用的网络拓扑，假定所仿真路网上边的两个方向的属性一致，所以可以用把有向图转换为无向图表示，每一条无向边表示正反两条弧．顶点用编号带坐标的方法表示，坐标值（Ｘ，ｙ）如果在真实地图中则换成（经度，纬度）元组；每条边用一个四元组（１ｅｎｓｔｈ，Ｓｐｅｅｄ，Ｔｏｉｌｓ，Ａｃｃｉｄｅｎｔ—ｒａｔｅ）来表示，其中元素分别表示距离、允许车速、通行费用、事故发生统计概率．距离，ｋｍ图１仿真所用网络拓扑Ｆｉｇ．１Ｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｕｓｅｄｉｎｓｉｍｕｌａｔｉｏｎ试验１：让算法尝试规划ｌ—１４之间最优路径．规定路径质量：允许的行车时间ＤＤ＜４ｈ，允许的事故发生率（１－Ｓｐ）＜＝ｌＯ‘５，通行费用＜１００．设置蚂蚁个数ｍ＝ｌＯ。信息素启发因子ａ＝ｌ，距离期望启发因子届＝５，信息素初值＝１００，信息素挥发因子ｐ＝Ｏ．５５，系数Ａ＝ＩＯ，拈１５，Ｃ－＝２００，Ｄ＝１５，迭代次数设定为１００次．经过３００次实验得到如表１所示结果．试验２：为了考查算法在无法给出驾驶员期望质量的路径时行为，作者尝试使程序规划１－９之间的路径，且规定路径质量：允许的行车时间Ｄｐ＜３ｈ，允许的事故发生率（１４）＜＝１０－５，通行费用＜５．设置蚂蚁个数ｍ＝１０，信息启发因子ａ＝ｌ，期望启发因子肛５，信息素初值＝１００，信息素挥发因子ｐ＝０．５５，系数Ａ＝１０，Ｂ＝１５，Ｃ＝２００，Ｄ＝１５，迭代次数设定为１１３０次．经过３００次实验得到如表２所示结果．表１路径规划结果表１Ｔａｂ．１Ｔａｂｌｅｏｆｐａｔｈｐｌａｎｎｉｎｇｒｅｓｕｌｔｓ１必须对其进行修改，文中重新设计了信息素更新算子，把路径质量约束添加到了信息素更新算子中，改进了能见度启发因子，从而增强了算法的正反馈作用，提高了算法的收敛速度．仿真试验表明：在驾驶员规定的路径质量能够满足时，算法能够快速有效的求得满足质量约束的最优路径或次优路径；在驾驶员规定的路径质量不能满足时，算法能够求出最短路径或次短路径．这对导航系统的路径规划问题的研究有一定的参考价值．参考文献：【１】Ａｎｅｊ．Ｙ，ＡｇｇａｒｗａｌＶ，ＮａｉｒＫ．Ｓｈｏｒｔｅｓｔｃｈａｉｎ鬃怒所得牌霎磊距离豁。裹鸶萎曩嚣１－１４１Ｊ６—７—１２—１４９５３４０１－６＿７—１１—１４８０３００３．２６５３．６２５１０ｒ５１０４２６６３４８８·６７１１．３３表２路径规划结果表２Ｔａｂ．２Ｔａｂｌｅｏｆｐａｔｈｐｌａｎｎｉｎｇｒｅｓｕｌｔｓ２ｓｕｂｊｅｃｔｔｏｓｉｄｅｃｏｎｄｉｔｉｏｎｓ［Ｊ１．Ｎ咖ｏｒｌ‘ｓ，１９８３，１３（１）：２９５－３０２．【２】ＢｅｎｓｌｏｙＪ，ＣｈｒｉｓｔｄｌｄｅｓＮ．Ａｎａｌｇｏｒｉｔｈｍｆｏｒｓｈｏｒｔｅｓｔｐａｔｈｐ，ｏｂｉｅｍｌＪ】．Ｎｅｔｗｏｒｋｓ。１９８９，１９（２）：３７９－３９４．Ｍ，ｅｔ．ａｆ．Ｔ＇ｒｍｔｃｏｎｓｔｒａｉｎｅｄｒｏｕｔｉｎｇａｎｄ【３１ＤｅｓｒｏｓｉｅｍＪ，Ｄｕｍａｓ８ｃＩｌｅｄｕｌｉｎｄＪ】．ＮｅｔｗｏｒｋＲｏｕｔｉｎｇ，１９９５，８（１）：３５－１３９．Ｄｕｍｉｕ＇ｅｓｃｕ［４１Ｉ，ＢｏｈａｄＮ．Ｔｈｅｗｅｉｇｈｔ－ｃｏｎｓｔｒｓｉｎｅｄｓｈｏｒｔｅｓｔｐａｔｈｐｍｂｌｅｍ：ｔｈｅ埘删ｃｏｎｓｔｒａｉｎｅｄＹ，Ｓｏｌｏｎａｎｄ３．２结果分析试验１可以看出，发现最优解率为８８．６７％；发现ｉＳｌｐｒｅｐｒｏｃｅｓｓｉｎｇ，眈ａｌｉｎｇｎｕｍｅｒｉｃａｌＰｒ叼胁ｍｉＩｌｇ（ＩＳＭＰ），ＳｐｒｉｎｇｅｒＬＮＣＳ。２０００：４５３－－４６１．ＳｅｌｌｍａｎｎＭ．Ｃｏｓｔ－ｂａｓｅｄｆｉｌｔｅｒｉｎｇｆｏｒｓｈｏｒｔ日ｐａｔｈｃｏｎｓｔｒａｌｎＮ阑．Ｐｒｉｎｃｉｐｌｅｓａｎｄｃｏｍｐｔｌｒｌ９０ｎｓ【Ｃ胁ｔ∞诅ｌｉｍａｌｄｙｎｍｉｃｐ】ｑ印ｌⅢ皿ｉＩ，ｇＳｙｍｐｏｓｉｕｍａｌｇｏｒｉｔｈｍｓｗｉｔｈＭａｔｈｅｍａｔｉｃａｌ次优解率为１１．３％，没有无效解，说明改进后蚁群算法具备良好的寻优能力．从图中可以看出ｌ—１４的路由中存在ｌ＿４—８—１ｌ—１４，虽然通行费用只要２５，距离２９０，但耗时达到５．５５ｈ，且事故率达到ｌ旷数量级，路径质量没达到要求，算法没选择它．试验２可以看出，当驾驶员给出的路径质量约束不能满足时，算法还是能够规划出路线ｌ－４—８—９和ｌ一２—３—９，此时算法已经退化为求距离最短的路径规【８１ｆ９】１６１［７１Ｐｒａｃｔｉｃｅ０ｆＣｏｎｓｔｒａｉｎｔＰｒ叼舢删ｉＩｌｇ（ＣＰ），ＳｐｒｉｎｇｅｒＬＮＣＳ，２００３：６７９－６９３．ＨａｎｄｉｅｒＧＹ，ＺａｎｇＬＡｄｕａｌａＬ耐ｔｌｌｍｆｏｒｔｈｅｃｏｎｓｔｒａｉｎｅｄｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍ［Ｊ］．Ｎａｗｏｒｋｓ，１９８０，１０（４）：２９３－３ｌｏ．ＷａｎｇＺ．ＣｍｗｃｒｏｆｔＪ．Ｑｕａｌｉｔｙ０ｆⅫ一∞ｒｏｕｔｉｎｇｆｏｒｓｕｐｐｏｒｔｉｎｇｍｕｌｔｉｍｅｄｉａ印ｐｌｉｅａｔｉｏｎｓ叨．ＩＥＥＥＪｏｕｒｎａｌ帆ＳｅｈｅｔｅｄＡｒｅａｓｉｎＣｏｍｍｕｎｉｃａｔｉｏｎｓ，１９９６。１４（７）：１２２８—１２３４．ＭｕｌｌｅｎＲＪ。ＭｏｎｅｋｅｓｓｏＤ，Ｂａｒｍａｎｓ，ｅ‘ａｆ．Ａｒｅｖｉｅｗｏｆａｎｔａ蛳ｔＩＩｍＢ叨．ＥｘｐｅｒｔＳｙｓｔｅｍｓｗｉｔｈＡｐｐｌｉｃａｔｉｏｎｓ．２００９，３６（２）：９６０８－９６１７．ＣｏｌｏｒｍＡ，ＤｏｒｉｇｏＭ，ＭｉｎｌｅｚｚｏＶ．Ｄｉｓｔｒｉｂｕｔｅｄｏｐｔｉｍｉｚａｔｉｏｎｂｙａｒｔｔｃｏｌｏｎｉｅｓ［Ｃ］／／ＰｒｏｅｅｅｄｉｎｇｏｆｔｈｅＦｉｒｓｔＥｕｒｏｐｅａｎＣｏｎｆｅｒｅｎｃｅＡａｉｆｌｃｉａｌＬｉｆｅ，ＥＩ砌Ｐｕｂｌｉｓｈｉｎｇ，１９９１：１３４－１４２．垃砌ｌ培ｓａｌｅｓｍａｎ划算法，保证了路径规划结果，体现了算法的鲁棒性．【１０］ＤｏｒｉｇｏＭ，ＣａｍｂａｒｄｅｌｌａＬＭ．Ａｅｔｍｐｅｒａｔｉｖｅｌｅｓｍｉｎｇａｐｐｒｏａｃｈｔｏｔｈｅｐｒｏｂｌｅｍ［／１．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ帆ＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，１９９７。ｌ（１）：５３－６６．【１１】ＹａｎｇＪＨ，ＳｈｉＸＨ．Ａｎａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｍｅｔｈｏｄｆｏｒｇｅｎｅｒａｌｉｚｅｄ【１２】ＪｅｌｍｅｒＭａｄｎｎｓｖａｎＡｓｔ，ＲｏｂｅｒｔＢａｂｕｓｋａ．ＮｏｖｅＩａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｐｐｒｏａｃｈｔｏｏｐｔｉｍａｌｃｏｎｔｒｏｌ叨．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌ０ｆＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｉｎｇａｎｄＣｙｂｅＩ讹ｔｉ伪，２００９，２（３）：４１４－４３４．［１３１ＳａｒａＭｏｒｉｎ，Ｃｌｌｌ，ｏｌＪｎｅＧａ口６，ＭａｒｅＯｒａｖｄ．Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｗｉｔｈｓｐｅｃｉａｌｉｚｅｄｐｈｅｒｏｍｏｎｅｔｒａｉｌｆｏｒｔｈｅｅａｒ－ｓｅｑｕｅｎｃｉｎｇｐｒｏｂｌｅｍ【刀．ＥｕｒｏｐｅａｎＪｏｕｍａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅｓｒｅｈ，２００９，１９７（１）：１１８５一１１９１．４结论针对导航系统中多约束路径规划问题，引入蚁群算法求解，为求解属于ＮＰ－Ｃ的带约束最短路径问题ＴＳＰｐｒｏｂｌｅｍ［Ｊ］．Ｐｒ删ｉｎＮａｔｕｒａｌＳｃｉｅｎｃｅ，２００８，１８（１）：１４１７－１４２２．提供了一个可行方案．基本蚁群算法式是求解ＴＳＰ问题的，要使之能够应用于求解多约束最短路径问题，Ｍｕｌｔｉ－ｃｏｎｓｔｒａｉｎｅｄｓｈｏｒｔｅｓｔｐａｔｈｍｏｄｅｌａｎｄｓｏｌｖｉｎｇＨＵＹａｏ～ｍｉｎｌ，一．ＬＩＵ（１．ＧｕａｎｇｚｈｏｕＰａｎｙｕＡｂｓｔｒａｃｔ：ＨｏｗｔｏＷｅｉ—ｍｉｎ９２Ｐｄ归ｈｍｅ，Ｇｕａｎｇｚｈｏｕ５１１４８３，Ｃｈｉｎａ；２．ＳｏｕｔｈＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ。Ｇｕ仰ｇｚｈＯＲ５１０６４０，Ｃｈｉｎａ）ｐｒｏｖｉｄｅｒｏｕｔｅｔｏｍｅｅｔｔｈｅｄｒｉｖｅｒ。ｓｍｕｌｔｉｐｌｅｐｓｙｃｈｏｌｏｇｉｃａｌｅｘｐｅｃｔａｆｉｏｎｓｉｓｔｈｅｋｅｙｐｒｏｂｌｅｍｏｆｎａｖｉｇａｔｉｏｎｓｙｓｔｅｍ．Ｔｈｅｅｓｓｅｎｃｅｏｆｔｈｉｓｐｒｏｂｌｅｍｉｓｒｅ８０ｕｒｃｅｃｏｎｓｔｒｍｎｅｄｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍ（ＲＣＳＰ），ｗｈｉｃｈｂｅｌｏｎｇｓｔｏＮＰ－Ｃｐｒｏｂｌｅｍｓａｎｄｃａｎｎｏｔｂｅｓｏｌｖｅｄｗｉｔｈｔｈｅｔｒａｄｉｔｉｏｎａｌｓｈｏｒｔｅｓｔｐａｔｈａｌｇｏｒｉｔｈｍ．Ｍｕｌｔｉ—ｃｏｎｓｔｒｍｎｅｄｓｈｏｒｔｅｓｔｐａｔｈｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｗ鹪ｐｒｅｓｅｎｔｅｄ，ａｎｄｕｐｄａｔｅｒｕｌｅａｎｄｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｗ如ｕｓｅｄｔｏｓｏｌｖｅｉｔ．Ａｉｍｅｄａｔｔｈｅｐｒｏｂｌｅｍ．ｐｈｅｒｏｍｏｎｅｈｅｕｒｉｓｔｉｃｆａｃｔｏｒｗｅｒｅｒｅｄｅｓｉｇｎｅｄｉｎｔｈｅａｌｇｏｒｉｔｈｍ．ＥｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄｏｐｔｉｍｉｚａｔｉｏｎａｎｔａｌｇｏｒｉｔｈｍｈａｖｅＫｅｙｇｏｏｄａｂｉｌｉｔｙｔｏａｃｃｕｒａｔｅｌｙｆｉｎｄｍｕｌｔｉ－ｃｏｎｓｔｒａｉｎｅｄｓｈｏｒｔｅｓｔｐａｔｈｉｎｒｏａｄｎｅｔｗｏｒｋ．ｐｌａｎ；ｉｍｐｒｏｖｅｄａｎｔｗｏｒｄｓ：ｍｕｌｔｉ－ｃｏｎｓｔｒａｉｎｅｄ；ｒｏｕｔｅｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ万方数据多约束最短路径模型与求解作者：作者单位：胡耀民， 刘伟铭， HU Yao-min， LIU Wei-ming胡耀民,HU Yao-min(广州番禺职业技术学院,信息工程学院,广东,广州511483;华南理工大学,土木与交通学院,广东,广州510640)， 刘伟铭,LIU Wei-ming(华南理工大学,土木与交通学院,广东,广州510640)湖南科技大学学报（自然科学版）JOURNAL OF HUNAN UNIVERSITY OF SCIENCE & TECHNOLOGY2010，25(1)0次刊名：英文刊名：年，卷(期)：被引用次数：

al K

Shortest chain subject to side conditions 1983(1)y ofides N

An algorithm for the resource constrained shortest path problem 1989(2)iers n M

Timne constrained routing and scheduling 1995(1)escu N

The weight-constrained shortest path problem:preprocessing,scaling anddynamic programming algorithms with numerical comparisons nn M

coet-based faltering for shorter poth canstrsints r G I

A dual algorithm for the constrained shortest path problem 1980(4) oft J

Quality of service routing for supporting multimedia appllcations 1996(7) R sso S

A review of ant algorithms 2009(2) zo V

Distributed optimization by ant colonies della L M

A cooperative learning approach to the traveling salesman problem1997(1) io n Liang

An ant colony optimization method forgeneralized TSP problem[期刊论文]-自然科学进展（英文版） 2008(11) Marinus van Babus ks

Novel ant colony optimization approach to optimal control2009(3) ne Gagn Gravel

Ant colony optimization with a specialized pheromone trailfor the ear-sequencing problem 2009(1)

1.学位论文

叶媛媛

多UCAV协同任务规划方法研究

2005 多UCAV协同任务规划是充分发挥多UCAV协同作战优势、使任务复杂性与UCAV能力之间保持良好协调性所必须解决的关键问题。它是一个多约束、强耦合的复杂多目标优化与决策问题，其本质是通过综合利用各种优化、决策和智能计算等技术为UCAV设计出协同的任务计划，使多UCAV协同作战的整体效能优于各个UCAV单独作战效能的总和。论文以问题解耦降低复杂度、问题建模和问题求解为主线，重点研究了多UCAV协同任务规划的两个关键问题——多UCAV协同任务分配和多UCAV协同路径规划问题。 对多UCAV协同任务规划问题的相关概念进行了定义，并阐述了问题的复杂性。以对多UCAV任务的层次特性分析为基础，提出了任务规划分层迭代框架，将任务规划分为编队层和单机层。在此基础上，依据一定的战术约定，进一步提出了多UCAV协同任务规划逻辑流程，通过层间和层内解耦将问题分解为不同层次的子问题，有效降低了任务规划问题的求解难度。以所提出的逻辑流程为基础，论文从子问题中抽象出多UCAV协同任务分配和多UCAV协同路径规划两个关键问题。 建立了多UCAV协同任务分配多目标整数规划模型(MOIP)。通过引入虚任务区概念，将三维约束降为二维约束，有效地降低了决策变量的复杂性。以多目标优化理论为基础，对约束条件与规划指标进行了形式化描述，提出了多UCAV协同任务分配MOIP模型，为一类具有复杂多约束的多UCAV协同任务分配问题建模提供了有效方法。 建立了基于V(VORONOI)图的多UCAV协同路径规划(VBCUPP)模型。利用V图的拓扑特性，对包括禁/避飞区和威胁的战场环境建立了V图形式化描述。对V图进行了扩展，使之有效处理不同类型、强度的威胁，及UCAV飞行安全高度约束等。建立了基于V图的威胁源索引，更真实地反应了战场空间的威胁度分布。在此基础上，以V图顶点为路径点，V图的边为路径段，建立了多UCAV协同路径规划VBCUPP模型，为复杂环境下的一类多路径规划问题建模提供了一种有效方法。 依据任务分配MOIP模型，提出了多目标整数规划进化算法(MOIPEA)。分析了任务分配问题约束条件的特点，提出了全局/局部约束和自由/非自由变量概念，设计了整数编码方案和基于整数编码的进化算子，并在编码设计和进化算子中利用约束启发信息提高了约束满足率。论文采用外部非劣集技术防止进化中已经产生的非劣解被丢失，提出并设计了从Pareto占优数、次占优数以及占优幅度三个不同粒度计算外部非劣集个体适应度的方法，提高了非劣解的性能。仿真结果表明，MOIP模型和MOIPEA算法能够有效地解决多约束的复杂多UCAV协同任务分配问题，且MOIPEA算法具有高约束满足率的优良性能。MOIPEA算法为一类具有复杂多约束的多目标整数规划问题求解提供了一种思路和方法。 分析了多UCAV协同路径规划VBCUPP模型以及基于共生机制共同进化算法的特点，以每一UCAV的所有潜在路径构成一个进化路径种群，多个UCAV的进化路径种群构成进化路径群落，提出了基于V图的多UCAV协同路径规划共同进化算法(VBCEA)。通过在染色体编码中引入关键基因段和可选基因段有效处理了关键点约束，并深入讨论了适应度计算和进化算子设计等关键问题。通过原型算法仿真验证了V图用于路径规划的可行性以及VBCUPP模型和VBCEA算法的有效性。最后在某UCAV系统综合仿真验证环境中对基于VBCEA的多UCAV协同编队层和单机层路径规划方法进行了仿真。仿真结果表明，VBCUPP模型和VBCEA算法可以有效地解决多UCAV协同路径规划问题。VBCUPP模型和VBCEA算法为一类复杂环境下的多约束多路径规划问题求解提供了一种有效方法。2.学位论文

史美萍

基于人机协同的月球车路径规划技术研究

2006 月球车的研制是探月工程的重要组成部分，而导航与控制又是月球车研制的核心技术之一。在不确定的非结构化的月面环境下，实现月球车安全导航面临的一个关键问题是路径规划。月球车路径规划不仅要考虑行程的优化，还需要考虑地形的可通行性、障碍的不确定性等因素。考虑到人机智能融合对于提高月球车导航性能的意义，本文重点对基于人机协同的多约束多目标优化的路径规划方法进行了研究。 本文完成的成果和创新点为： 1)提出了一种基于人机协同的三层递阶式导航控制系统结构。该结构采用了慎思与反应相结合的导航控制策略。建立了多种人机协同机制，将人的规划能力和反应能力融入到地面协同规划层，并通过遥控命令作用到车载导航系统，实现了人机智能的有机结合，提高了月球车运行的安全性和环境适应性。 2)提出了一种基于人机协同的多约束路径规划的环境建模方法。该方法综合考虑了四个方面的因素：针对月面地形的可通行性，利用月面数字高程模型，结合月球车的通过性约束，实现了可通行性分析；针对环境感知的不确定性和控制器执行的不确定性，建立了障碍物的概率分布模型，并引入潜在危险区和危险性度量函数，将不确定性反映到环境建模中；针对规划过程中的人机交互行为，引入了路径导引点和路径导引函数，将人的智能融合到环境建模中；针对月球车运动的平稳性，建立了路径平滑性度量模型。 3)提出了一种面向人机协同的多目标路径规划的性能评估方法。以多目标优化理论为基础，建立了多目标路径规划优化模型。在此基础上给出了一种多目标路径规划进化算法，该算法能同时得到各个优化指标相互制衡下的多个非劣解。 4)提出了一种基于模糊偏好关系的路径规划参数优选方法，将多目标决策问题转化为符合人的主观意愿的单目标决策问题。研究并实现了一种利用完全一致性约束快速构建模糊偏好关系矩阵的算法，该算法不仅能真实地反映操作员的主观偏好，而且还减小了操作员对各优化目标重要性判断的盲目性。 在上述工作的基础上，设计并实现了一个基于人机协同的路径规划系统，并在自行研制的月球车平台上进行了实车试验，验证了以上方法和算法的可行性与有效性。3.学位论文

刘志宏

野战数字化信息系统体系结构与总体技术--路径规划子系统的设计与实现

1998 该论文详细介绍了路径规划系统的组成、功能及其实现过程.对Mapinfo地理信息系统的功能和其功能的再利用进行了详细地研究,以Mapinfo系统为辅助工具,在路径规划系统中实现了地图的分层显示、地图的编辑、地图要素的查找、地图分析和地理信息管理的功能.该论文还对路径规划的算法进行了详细的研究,设计了多目标、多约束的路径规划算法,在系统中实现了较为高效的路径规划功能.4.学位论文

王海梅

基于GIS的最优路径算法研究与实现

2008 最优路径规划是网络优化的基本科学问题之一，多年来产生了大量相关领域的研究成果，然而计算机网络与通信系统，基于GIS的智能交通系统、移动机器人、军事指挥系统等众多应用领域出现的新问题，对最优路径的研究又提出了新的任务和要求。论文在相关研究的基础上，以军工科研项目为主要需求，重点研究了作战背景下满足一定解算条件的单任务、多任务最优路径问题，最短路径的高效算法，多约束最优路径问题以及时变网络最优路径问题。 论文的研究成果主要包括： （1）基于数字地图线状图元文件，构建了适于最优路径算法研究的道路网拓扑结构。 （2）设计并实现了作战背景下满足最短和最快解算原则的单任务、多任务最优路径辅助决策系统。针对多任务算法实现过程中出现的路段冲突，提出了同步法和异步法两种解决方案。原型系统试验显示上述算法有效可行。 （3）最短路径算法效率是战时辅助军事决策、应急救援等系统普遍关注和迫切需要解决的问题。论文针对项目地理信息系统平台中路网道路分布不均、道路不规则等特点，提出了两种最短路径的改进算法：比值系数τ分段取值的矩形限制搜索区域算法和带启发因子的直线优化A*算法。上述两种改进算法稳定性好，且在路段搜索范围、算法的速度、资源消耗等方面较经典Dijkstra算法有较大改善。 （4）针对多弧权网络最优路径问题，提出了多约束最优路径问题的MCOP算法；将启发式思想引入多约束最优路径问题的研究，提出了多约束最优路径问题的A*_MCOP算法。实例验证了上述算法的正确性以及A*_MCOP算法的优越性。 （5）系统研究了FIFO网络、非FIFO网络最短时间路径的算法理论并给出相应的证明。所提出的非FIFO网络最短路径理论为解决非FIFO网络最短时间路径问题提供了新的途径。文中还对各种等待约束情况下的“前向”、“反向”最短时间路径算法进行了设计和总结。 对于最优路径算法研究这一具有很强应用背景的课题，本文从军工科研项目需求出发，通过对已有算法的总结及现存问题的分析，提出了一系列新的算法思想与算法理论。实际系统运行结果及算法实例表明文中所提出的最优路径算法的正确性和有效性。5.期刊论文

史美萍.吴军.李焱.贺汉根.SHI Han-gen

面向月球车路径规划的多约束环境建模方法

-国防科技大学学报2006,28(5) 面向月球车路径规划,从建立合理、鲁棒的月面环境模型的需求出发,提出了一种新的多约束环境建模方法--MCWM方法,它综合考虑了月面地形的可通行性、系统的不确定性、人机协同性和运动的平稳性等四个因素,最后产生了一个能支持路径规划的综合代价地图--MCWM模型.仿真结果表明,MCWM方法合理、有效,可提高所规划路径的安全性和可执行性.6.学位论文

张雷

机器人路径规划及编队问题的研究与仿真

2007 机器人技术的发展彰显一个国家科技水平的高低。在机器人关键技术的发展过程中，提高个体机器人的智能程度和群体机器人之间的协调与协作成为研究的热点。因此，涉及机器人自主规划、多机器人协作的路径规划问题与编队问题成为机器人研究的重要课题，无论是工业机器人还是移动机器人的设计都与此息息相关。对提高机器人的智能化水平及加快机器人的实用化进程具有重要的理论研究意义和实用价值。 论文分析机器人路径规划所要解决的基本问题与相关技术，由于机器人路径规划具有复杂性、随机性、多约束、多目标等复杂系统的特点，在现有的研究基础上，本文提出面向机器人的全局规划思路，设计单个机器人路径规划方法，将机器人所处的客观环境知识与遗传算法融合，改变了原有的编码、种群初始化方法，设计新的进化操作算子。通过仿真验证了算法的可行性，同时对于算法的参数影响进行了分析和研究。 在此基础上，论文进一步分析多机器人的路径规划特点，引入协同进化概念，设计一种新的基于共生机制的遗传算法。该方法依据协同进化论的理论，充分发挥遗传算法的本质并行性，通过种群划分和信息交换的协作，实现了多机器人的全局路径规划。 关于机器人编队问题，论文从队形形成和队形控制两个层次分析问题，设计并实现了一种多机器人在执行协作任务时的协调控制方法。采用基于Leader的队形控制方法与队形动态调整相结合的策略，增强多机器人队列处理突发事件的能力，同时结合机器人角色转换方法，使得机器人协作任务得以更好地完成。 本文分析了智能机器人仿真系统的功能结构，设计用户交互界面和功能模块，开发用于路径规划、编队问题研究的机器人仿真软件，并对本文中提出的路径规划中的算法和队列控制算法进行了仿真验证。7.学位论文

胡松

5自由度移动机器人的建模与仿真

2009 机器人在21世纪生产、生活中的作用日益重大。移动机械手是由移动平台和固定在其上的多自由度机械手构成的。其工作空间和活动范围可以说是不受约束的。但是，由于具有强耦合性、高冗余度和非完整性的存在，使得移动机器人在运动过程中的控制变的非常困难。本文在参考前人研究成果的基础上，对5自由度移动机器人的运动学和动力学方面做了比较系统的、全面的分析。这在工业实用领域中有很多实际意义。 本文所做工作主要有以下几点： 第一，首先介绍机械手臂的相关数学概念，然后根据给定的DH参数表建立5自由度机械手的模型，并研究了各关节速度。在此基础上，建立手臂运动学模型，同时也建立了平台的数学模型。 第二，分析了移动机械手的连续路径规划问题。机器人路径规划具有复杂性、多约束等复杂系统的特点，在现有的研究基础上，利用微分几何学，将运动的插值法扩展到笛卡尔空间，产生其与关节空间的光滑运动。在给定术端执行器两端的位姿后，此法可实现手臂的平滑运动。在接下来的计算机仿真中证明了运动的稳定性。 第三，利用牛顿-欧拉法推导了机械手的动力学模型以及平台的动力学模型，并利用力矩平衡方程建立统一的动力学模型。最后根据所得结论，为移动机器人设计了动力学跟踪控制器，使其能按期望轨迹运动。随后利用matlab对控制器的效果做了仿真，证明控制器的可行性。8.期刊论文

郭颖辉.朱华勇.沈林成

基于遗传算法的飞行航路规划

-计算机仿真2004,21(2) 飞行航路规划是一个大范围多目标多约束的三维规划问题.遗传算法是一种求解复杂问题的通用方法,该文在遗传算法中加入了飞行航路规划的相关知识来求解问题.首先,根据飞行航路规划中导航点属性复杂的特点,扩充导航点的模型,并在此基础上采用导航点链表形式的自由编码.第二,为加速规划的进程,同时保证充分的随机性和广泛性,初始群体构造采用端点启发初始化方法.第三,适应度函数由惩罚函数和代价函数组合计算,其中惩罚函数对应问题的约束条件,而代价函数对应问题的目标.第四,采用启发式交叉和启发式变异.最后,通过剖面优化操作实现高度维上的调整.仿真结果证明这是适于所研究问题的有效方法.9.学位论文

卢文长

多目标多约束条件最优机动路径规划技术研究

2002 多目标多约束条件最优机动路径规划系统是根据集团军(师)炮兵作战指挥系统的需求开发的.该系统的功能是,在交通网络中根据单(多)个路径规划目标及单(多)个路径规划约束条件,在路径规划起始点与路径规划终止点间规划出一条最优路径.另外,该论文在介绍多目标多约束条件最优机动路径规划系统的基本组成、功能的基础之上,详细地阐述及研究了为实现该系统所采用的路径规划算法、路段分割算法、路段拓扑生成算法、以及表达式的生成、编译及计算,并以军事地理信息系统(MGIS)为辅助工具研究了路径规划系统交互平台技术.10.学位论文

高金凤

多目标多约束条件最优机动路径规划技术研究

2003 该论文介绍了动态路径规划系统的组成、功能、实现过程、路径规划算法以及相关网络拓扑结构生成算法,对军用地理信息系统(MG1S)和态势系统(MGS)的功能和其功能的再利用进行了详细地研究.并以MGIS和MGS为辅助工具,在路径规划系统中实现了地图的分层显示、地图的编辑、地图要素的查找、地图分析和地理信息管理的功能.在介绍多目标多约束条件最优机动路径规划系统的基本组成、功能的基础之上,详细地阐述及研究了为实现该系统所采用的路径规划算法、路段拓扑生成算法、以及图幅拼接算法.

本文链接：/Periodical_授权使用：东北大学(dbdx)，授权号：58b67b8a-f5f8-4f00-ade0-9dfc016313fd下载时间：2010年9月25日