摘　要：交通资源规划是一种比较典型的组合优化问题，新型的仿生算法——蚁群算法，由于具有正反馈性、鲁棒性、并行计算、协同性等特点，非常适合于解决交通资源规划问题。针对出租车路径规划问题的特点以及蚁群算法在这方面应用的一些不足，提出了一种改进的蚁群算法。根据同一蚁群的信息素相互激励，不同蚁群之间信息素相互抑制的原理，该算法实现了出租车资源的合理分布。
    关键词：交通资源规划；出租车路径规划；蚁群算法；多蚁群

    随着经济的发展和城市的急速扩张，城市交通问题一直是制约很多大城市发展的问题之一。
    出租车路径规划问题的背景是出租车公司如何调度所属的出租车完成顾客提出的具体服务要求。对于某个出租车公司，在出租车资源需求不变的情况下，如何减少出租车的空驶时间，减少预期乘客等待时间，取决于出租车在空驶时的路线运行行为^[1]。
    出租车调度的优化目标就是让所有出租车在完成特定的交通需求前提下，使得所有出租车所行的总里程数最小，继而达到总费用最低和节省能源的目标^[2]。
1 基本蚁群算法原理
    蚁群算法是通过对真实蚁群行为研究而提出的。仿生学家经过长期研究发现蚂蚁在寻找食物时，能在其经过的路径上释放一种特殊的分泌物——信息素，使得一定范围内的其他蚂蚁能够感觉到这种物质，且倾向于朝着该物质强度高的方向移动，因此，蚁群的集体行为表现为一种信息正反馈现象：某条路径上经过的蚂蚁数越多，其上留下的信息量也就越多(当然，随着时间的推移会逐渐蒸发掉一部分)，后来蚂蚁选择该路径的概率也越高，从而增加了该路径上信息素的强度。这样最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的流逝而逐渐减少，最终整个蚁群会找出最优路径^[3]。
    目前，人们已总结出蚂蚁在觅食过程中的一些简单规则。假设在t时刻位于节点i的蚂蚁k，利用路径(i, j)上的信息素浓度t_ij(t)，则下一个节点j∈N_i的转移概率p_ij^k(t)可表示为：
   
    其中，allowed_k={0,1,…,n-1}-tabu_k表示蚂蚁k当前能选择的节点集合；tabu_k为禁忌表，记录蚂蚁k已走过的节点；α为信息启发式因子，表示路径的相对重要性；η_ij(t)为t时刻的能见度，反应由节点i转移到节点j的期望程度；β为启发式因子，表示能见度的相对重要性^[4]。
　　同时，为了避免残留信息素过多引起残留信息淹没启发信息，可以规定在一个时间段完成一次循环后，对残留信息进行更新。路径(i, j)的信息素强度τ_ij(t)的更新方程为：
　　
　　其中，ρ为信息素的持久系数(0<ρ<1)，则(1-ρ)为信息素的挥发系数；表示完成一次循环后路径(i, j)上的信息素增量；表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量，一般来说，最基本的取值形式为：
　　
　　(4)式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度，表示第k只蚂蚁在本次循环中所走路径的总长度。
　　由式(1)可知，当η_ij>0时，蚂蚁i按概率从节点i转移到节点j；当η_ij≤0时，蚂蚁i作邻域搜索。也就是，蚂蚁要么转移至其他蚂蚁走过的路径，要么进行邻域搜索，最终蚂蚁走的路径取以前蚂蚁所走路径的最优值。一旦有足够多的蚂蚁对定义区间进行这种地毯式的搜索，这种寻优方式便能逐渐收敛到全局最优解。
2  改进的蚁群算法在出租车路径规划中的实现
2.1 改进蚁群算法的基本原理
　　利用蚁群算法进行交通资源调度是一个比较新的思路。由于交通资源分配属于优化问题，交通资源调度就是在有限的交通资源条件下^[5]，缓解城市交通资源时间和空间分布不均匀的现状，最大限度满足市民对于交通资源的需求。而出租车的调度相比于其他交通资源，有更大的灵活性和可操作性。可以在满足城市各区域市民出行需求的前提下，最大限度减少出租车的空驶时间和路程，减少资源浪费。
　　针对出租车路径规则对比蚁群算法的基本原理，做出如下改进：
　　(1)跟蚁群算法找到单一食物作为蚁群目的地不同，空载出租车需要考虑到各个区域市民的出租车需求量，从而将出租车资源合理有效地分配到这些地区，不仅满足出行需求热点地区市民的交通需求，还要在一定程度上照顾次热点乃至偏远地区市民的出行需求。
　　(2)由于每个交通区域一些固有交通特性不同，相当于信息素的持久系数ρ，例如写字楼集中区域在上下班时间交通需求大，而在其他时间段交通需求则少，因而这些区域信息素持久系数要低，以免大量冗余的信息素残留导致过了交通高峰期后仍有大量出租车赶去系统认为的这些“热点”地区。
　　(3)由于交通需求的特殊性，根据时间而变化的交通需求异常显著。因而在不同时间由区域i转移到区域j的概率，可以根据时间t的变化决定的能见度。
2.2 改进蚁群算法的设计
　　通过以上分析，可以对算法进行如下改进：文中根据不同出租车公司所属的出租车组相互竞争来实现这种交通资源合理分配的规划算法。同一个出租车公司所属的出租车之间通过信息素来进行正向反馈，而不同出租车公司所属的出租车之间则通过信息素相互抑制^[6]。
　　将m个出租车公司假设为蚁群A₁，A₂，A₃，…A_m-1，A_m，t时刻对应的信息素浓度分别为τ(t，1),τ(t,2),τ(t,3)，…τ(t,n-1)，τ(t,n)。则属于蚁群A_n(1≤n≤m)的蚂蚁k由区域i行驶到区域j的转移概率可表示为：
   
    其中，τ_ij(t,n)是t时刻蚁群n在路径(i, j)上的信息素，η_ij(t, n)是t时刻蚁群n在路径(i, j)上的启发程度，由区域交通需求变化量决定，这个量可能发生变化，值越大表明启发程度越高。α为信息启发式因子，表示路径的相对重要性；β为启发式因子，表示能见度的相对重要性；allowed_k表示蚂蚁k未走过且当前能选择的节点集合；表示其他蚁群对蚁群选择路径(i, j)的概率抑制因子之和。θ_ij(t, n)的计算公式如下：
   
    其中，allowed_k表示蚁群A_u尚未走过且当前能选择的节点集合。
    这样，通过多个蚁群在同一路径上的相互抑制，便能有效防止很多蚁群拥挤到同一条路径上。同时，为了保证只有同一个蚁群的蚂蚁才能通过信息素进行正向反馈，因而τ_ij(t, n)的计算公式如下：
　　
