多目标蚁群算法城市车辆调度站部署的研究*

黄兆年 李海山 赵 君

(武汉数字工程研究所 武汉 430205)



多目标蚁群算法城市车辆调度站部署的研究*

黄兆年 李海山 赵 君

(武汉数字工程研究所 武汉 430205)

因为蚁群算法在解决NP难问题有很多优势,正反馈机制可以引导整个系统向最优解的方向进化,最后得出最优解,来解决国内城市运营费用非常大、车辆调度站和交通枢纽部署不合理的问题。

蚁群算法; 车辆调度站部署; 运营费用

Class Number TP301

1 引言

车辆调度站部署问题关键在于部署车辆调度站到城市的交通节点上,使整个交通的总体车流量达到最小,同时使整个交通系统的运营费用也达到最小。

假设武汉市交通枢纽的数目为M,车辆调度站的数目为N,车辆调度站部署到交通枢纽的解空间为MN,是一个类似于装箱问题的NP-hard问题[3],需要找到一个近似优化解。很多启发式算法被提出用来解决这个问题,比较典型的为贪心算法。本文将车辆调度站部署问题定义为一个多目标优化问题,同时优化两个目标:最小化的交通枢纽的数量来优化武汉庞杂的交通问题;最小化车辆来改善武汉市公交车的总车辆流量。

2 问题建模

设车辆调度基站的集合为CAR={car1,car2,…,carn},交通枢纽集合TRANS={trans1,trans2,…,transm},交通枢纽总数为m。调度基站部署到交通枢纽的方案为一个映射函数f(x),其中x为调度站,函数值为调度站部署的交通枢纽。

2.1 交通费用模型

为了充分利用多维资源,第j个交通调度站用定义为人员总费用和车辆的运营费用,具体描述为

(1)

设yj表示车辆调度站i是否放置在交通枢纽j上,则交通线路上所有交通枢纽的运营费用为

(2)

2.2 城市交通线路流量模型

相邻交通枢纽间车辆流量用n×n矩阵表示,车辆调度站间的距离用m×m矩阵表示,具体描述为

其中,dij为交通枢纽i发送到交通枢纽j的车流量,cij为调度站i到调度站j的距离。

那么整个交通系统网络总流量为

(3)

2.3 多目标优化

本文优化目标包含最小化交通枢纽运营费用和最小化网络总流量,因此将车辆调度站放置问题建模为一个多目标优化问题。具体描述为

(4)

(5)

Subject to:

yi,xij∈{0,1} ∀j∈{1,…,m} and ∀i∈{1,…,n}

其中,第一条限制条件表示yj、xij的取值范围,0为否,1为是;第二条限制条件表示一个车辆调度站只能放置到一个交通枢纽上。

3 改进蚁群算法优化

3.1 改进ACO算法

蚁群算法(Ant Colony Optimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在其博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。

3.2 信息素定义

信息素表示车辆调度站放置到指定交通枢纽上的支持率。信息素强度越大越选择当前交通枢纽。改进ACO算法信息素包含两种信息素,分别为数据中心交通枢纽资源浪费信息素和网络总流量信息素。

交通枢纽资源浪费信息素初始值和交通网络总流量信息素初始值分别为

(6)

(7)

其中,W0为初始车辆调度站放置方案下根据式(2)计算得到运营费用,T0为初始车辆调度站放置方案下根据式(3)计算得到的整个交通网络车辆总流量,i为车辆调度站,j为交通枢纽。

3.3 启发信息定义

启发信息表示将车辆调度站放置到指定交通枢纽的期望程度。使用网络总流量增加值ΔT来表示启发信息。计算方法如下:

算法1 总流量增加值计算。

输入:待放置的车辆调度站A,考察的交通枢纽B;

输出:交通总车流量增加值ΔT。

步骤:

1) 令ΔT=0;

2) 遍历dAj(j=1,2,…,nandj≠A),如果车辆调度站j已放置,ΔT=ΔT+dAj×cBf(j);

