内容发布更新时间 : 2024/12/26 13:20:55星期一 下面是文章的全部内容请认真阅读。
遍用奇话酗m昨。,咖㈣。n
基于改进蚁群算法的出租车路径规划算法 谭卫,赖斌
(华南理工大学计算机科学与工程学院,广东广州510006
摘 要:交通资源规划是一种比较典型的组合优化问题,新型的仿生算法一蚁群算法,由于 具有正反馈性、鲁棒性、并行计算、协同性等特点,非常适合于解决交通资源规划问题。针对出租 车路径规划问题的特点以及蚁群算法在这方面应用的一些不足,提出了一种改进的蚁群算法。根据 同一蚁群的信息素相互激励,不同蚁群之间信息素相互抑制的原理,该算法实现了出租车资源的合 理分布。
关键词:交通资源规划;出租车路径规划;蚁群算法;多蚁群 中图分类号:TP24文献标识码:A
Taxi routing algorithm based on improved ant colony algorithm TAN Wei,LAI Bin
(CollegeofComputerScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou510006,Chim,
Abstract:Thephnnmgoftransportation
resourceisaverytypicaloptimizationproblem.Asanovelsimulatedevolutionaryalgorithm,antcolony algorithm has many merits such嬲positive feedback,robust,parallel computing and coordination.So it is very suitable to solve the planning problem oftransportation resource.An impmvM ant colony algorithm WSB presented,which aimed at the character ofthe taxi muting pmblem and the drawback ofant colony system applied in the pt=ming ofthe transportation resource.This algorithm carry out the reasonable distribution oftaxi resoul'e贮,according to the principle of
ants in the sine colony pmmotes each other and ants in different colony restrains each other.
Key words:planning oftransportation resource;taxi muting;ant colony algorithm;multiple ant colony
随着经济的发展和城市的急速扩张,城市交通问 题一直是制约很多大城市发展的问题之一。
出租车路径规划问题的背景是出租车公司如何调 度所属的出租车完成顾客提出的具体服务要求。对于 某个出租车公司,在出租车资源需求不变的情况下,如 何减少出租车的空驶时间,减少预期乘客等待时间,取 决于出租车在空驶时的路线运行行为…。
出租车调度的优化目标就是让所有出租车在完成 特定的交通需求前提下,使得所有出租车所行的总里 程数最小,继而达到总费用最低和节省能源的目标【2l。 1基本蚁群算法原理
蚁群算法是通过对真实蚁群行为研究而提出的。 仿生学家经过长期研究发现蚂蚁在寻找食物时,能在 其经过的路径上释放一种特殊的分泌物——信息素,使 得一定范围内的其他蚂蚁能够感觉到这种物质,且倾 向于朝着该物质强度高的方向移动,因此,蚁群的集体
72 行为表现为一种信息正反馈现象:某条路径上经过的 蚂蚁数越多,其上留下的信息量也就越多(当然,随着 时间的推移会逐渐蒸发掉一部分,后来蚂蚁选择该路 径的概率也越高,从而增加了该路径上信息素的强度。 这样最优路径上的信息量越来越大,而其他路径上的 信息量却会随着时间的流逝而逐渐减少,最终整个蚁 群会找出最优路径【3】。
目前,人们已总结出蚂蚁在觅食过程中的一些简 单规则。假设在t时刻位于节点,的蚂蚁七,利用路径(? 力上的信息素浓度t,/O,则下一个节点J E一的转移概 率pi产(f可表示为:
f 劈(,={
【 一∽一,㈣ ∑k(f]8帆(f】”。 “… 《信息化纵横》2009年第10期 万方数据 锣
应用奇葩Exampie。f Application
其中,allowed7{0,l,…,刀.1}-tabuk表示蚂蚁k当前能 选择的节点集合;tabu.为禁忌表,记录蚂蚁k已走过的 节点;口为信息启发式因子,表示路径的相对重要性; 矸,,(f为t时刻的能见度,反应由节点i转移到节点.,的期 望程度;卢为启发式因子,表示能见度的相对重要性【4】。 同时,为了避免残留信息素过多引起残留信息淹没启 发信息,可以规定在一个时间段完成一次循环后,对残留 信息进行更新。路径(f,力的信息素强度呱f的更新方程为: ru(O=p×%(t-1+△%(2 .—艮 。
△气。乙△巧 (3 其中,P为信息素的持久系数(O<班1,贝lJ(1一动为信 息素的挥发系数;表示完成一次循环后路径(f,,上的信息 素增量;厶露表示第k只蚂蚁在本次循环中留在路径瓴,上 的信息量,一般来说,△《最基本的取值形式为:
△唠=舻涕坝蚂蚁焉慧循环中经过路襁¨?(4 (4式中,Q表示信息素强度,它在一定程度上影响 算法的收敛速度,表示第k只蚂蚁在本次循环中所走路 径的总长度。
由式(1可知,当,7。>o时,蚂蚁i按概率p篡f从节点 礴睾移到节点歹;当tlil≤0时,蚂蚁i作邻域搜索。也就 是,蚂蚁要么转移至其他蚂蚁走过的路径,要么进行邻 域搜索,最终蚂蚁走的路径取以前蚂蚁所走路径的最优 值。一旦有足够多的蚂蚁对定义区间进行这种地毯式的 搜索,这种寻优方式便能逐渐收敛到全局最优解。 2改进的蚁群算法在出租车路径规划中的实现
2.1改进蚁群算法的基本原理