GIS路径优化算法（共7篇）
GIS路径优化算法 篇1
1 应急疏散路径优化模型
本文结合GIS和多目标进化算法, 提出应急疏散路径优化三步法模型来求解疏散路径最优方案, 如下图1所示。
1.1 安全避难区域选址
在Arcgis软件中矢量化合适的场地作为安全避难区域, 建立安全避难区域地理信息数据库, 包括:地理位置、面积、可容纳人数等。
1.2 待疏散区到安全避难区域的最优路径
将待疏散区数据、安全避难区域数据和道路网络数据导入Arcgis软件, 求解出每个待疏散区到指定安全避难区域的最优路线和最优路线的长度。
2 应急疏散路径优化
2.1 构建空间多目标优化模型 (Spatial MOP)
建立的应急疏散路径多目标优化数学模型如下所示:
其中, U表示过载能力最小化, V表示总疏散时间最短, Cj为第j个安全避难区域的容量, 和分别表示第i个待疏散区到第j个安全避难区域的最短距离dij和Pij人数。
2.2 多目标进化算法求解MOP
采用NSGA-Ⅱ算法来求解应急疏散路径多目标优化数学模型。算法流程如图2所示。
2.3 最优化方案:pareto前沿
pareto前沿上的A、B、C三点都是最优解, 他们之间不存在支配关系 (占优关系) 。例如B点的支配域为以B点为两条射线顶点的范围, B点的解比支配域范围内E、F和G点的解更优。所以, 实线pareto前沿上的点都为最优解, 如图3。
3 结论
(1) 构建了应急疏散路径优化三步法模型, 该模型同时满足过载能力最小化和总疏散时间最短两个决策目标, 提高了应急疏散路径规划的准确性。
(2) 将NSGA-Ⅱ多目标进化算法与GIS技术有效结合, 求解应急疏散路径空间多目标优化问题。
(3) 由于以pareto前沿形式来表示一组应急疏散路径优化方案的方法是首次提出, 因此如何从pareto前沿中再次选择最优化方案还有待进一步研究。
摘要：针对现有应急疏散路径规划较少考虑多个决策目标和可视化能力不足的问题, 提出一种将GIS (地理信息系统) 技术和多目标进化算法结合的模型, 建立可以优化应急疏散路径的方案。建立空间多目标优化模型, 并用NSGA-Ⅱ多目标进化算法来求解, 得出一组疏散路径最优方案。结果表明:该模型在进行应急疏散路径规划上具有可行性, 并且有很好的可视化效果, 其疏散路径优化结果可直接为决策者制定疏散方案提供参考。
关键词：GIS,多目标进化算法,应急疏散,疏散路径
参考文献
[1]何健飞, 刘晓.基于拥挤度的地铁应急疏散路径优化方法[J].中国安全科学学报, 2013, 23 (2) :166-171.
[2]刘少丽, 陆玉麒, 顾小平等.城市应急避难场所空间布局合理性研究[J].城市发展研究, 2012, 19 (3) :113-117, 120.
[3]伍丽, 唐羚姿, 饶智杰.重庆市荣昌县应急管理问题及对策研究[J].现代商贸工业, 2015, (20) :206.
[4]刘楠楠.基于进化算法的多目标优化算法及应用研究[D]:南京:南京航空航天大学, 2010.
GIS路径优化算法 篇2
KSP问题是一个非常复杂的问题，而且根据不同的应用场景以及具体需求要采用完全不同的算法来解决[1]。目前虽然存在多种KSP算法，但没有一种算法能够普遍适用于常规多条路径规划的问题，而且每种KSP算法都倾向于问题的某些方面对问题进行解决[2]。
1 K优路径规划算法及其扩展
KSP问题是一个非常复杂的问题，根据不同的应用场景以及具体的需求，KSP问题需要相应的解决办法。现有的各种算法并不能很好地解决本文所面对的在大规模数据下寻找多条满足一定差异性路径的问题。因此，提出了大规模数据下满足重复度要求的K优路径规划算法（KPLR)[3]。
KPLR算法可有效解决在大规模数据下多条差异路径规划的问题。KPLR算法引入了有利度的概念，它是一种简单的启发信息，是图中每条边的附加属性，促使算法在每次循环中搜索有别于上次结果的其他路径[4]。同时，KPLR算法引入了重复度的概念，它的使用保证了结果集的质量。由于使用的启发信息较为简单，算法得到的路径结果牺牲了一定的精度，但大大提高了效率。考虑到在大规模数据下进行路径规划的需求以及用户注重路径之间差异的特点，这样的做法是较为合理的。由于需要解决的是实际中的问题，因此暂不考虑负边值所带来的问题[5]。
1.1 KPLR算法
使用path＿current表示当前分析路径，path＿current＿vertex表示其顶点序列；path＿current＿edge表示其边序列；path＿result表示已经得到的可用路径结果集合；函数Repetition(path＿current,path＿result）计算当前路径与路径结果集合中每条路径的重复度是否满足重复度限制系数θ；Kth表示需要找到的路径数量；Count表示在给定某θ值时算法可以进行的循环次数上限；Δθ表示当需要放宽重复度限制时的递增步长。KPLR算法如下：
(1)int k=0（用整数k记录已经得到的路径数目）；int c=0（用整数c记录在当前θ值下算法已循环的次数）；path＿result=∅。
(2）若k>Kth或者θ1，算法退出，否则转步骤（3）。
(3）若c>Count，置c=0；对所有ei∈E，重置ei.u=1；同时θ=θ+Δθ，即放宽重复度的限制。
(4)path＿current=Dijkstra(G,s,e);c=c+1。
(5）按顺序遍历path＿current＿edge中所有的边ei，降低其有利度，使ei.u=ei.uα。
(6）若Repetition(path＿current,path＿result）为真，即对任意path∈path＿result,Repetition(path,path＿current）<θ，则当前路径满足重复度要求，path＿result=path＿result∪{path＿current}，同时k=k+1，转步骤（2）；若Repetition(path＿current,path＿result）为假，无操作，直接转步骤（2）。
在步骤（5）中，对当前路径path＿current中所有边降低其有利度，这样就改变了当前图G，并降低了path＿current在下次循环中的有利度，促使Dijkstra在新图G′’中寻找有别于它的最短路径。
在具体的实现过程中，可以通过有利度惩罚因子α以及重复度限制系数θ对算法进行一定的控制。
1.2 扩展的多点规划KPLR算法
在实际应用场景中的路径规划往往不仅限于两点之间，经常会有在多点之间规划路线的需求，而上述KPLR算法无法满足这种需求，因此需要将其扩展，以便满足这种需求[6]。
扩展的KPLR算法（EKPLR）可用于进行多点之间的K优路径规划。在实际应用中的多点规划除起始点和终止点外，还有必经点、禁止点以及危险区域等[7]。
用ViaNode表示必经点序列，ForbiddenNode表示禁止点集合，DangerousArea表示危险区域集合，vi∈ForbiddenNode表示点vi为禁止点，vi∈DangerousArea表示点vi在危险区域中。使用Edge(vi）表示以点vi为某一端点的所有边的集合。使用ForbiddenEdge表示某一禁止点或位于危险区域中的点vi为某一端点的所有边的集合。其他符号同上文描述。带必经点、禁止点和危险区域的KPLR算法如下：
(1）对任意vi∈V，若vi∈ForbiddenNode或vi∈DangerousArea，则对所有ei∈Edge(vi），做ei.u=1∞，使其任意小，同时将ei加入ForbiddenEdge。
(2）将起点s加入ViaNode开头，终点e加入ViaNode末尾。
(3)int k=0（用整数k记录已经得到的路径数目）；int c=0（用整数c记录在当前θ值下算法已循环的次数）；path＿result=∅。
(4）若k>Kth或者θ≥1，算法退出，否则转步骤（5）。
(5）若c>Count，置c=0；对所有ei∈E且ei∈ForbiddenEdge，重置ei.u=1；同时θ=θ+Δθ，即放宽重复度的限制。
(6）对每两个相邻必经点vi和vi+1，其中i=0,1，…，|ViaNode|-2,pathi=Dijkstra(G,vi,vi+1）。
(7)path＿current=∑pathi;c=c+1。
(8）按顺序遍历path＿current＿edge中所有的边ei，降低其有利度，使ei.u=ei.uα。
(9）若Repetition(path＿current,path＿result）为真，即对任意path∈path＿result,Repetition(path,path＿current）<θ，则当前路径满足重复度要求，path＿result=path＿result+path＿current，同时k=k+1，转步骤（4）；若Repetition(path＿current,path＿result）为假，无操作，直接转步骤（4）。
在步骤（1）中，首先对禁止点和危险区域进行处理，对所有禁止点以及在危险区域中的点，将其所属的所有边的有利度降低为任意小，从而其权值为任意大，也即标记为该边不可行。
在步骤（2）中，将起点和终点作为必经点加入ViaNode可以简化程序代码，同时仍保持程序的正确性。
在步骤（6）中，首先求出每两个相邻必经点之间的最短路径段，然后在步骤（7）中将这些路径段依次连接，从而得到最终的当前路径path＿current。
2 野外区域路径规划
2.1 问题概述
野外区域是指没有路网覆盖的区域，由于野外区域并没有路网覆盖，而常规的路径规划算法是在从路网抽象而成的图中利用点和线的关系进行搜索的，因此常规算法无法直接应用于野外区域的路径规划，在野外区域中进行路径规划之前，需要根据所采用的算法对野外区域进行一定的预处理[8]。
2.2 多路径野外规划
在对野外区域进行网格化处理后，便可采取相应的KSP算法对多路径的野外区域规划问题进行求解。在选用相应的算法时，结合野外区域的特点，要重点考虑网格的密度和路径的重复程度。
提出的KPLR算法较适用于求解该问题，但需要结合野外区域的上述几个特点对KPLR算法进行如下改进：
(1）在算法的每次循环后，不仅仅是对本次循环所得临时路径进行有利度的衰减，而是将衰减范围扩展到包括图中所有以临时路径中的节点为某一端点的所有边。
(2）在计算路径之间的重复程度时，也将被对比的路径扩展为包括其上各节点的所有相邻8个节点，即将重复度的计算改为如下公式：
设path1和path2为两条野外路径，设Vertex(path1）为path1中所有节点与其中每个节点的所有8个相邻节点组成的集合，则path2相对于path1的路径重复度为path2与集合Vertex(path1）中相同节点的数目占path2中所有边数的比重，记为YeWaiRepetition(path1,path2):
YewaiRepetition(pathi,pathj）=|SameVertex(Vertex(pathi),pathj）||pathj|
其中|pathj|表示路径pathj中节点的数目；集合SameEdge(Vertex(pathi),pathj）={ei|ei∈Vertex(pathi）∧ei∈pathj}，|SameEdge(Vertex(pathi),pathj）|表示该集合中元素的个数。
采用上述两种改进是为尽可能防止算法所得各结果路径出现如图1所示的情况，即各路径虽不相同，但其均通过相同的一片区域，并无实际意义。
将结合野外区域的特点进行上述改进后的KPLR算法称作WKPLR算法。因此，野外区域中的多路径规划问题的解决步骤大体如下：首先，根据选择的所有必经点（包含起始点和终止点）划定一个矩形框，将该矩形框作为搜索范围；其次，将该矩形框按步长或按数量划分为网格，并将该划分好的网格拓扑为一张图；最后，在该图中应用WKPLR算法进行路径规划。
野外区域规划WKPLR算法在对野外区域进行上述预处理之后，就可以应用WKPLR算法在处理得到的图中进行路径规划。使用path＿current表示当前分析路径，path＿current＿vertex表示其顶点序列；path＿current＿edge表示其边序列；path＿result表示已经得到的可用路径结果集合；函数YewaiRepetition(path＿current,path＿result）计算当前路径与路径结果集合中每条路径的重复度是否满足重复度限制系数θ；Kth表示需要找到的路径数量；Count表示在给定某θ值时算法可以进行的循环次数上限；Δθ表示当需要放宽重复度限制时的递增步长。野外区域WKPLR算法如下：
(1)int k=0（用整数k记录已经得到的路径数目）；int c=0（用整数c记录在当前θ值下算法已循环的次数）；path＿result=∅。
(2）若k>Kth或者θ≥1，算法退出，否则转步骤（3）。
(3）若c>Count，置c=0；对所有ei∈E，重置ei.u=1；同时θ=θ+Δθ，即放宽重复度的限制。
(4)path＿current=Dijkstra(G,s,e);c=c+1。
(5）按顺序遍历path＿current＿edge中所有的节点vi，降低以vi为某一端点的所有边eii的有利度，即做eii.u=eii.u/α。
(6）若YewaiRepetition(path＿current,path＿result）为真，即对任意path∈path＿result,YewaiRepetition(path,path＿current）<θ，则当前路径满足重复度要求，path＿result=path＿result∪{path＿current}，同时k=k+1，转步骤（2）；若YewaiRepetition(Path＿current,path＿result）为假，无操作，直接转步骤（2）。
上述WKPLR算法与KPLR算法基本相同，区别在于降低有利度的边的范围有所扩展，以及计算重复度时有所改变。
3 实现设计及分析
基于GIS系统，以Microsoft VC++6.0为软件开发平台，实现了基于某地域道路信息网及野外区域的多条差异路径选取功能。
3.1 KPLR对比实验
将该算法与候选消除边算法（下称对比算法）进行对比实验，其为各前K条最短路径算法中最精确的算法。对比算法所得数据作为参考来说明本文算法在上述特定需求下的有效性。其中，以前5条路径为例，且本文算法各系数设置为：θ=0.5，Δθ=0.1，α=1.1。
采用1∶50 000比例尺地图，选取的起讫点直线距离约为200 km，采用Dijkstra算法找到的最短路径长度均为229.70 km。经过对地图数据处理后得到的图包含201 070条边，145 029个节点。图2为本文算法得到的5条差异路径，图3为对比算法得到的前5条最短路径。表1为两种算法得到的路径之间的重复度系数。表2为两种算法得到的路径长度信息（单位：km）以及算法运行时间（单位：ms）。
实验中数据量大幅增加，由103级增长为105级。此时，本文算法所得路径之间重复度最大值为0.286，小于重复度初始阈值0.5，对比算法重复度均在0.97以上。运行时间方面，本文算法约为13 s，考虑到数据量之大，在实际应用中，这是较为合理的时间；对比算法耗时约为85 min，仅作参考。
在路径长度方面，两种算法得到的路径1长度相同，本文算法得到的剩余4条路径长度值也较为合理，其中路径5与对比算法差值最大为13.43 km，占总长度比重不到10%。
本次实验较好地体现了在大量数据下本文算法的有效性。在运行时间上，本文算法有着绝对的优势，同时13 s的运行时间在实际应用中也是较合理的时间。在大幅度提升效率的同时，本文算法并未损失太多精度，同时考虑到对差异度的要求本身就是对一部分精度的放弃，因此本文算法较好地满足了大量数据、一定重复度要求以及合理的运行时间的综合需求。
3.2 WKPLR对比实验
下面进行野外区域中多条差异路径规划的对比实验，对比算法为针对野外区域进行改进的WKPLR算法与双向搜索算法。实验以前3条路径为例，且WKPLR算法各系数设置为：θ=0.5，Δθ=0.1，α=1.1。
采用1∶250 000比例尺地图，选取的起讫点直线距离约为13 km。由于起讫点距离长度较为合适，因此实现中网格划分采用按步长的方式，以保证路径结果的精确程度。在具体实现中，步长设置为200 m。图4为WKPLR算法所得的3条差异路径，图5为对比算法所得的3条差异路径。表3为两种算法得到的路径之间重复度系数。
由图4，图5可以看到WKPLR算法和对比算法在野外区域中规划所得路径的直观效果。对比算法所得3条路径全部通过同一条带状区域，且3条路线交织在一起，这样的3条路线在实际应用中其实可看做是同一条路线，并无太多实际应用价值。而针对野外区域改进后的WKPLR算法所得3条路径能够找到规划区域中的3个差别较大的带状区域，从直观效果来看，3条路线之间的差异度较大，效果也较好。
表3的数据也证实了这种差异性。由于在计算野外区域中路线的重复度时采用了改进的带状区域重复度计算方式，不仅计算路线上的点，而且包括这些点的所有相邻节点，也即被对比的点集合为路线所经过的一条带状区域，因此对比算法的3条路径之间差异度均在0.98以上，虽然它们经过的点有一定的区别，但这些点均在同一带状区域中。而改进的KPLR算法所得重复度均在0.5以下。因此，实验数据也进一步证实了WKPLR算法在野外区域中进行多条差异路径规划的有效性。
4 结论
KSP问题是路径规划领域中的重点问题之一，也是近些年研究的热点问题。KSP应用场景非常广泛，它是GIS中的重点研究内容，同时也应用到路由选择、图像分割以及语音识别等领域。KSP问题是一个非常复杂的问题，针对不同的应用场景及需求往往需要不同的解决办法。
本文从实际应用的角度，结合大规模数据以及路径差异度的需求提出了KPLR算法及其野外区域版本WK PLR，其中KPLR算法是解决大规模数据下进行多条差异路径规划问题的有效算法，同时，WKPLR算法结合野外区域的特点对KPLR算法进行改进，可有效解决野外区域中的多条差异路径规划问题，具有实际的应用价值。
参考文献
[1]牛振东,师雪霖,叶成林.数字图书馆支撑技术领域标准规范的现状和发展[J].我国数字图书馆标准规范建设,2003(7):11-12.
[2]蔡俊,李钦富,王金泉.一种Dijkstra优化算法的研究与实现[J].信息技术,2011,35(4):104-107.
[3]王开义,赵春江,胥桂仙,等.GIS领域最短路径搜索问题的一种高效实现[J].中国图象图形学报,2003,8(8):951-956.
[4]高松,陆峰.K则最短路径算法效率与精度评估[J].中国图象图形学报,2009,14(8):1677-1683.
[5]柴登峰,张登荣.前N条最短路径问题的算法及应用[J].浙江大学学报,2002,36(5):531-534.
[6]袁红涛,朱美正.K优路径的一种求解算法与实现[J].计算机工程与应用,2004,40(6):51-53.
[7]马炫,刘庆.求解K条最短路径问题的混合蛙跳算法[J].信息与控制,2011,40(5):614-618.
GIS路径优化算法 篇3
通过研究,基于适当的处理的城市道路数据,我们可以开发一个原型模型,在城市各个道路之间,我们确定它们之间的具体位置,这样我们就提出了一个优化的问题,我们采用遗传算法进行结算,遗传算法(Genetic Algorithm)[1]是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
文章采用了基于GIS遗传算法道路网数据采集优化模型,首先从数据的采集开始,运用一定的条件及技术形成符合规划条件的数字测量成果。把外业计算与内业计算、原始规划条件数据与成果数据,放在一起进行研究与讨论。
1 GIS主要功能和特点
地理信息信息(GIS)的基本功能是数据的采集、管理、处理、分析和输出。GIS依托这些基本功能,通过利用空间分析技术、网络技术、模型分析技术、数据库和数据集成技术、二次开发环境等产,演绎出应用功能。应用于各个领域以满足社会和用户的广泛需求。
1)数据采集与编辑:数据采集与编辑功能就是保证各层实体的地物要素按顺序转化为x、y坐标。数据输入的方式多样,主要有通过数字化仪将地图数字化、遥感数据扫描、文字数据的键盘输入或其它形式数字化数据的转换等等。
2)数据存储与管理:GIS数据库与普通数据库不同,它数据量大,空间数据与属性数据相互联系,空间数据之间有拓扑结构。所以GIS数据库管理功能除了与属性数据有关功能之外,对空间数据的管理技术主要包括:从属性条件检索空间物体及其位置、数据更新和维护、空间数据库的定义、从空间位置检索空间物体及其属性、开窗和接边操作等。
3)空间分析和统计:空间分析和统计功能是GIS的一个独立研究领域,它的主要特点是帮助确定地理要素之间新的空间关系,它已经不仅成为区别于其他类型系统的一个重要标志,而且为用户提供了灵活地解决各类专门问题的有效工具。
4)二次开发和编程:为使GIS技术广泛应用于各个领域,满足各种不同的应用需求,它必须具备的另一个重要基本功能是二次开发环境,包括提供专用语言的开发环境、用户可在自己的编程环境中调用GIS的命令和函数,或者系统将某些功能做成专门的控件供用户的开发语言调用等。这样用户可以非常方便地编制自己的菜单和程序,生成可视化的用户应用界面,完成GIS的各项应用功能的开发。
2 数据处理
城市区域规划是一个决策和控制过程,这个过程不仅要研究空间,资源配置等物质实体,还要研究其间的相互作用、影响因素和信息流通,同时做出一系列决策。信息获取和处理在整个研究和决策过程至关重要,如图1所示,规划体系包括规划立法,规划编制和规划管理等几个部分,规划信息系统在整个规划体系中处于极其重要的地位,是规划编制、规划立法与规划管理的基础与纽带。GIS在城市和区域规划研究中的应用,在很大程度上并将在更大程度上改变规划领域传统的空间信息获取和处理的方法。
GIS用于总体规划及土地利用功能区划中,工作质量和效率明显优于传统手工操作方法。我国城市规划界从20世纪80年代中期开始探索计算机处理地理空间信息的技术,十几年来,经历了许多曲折,GIS终于在城市规划中积累了不少成果。例如规划人员利用GIS对交通流量、土地利用和人口数据进行分析,预测将来的道路等级;工程人员利用GIS将地质、水文和人文数据结合起来,进行路线和构造设计;GIS软件帮助政府部门完成总体规划、分区,现有土地利用、分区一致性,空地、开发区和设施位置等分析工作。对于注重政策引导“重文轻图”的区域规划,GIS同样可以在数据管理、数据分析、辅助决策和规划成果表达等方面发挥其高速度、空间信息与属性信息紧密结合的优势,成为新形势下区域规划的强有力工具。
区域规划是建立在对区域自然地理环境、人文社会经济发展状况等诸多要素全面了解的基础之上,相关数据的获取和有效管理是区域规划研究的前提和必要保障。在进行区域规划研究时,面对形式多样(文字、图表、地图、影像)、比例尺不等、性质不同(规划行业原有的数据多为CAD格式)的资料,通过适当的处理和转换,GIS可以有效地获取(输入)、存储、更新、显示各种相关数据,把空间信息和属性信息关联起来,对数据进行有效的管理,并能以极快的速度,以用户所需的形式提供精确的信息,满足区域规划研究的需要。准确、实时、适当精度的数据是用GIS进行区域规划研究的基础,在用GIS进行区域规划时,要从项目立项就考虑GIS对数据的精度和形式要有明确的要求。并进行修改调整根据实际情况,来满足GIS对空间分析和辅助决策的需要。数据库要进行经常性维护和更新来保证数据的有效实时性。为规划实施过程中的适当调整和下一轮规划做好数据准备文件输出包括如图2所示文件及WORD文件(道路名称,道路坐标)。成果正确后可以打印输出并存储数据。
3 遗传算法城市规划道路数据的设计
遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍.作为一种搜索算法,遗传算法通过对这些操作的适当设计和运行,可以实现兼顾全局搜索和局部搜索的所谓均衡搜索,具体实现见图3所示。
应该指出的是,遗传算法虽然可以实现均衡的搜索,并且在许多复杂问题的求解中往往能得到满意的结果,但是该算法的全局优化收敛性的理论分析尚待解决.目前普遍认为,标准遗传算法并不保证全局最优收敛.但是,在一定的约束条件下,遗传算法可以实现这一点。将城市道路分为空间数据库和属性数据库。空间数据库是将规划道路的空间位置分为点、线两种空间实体,点表示道路红线的桩点,即每一条道路的拐角点或交叉点。线表示道路,而道路又可分为道路中线、道路边线,它们用来精确表示规划道路的坐标和空间位置。
规划成果的可视化输出是最成熟、最普及的GIS功能模块。GIS除能像其他辅助设计系统一样,便利地绘制各种不同比例尺的常规规划图件外,更以其数字地图(电子地图)功能为区域规划成果提供卓有成效的表述手段,通过与属性数据库、多媒体信息连接,数字地图能够交互、高效、无缝、无级缩放地对区域各种信息进行显示、查询,根据需要增减不同的图层,并对区域特征进行计算、统计和分析,使规划部门的日常规划管理工作变得十分方便,还可利用其三维GIS技术和虚拟现实GIS技术,并与多媒体技术结合静态或动态地模拟区域的现状和发展景观。
4 结束语
利用GIS技术建立起城市规划道路数据库,就能够为城市规划管理部门的规划辅助设计、辅助决策、辅助审批提供规范、精确的根据。
参考文献
[1]Zhang Fei-zhou,Yang Dong-kai,Chen Xiu-wan.Intelligent scheduling of public traffic vehicles based on hybrid genetic algorithm[J].In-telligent Transportation Systems,2003(2):1674-1678.
[2]郭晓敏,邢汉承,冉明.基于GPS和DR的公路数据采集GIS系统[J].计算机仿真,2005(2).
[3]袁国斌,周顺平,李四维.GIS在城市规划行业中的应用研究[J].中国地质大学学报,1998,23(4):408-411.
[4]罗大宁,郭薇.电信GIS的分级寻道式通道选择算法设计[J],计算机工程与应用,2003(17).
[5]曾志明,朱江,张立立,等.设计模式在可复用GIS软件开发中的应用[J].计算机工程,2006(4).
GIS路径优化算法 篇4
关键词：农村电网,选址定容,地理信息系统,变电站增容,变电站规划
0 引言
在配网规划的以往研究中, 根据规划时对负荷和配电网的处理方法的不同, 将配网规划模型分为4类[1], 即单阶段子系统、单阶段全系统、多阶段子系统和多阶段全系统。各种规划模型多以变电站、线路投资费和运行费构成的年运行费, 或者只计及部分年费用 (如网络损耗和馈线总投资) 作为目标函数。早期的变电站选址规划研究中提供备选新建站位置供规划人员选择;近年来则侧重于在连续单或多场址选择模型[2]的基础上建立规划模型, 直接用算法对新建站位置进行搜索, 无需提供备选信息, 从而减少了输入数据。智能算法也被广泛应用在变电站规划领域, 如混合遗传算法 (LA-GA) [3]、粒子群优化算法 (PSO) [4]和微分进化算法 (DE) [5]等。
使用变电站规划的全系统最小年费用模型[3,6]和文献[3]提出的混合遗传算法, 较好地解决了负荷密度较大地区的城网规划问题, 但要将混合遗传算法应用到农村电网 (以下简称农网) 变电站选址定容中来, 仍存在两方面的问题:一方面, 与城市电网相比, 农村的电网的负荷密度较小, 但分布区间较大, 从数十到数百千瓦每平方千米不等, 供电半径约束是不确定的, 所以文献[3]的城市电网变电站选址定容模型要具体应用到农村电网尚需要继续研究;另一方面, 在文献[3]的算法中, 在新建站选址定容的同时没有给出已有站的增容方案。
本文对该数学模型的供电半径约束、算法的适应度函数及其染色体编码环节进行了改进, 并通过控制染色体中已有变电站基因不参与算法部分环节的方式计及了已有站的增容问题, 较好地解决了农村电网中变电站规划问题。
1 农网变电站规划的数学模型
通过负荷预测和空间负荷预测[7], 明确规划水平年的负荷大小和空间分布情况。由于农村电网的负荷比较分散, 可以以村或乡镇为小区将负荷等效为集中负荷来处理。变电站优化规划的模型为
变电站容量约束条件为
供电半径约束条件为
辐射运行约束条件为
式中 CZ (Si) —第i个新建变电站的投资费用 (万元) ;
CU (Si) —第i个新建变电站的年运行费用 (万元) ;
m—变电站的折旧年限 (a) ;
n—新建变电站个数;
k—变电站低压侧线路折旧年限 (a) ;
r0—名义利率;
N—变电站个数之和 (包括规划水平年的新建站和已有站) ;
C′Z (Si) —第i个已有变电站的投资费用 (万元) ;
C′U (Si) —第i个已有变电站的年运行费用 (万元) ;
rmin (Si) —变电站的最小容载比;
rt—最大负荷的同时率;
cosφ—变电站的功率因数;
lij—变电站i与负荷点j之间线路的长度 (km) ;
ρ—划分出的变电站供电区域的实际最大供电半径所对应圆形区域内的负荷密度 (k W/km2) ;
Rimax (ρ) —变电站供电区域内的负荷密度所对应的最大合理供电半径[8] (km) ;
Ji—第i个变电站所供负荷的集合;
J—全体负荷点的集合。
该模型的特点在于:对约束条件中的最大供电半径进行了基于负荷密度的动态映射, 适用于负荷密度较小, 但分布区间较大的农网规划。
2 改进混合遗传算法
2.1 染色体编码及其初始种群的生成
染色体编码采用实数二维编码, 直接使用变电站的经纬度数值进行编码。染色体编码如图1所示。
图1中, 前n对基因包含了新建站的站址信息, 后N-n对基因包含了已有站的站址信息。
2.2 适应度函数和遗传算子
为了让适应度函数更充分的发挥作用, 使变电站供电半径只要小于或在合理供电半径附近都承认该方案的合理性。利用分段函数设计适应度函数, 通过适应度函数筛选出较好的选址定容方案。
式中 tRPen—罚因子;
C—目标函数取值。
式中 ε—一非常小的正数。
可以看出:一旦当供电半径超出变电站的合理供电半径, 惩罚系数将快速减小到接近为0, 在进化过程中滤除该方案。
遗传算子中选择算子采用轮盘赌算子, 交叉算子采用算术交叉, 即两个方案中新建变电站位置的凸组合, 变异算子采用非均匀变异。
2.3 LA算子和变电站的定容策略
方案个体经过LA算子处理完成分配定位环节, 该环节的作用是以地理距离就近为原则划分供电区域。然后, 使用保留精英策略使已经出现的较好方案在遗传过程中保留下来。
变电站定容的基本原则是:在保证满足负荷和变电站最小容载比技术要求的同时, 提高变电站的负载率, 经济地进行容量配置。改进算法中容量不作为染色体的基因参与编码, 生成一个染色体方案, 即新建变电站的个数和位置确定后, 就可以重新划分各个变电站的供电区域。根据供电区域内负荷的大小和变电站容量约束条件及其标准容量配置, 选择新建变电站的最经济容量。对于已有变电站, 如果供电区域内所带负荷大于已有容量, 说明需要对已有站进行增容。每个方案中, 第i个新建变电站的容量可参照以下公式进行计算。
式中 S (k) —将标准容量配置集合Q中q个标准
配置容量按从小到大顺序排列后, 排在第k位的标准配置容量值, k=2, 3, …, q;
ζ—一很大的正数。
该表达式的物理意义是:如果LA算子划分的新建变电站供电区域中负荷过大或过小, 超过了事先给出的标准容量配置, 说明变电站供电区域划分不够合理, 该方案经济性差, 则将该变电站的造价指定为一非常大的正数, 反映到方案的综合造价[9]中, 适应度函数将对该方案进行惩罚, 在进化过程中从种群里对该方案进行淘汰。
2.4 基于改进混合遗传算法及GIS的变电站规划
求解该变电站选址定容模型算法的实质是要解决供电区域的划分问题。完成供电区域的划分后, 新建变电站的位置、容量和已有变电站的增容容量就可以根据供电区域内负荷分布状况来进行确定。确定新建变电站个数范围[3]后, 基于GIS的改进混合遗传算法的步骤如下。
1) 从GIS图形界面获取已有变电站和负荷点数据, 设置新建变电站的个数为最小值。
2) 初始化种群, 并执行分配运算, 确定增容站和新建站容量, 计算个体适应度。
3) 对染色体执行遗传算法的选择操作。
4) 进行交叉变异操作。软色体中新建变电站基因参与交叉变异操作, 已有变电站基因不参与。
5) 分配操作。对染色体中的所有变电站按物理距离就近原则进行供电区域的划分。
6) 使用定位算子求解变电站的位置。软色体中新建变电站基因参与定位操作, 而已有变电站基因不参与。
7) 保留精英, 将遗传操作前适应度较大的染色体复制到定位操作后的种群中来。
8) 计算个体适应度, 并输出当前进化代数的种群信息。
9) 判断算法是满足中止条件 (即否收敛或达到最大进化代数) 。如果满足, 终止计算;如果不满足, 转向步骤3。
10) 判断新建站的个数是否达到最大个数。如是, 则停止计算, 将年费用最小的规划方案结果在GIS图形界面上输出显示, 并结合地理信息进行人工干预;如否, 则新建变电站个数以1为步长进行递增, 转向步骤2。
3 算例分析
下面给出了一个使用改进混合遗传算法进行农村电网变电站规划研究的应用算例。某县农村地区规划区域面积为300km2, 已有变电站4座, 即10MVA变电站3座, 20 MVA变电站1座。基准年最大负荷为29 759 k W, 负荷预测后得出规划水平年的负荷大小共计52 446k W, 负荷密度为174.82 k W/km2。完成空间负荷预测后, 在GIS图形界面上根据地域连续性用集中负荷点等效描绘出规划水平年的负荷大小和分布情况。在该算例中, 集中负荷点和等效集中负荷点共有68个。
完成计算后的变电站的新建方案如表1所示。由表1可以看出, 随着新建变电站个数的增多, 所有变电站的年费用 (其中包含了需要增容的已有站的年费用) 先减少后增加。线路的年费用逐渐降低, 当新建4个变电站时, 网络的总年费用达到最小值539万元, 所以选择该方案进行水平年的变电站规划。表1所显示的计算结果说明:满足技术指标约束的条件下, 在负荷密度较小的农村地区, 新建小容量变电站比建大容量变电站有更好的经济性。
变电站的标准容量配置 (MVA) :A (2×5) , B (2×10) , C (31.5) , D (40) , E (50) 。
已有变电站的增容方案如表2所示。
由表2可知:新建3个站时对2个已有站进行了增容;而新建4个站时只对1个站进行了增容, 且增容和新建变电站年费用比新建3个站要高些。
表3列出了新建4个变电站时各变电站供电区域的相关信息。由表3可以看出:新建4个变电站时, 各变电站均满足供电半径和容量约束要求。各变电站位置及其供电区域如图2所示。
4 结论
本文把地理信息系统和混合遗传算法应用到农网变电站优化规划问题中来, 并对以往研究中的配电网变电站选址定容模型和混合遗传算法进行了改进。改进后的主要特点和优点如下:
1) 染色体编码计入了已有站的信息, 通过模型和算法的改进, 在计算新建变电站方案的同时考虑了已有站增容;
2) 数学模型考虑了不同大小负荷密度对变电站供电半径的约束影响, 通过设计的适应度函数, 保证了新建变电站的供电半径不超过或处于合理供电半径附近, 适合于负荷较为分散的农村电网变电站规划使用;
3) 使用GIS图形界面提供已有变电站和规划水平年的负荷分布的地理信息数据, 并将规划结果在GIS图形界面上显示出来, 可结合地理信息进行人工干预, 使规划过程更方便直观。
参考文献
[1]方兴, 郭志忠.配电网规划研究述评[J].电力自动化设备, 2003, 23 (5) :71-74.
[2]汤红卫, 王华, 郭喜庆.一种基于地理信息系统的配电网规划方法[J].电网技术, 2002, 26 (12) :81-84.
[3]王成山, 刘涛, 谢莹华.基于混合遗传算法的变电站选址定容[J].电力系统自动化, 2006, 30 (6) :30-34.
[4]刘自发, 张建华.基于改进多组织粒子群体优化算法的配电网络变电站选址定容[J].中国电机工程学报, 2007, 27 (1) :105-111.
[5]牛卫平, 刘自发, 张建华, 等.基于GIS和微分进化算法的变电站选址及定容[J].电力系统自动化, 2007, 31 (18) :82-86.
[6]DAI Hong-wei, Yu Yi-xin, HUANG Chun-hua, et al.Optimal planning of distribution substation locations and sizes-model and algorithm[J].Electrical Power and Energy Sys-tems, 1996, 18 (6) :353-357.
[7]王天华, 范明天, 王平洋, 等.基于地理信息系统平台的配电网空间负荷预测[J].电网技术, 1999, 23 (5) :42-47.
[8]中华人民共和国国家经济贸易委员会.DL/T5118-2000.中华人民共和国电力行业标准-农村电力网规划设计导则[S].北京:中国电力出版社, 2000:12.
基于遗传算法的路径优化问题研究 篇5
物流配送活动不受时间、地域的限制,配送任务复杂又琐碎。作为一种经济活动,配送的成本始终备受企业关注,而影响配送成本的直接因素就是配送路程的长短,因此为了降低运营成本,管理者都在配送策略上寻找出口。
1 路径优化问题描述
配送路径优化本着效率高、成本低、距离短、消耗小等原则。这些原则使得路径选择受多元因素影响,但为了更有效的阐述路径优化方案,该文确定了“路径最短”的单一研究目标。
假设某次的配送活动中,有L个配送车辆、一个物流配送中心和I个配送的终端客户,要求合理安排车辆和配送路线,将货物从配送中心配送到终端客户,并使路径方案最优。
现实生活中的车辆调度和路径选择问题十分复杂,为了方便建模和求解,该文对研究的问题进行了抽象和简化。现对本文研究的物流配送车辆调度问题做如下界定:
货物统一从一个物流配送中心发往多个客户终端;配送中心和终端的位置固定并已知;多个包裹可以混放在一辆车中;同一个客户的配送总量不超过车辆的载重;每个客户的货物不允许分批配送;每台车辆的最大载重量固定,不许超载;每台车辆均从物流中心出发,配送后返回物流中心;客户无到货时间的限制;不考虑交通运输中的汽车流量限制。
2 路径优化问题数学建模
设配送车辆共有L台,每台车的载重为Bl( l =1,2,3…,L),每个终端的配送量为Si (i=1,2,3…,I),I为需配送的终端总数。终端i到终端j的距离记为Rij,nl表示第l辆车要完成的配送任务终端总个数,Tl={ tli| 0≤i≤nl}表示第l辆车要送货的终端集合,其中tli为第l辆车要配送的第i个终端,tl0为第l辆车的始发点。为该车辆配送问题进行数学建模[1]:
公式中的Z得到配送过程中的路径总和。再将配送中的所有约束条件考虑在其中:(1)所有配送点都应配送到;(2)每个车辆配送点数<=总的配送点数;(3)每条路径的配送量不超过车辆载重;(4)每个配送点只安排一辆车进行配送。
得到最优化问题的数学建模为:
3遗传算法
遗传算法的基本思想是从问题可能的多个解开始,通过一定进化原则多次迭代不断产生新的解,随着迭代次数的增加,得到的解越来越接近最优解,该算法是一个“生成+检测”的迭代优化过程。这多个解的集合称为一个种群。一般种群中元素的个数在进化过程中不变,称为群体规模。种群中的每个个体称为染色体。算法的基本流程如下[2]:
编码并生成初始群体:遗传算法必须先通过编码将空间数据表示成遗传空间的基因型数据串。然后随机产生M个不同的染色体构成算法的初始群体,其中每个染色体对应问题的一个初始解。
评估适应度并繁殖:遗传算法在搜索过程中采用适者生存的原理来评估个体,并根据个体的适应度高低进行繁殖操作。在初始种群中将适应度较高的M个个体作为父代繁殖下一代子孙。
杂交:杂交是遗传算中最关键的信息交换操作,分为两步:一是随机抽取群体中个体进行配对,该文中按事先确定的杂交概率Pc在M个个体中随机选择两个个体;二是对配对个体设定随机交叉点,使两者交换部分信息,并产生两个新个体进入下一代。重复这个过程,直到所有需杂交的个体完成杂交过程。
变异:变异是按一定概率随机改变个体的基因链。目的是挖掘个体的多样性,避免算法陷入局部最优解。该过程在M个个体中根据事先确定的变异概率Pm随机选择个体,并按变异策略进行运算。
停止条件:当优化的结果满足判断条件或迭代的次数达到指定要求是运算停止;否则继续重复以上的优化过程,不断产生新一代群体。
在遗传算法的运算过程中,群体规模、交叉概率、变异概率、中止进化代数等因素都会对算法结果和效率有直接影响。
4 路径优化问题的遗传算法设计与实现
4.1 染色体编码
本文中的染色体编码选用实数编码方式。用矢量表示一个染色体个体,如矢量T(t1,t2, ……,tI),ti取[1,I]中的任一个自然数,表示第i个配送点,每个染色T是[1,I]之间I个不重复自然数的随机排列。假设共有9个配送点,预先对每个配送点进行编号1~9,个体T(3,5,7,2,4,6,9,8,1)表示依次按照“配送点3、配送点5、……、配送点1”的顺序完成9个配送点的任务。随机产生一组这样的染色体个体Tm(m=1,2,……M)构成规模为M的初始种群。
4.2可行化分析
将染色体矢量映射为满足约束条件的可行解的过程称为可行化[3]。可行化分析是将实数编码的染色体个体映射为种可行的路径选择方案的过程。基本流程如下[3]:
以上流程中,L记录了需要参与配送的车辆总数,Tl{ l =1,2…,L}记录了第l辆车依次配送的终端,即一组可行的路径。
本文提出的可行化分析完成了从一个矢量编码(染色体)到一种可行路径方案的映射,是用遗传算法实现车辆配送问题的核心设计,算法的主要优势在于搜索过程中动态的决定车辆的使用数目,减少了个体的可行性验证次数。
4.3 适应度评价
在种群中,需要对每个个体进行评价,选择最优解。选择的依据就是个体适应度函数,如将某一代种群中的染色体T(t1,t2, ……,tI)的可行化路径代入目标函数:
可以计算出该个体对应的路径代价。路径代价越小,该个体的适应度越强。设Zh的适应度函数为[4]gh=1/Zh,gh越大对应染色体个体越接近最优解。
4.4 自然选择过程
本文中自然选择的过程,在保证最优个体进入下一代同时,让其他个体根据适应度不同而按概率进入下一代。
基本设计:将一代种群中M个个体按适应度gh由大到小排列,排在前10%的直接进入下一代,而另外M-10%个个体从当前种群M个染色体中生成,生成的过程使用轮转选择法[4],该自然选择过程保证了新一代个体的多样性和算法的收敛速度。
4.5交叉操作
交叉概率Pc决定了交叉操作被使用的频率[5]。交叉概率值较低,容易使算法搜索陷入迟钝的状态,交叉概率值较大虽能扩大遗传算法搜索范围,但高性能的特点也会受到影响。文献[5]表明当交叉概率在Pc=0.6~0.8之间时,进化性能较好,该文仿真实验中选择了选择Pc=0.7。
交叉操作的过程演示:随机选取两个互不相同的个体T1和T2,每个个体含有n个基因。随机产生[1,n]之间的两个不相等的整数s和l(设1≤s < l≤n),以s、l为断点将个体T1和T2各分成三块,先将T1的第三块移到T2的个体首部,再削去T2中相同的基因,得到新个体T'2;另将T2的第一块移到T1的尾部,并削去T1中相同的基因,得到新基因T'1。如下设s=3和l =6:'
交叉操作后,计算个体T1, T2, T'1, T'2的适应度,从中选择适应度较大的两个进入下一代。该方法即使用于两个相同个体,仍然可以进化出不同的两个新个体,避免了局部最优解,克服了“早熟收敛的缺点。
4.6变异操作
变异[5]的主要目的是维持群体中个体的多样性。变异几率小可防止群体中优良基因的丢失,又避免将遗传算法变成随机搜索法。该文中使用变异概率Pm为0.02。
5 路径优化问题的遗传算法仿真实验
根据以上遗传算法的设计,该文使用Java编码实现基于遗传算法的路径优化搜索。系统在实现时保留了用户输入接口,用户可以通过UI界面设置系统参数,如:M(种群大小)、N(遗传搜索的代数)、Pm(变异概率),Pc(交叉概率)等。输入参数后,系统对配送目的及配送重量进行录入处理,并根据预存的节点距离表,进行路径优化搜索,最后得到理想的配送方案。
为了验证以上方案的有效性和搜索效率,该文模拟了有8个需求终端物流运送任务,设车辆的载重为8吨。
已知各配送终端之间的距离和各终端的需求货物量为di (i=1,2,3…..8()单位:吨),参见表1[6],要求合理安排车辆的行驶路线,使得总的路径最短。
参数设置:M=100、N=50、Pc=0.7、Pm=0.02,带入以上数据,得到最优路径方案为:共需要4辆车进行配送,每辆车的配色路径为第一辆车:0→1→4→0;第二辆车:0→2→3→8→0;第三辆车:0→5→7→0;第四辆车:0→6→0;
搜索的效率见表2:
分析数据得出,配送规模在8个需求点的路径优化问题上,本算法的搜索时间基本控制在1000毫秒以内。为了对比算法优越性,该文还实现了禁忌搜索算法的搜索仿真,实验结果证明文中设计的遗传算法在路径优化问题的搜索效率上明显具有优势。
6 结束语
本文分析了遗传算法的原理,并针对路径优化问题进行遗传算法优化设计。该算法的特点是对车辆的数目没有作事先要求,省去了可行性判断过程中的大量搜索浪费。实验数据表明算法的搜索性能相比其他搜索方案具有明显的效率优势。
参考文献
[1]Gendreau M,Hertz A,Laporte G.A tabu Search Heuristics for the Vehicle Routing Problem[J].Management Science,1994,40:1276-1290.
[2]玄光男,程润伟.遗传算法与工程优化/应用数学译丛[M].于歆杰,周根贵,译.北京:清华大学出版社,2004.
[3]Teodorovic D,Pavkovic G.A simulated annealing technique approach to the vehicle routing in the case of stochastic demand[J].Transprotation Planning and Technology,1992,16:16:291-293.
[4]Chang Wook Ahn,Ramakrishna R S.A genetic algorithm for shortest path routing problem and the sizing of populations[J].IEEE Transaction on evolutionary computation,2002,6(6).
[5]陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,2001.
基于混合算法的联合运输路径优化 篇6
近年来, 伴随着“门到门”运输的兴起, 铁路系统对货物运输进行多方位改革, 大力发展全程物流服务。与此同时, 单一运输方式由于其技术经济特点和网络覆盖的限制, 很难满足多方面的运输要求, 这些促进了联合运输的快速发展。
目前, 针对联合运输路径优化方面的研究较少, 这与联合运输的发展趋势不相适应, 势必会对联合运输产生不利影响。笔者在总结与吸收前人研究成果的基础上, 提出将遗传算法、动态规划方法与多重图数据结构结合起来求解联合运输路径优化问题。
1联合运输路径选择模型及数据结构
联合运输路径选择模型及数据结构是解决联合运输路径优化问题的基础。在以往的路径优化研究中, 吴静［１］定义了节点与邻节点数据结构, 并使用遗传算法解决了简单无向图路径优化问题。 温晓磊［２］定义了无向网络数据结构并使用混合算法解决了简单图路径优化问题, 仿真实验表明2种方法效果较好。但联合运输网络属多重图结构, 需对上述数据结构与算法进行改进, 才能应用于联合运输路径优化问题。笔者采用了与文献[1]相似的方法进行处理。
1.1联合运输路径选择模型
联合运输路径优化问题实质上是1个点对点的运输问题。它要解决的是:在已知网络中选择最优的运输路径与运输方式组合, 从而使运输过程达到货运企业的特定目标。在以往研究中通常以运输费用［３－７］或运量与运输时间的组合［８］为目标函数建立模型。在本文中, 将建立以总运输费用最小为目标的联合运输模型。运费只考虑节点间运费与节点发生运输方式转换时所产生的中转费用。该模型如下。
式中:O与D分别为运输起点与终点;Iｉｊ选择的路径是否包括i到j的边, 包含时取值为1, 否则为0; Wｉｊｋ为城市节点i与j之间采用第k种运输方式的运费;Eｉｊｋ为是否选择城市节点i与j之间第k种运输方式, 选择时取值为1, 不选择时取值为0;Cｉｌ为在城市节点i第l种中转方式的中转费用;yｉｋｌ为在城市节点i是否由第k种运输方式转换时为第l种运输方式, 发生转换时取值为1, 否则为0。
模型中目标函数左侧部分为节点间运输费用, 右侧为节点进行运输方式转换时的中转费用;约束条件式 (1) 表示任意2个节点之间只能选择1种运输方式;约束条件式 (2) 表示在任意节点只能进行1次中转。
1.2数据结构定义
数据结构的定义分为2个部分:节点数据结构与邻节点数据结构。简单图由于节点间只有1条边, 其数据仅用单个变量存储, 而联合运输网络由于节点间可供选择的运输方式不止1种, 节点2端所采用的运输方式也未必相同, 因此节点间的运费与节点中转费用均使用数组变量存储, 2种网络的其他变量设置则类似。
1.2.1邻节点数据结构
邻节点数据结构是为相邻节点的各属性而设置的, 同1节点的邻节点采取链式结构存储, 访问某1邻节点的数据时, 由头结点向后依次查找, 直至找到所需节点。其数据结构为
邻节点编号/节点至邻节点运费
struct point{
int No;//邻节点编号
double Weight[length];//节点至该邻节点运费
piont*next;};
1.2.2节点数据结构
采取结构体数组形式存储节点信息, 其中, Neighbor存储邻节点链的首地址。节点编号与数组位置相对应, 这样的存储方式方便后期数据的存取。其数据结构为
节点编号/邻节点数目/邻节点链/节点中转费用
struct graph{
int No;//节点编号
int Neighbornum;//邻节点数
piont*Neighbor;//邻节点链
double Cost[num];//节点中转费用
}Node[pointnum];
按照上述方式定义的数据结构, 有利于数据的存取操作与具有普适性的运输网络图的构建, 也提升了笔者所设计算法的执行效率。
2算法设计
联合运输路径优化问题属NP问题, 应用遗传算法进行求解的效率较高。在本文中, 适应度的计算与当前路径的最佳选择通过动态规划方法来确定。算法流程见图1。
2.1编码策略
遗传算法最常采用的编码方式为二进制码, 然而在路径优化中, 由于节点与边的信息量较大, 二进制编码会变的十分冗长, 因此, 笔者采用整数编码, 即仅以节点编号作为染色体中基因编码。节点其他信息不参与编码, 其读取通过对结构体数组的访问实现。染色体的首位与末位基因分别对应运输起点与终点, 且染色体长度不超过节点总数。
2.2适应度函数
适应度是染色体进行遗传操作的基础。由于研究的网络图为多重图, 在未进行遗传算法操作时, 无论2节点间的路径为单条或多条, 都将其视为单条路径。生成染色体之后, 再通过适应度 (适应度取值为路径的最小运费) 的计算来确定具体路径。对于每条染色体, 可将其归为单源点最短路问题或多阶段决策问题来求解。由此笔者采用动态规划方法求解, 其基本思想为:以染色体 (染色体中包含基因数量为k+1) 中的每个节点为界, 将其划分为k个阶段求解。在任意节点处, 不论其后部子过程如何, 其前部子过程均要达到最优。
该问题的动态规划模型为
式中:fｋ (Xｉ) 为采用运输方式xｉ到达第k节点的最小费用;costｉｊ (k) 为在第k节点由运输方式i转换为运输方式j时的费用;weight (xｊ) 为采用运输方式xｊ从第k节点到达第k+1节点的运费。 f１ (xｊ) 与costｉｊ (1) 为边界条件。
2.3种群初始化
产生初始种群时, 采用深度优先搜索策略, 选取运输起点作为染色体的第1个基因码, 随机选取该节点的任意邻节点作为第2个基因码, 依此类推直至到达目标节点。若某1节点的邻节点全部访问过, 则回退1个节点继续搜索。此外, 设置数组变量Route[pointnum]、map[pointnum], 前者记录当前路径经历的节点, 后者作为节点访问标识。该设置能有效地避免产生回路。
2.4交叉运算
交叉运算是在按照一定概率随机选取的2个染色体之间进行的, 包括单点交叉、2点交叉与多点交叉3种方式。笔者采用单点交叉, 具体操作为:按照一定的概率选取2条染色体, 并交换2条染色体相同基因位 (不包括源节点与目标节点代表的基因位, 若包含2组以上相同基因, 则选取靠近目标节点的基因) 的前部, 此时得到2条子染色体, 检查子染色体所代表的路径是否包含回路, 若有, 则删除构成回路部分的基因, 直至染色体中不再包含回路。最后计算2条子染色体的适应度, 并保留4条染色体中适应度最高的2条进入下一代。参与交叉的染色体数为交叉率与种群数量相乘并取偶整数, 当不足2时, 则取2条染色体参与运算。每代种群中适应度最高的个体不参与运算。
2.5变异运算
变异运算的目的是改善算法的局部搜索能力、预防算法出现局部收敛。在本文中变异运算采用2种操作:基因插入与基因删除。
1) 基因插入。以一定的规则选择染色体, 任选染色体中的1个节点i, 搜索节点i所有邻节点中是否存在指向其下1节点j的节点, 若存在, 则计算插入之后形成的新染色体适应度值, 并与原染色体适应度进行比较, 若原染色体适应度值大, 则用新染色体代替原染色体, 插入操作结束, 若原染色体适应度值小或不存在指向j的节点, 则i向后移动1位, 继续上述操作直至染色体更新或到达目标节点为止。
2) 基因删除。以一定的概率选取染色体, 用j存储源节点, i存储目标节点。检查j与i之间是否存在直接通路, 若存在, 则计算新染色体的适应度值并与原染色体进行比较, 若新染色体适应度值小, 则替换原染色体并结束, 若新染色体适应度值大或者j与i之间不存在直接通路, 则节点j向后移动1位, 继续上述操作, 直至j=i或染色体发生替换时为止。
3实验仿真
对于图2~4所示的3种运输方式组成的运输网络, 应用C语言编程实现上述算法的仿真实验。算法设定当迭代次的数达到50或者种群总体适应度不再改变时, 算法终止。由于遗传算法进行一定代数以后, 种群越来越收敛至最优个体, 此时交叉操作所起到的作用将不会很明显, 而变异操作将承担继续引导种群向最优解收敛的任务, 因此在不同代数采用不同的交叉率与变异率。
种群规模:50。
对于上述运输网络, 选取节点1作为运输起点, 节点16作为运输终点, 使用图2~4与表1中所示的运费与中转费用数据进行多次仿真实验, 结果显示均能找到最优解。在大多数实验中算法进行至15代左右 (见图5) 、少数进行至25代左右时, 种群总体适应度不再变化, 此时算法终止, 得到最优解。上述运输网络的最优运输方式组合为:1-铁路-6-公路-8-公路-16 (数字代表运输过程中通过的节点, “1-铁路-6”表示节点1与6之间采用铁路运输, 其他依此类推) , 总费用为63, 在节点6进行过1次铁路与公路2种运输方式的中转作业。
注:a/b/c中, a, b, c分别为公路与铁路、公路与航空、铁路与航空之间的中转费用;“—”为不存在当前中转方式。
4结束语
在以总成本最小为目标的联合运输路径选择模型基础上, 定义了适用于联合运输网络的多重图数据结构并采用结构体数组来存储网络数据, 然后通过遗传算法计算得到最优的路径组合方式。由于联合运输网络图为多重图, 在采用笔者设计的遗传算法进行每次迭代时, 需要先生成节点链, 再通过动态规划方法确定具体的运输方式。 通过仿真实验表明, 这种方法, 能够在较短的时间和可预期的迭代次数内找到最优运输路径与运输方式组合。但模型考虑的情况毕竟与实际情况不完全一致, 需要在下1步的工作中继续研究。
摘要：为了求解联合运输网络的最优运输方式组合问题, 采用遗传算法并使用整数编码方式对城市节点进行编码, 摒弃了传统的二进制编码方式, 有效地缩减了编码长度并简化了编解码工作;城市节点链的运输方式组合与节点间运输方式转换使用动态规划方法来确定;至于联合运输网络数据, 在建立多重图数据结构基础上, 采用结构体数组与链式存储结构相结合的方式来存储。通过仿真实验表明, 该方法可行, 能够在较短的时间和可预期的迭代次数内找到最优解。
关键词：多重图,路径优化,数据结构,遗传算法,动态规划,联合运输
参考文献
[1]吴静, 王鹏涛.基于遗传算法的无向网络路径优化[J].天津师范大学学报:自然科学版, 2007, 27 (3) :72-75.
[2]温晓磊.基于混合算法的最短路径优化算法[J].天津理工大学学报, 2009, 25 (1) :37-40.
[3]卢欣, 雷强, 王其才.有时间限制的多式联运路径优化模型研究[J].铁道运输与经济, 2012, 34 (10) :52-55.
[4]孙华灿, 李旭宏, 陈大伟, 等.综合运输网络中合理路径优化模型[J].天津师范大学学报:自然科学版, 2008, 38 (5) :873-877.
[5]肖天, 国符卓.基于遗传算法的联合运输路径优化[J].中国科技论文在线, 2008 (7) :720-724.
[6]王玲玲, 覃运梅.多式联运的运输方案选择研究[J].铁道运输与经济, 2009, 31 (10) :78-81.
[7]李庚, 李常双, 周飞飞, 等.应急铁路军事运输径路优化问题研究[J].交通信息与安全, 2010, 28 (4) :89-92.
基于物流配送路径的优化算法研究 篇7
1 物流配送路径优化问题的精确算法
1)动态规划法。此算法(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
2)分枝定界法。该法是将原始问题分解,产生一组子问题。分支是将一组解分为几组子解,定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外,就将这一子组舍弃(剪枝)。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。
3)切平面法。此方法与分枝定界法相类似,它也是在整数规划与求解相对应的线性规划上,不断的增加新的约束,相区别是会加入一些特别的约束条件,然后切掉非整数规划中的可行解,获得最优解。
2 物流配送路径优化问题的传统启发式算法
传统的启发式算法在求解过程中主要是从初始解出发,以搜索邻域的方式实现解的改进,并在较短的时间内获得一个可以接受的解。传统的启发式算法主要有以下4种:1)节约算法。此算法是将较短路径与原路径定义为节约值,然后将节约值从大到小进行排序,在节点的数量允许的情况下,依此将节点对应的顾客点插入到路径中,直到所有的顾客都被插入路径为止,从而获得可行解,不过解非最优。2)邻接算法。此算法是由数据结构中的邻接表演变过来。邻接表是图的一种链式存储结构,对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。此算法的思想是从一个起始点出发,然后搜索路线中与之距离最近的点,然后在次以此方法不断搜索最近的点,从而进行路线的构造。这种方法可以保持原有路线的可行性,从而搜索着一条疑似最短的路线,节约路线成本。3)插入算法。此算法是又数据结构中的插入排序演变过来。它将邻接算法与节约算法有机的结合起来,先利用节约算法确定一条基本路线,然后根据邻接算法搜索客户节点的位置,依次按距离将客户节点插入到原有路径中,最后形成新的配送路线。4)扫除算法。此算法是将邻接算法与插入算法相结合,它是先对车辆进行分组,然后确定不同的路线,在配送过程中以扫除的方式搜索未被分配的点,然后用插入算发对路线进行扩充,如果一次分组之后还存在未被分配的点,那么继续对路线进行构造,直到所有的点都被分配为止。
3 物流配送路径优化问题的现代启发式算法
与传统的启发式算法相比,现代启发式算法并不是每次在迭代中都延着目标值下降的方向进行搜索,它还允许在搜索中接受目标值上升甚至是不可行的解,现在启发式算法与传统启发式算法的一大区别就是它会在搜索过程中跳出局部邻域进行全局搜索。现代启发式算法有以下4种:1)禁忌搜索算法。此算法是一种亚启发式(meta-heuristic)随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向。禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解,从而跳出局部搜索的目的。2)遗传算法。此算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它最初由美国Michigan大学J.Holland教授于1975年首先提出来的。遗传算法从问题解的串集开始嫂索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的,容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。3)模拟退火算法。模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。此算法是一种随机松弛技巧,它模拟了退火的过程,在搜索的初始阶段,算法跳向远点,随着时间的延伸或下降,跳跃幅度逐渐减小,最终转向局部搜索的下降方法。4)蚁群算法。蚁群算法又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。
4 各种优化算法的比较
以上各种优化算法在不同时期与情况下都有其优缺点,都有解决某些问题的能力,但随着发展的需要,对优化算法的要求也越来越高。下面对各种方法进行比较分析,通过表格的形式展示出各自的特点,如表1所示。
5 结束语
车辆路径问题由于在管理学和运筹学上非常重要而且求解有一定的难度,同时由于它具有很强的现实价值,可产生极其可观的经济效益,因而是理论界与企业界关注的一个极其具有魅力的优化问题。通过表格的分析比较,可以看出各种方法的优点和缺点,在不同的任务中可以挑选不同的优化算法,从而使物流效率达到最高。本文通过介绍各种优化算法来比较各类算法的优缺点,以便能在实际中解决各种复杂的物流路径优化问题,从而找到最好的优化方法。
参考文献
[1]孙学农,徐辉增.物流配送车辆调度问题方法综述[J].科技信息:学术研究,2007(12).
[2]刘明广,李高扬.物流配送车辆优化调度模型及其求解策略[J].工业工程,2007(2).
[3]方金城,张岐山.物流配送车辆路径问题(VRP)算法综述[J].沈阳工程学院学报:自然科学版,2006(4).
[4]李贵春,刘冬梅.物流配送系统车辆的优化调度算法[J].天津工业大学学报,2006(3).