3) 遍历diA(i=1,2,…,nandi≠A),如果车辆调度站i已放置,ΔT=ΔT+diA×cf(i)B;首先假设车辆调度站放置到指定交通枢纽上,然后根据式(2)计算当前交通枢纽的总费用。

为了兼顾考虑最小化交通枢纽资源浪费和最小化网络总流量,启发信息计算公式为

(8)

其中,i为车辆调度站,j为交通枢纽。启发信息越大,越大概率选择该交通枢纽放置车辆调度站。

3.4 状态转移规则

蚂蚁在车辆调度站i选择交通枢纽j的规则为状态转移规则的定义如下:

(9)

其中,i为车辆调度站;j为交通枢纽;τij,w的初始值用式(6)计算;τij,t的初始值用式(7)计算;启发信息ηij使用式(8)计算;Ωk(i)为满足车辆调度站i需求的所有交通枢纽集合;σ是在每次选择中生成的0到1范围内的随机数,是两种信息素相对重要性系数,可以增强对解空间的搜索、避免陷入局部最优解;α为信息素因子;β为启发信息因子;q0为状态转移概率,是0～1范围内的实数。

每步选择时,生成0～1范围内的一个随机数q,当q≤q0时,在满足车辆调度站i资源需求的交通枢纽集合中,根据式(10)选择具备最大值的交通枢纽;当q>q0,随机选择一个满足车辆调度站i资源需求的交通枢纽,增强了搜索的随机性且降低了计算复杂性。

3.5 信息素局部更新规则

在蚂蚁每一步搜索完成时,都需要对该步信息素进行更新,这种规则为信息素局部更新规则。良好的信息素局部更新规则可以有效地减少信息素,避免陷入局部最优解。交通枢纽运营费用和交通总体流量信息素局部更新规则计算公式为

τij,w(t)=(1-ρl)×τij,w(t-1)+ρl×τ0,w,

τij,t(t)=(1-ρl)×τij,t(t-1)+ρl×τ0,t

(10)其中,ρl为信息素局部蒸发系数,取值范围为0～1。

3.6 信息素全局更新规则

在蚁群每一次迭代完成时,需要对Pareto[4]解集中所有最优解构建的车辆调度站放置方案进行信息素更新,更新规则为信息素全局更新规则。交通枢纽资源浪费信息素全局更新规则和网络总流量信息素全局更新规则计算公式如下:

τij,w(t)=(1-ρg)×τij,w(t-1),

τij,t(t)=(1-ρg)×τij,t(t-1)

(11)

其中,ρg为信息素全局蒸发系数,取值范围为0～1;λ为当前迭代过程Pareto解集中最优解的个数。

3.7 算法描述

下面介绍改进ACO算法的具体流程。

基于多目标蚁群优化的车辆调度站放置算法的步骤如下:

2)NA个蚂蚁分别建立车辆调度站放置方案。每个蚂蚁建立方案过程:(1)随机排列车辆调度站表、交通枢纽表;(2)响应车辆调度站表中一个车辆调度站放置请求,根据式(9)为车辆调度站选择合适的交通枢纽,放置车辆调度站到该交通枢纽上,从车辆调度站表中删除该车辆调度站;(3)根据式(11)更新该步的两个信息素τij,w(t)和τij,t(t);(4)如果车辆调度站表非空,返回(2),否则方案建立过程结束。

3) 根据交通枢纽资源浪费最小化和网络总流量最小化两目标,评估步骤2产生的NA个解,更新Pareto最优解集合P。

4) 遍历P中所有最优解,根据式(6)、式(7)分别对交通枢纽资源浪费信息素τij,w(t)和总车流量信息素τij,t(t)进行全局更新。

5) 迭代次数加1。如果迭代次数小于迭代次数,跳到步骤2);否则跳到步骤6)。

6) 算法结束,输出Pareto最优解集P。

4 数据实验及分析