　　其中，ρ为信息素的持久系数(0<ρ<1)；Δτ_ij(u)表示完成一次循环后蚁群A_u中的蚂蚁留在路径(i, j)上的信息素增量。表示属于蚁群A_u中的所有蚂蚁在本次循环中留在路径(i, j)上的信息量总和，一般来说，最基本的取值形式为：
   
    (9)式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；L_k表示第k只蚂蚁在本次循环中所走路径的总长度。
    值得注意的是，该改进算法在只对单一蚁群进行规划时退化为传统的蚁群算法。
3  实验结果及分析
    如图1所示，假设a、b、c、d为4个不同区域，取α=1，β=2，ρ=0.7，Q=100，所有路径成本均取1，使用Matlab6.5进行仿真试验。得到每个时段区域b的出租车需求量均为80，区域c的出租车需求量为40，区域d的需求量为20。初始信息素浓度为τ_init=0。设有3个出租车公司所属的出租车数目比为4∶2∶1，则位于区域a的空载出租车路径选择概率分布如图2所示。

 
    观察图2可知：
    (1)当区域a点的空载出租车数量小于20时，选择路径ab的概率为1，而选择路径ac与路径ad的概率为0；
    (2)当区域a点的空载出租车数量大于20小于40时，路径ac上的转移概率开始增大，路径ab上的转移概率开始减小，但此时路径ad上的转移概率仍然为0；
    (3)当区域a点的空载出租车数量大于40小于140时，路径ac和路径ad上的转移概率都增大，路径ab上的转移概率减小；
    (4)当区域a点的空载出租车数量大于140时(即空载出租车供给量大于需求量时)，路径ab、路径ac、路径ad的转移概率接近于80∶40∶20。
    通过试验可进一步得出空载出租车路径选择情况分布图，如图3所示。

    观察图3可知：
    (1)当区域a点的空载出租车数量大于20时，开始有空载出租车选择路径ac；
    (2)当区域a点的空载出租车数量大于40时，开始有空载出租车选择路径ad；
    (3)当区域a点的空载出租车数量小于140时，选择路径ab、路径ac、路径ad的空载出租车数量比例接近于80∶40∶20。
    由此可以看出，改进蚁群算法不仅能有效引导空载出租车转移到能最快找到乘客的交通区域，而且能有效防止过度将交通资源集中于最热点地区，通过改进蚁群算法中蚁群间的相互抑制作用达到将交通资源更合理分布到各个不同交通区域的目的。
    本文将蚁群算法应用到出租车交通资源的路径规划问题，提出一种基于改进蚁群算法的空载出租车路径规划算法，不仅发挥了蚁群算法的正反馈机制的优点，同时也符合现实交通状况中的资源分布需求。蚁群算法在交通资源规划中的应用目前还不完善，本算法的效率和优化度还待进一步改进。
参考文献
[1] BELL J E，MCMULLEN P R.Ant colony optimization techniques for the vehicle routing problem [J].Advanced Engineering Informatics，2004，18(1)：41-48.
[2] JINNIFER L.A computational study of vehicle routing applications[D].Ph.D.thesis，RICE，UNIVERSITY，Huston，1999.
[3] 李士勇.蚁群算法的改进及应用研究进展[J].计算机测量与控制， 2003，11(12)：911-917.
[4] 杨志晓，郭胜国．基于改进蚁群算法的机器人路径规划算法[J]．微计算机信息，2008，7(2)：252-253.
[5] 周涛.基于蚁群算法的车辆优化调度系统[D].成都：电子科技大学，2007.
[6] 肖晓丽，田悦宏，李振.一种基于蚂蚁算法的网络负载分担路由方法[J].计算机应用， 2006,26(7).