<%JournalFullName%> Vol.<%Volume%> No.<%Issue%><%IssueYear%>, Article ID:<%PaperID%>,<%PageCount%> pages <%DOI%>
Application of Improved Genetic Algorithm in Ambulance Operation Management
Jiangeng Xu1, Qin Luo2*
1College of the Transportation, Shenzhen University, Shenzhen
2Shenzhen Key Laboratory of Urban Rail Transit, Shenzhen
Email: *luoqin82@126.com
Copyright © 2014 Jiangeng Xu, Qin Luo. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accordance of the Creative Commons Attribution License all Copyrights © 2014 are reserved for Hans and the owner of the intellectual property Jiangeng Xu, Qin Luo. All Copyright © 2014 are guarded by law and by Hans as a guardian.
Abstract: Due to the disadvantage of genetic algorithm in dynamic route guidance, a dynamic router guidance algorithm based on the net of vehicles was presented to calculate the shortest route in ambulance operation management. By introducing inducing factor, and changing coding method and variation mode, the number of invalid router might decrease exponentially in the process of algorithm and raise the efficiency in some degree. Improved algorithm in ambulance management could avoid blindness caused by traditional administration and increase the utilization of medical resources. Finally, the paper calculated the shortest route in the virtual example with this algorithm and the result shows that it could aggrandize the efficiency of router guidance.
改良遗传算法在救护车运行管理中的应用
徐健庚1，罗 钦2*
1深圳大学轨道交通学院，深圳
2深圳市城市轨道交通重点实验室，深圳
Email: *luoqin82@126.com
收稿日期：2013年12月18日；修回日期：2014年1月10日；录用日期：2014年1月15日
摘 要：针对基本遗传算法在动态路径规划中的不足，提出基于车联网的改良遗传动态路径诱导算法用于救护车调度管理中。通过引入诱导因子、改变编码方式和变异方式，在宏观上有效减少算法操作过程中产生的无效路径，较好的提升了算法效率。改良算法应用于救护车管理中能够避免传统调度的盲目性，提高医疗资源的利用率。最后采用此算法进行模拟实验，结果表明改良算法能够提高路径规划效率。
关键词：车联网；动态路径规划；遗传算法
1. 引言
目前，特大型城市的交通拥堵已经严重影响到病人转移。交通高峰期内，一辆救护车“不到3公里的路走了40分钟”的事件引发各界关注。为逝者哀悼
的同时，一个已长久困扰急救人员的难题，凸显在大众面前：特大型城市中的救护车如何应对交通拥堵困境。许多人看来，解决这个矛盾最快的方式建立健全的法律保障救护车的顺畅。公众和媒体对立法规定“救护车的道路通行优先权”很是期待。事实上，《北京市实施〈中华人民共和国道路交通安全法〉办法》的规定已很明确，驾驶机动车遇有执行紧急任务的警车、消防车、救护车、工程救险车未按照规定让行的或违反规定在应急车道内行驶或停车的，处200元罚款等。但是，实际操作中具有巨大的难度。据基层交警反映，如果遇到救护车一般会主动上前引导、疏通，但是受限于路况，很难认定其他社会车辆是否触犯法规，给处罚取证带来很大障碍。因此从行政角度的解决方式几乎都不能有效缓解现在因交通拥堵给救护车带来的不便。面对救护车所处困境，应用动态路径规划方式在一定层面上能为救护车提供适当的帮助。动态路径规划利用遗传算法，根据车联网实时数据，为城市道路行驶的救护车提供指引服务。达到有效避开拥堵路口和拥堵区间的目的，改变以往的困境。
遗传算法，最初由美国密歇根大学J. Holland教授于1975年首先提出，是计算机科学人工智能领域中用于解决最优化的一种启发式搜索算法。通过模拟达尔文进化论和孟德尔遗传定律，从而得到相对最优解，求解过程高效稳定，应用领域广泛。
2. 救护车运行管理
2.1. 车辆调度
对于城市医疗服务资源而言，救护车日常运作管理通常分为3个阶段实施：计划、调度与控制。其中调度是关键环节，通常分为两种。1) 原始调度、车辆计划安排，按照单一原则为病人提供运输服务，一个运输周期内任务通常只有一个，任务与任务之间不具有相关性各自独立，称为静态调度[1]；2) 动态调度[1]，实时掌握所有救护车的信息，充分利用现有资源。动态调度具有如下优势：较强的应激性、较快的反应速度、突出城市医疗系统的整体性和全局性，同时相比传统调度方式具有明显的效率提升。救护车动态调度的实质就是针对某项运输任务，在一定约束条件下，合理安排组织所占用资源、运行车型以及先后顺序，以获得时间或运输成本等目标的最优化。
2.2. 车联网技术及其应用
美国麻省理工学院教授Kevin Ash-ton首先提出物联网(The internet of things)的概念。物联网的普及加快了社会信息化和网络化的进程。车联网作为物联网的最典型的应用，利用无线射频识别技术(Radio Frequency Identification, RFID)、无线数据通讯技术，有效地连接道路上行驶的车辆，实现车与车、车与道路和车与人之间的自动识别和信息共享。
车联网利用装载在车辆上标签，通过无线射频技术进行读取，可以获得车辆的具体信息包括行驶速度、行驶方向和行驶区间等。同时还能获取道路、桥梁和隧道的区间平均行驶速度，区间内车辆数和其他的路况信息。通过GPS定位系统，确定车辆的具体的位置。利用无线3G通信技术，可以将所有通过车连网获取的车辆和道路信息汇总至控制云端，实现信息传输和共享。
从技术角度区分[2]，车联网技术主要有电子标签技术(RFID等)、位置定位技术(GPS等)、无线传输技术(3G无线通信技术)、数字广播技术(CMMB等)、网络服务平台技术(如Web服务、数据融合处理技术、地图匹配技术等)。
2.3. 动态路径规划
传统路径选择一般依靠司机经验，因此大多数情况下都无法寻找到最优路径。从而造成救护车深陷车流之中，之后再寻求交警求助，不仅造成极大社会资源的浪费，而且给病人带来巨大的风险。车辆调度能够合理化地利用现有医疗资源，避免救护车使用的盲目性和无序性，一定程度上能够确保病人的及时转运。但是目前的车辆调度主要为人工调度，路径安排主要依靠从业者的调度经验和依靠一些简单的道路状况信息，无法精确地高速地制定耗时最短的路径且无法做到动态调度，从一定程度上浪费了救护车资源。特别处于城市早晚高峰时期，由于缺乏准确的和全面的道路状况信息，很多情况下只能凭借司机的感觉“走一步看一步”，这种摸索探路式的转运病人方式是对生命的不重视，不负责，不尊重。车联网技术可以从根本上解决现有调度方式的盲目性和无序性。因为其高效地信息共享和交流系统能够将城市每个角落的道路信息及时的反馈给调度中心。根据这些数据，调度中心可以对全市的所有救护车进行动态调度，缩短以往静态调度的间隔，提高车辆使用率和效率，动态路径规划为动态调度提供了有力的保障。交通道路网络的信息特点具有高动态性、区间通行的不稳定性。这些不确定性给调度工作带来了巨大的挑战。动态路径规划可以根据实时获取的信息快速的调整车辆行驶路线，确保了最优路径的有效性，同时利用改良遗传算法为救护车进行最优路径搜索可能可以提高算法求解速度。
3. 模型建立
3.1. 模型描述
根据数学家莱昂哈德·欧拉的图论，可以将算法所涉及的各个研究对象建立在一张一维图中。为了给算法提供一个便利的运行平台。所建模型做如下限定。
图中节点表示道路交叉路口，同时设置所有节点有且仅有四个相邻节点且连通。当道路路口出现超过四个行车方向时，可引出另一个节点并把这两节点之间的阻抗赋为零。即两个节点最多可以表示一个道路口的六个通行方向。
节点之间的数值表示区间旅行时间。具体计算根据道路阻抗等相关数据进行。道路实时阻抗由车联网信息网络获取，保证调度过程中的信息的可靠性。
起点为闲置救护车所在位置并非医院所在位置。动态调度为救护车任务的连续性提供了良好的保障。
终点为患者所在位置。
由上述方法，可将城市道路网络抽象化为一个n阶矩阵。区间旅行时间存入数组
，其中从第i行第j列至第i行第j + 1列耗时为ax，
，若从第i行第j列至第i + 1行第j列，则
。第m辆救护车由所处位置到终点的耗时Am可以根据N中动态数据算出。当接受到用车请求时，由搜索算法求得
。搜索结果为当前道路网络中旅行时间最短路径或在搜索代数结束时已经寻找到的耗时最短路。模型如图1。
3.2. 模型技术支持
动态路径规划过程中技术支持包括：GIS(地理信息系统)、IOV(车联网)、GPS(全球定位系统)和GPRS(通用分组无线服务技术)。通过改良的遗传算法将各个部分有机整合达到最优动态路径诱导的目的。以下将简略介绍各部分系统在算法中扮演的角色和作用。
Figure 1. Diagram of the model
图1. 模型示意图
地理信息系统结合地理学和地图学，广泛应用于不同领域。此系统为诱导算法提供地理数据包括道路信息、医院及病人位置信息等。
车联网是利用先进的传感技术、网络技术、计算技术、智能技术对道路和交通实现全面感知，准确了解车辆具体状态如：行驶方向、坐在位置等对交通优化有利的实时数据。车联网为算法提供实时道路区间阻抗，为救护车动态路径规划提供可靠的数据。
通过全球卫星定位系统，诱导算法可以获得救护车的精确位置信息，为诱导规划提供依据。
实际操作过程中，通用分组无线服务技术负责信息传递实现救护车与算法间的实时通信。
4. 求解算法
4.1. 算法简介
基本遗传算法[3](标准遗传算法或简单遗传算法，Simple Genetic Algorithm, SGA)是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(Genetic Operator)：比例选择算子、单点交叉算子、基本位变异算子。基本遗传算法有下列4个运行参数需要预先设定，即M, T, Pc, Pm。其中M为群体大小，即群体中所含个体的数量，一般取20~100；T为遗传算法的终止进化代数，一般取100~500；Pc为交叉概率，一般取0.4~0.99；Pm为变异概率，一般取0.0001~ 0.1。
算法改良主要体现在遗传编码方式、适应性计算和历史数据的处理。
算法数据主要从车联网中获取，包括道路路况及通行状况，及全部救护车的行驶状况。通过以上数据可以计算获得道路区间阻抗和动态路径规划的始点。
改良遗传算法流程图如图2。
4.2. 遗传编码方式
任意一个复杂的城市道路网络都可抽象成一个N*N的矩阵。矩阵中的每一个节点(除去部分边缘节点外)都具有四个通行方向，如图3。应用于动态路径规划的遗传算法的传统编码方式为，随机生成节点序列或方向序列。但此类编码方式效率极低，产生大量无效序列如：无法到达目的地、超出矩阵范围等，严重影响到算法的效率。
改良遗传算法编码方式[4]采用方向序列。但与以往编码方式不同，改良编码方式增加动态方向诱导因
Figure 2. Flowchart of improved genetic algorithm
图2. 改良遗传算法流程图
Figure 3. Diagram of a point and directions
图3. 节点方向标号示意图
子，即初始位置与终止位置的相对坐标。方向序列随机生成过程中，每产生一个新的方向，都应将方向序列翻译为结点序列并进行动态方向诱导因子的重新计算，直至动态方向诱导因子为(0, 0)。另外通过改变各个方向的随机概率，动态方向诱导因子具有影响方向序列的作用，例如：当动态方向诱导因子为(2, 1)时，可以适当调整为上行概率和右行概率分别为0.275，下行概率和左行概率分别为0.225。为避免出现圈或往复行驶在同一区间，可将来行的逆方向概率设为零(同时边缘节点亦可采用类似方式避免超出行进范围)，将其原有概率平均分配到其余方向上。另外方向概率的调整幅度应根据城市道路状况自行决定。如若调整幅度过大，可能造成算法早熟，最终无法获得最优解。
综上所述，基于选择方向的编码方式，采用1~4的综合序列来表示染色体。
除随机生成可能解之外，改良遗传算法具有类似免疫算法的记忆功能。即每次求得最优解后将其记录，再次遇见类似调度方案时，直接将原有解添加至种群中。加速算法收敛，达到提高效率的目的。
4.3. 适应度计算及选择方式
适应度主要用于描述染色体序列在当前环境中的竞争力程度，对解的优劣性进行评估，为解的选择提供一定的量化标准。适应性函数[2]为：
(1)
其中：f：为染色体的适应性；
为惩罚因子(若出现回路或通过非连通区间，则赋一个较大值)；d为通过车联网获得的实时道路交通阻抗。
染色体选择采用赌轮盘法，在传统选择方式的基础稍加改动，避免算法早期过早成熟和算法后期滞涨。改动方式如下：将获得适应度进行排序，将位于前17%部分的复制三次，紧接的33%部分复制两次，最后剩余50%不复制。 
最大可能保留产生的优良品质。选择数量为上一代复制前染色体总数量的0.5倍。
4.4. 交叉运算
交叉运算过程直接影响到算法最终能否获得最优解或相对最优解。传统交叉方式沿用基本遗传算法交叉方式，即通过随机方式交换不同序列之间的额遗传信息。这种交叉方式不适用于有较强连续性的遗传信息改良交叉方式采用定向选择交叉，即通过对节点序列的搜索，寻找出一个OD对中的不同通行路径进行交叉，这样能有有效的避免因交叉产生的无效序列，在一定程度上能够加快算法收敛。
为了增加交叉效率，避免近亲繁衍造成算法滞涨，进行交叉两个染色体相识度要低于0.5。相识度[5]定义如下：
(2)
其中：
；n为两染色体的相同部分长度；l为染色体长度。
4.5. 变异运算
变异在自然进化中扮演着举足轻重的作用。如若没有变异，生物无法进化到当今如此的多样化程度。本算法变异方式为随机产生偶数个方向插入方向序列中，并且保证连续的两个方向序列不为相反方向，翻译为节点序列进入种群，变异前后染色体均保留。其中插入至方向序列的偶数个方向应保证其组合为零，即上行数量应与下行数量相等，同理左行数量应与右行数量相等。此种变异方式能最大程度保证变异后的方向序列的有效性，减少无效路径的产生。传统变异仅随机添加几个方向序列至原序列中，经测算当仅增加两个方向变量，其变异后序列有效性仅为0.0625，随着变异数量的增加，其有效性呈现急剧下降。
与基本遗传算法相类似，变异概率自行根据实际情况设定。变异改良设定应该充分考虑道路网络、救护车需求量、路况等影响因数，建议通过实验的方式获取。
5. 算例
通过算法示例说明改良遗传算法应用于救护车动态调度的优越性。为避免范例过于复杂，算法示例使用9个节点的矩阵。如图4所示。各区间阻抗随机产生已标注于图上，假定区间为双向通行。起点为一号节点终点为九号节点。
算法参数设定如下，初始种群设定为4个，遗传代数上限为20代，个体变异概率0.05，动态方向诱
Figure 4. Diagram of the system of roads
图4. 道路示意图
Table 1. The possibility of the different directions in various points
表1. 节点方向概率
节点编号
上行概率
下行概率
左行概率
右行概率
一号
0
0.55
0
0.45
二号
0
0.32
0.33
0.35
三号
0
0.55
0.45
0
四号
0.32
0.33
0
0.35
五号
0.24
0.26
0.24
0.26
六号
0.3
0.4
0.3
0
七号
0.5
0
0
0.5
八号
0.3
0
0.3
0.4
(注意：节点方向概率是通过历史统计数据生成的，与实时阻抗并无直接关系)。
导因子区间值设定为[0.05, 0.01]，节点方向概率设定如表1。
经计算，改良算法随机出现最优解的概率约为基本算法出现最优解概率的18倍。另一方面，通过动态方向诱导因子的诱导，产生的随机解较原始生成方式更逼近最优解。使用改良后的遗传算法求得最终路径为：1---4---5---8---9。与Dijkstra算法求得结果相同。原始算法平均所需收敛代数为16代，改良遗传算法平均收敛代数为12代。经过15次有效计算比较，收敛代数如图5所示。算法效率提高40%左右。
6. 总结
改良后的遗传算法添加动态方向诱导因子，其核心思想就是，通过对城市道路的长时间研究积累，利用司机经验或观察结果诱导道路生成，使得生成过程具有一定的方向性，避免了盲目性。一定程度上提高了算法效率。值得注意的是，如果过分强调或突出经验在道路选择中的作用，可能会使算法失去意义。因
Figure 5. The comparison of tow algorithms in demanding generation
图5. 两种算法所需求解代数比较
此，动态方向诱导因子的设定应根据实际城市交通状况和道路结构。
改良遗传算法中，添加了染色体相似度判断为了防止近亲繁衍。近亲繁衍对于遗传算法危害极大。因为其产生的后代多与父代相识，达不到多样组合求解的目的，使得计算资源大量浪费。算法总体进度停滞不前，极大地延长了算法求解时间。
另外，改良后的遗传算法增加类似免疫算法的记忆功能。新增功能可以使算法随着使用时间的增加，求解速度越来越快，特定区域适应性越来越强。
相比基本遗传算法，改良后的算法，在性能上明显优于基本算法。
[1] 参考文献 (References)
[2] 滕继涛, 张飞舟, 李跃鹏, 等 (2003) 智能交通系统中车辆调度问题的遗传算法研究. 北京航空航天大学学报, 1, 13-15.
[3] 诸彤宇, 王家川, 陈智宏 (2011) 车联网技术初探. 公路交通科技(应用技术版), 5, 266-268.
[4] 曳永芳, 杜永清, 行小帅 (2010) 一种抑制早熟收敛的改进遗传算法. 山西师范大学学报(自然科学版), 2, 24-28.
[5] 李春元, 魏武, 谢赛, 等 (2007) 基于改进遗传算法的最优路径求解. 交通与计算机, 5, 88-92.
[6] 曹道友, 程家兴 (2010) 改进交叉算子和变异算子抑制GA算法早熟. 科学技术与工程, 6, 1540-1542.
NOTES
*通讯作者。
Received: Dec. 18th, 2013; revised: Jan. 10th, 2013, 2014; accepted: Jan. 15th, 2014
Keywords: Net of Vehicles; Dynamic Router Guidance; Genetic Algorithm
1. 引言
目前，特大型城市的交通拥堵已经严重影响到病人转移。交通高峰期内，一辆救护车“不到3公里的路走了40分钟”的事件引发各界关注。为逝者哀悼
的同时，一个已长久困扰急救人员的难题，凸显在大众面前：特大型城市中的救护车如何应对交通拥堵困境。许多人看来，解决这个矛盾最快的方式建立健全的法律保障救护车的顺畅。公众和媒体对立法规定“救护车的道路通行优先权”很是期待。事实上，《北京市实施〈中华人民共和国道路交通安全法〉办法》的规定已很明确，驾驶机动车遇有执行紧急任务的警车、消防车、救护车、工程救险车未按照规定让行的或违反规定在应急车道内行驶或停车的，处200元罚款等。但是，实际操作中具有巨大的难度。据基层交警反映，如果遇到救护车一般会主动上前引导、疏通，但是受限于路况，很难认定其他社会车辆是否触犯法规，给处罚取证带来很大障碍。因此从行政角度的解决方式几乎都不能有效缓解现在因交通拥堵给救护车带来的不便。面对救护车所处困境，应用动态路径规划方式在一定层面上能为救护车提供适当的帮助。动态路径规划利用遗传算法，根据车联网实时数据，为城市道路行驶的救护车提供指引服务。达到有效避开拥堵路口和拥堵区间的目的，改变以往的困境。
遗传算法，最初由美国密歇根大学J. Holland教授于1975年首先提出，是计算机科学人工智能领域中用于解决最优化的一种启发式搜索算法。通过模拟达尔文进化论和孟德尔遗传定律，从而得到相对最优解，求解过程高效稳定，应用领域广泛。
2. 救护车运行管理
2.1. 车辆调度
对于城市医疗服务资源而言，救护车日常运作管理通常分为3个阶段实施：计划、调度与控制。其中调度是关键环节，通常分为两种。1) 原始调度、车辆计划安排，按照单一原则为病人提供运输服务，一个运输周期内任务通常只有一个，任务与任务之间不具有相关性各自独立，称为静态调度[1]；2) 动态调度[1]，实时掌握所有救护车的信息，充分利用现有资源。动态调度具有如下优势：较强的应激性、较快的反应速度、突出城市医疗系统的整体性和全局性，同时相比传统调度方式具有明显的效率提升。救护车动态调度的实质就是针对某项运输任务，在一定约束条件下，合理安排组织所占用资源、运行车型以及先后顺序，以获得时间或运输成本等目标的最优化。
2.2. 车联网技术及其应用
美国麻省理工学院教授Kevin Ash-ton首先提出物联网(The internet of things)的概念。物联网的普及加快了社会信息化和网络化的进程。车联网作为物联网的最典型的应用，利用无线射频识别技术(Radio Frequency Identification, RFID)、无线数据通讯技术，有效地连接道路上行驶的车辆，实现车与车、车与道路和车与人之间的自动识别和信息共享。
车联网利用装载在车辆上标签，通过无线射频技术进行读取，可以获得车辆的具体信息包括行驶速度、行驶方向和行驶区间等。同时还能获取道路、桥梁和隧道的区间平均行驶速度，区间内车辆数和其他的路况信息。通过GPS定位系统，确定车辆的具体的位置。利用无线3G通信技术，可以将所有通过车连网获取的车辆和道路信息汇总至控制云端，实现信息传输和共享。
从技术角度区分[2]，车联网技术主要有电子标签技术(RFID等)、位置定位技术(GPS等)、无线传输技术(3G无线通信技术)、数字广播技术(CMMB等)、网络服务平台技术(如Web服务、数据融合处理技术、地图匹配技术等)。
2.3. 动态路径规划
传统路径选择一般依靠司机经验，因此大多数情况下都无法寻找到最优路径。从而造成救护车深陷车流之中，之后再寻求交警求助，不仅造成极大社会资源的浪费，而且给病人带来巨大的风险。车辆调度能够合理化地利用现有医疗资源，避免救护车使用的盲目性和无序性，一定程度上能够确保病人的及时转运。但是目前的车辆调度主要为人工调度，路径安排主要依靠从业者的调度经验和依靠一些简单的道路状况信息，无法精确地高速地制定耗时最短的路径且无法做到动态调度，从一定程度上浪费了救护车资源。特别处于城市早晚高峰时期，由于缺乏准确的和全面的道路状况信息，很多情况下只能凭借司机的感觉“走一步看一步”，这种摸索探路式的转运病人方式是对生命的不重视，不负责，不尊重。车联网技术可以从根本上解决现有调度方式的盲目性和无序性。因为其高效地信息共享和交流系统能够将城市每个角落的道路信息及时的反馈给调度中心。根据这些数据，调度中心可以对全市的所有救护车进行动态调度，缩短以往静态调度的间隔，提高车辆使用率和效率，动态路径规划为动态调度提供了有力的保障。交通道路网络的信息特点具有高动态性、区间通行的不稳定性。这些不确定性给调度工作带来了巨大的挑战。动态路径规划可以根据实时获取的信息快速的调整车辆行驶路线，确保了最优路径的有效性，同时利用改良遗传算法为救护车进行最优路径搜索可能可以提高算法求解速度。
3. 模型建立
3.1. 模型描述
根据数学家莱昂哈德·欧拉的图论，可以将算法所涉及的各个研究对象建立在一张一维图中。为了给算法提供一个便利的运行平台。所建模型做如下限定。
图中节点表示道路交叉路口，同时设置所有节点有且仅有四个相邻节点且连通。当道路路口出现超过四个行车方向时，可引出另一个节点并把这两节点之间的阻抗赋为零。即两个节点最多可以表示一个道路口的六个通行方向。
节点之间的数值表示区间旅行时间。具体计算根据道路阻抗等相关数据进行。道路实时阻抗由车联网信息网络获取，保证调度过程中的信息的可靠性。
起点为闲置救护车所在位置并非医院所在位置。动态调度为救护车任务的连续性提供了良好的保障。
终点为患者所在位置。
由上述方法，可将城市道路网络抽象化为一个n阶矩阵。区间旅行时间存入数组，其中从第i行第j列至第i行第j + 1列耗时为ax，，若从第i行第j列至第i + 1行第j列，则。第m辆救护车由所处位置到终点的耗时Am可以根据N中动态数据算出。当接受到用车请求时，由搜索算法求得。搜索结果为当前道路网络中旅行时间最短路径或在搜索代数结束时已经寻找到的耗时最短路。模型如图1。
3.2. 模型技术支持
动态路径规划过程中技术支持包括：GIS(地理信息系统)、IOV(车联网)、GPS(全球定位系统)和GPRS(通用分组无线服务技术)。通过改良的遗传算法将各个部分有机整合达到最优动态路径诱导的目的。以下将简略介绍各部分系统在算法中扮演的角色和作用。
Figure 1. Diagram of the model
图1. 模型示意图
地理信息系统结合地理学和地图学，广泛应用于不同领域。此系统为诱导算法提供地理数据包括道路信息、医院及病人位置信息等。
车联网是利用先进的传感技术、网络技术、计算技术、智能技术对道路和交通实现全面感知，准确了解车辆具体状态如：行驶方向、坐在位置等对交通优化有利的实时数据。车联网为算法提供实时道路区间阻抗，为救护车动态路径规划提供可靠的数据。
通过全球卫星定位系统，诱导算法可以获得救护车的精确位置信息，为诱导规划提供依据。
实际操作过程中，通用分组无线服务技术负责信息传递实现救护车与算法间的实时通信。
4. 求解算法
4.1. 算法简介
基本遗传算法[3](标准遗传算法或简单遗传算法，Simple Genetic Algorithm, SGA)是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(Genetic Operator)：比例选择算子、单点交叉算子、基本位变异算子。基本遗传算法有下列4个运行参数需要预先设定，即M, T, Pc, Pm。其中M为群体大小，即群体中所含个体的数量，一般取20~100；T为遗传算法的终止进化代数，一般取100~500；Pc为交叉概率，一般取0.4~0.99；Pm为变异概率，一般取0.0001~ 0.1。
算法改良主要体现在遗传编码方式、适应性计算和历史数据的处理。
算法数据主要从车联网中获取，包括道路路况及通行状况，及全部救护车的行驶状况。通过以上数据可以计算获得道路区间阻抗和动态路径规划的始点。
改良遗传算法流程图如图2。
4.2. 遗传编码方式
任意一个复杂的城市道路网络都可抽象成一个N*N的矩阵。矩阵中的每一个节点(除去部分边缘节点外)都具有四个通行方向，如图3。应用于动态路径规划的遗传算法的传统编码方式为，随机生成节点序列或方向序列。但此类编码方式效率极低，产生大量无效序列如：无法到达目的地、超出矩阵范围等，严重影响到算法的效率。
改良遗传算法编码方式[4]采用方向序列。但与以往编码方式不同，改良编码方式增加动态方向诱导因
Figure 2. Flowchart of improved genetic algorithm
图2. 改良遗传算法流程图
Figure 3. Diagram of a point and directions
图3. 节点方向标号示意图
子，即初始位置与终止位置的相对坐标。方向序列随机生成过程中，每产生一个新的方向，都应将方向序列翻译为结点序列并进行动态方向诱导因子的重新计算，直至动态方向诱导因子为(0, 0)。另外通过改变各个方向的随机概率，动态方向诱导因子具有影响方向序列的作用，例如：当动态方向诱导因子为(2, 1)时，可以适当调整为上行概率和右行概率分别为0.275，下行概率和左行概率分别为0.225。为避免出现圈或往复行驶在同一区间，可将来行的逆方向概率设为零(同时边缘节点亦可采用类似方式避免超出行进范围)，将其原有概率平均分配到其余方向上。另外方向概率的调整幅度应根据城市道路状况自行决定。如若调整幅度过大，可能造成算法早熟，最终无法获得最优解。
综上所述，基于选择方向的编码方式，采用1~4的综合序列来表示染色体。
除随机生成可能解之外，改良遗传算法具有类似免疫算法的记忆功能。即每次求得最优解后将其记录，再次遇见类似调度方案时，直接将原有解添加至种群中。加速算法收敛，达到提高效率的目的。
4.3. 适应度计算及选择方式
适应度主要用于描述染色体序列在当前环境中的竞争力程度，对解的优劣性进行评估，为解的选择提供一定的量化标准。适应性函数[2]为：
(1)
其中：f：为染色体的适应性；为惩罚因子(若出现回路或通过非连通区间，则赋一个较大值)；d为通过车联网获得的实时道路交通阻抗。
染色体选择采用赌轮盘法，在传统选择方式的基础稍加改动，避免算法早期过早成熟和算法后期滞涨。改动方式如下：将获得适应度进行排序，将位于前17%部分的复制三次，紧接的33%部分复制两次，最后剩余50%不复制。 最大可能保留产生的优良品质。选择数量为上一代复制前染色体总数量的0.5倍。
4.4. 交叉运算
交叉运算过程直接影响到算法最终能否获得最优解或相对最优解。传统交叉方式沿用基本遗传算法交叉方式，即通过随机方式交换不同序列之间的额遗传信息。这种交叉方式不适用于有较强连续性的遗传信息改良交叉方式采用定向选择交叉，即通过对节点序列的搜索，寻找出一个OD对中的不同通行路径进行交叉，这样能有有效的避免因交叉产生的无效序列，在一定程度上能够加快算法收敛。
为了增加交叉效率，避免近亲繁衍造成算法滞涨，进行交叉两个染色体相识度要低于0.5。相识度[5]定义如下：
(2)
其中：；n为两染色体的相同部分长度；l为染色体长度。
4.5. 变异运算
变异在自然进化中扮演着举足轻重的作用。如若没有变异，生物无法进化到当今如此的多样化程度。本算法变异方式为随机产生偶数个方向插入方向序列中，并且保证连续的两个方向序列不为相反方向，翻译为节点序列进入种群，变异前后染色体均保留。其中插入至方向序列的偶数个方向应保证其组合为零，即上行数量应与下行数量相等，同理左行数量应与右行数量相等。此种变异方式能最大程度保证变异后的方向序列的有效性，减少无效路径的产生。传统变异仅随机添加几个方向序列至原序列中，经测算当仅增加两个方向变量，其变异后序列有效性仅为0.0625，随着变异数量的增加，其有效性呈现急剧下降。
与基本遗传算法相类似，变异概率自行根据实际情况设定。变异改良设定应该充分考虑道路网络、救护车需求量、路况等影响因数，建议通过实验的方式获取。
5. 算例
通过算法示例说明改良遗传算法应用于救护车动态调度的优越性。为避免范例过于复杂，算法示例使用9个节点的矩阵。如图4所示。各区间阻抗随机产生已标注于图上，假定区间为双向通行。起点为一号节点终点为九号节点。
算法参数设定如下，初始种群设定为4个，遗传代数上限为20代，个体变异概率0.05，动态方向诱
Figure 4. Diagram of the system of roads
图4. 道路示意图
Table 1. The possibility of the different directions in various points
表1. 节点方向概率
(注意：节点方向概率是通过历史统计数据生成的，与实时阻抗并无直接关系)。
导因子区间值设定为[0.05, 0.01]，节点方向概率设定如表1。
经计算，改良算法随机出现最优解的概率约为基本算法出现最优解概率的18倍。另一方面，通过动态方向诱导因子的诱导，产生的随机解较原始生成方式更逼近最优解。使用改良后的遗传算法求得最终路径为：1---4---5---8---9。与Dijkstra算法求得结果相同。原始算法平均所需收敛代数为16代，改良遗传算法平均收敛代数为12代。经过15次有效计算比较，收敛代数如图5所示。算法效率提高40%左右。
6. 总结
改良后的遗传算法添加动态方向诱导因子，其核心思想就是，通过对城市道路的长时间研究积累，利用司机经验或观察结果诱导道路生成，使得生成过程具有一定的方向性，避免了盲目性。一定程度上提高了算法效率。值得注意的是，如果过分强调或突出经验在道路选择中的作用，可能会使算法失去意义。因
Figure 5. The comparison of tow algorithms in demanding generation
图5. 两种算法所需求解代数比较
此，动态方向诱导因子的设定应根据实际城市交通状况和道路结构。
改良遗传算法中，添加了染色体相似度判断为了防止近亲繁衍。近亲繁衍对于遗传算法危害极大。因为其产生的后代多与父代相识，达不到多样组合求解的目的，使得计算资源大量浪费。算法总体进度停滞不前，极大地延长了算法求解时间。
另外，改良后的遗传算法增加类似免疫算法的记忆功能。新增功能可以使算法随着使用时间的增加，求解速度越来越快，特定区域适应性越来越强。
相比基本遗传算法，改良后的算法，在性能上明显优于基本算法。
参考文献 (References)
- 滕继涛, 张飞舟, 李跃鹏, 等 (2003) 智能交通系统中车辆调度问题的遗传算法研究. 北京航空航天大学学报, 1, 13-15.
- 诸彤宇, 王家川, 陈智宏 (2011) 车联网技术初探. 公路交通科技(应用技术版), 5, 266-268.
- 曳永芳, 杜永清, 行小帅 (2010) 一种抑制早熟收敛的改进遗传算法. 山西师范大学学报(自然科学版), 2, 24-28.
- 李春元, 魏武, 谢赛, 等 (2007) 基于改进遗传算法的最优路径求解. 交通与计算机, 5, 88-92.
- 曹道友, 程家兴 (2010) 改进交叉算子和变异算子抑制GA算法早熟. 科学技术与工程, 6, 1540-1542.
NOTES
*通讯作者。