上述算法在Java平台上实现,在XP环境下运行,实现了改进ACO算法和FFD算法。仿真实验使用100个车辆调度站,100个交通枢纽,1个车辆流量矩阵,1个交通枢纽距离矩阵。通信目的虚拟机随机选择,交通枢纽的车辆流量是[1,100]范围内的随机整数,由此生成车辆流量矩阵。设置α=1,β∈{1,2},q0∈{0.1,0.4,0.6,0.9},迭代次数为100,运行10次取平均结果,如图1所示。

图1 结果图

如图1结果所示, 1) 贪心算法得出的结论比蚁群算法得出的结果要大; 2) 两个蚁群算法都收敛,而且这两个矛盾的变量存在多个近似最优解,决策者可以根据自己的需要来选择一个最佳的方案。试验中进行多次迭代,图1只显示了两次迭代的结果。不同的迭代会产生不同的方案,可以通过多次迭代来产生很多个近似最优解,这样结果更加准确。从其他文献中知道q0=0.9时算法比其他参数组合算法收敛性好,本文直接设置q0=0.9,但是作为实验,可以设置不同的q0,来观察算法的收敛性。

5 结语

本文首先介绍了蚁群算法在多目标优化中的研究,并且结合现在普遍的城市交通比较复杂的NP难问题,通过Pareto多目标优化算法得出多个相似最优解,来解决这个NP难问题。当问题比较复杂,不能明确判断是否到某一代就进化到达到最优,当种群中个体的适应度值在一定代数内没有提高时,就让这个算法停止,多目标优化得到的不是一个解,而是Pareto最优解的集合。

[1] 王晶,方伟,陈静怡,等.云计算环境下的自适应资源管理技术综述[J].上海市重点学科基金项目,2011,9(22):172-174.

[2] 李强,郝沁汾,肖利民,等.云计算中虚拟机放置的自适应管理与多目标优化[J],计算机学报,2011,12(1):5-8.

[3] 张锦,谢克明.蚁群算法在医药物品配送路径优化中的应用[J].太原理工大学学报,2009(6):600-603.

[4] 徐沪萍,姚念.基于物联网的医药物流管理信息系统研究[J].武汉理工大学学报(信息与管理工程版),2013(3):361-364.

[5] 熊道勇,肖人岳.遗传算法和蚂蚁算法混合求解旅行商问题[J].科学技术与工程,2009(10):5817-5819.

[6] 张文洁,邓卫.基于蚁群算法的动态路径选择问题[J].交通科技与经济,2009,11(1):51-53.

[7] 谷远利,李善梅,邵春福.基于蚁群算法的交通控制与诱导协同研究[J].系统仿真学报,2008,20(10):2754-2761.

[8] SONG Ying, WANG Hui, LI Yaqiong, et al. Multi-tiered ondemand resource scheduling for VM-based data center[C]//Shanghai: Intemational Symposium on Cluster, Cloud and Grid Computing,2009:148-155.

[9] Vasileios Pappas. ZHANGu Improving the scalability of data center networks with traffic-Aware virtual machine[C]//SanDiego, CA: IEEE INFOCOM,2010:1-9.

[10] Deb K, Thiele L, Laumanns M, et al. Scalable multi-objective optimization test problems[C]//Fogel DB, ed. Proc. of the IEEE Congress on Evolutionary Computation, CEC 2002. Piscataway: IEEE Service Center,2002:825-830.

A Multi-objective Ant Colony Optimization Algorithm for Vehicle Scheduling Transportation Placement

HUANG Zhaonian LI Haishan ZHAO Jun

(Wuhan Digital Engineering Institute, Wuhan 430205)

Because the ACO in solving the NP hard problems has many advantages, positive feedback mechanism can guide the whole system evolution in the direction of the optimal solution. Finally optimal solution is obtained to solve the domestic urban traffic operating expenses, vehicle scheduling transportation hub unreasonable deployment problem.

ant colony optimization, vehicle scheduling transportation hub, urban traffic operating expenses

2015年2月5日,

2015年3月29日

黄兆年,男,硕士研究生,研究方向:系统结构,容错技术。李海山,男,博士,研究员,研究方向:容错技术。赵君,男,博士,高级工程师,研究方向:网络通信。

TP301

10.3969/j.issn1672-9730.2015.08.012