基于图论的救护车路线优化

基于图论的救护车路线优化基于图论的救护车路线优化温海春广东南方电信规划咨询设计院有限公司惠州分公司广东惠州 516003 【摘要】救护车的路线选择是图论优化问题。本文通过对城市交通网络的特点抽象问题、简化模型，在最短路径和道路最大畅通概率两重目标约束下的救护车路线选择及优化。首先用 D_j k s t r a算法求最短路，考虑到不同路段道路的通行情况不同，建立多目标规划模型，并描述了用 S T E M 算法求解的过程。实例验证了模型和算法的可行性。最后提出了该 ...

基于图论的救护车路线优化温海春广东南方电信规划咨询设计院有限公司惠州分公司广东惠州 516003 【摘要】救护车的路线选择是图论优化问题。本文通过对城市交通网络的特点抽象问题、简化模型，在最短路径和道路最大畅通概率两重目标约束下的救护车路线选择及优化。首先用 D_j k s t r a算法求最短路，考虑到不同路段道路的通行情况不同，建立多目标规划模型，并描述了用 S T E M 算法求解的过程。实例验证了模型和算法的可行性。最后提出了该系统性能还可以得到提升的方法。【关键字l救护车图论最短路径多目标规划中图分类号：TP278 文献标识码：B 文章编号：1009—4067(2010)07—324-02 1、引言随着数学科学和计算机技术的发展，数学建模知识在各领域中发挥着重要的作用，抽象实际问题、建立正确的数学模型已成为解决实际应用问题的关键“1。通过建立数学模型，就可以对实际问题进行抽象、简化、确定变量和参数，并应用某些 “规律”建立起变量、参数间的确定的数学模型，一个理想的数学模型，它应满足两个条件：一是可靠性，即在允许的误差范围内，能正确反映所考虑系统相关特性的内在联系，反映客观实际；二是可解性，即便于进行数学计算。本文主要研究救护车的导航系统如何选路，使病人在路上的时间最短，即使病人能得到最及时的抢救。通过建立相应的数学模型，最终将该问题归结为图论中的最短路径问题。最短路径问题经过几十年的发展，产生了很多求解最短路径的算{去【】，这其中包括Dijkstra算法、Floyd算法、Warshall 算法、Prim算法和Kruskal算法。根据本文所要解决的问题的特点，本文应用Dijkstra算法计算了转移时间最短和道路拥堵概率最小的路线，然后用多目标规划的STEM算法对路线选择进行了优化，得出了比较合理的结论。 2、问题的提出与抽象假设—个城市A，其中心医院位于图1中v．，假设v 处有危重病人需要得到及时的抢救，中心医院需派救护车到v。史b将病人接到医院，途中可能经过的交通枢纽有v1，v 、v 和v7，我们的最终目标是选一条距离最短，同时堵车概率最小的路，只有这样病人才能被及时地送到医院进行抢救。图 1 由于影响实际问题的因素很多，要解决实际问题就要建立适当层次上的数学模型⋯，即要把建模对象所涉及的次要因素忽略掉，否则所得模型会因为结构太复杂而失去可解性同时又不能把与实质相关的因素忽略掉，而造成所得模型因为不能足够正确反映实际情况而失去可靠性。因此需要对实际问题进行抽象、简化、确定变量和参数，并应用某些“规律”建立起变量、参数间确定的数学模型。影响路线选择的因素很多，譬如瞬时车流量、是否有交通事故、车辆状况等，而实际要解决的是如何能使救护车在最短的时间内把病人送到医院，因此车流量和路径长度成为影响解决本问题的主要因素，而是否有交通事故发生和车辆状况等次要因素均可忽略掉。这样这个问题就转化为一个图论问题，即求最短路径问题。 3、最短路问题及Dj j kst ra算法】给定一个非空的简单有向网络G =(V，A，W，P)，如图1所示。其中：V为顶点集，V=(v ，v ，⋯，v )IA为有向弧集，A={(v ，V2)，(V2， v，)，⋯，(v ，v；)，⋯}lt和P为有向弧上的权值，w 表示通过这段路所需时间和p表示这段路畅通的概率值，t，P 0，且P∈【0，1]。有向弧 (v．， 324 中国电子商务● 2010·07 v ．)上权向量的第一个值为即转移时间，第二个值为P 即这段路畅通的概率值。设是加权有向图G自节点1到节点j的最短有向路的长度，并且对所有的j=l，2，3，⋯，n，S，为有限值。若图G中除节点1外其余各点能重新编写成如下的序号2，3，⋯，n使得对所有iSjRw(j，f)=oo，即(，，f)芒E(G)，则有 f =o 1S =卿 +w(七， _，=2,2，．． (2) 式(2)的解，是G中最短，V，J路的权(j=l，2，⋯，n)．下面给出边权为正值的有向图中求最短路算法的Dijkstra算法。 (1)置P=“}，T=(2，3，⋯，n)且 =o，sj=w(1，办j=2⋯3．．，，l l (2)在T中寻找一点k，使得：ra i n{ J，置P：Pu忙)，T：T一{k}。若T≠ ，终止。否则，转向(3)。 (3)对T中每一点j，置Sj=min~Sj，Sk+ 七，，然后转向(2)。 4、求最大道路畅通概率问题转化为求最短路问题在有向网络G=(V，A，w，P)中，任意一条从v 到的路P=v 。 v，，⋯，、m的道路畅通概率定义为P上所有弧的畅通概率的乘积，即 p(尸)= IIP ( 西(pj G中的所有(V，， )路中畅通概率最大的路即为最大畅通概率(v．，vn)路。如果 ( ，Vi)∈A(G)，令q．一一l0g ；，则G中最大畅通概率 (y ， v )路等价于G中关于q的最短 (v ，v )路，从而可以用Dijkstra算法进行求解。 5、救护车行驶路线优化的多目标线性规划模型及其解法 5．1多目标线性规划模型救护车行驶路线选择要满足主要两个目标，一是行驶时间最短，二是道路畅通概率最大。根据上面的叙述，两个目标均为线性规划问题，因此，可以建立多目标线性规划模型如下： minwo=∑ minq ∑ · r 1,i=1 “ ∑ 一∑ =0，2- 分析者把计算结果告诉决策者，决策者对计算结果做出评价判断。如果满意了，则迭代停止，否则分析者再根据决策者的意见进行修改和计算，直到求得决策者满意的解为止。这种对话式方式能有效地结合抢救指挥中心指挥人员的个人经验和判断能力，从而得到较合理的目标值。其求解步骤为： (1)分别用D ks竹a算法求单目标线性规划问题的解，得到最优解， ’和相应的两组目标函数值，分别为f坩’， ’】。f )，】。令 =min{w2)， }， =max{坩)， )}，qo=min{鼋 )， )}， Q~=max{g ，鸟52’}，转(2)。 (2)求权系数。为了找出目标函数值的相对偏差以及消除不同目标值的量纲不同的问题，进行如下处理：赢警方经归一化后，得权系数：，i：l，2 + (3)构造以下线性规划问题，并求解：一 s - t ．A >- 。， ( v X ， q ， g ， x ij - ， q o) ≥ lr 。 z 0，V ，V，J∈ ， ≥0 一 (1) 一(1) 一(1) 假定求得的解为，相应的目标函数值为Wo ，q ·如果为决策者的理想解 (” ，其相应的目标函数值为 w0(” 、 qoO) ,这时决策者将目标值进行比较后，认为满意了就可以停止计算。若认为相差太远，则考虑适当修正。若考虑对第1个目标宽容一下，即减少或增加一个△w，并令第1个目标的权系数．=0，表示降低这个目标的要求，再求解线性规划问题： rain 厂、 2>-f Zq 一q ∑woxo ∑ +△W x o，V ，v，J∈A， ≥0 — 0) 若求得的解为，再与决策者对话，直到决策者满意为止。 6、实例分析设问题为求解1个救护车的行驶路线，要从V。点机动至V 点，中间有多种路线可选，每条路线标有转移所需时间和道路畅通概率的估计，如图1 所示。将道路畅通概率取对数并求相反数，可得数据如图2所示。图2 )~Dijkstra算法求得目标函数值分别为：目标函数值1：Wo =13，选择有向路P1=V1V3V4V6V8，最优解 ={x13，x x46， 8} {1，1，1，1}， M／,~qoO)=q l 3+q +q46+q盯：O．155+0．097+0．301+0．046=0．599。道路畅通的概率 (。)=O．2518。目标函数值2：qo(2)：O ． 298(po(2)一O ．504)，选择有向路P2=vI 8，最优解㈨= {x1 3，x 3 6，x 6 8}= {1，l，1}，对应的转移时间为 wo =wl3+w36+w68=4+5+5=14。由此可求得d1 0．002679，c【2_-1．4757lⅡl 0．00202，丁T 2 O．86679。求解以下线性规划问题： m 、。‘。。。 j _ 。· Z ， q ,~xu-0"599 ／ ] ‘ ，v，／由此，可求得解为 ={ 3^'X6 }={l，l，1}，相应的目标 “1 f11 f11 函数值为 14，qo =O·298(Po 0·504)。分析者将计算结果告诉决策者，决策者将其与理想值【 )，g52’(p )]=[13，0．298(0．504)]进行比较，认为求得的结果基本满意若他提出将w0提高到l4，以便降低qn。此时线性规划问题修改为 ra in 厂、姐。。 A 2％J ，v，， ∑ ≤14 (7) x 0，V【v ，VJ)∈ ， 0 由此，可求得解与式 (6)解相等。此时决策者对结果满意，则停止计算。 7、结论与展望救护车路线选择问题是一个多目标规划问题，其中最主要的目标是路线长度最短和道路的畅通概率最大。Dijkst~a算法是比较成熟的求非负权网络最短路问题的算法，也是一种多项式算法[71-STEM算法是一种对话式算法，二者均易于在计算机上实现。因此研制救护车路线优化的辅助决策是可行的，能大大提高救护车救人的效率。目前该模型还存在一些可以改进的方面。第一，不同路段的交通高峰到来的时间不一样，可以统计出不同路段在不同时刻交通畅通的概率，可以把时间为该模型的一个函数；第二，这个系统与当地交警支队的交通指挥系统相连接，如果救护车在某路段遇到交通堵塞，可以通过交通管理系统控制信号灯等方式，完成交通调度，以最短的时间保证救护车通过该路段，或者是提前为救护车预留好相应的道路，等待救护车的到来。参考文献 [I】朱建青．数学建模[砌．解放军出版社，1 996． 2010·07-．中国电子商务 325

                    本文档为【基于图论的救护车路线优化】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

基于图论的救护车路线优化

你可能还喜欢