蚂蚁算法在复杂性运输路径问题中的应用

贾春梅

摘要:车辆路径问题中,行驶路线往往取决于一系列约束条件,如配送中心个数,货物需求量,交发货时间,车辆容量限制等。要想达到一定的目标,如路程最短,费用最小,时间尽量少,车辆尽量少等,就得借助于合适的算法去解决实际的问题。蚂蚁算法在解决著名的旅行商(TSP)问题上已取得了很好的成效,目前已陆续渗透到其他问题的求解上。文章主要针对多车场多车型车辆路径问题,用蚁群算法以及蚁群算法的优化算法去解决一些实际问题。

关键词:车辆路径问题;蚂蚁算法;优化算法

中图分类号:O227文献标识码:A

Abstract: In the vehicle routing problem(VRP), the traveling route usually depends on a series of restrictive conditions, such as the number of the distribution centers, the quantity of the demanding freight, the delivery time and the vehicle capacity constraints. To achieve a certain goal, such as the shortest distance, the minimum cost, the least time and the vehicles as few as possible and so on, we have to use appropriate algorithms to solve practical problems. Ant algorithm has achieved a good result in solving the well-known traveling salesman problem(TSP), now it has been infiltrated into the other problems' solving. In this paper, mainly for Multiple-depot and Heterogeneous-vehicle vehicle routing problems, we adopt ant algorithm and its improved method to solve some practical problems.

Key words: VRP; ant algorithm; optimization algorithm

1研究背景

根据物流管理中对运输车辆优化调配的要求,1959年,Dantzig和Ramser[1]首先提出了车辆路径问题(Vehicle Routing Problem,VRP)的数学模型。近几十年来,VRP[2]一直都备受学术界关注。VRP和TSP一脉相承,同属组合优化领域的NP-hard 问题,但因VRP的约束条件众多,因而其复杂程度也就远远高于TSP[3-4]。特别是对于大规模的VRP问题,寻找到高效的精确算法的可能性不大,因此,寻求高效近似的优化算法是非常必要和现实的。国内外专家和学者对VRP及其求解方法进行了大量的研究,提出了许多关于不同类型VRP的不同的求解算法。但往往是解决单一性问题,对复杂问题还缺少深入地研究。

2车辆路径问题的分类

车辆路径问题是从任务目标、车辆载货状况、车场数目、车辆类型、车辆对车场的所属关系、是否有时间限制等多个方面进行分类分析,然而现实生活中,往往是多个类型组合的问题。本文结合不同的分类方式,根据蚁群算法以及改进的蚁群算法求解以下四类车辆路径问题:(1)装卸混合问题;(2)多车场多车型路径问题;(3)开放式车辆路径问题;(4)带时间窗限制的车辆路径问题。本文重点分析其中的多车场多车型路径问题。

3蚂蚁算法的原理和算法设计

蚂蚁算法(ant algorithm),是一种源于昆虫世界的新的仿生类算法,作为通用型随机优化方法,其思想吸收了自然界蚂蚁群体的行为特性,通过其内在的搜索机制,在一些典型的困难组合优化问题求解中取得了成效,展现出了广阔的发展前景。研究表明,对于解决有多种约束条件的VRP,蚂蚁算法相对于其它一系列算法,有其更大的优势。本文侧重于运用蚁群算法以及改进的蚁群算法去解决存在一系列约束条件的各类车辆路径问题[5-6]。

3.1蚂蚁行为描述

根据仿生学家的长期研究发现:蚂蚁运动时会通过在路上释放出一种信息素来寻找路径。结合图1来形象说明:

图1中,设A点是蚁巢,E点是食物源。HC为障碍物。一开始从A点到达E点的路径选择是随机的,BHD和BCD路径上都存在数量相等的蚂蚁,显然蚂蚁通过BCD的路径时间较短,所以在该路径上的信息素浓度就相对比较大,后来的蚂蚁就会选择信息素浓度较大的路径。随着时间的推移,蚂蚁将会以越来越大的概率选择路径BCD,最终将会完全选择路径BCD,从而找到由蚁巢到食物源的最短路径。蚂蚁算法的优越性包括:分布式计算、自组织性、正反馈、启发性、较强的鲁棒性。

3.2基本蚂蚁算法的数学模型

假设:有n个城市点需要访问,共有m只蚂蚁,被放置于仓库位置,蚂蚁k从i点出发选择下一个要到达的城市j点,选择主要依据于以下两点:

(1)τt,t时刻从城市i到j路径上残留的信息素浓度。

(2)η由城市i转移到j的可见度,又称启发信息。算法给出在t时刻位于城市i的蚂蚁k选择城市j作为目标城市的概率是

Pt=(1)

令tabuk=1,2,…,m为每只蚂蚁保存的一个禁忌列表,用于记录蚂蚁k当前已经访问过的城市,而N

=0,1,2,n-1-tabu则用来记录到目前为止还未被访问过的城市,α为信息素的相对重要程度,β为启发信息的相对重要程度。

当一只蚂蚁完成对所有城市的访问后,信息素开始局部更新,公式如下:

τt+1=1-ρτt+τρ(2)

式中τt表示原来i、j之间的路径上的信息素浓度,τt+1表示经过一个时间单位后i、j路径上的信息素浓度,ρ定义为信息素的挥发度,一般取为0,1,则1-ρ即为信息素的残留度,τ为路径上的信息素初始浓度,一般设定为一个常数C。

在m只蚂蚁全部完成对所有n个城市的访问后,对残留信息进行全局更新处理,更新公式如下:

τt+n=1-ρτt+Δτ(3)

式中τt+n表示经过n个时间单位后,i、j路径上的信息素浓度,Δτ为蚂蚁k在时间段t 到t+n的过程中在路径i、j上留下的残留信息素。

4基于蚂蚁算法对多车场多车型车辆路径问题(MDMHVRP)的研究

(1)研究现状

在当前物流领域中,对车辆路径问题的研究主要集中在单车场问题上,对多车场车辆路径问题的研究尚不成熟[7]。由于物流行业配送货物的多样性,在研究单车场问题上也是结合了多车型的实际情况。为节约物流配送费用,针对单车场多车型路径问题存在的不足,本文试着对多车场多车型车辆路径问题(Multi-depots Meta-heuristic Vehicle Routing Problem, MDMHVRP)进行了探讨,提出运用自适应最大—最小蚁群算法(adaptive max-min ant colony algorithm, A-MMACA)来解决问题。

(2)MDMHVRP 的数学模型

本文着重考虑了多个车场下运用多种车型[8]进行配送的运输问题,试建立数学模型如下:

配送货物由H辆车从m个车场向n个客户点配送。配送任务可用一个加权图GV,E来表示,其中节点集V

=1,2,…,n, n+1,…,n+m,V的前n个节点为客户点,后m个节点为车场点;E=d|i,j∈V代表从节点i到节点j的行驶路径集合。λ表示路况对配送车辆的影响。标准路况下,λ=1,好于标准路况则λ<1,反之则λ>1,路况系数乘以配送点之间的实际路径长度d,就是考虑了路况影响之后的等价路径长度;L是一条可行路径,fL表示该路径对应的总费用;客户i点的需求量为q;Q为车辆h的最大容量;客户点i的重要性用权值Φ来表示;客户i点的时间窗为a,b;t为车辆h从客户i点到客户j点的行驶时间(或代价);车辆在客户点i服务所用时间s=s+ξqs=0,它包括固定服务时间s和可变服务时间ξq(用需求量q的系数倍表示);s是一个决策变量,表示车辆h到达客户点i的时刻。

(3)求解MDMHVRP的算法

1)多车场多车型的选择步骤

①把各车场中每辆车的信息(所属车场、车辆编号、车辆型号等)存入一个结构体,结构体的每一个数据表示车辆所在车场的编号,第二个数据表示车辆在该车场内的编号,第三个数据表示车辆型号,不同的型号代表不同的车辆容量。这样各车场中的车辆就形成了一个车辆序列。

②搜索最适合当前配送任务的车场。

③当搜索过程选中某一个车场时,抽出此车场中车辆的序列。

④按车型从小到大顺序进行排列,小车型优先,然后依次派出较大车型。

⑤把车辆序列中车型以约束形式加入路径,控制路径的组成。

如果车场2中车辆的型号为1、2、4,路径初始解为0—4—5—2—0—1—3—0—7—6—0,则车场0的插入点是在1、2、4这个序号顺序的车辆的容量限制的影响下产生的,即0—4—5—2—0要满足车型1的车辆容量要求而路径0—1—3—0要满足车型2的车辆容量限制。同样,其他的性能指标,如不同车辆的最大运行距离、速度大小等都可以以这种形式加入,来影响初始解的产生和优化[9]。

2)自适应最大—最小蚁群算法应用步骤

步骤1以较早的服务开始时间优先服务的规则产生一个可行解fL。

步骤2根据公式

(4)

进一步确定τ、τ,其中ρ表示信息素的挥发系数、fL表示当前较好解所对应的费用、n表示客户点(节点)个数,τ=1nfL且满足τ≤τ≤τ。此时Δτ=0, N=0, Lr=0,在接下来的步骤一旦信息素更新后,以公式

(5)

重新确定τ, τ。以便避免过早陷于局部最优解。

步骤3将k只蚂蚁均匀分布到各客户点。

步骤4用状态转移概率公式(6)计算蚂蚁k的状态空间转移概率,选择下一个目标城市。

P=(6)

步骤5应用局部信息素更新式:

(7)

进行信息更新,探索子路径。其中,Y表示第k只蚂蚁到达节点i之前已有Y只蚂蚁经过i点,有y只蚂蚁选择了有向弧段i,j,yY表示有向弧段i,j的蚂蚁吸引力,Q表示蚂蚁每次释放的信息量。

步骤6判断Lr

步骤7输出当前所有蚂蚁的路径,更新禁忌表,保留最优解。

步骤8判断是否遍历所有节点,是就继续步骤9,否则返回步骤4。

步骤9以信息素水平更新式

τ=1-ρτ+w-μ+1Δτ+wΔτρ∈0,1 (8)

对最好蚂蚁进行全局更新,保留全局最优解,禁忌表清空。其中,w表示k只蚂蚁在一个循环旅行之后,根据旅行总费用按递增升序排列,排名前w位的精英蚂蚁数量,一般取3～6之间的整数,只有路径i,j被排名第μ1≤μ≤w的最好蚂蚁利用时,其信息才增加w-μ+1Δτ,而Δτ=1fL, fL为第μ最好解的路径费用。此时所有当前最好路径上的信息素都被加强wΔτ, Δτ=1fL, L为全局最优解对应的长度。

步骤10判断N=N是否成立,成立则输出最优解并结束,否则返回步骤3进行第N+1次的循环。

5总结及展望

当前,物流业正朝着全球化、信息化、一体化发展,正积极融入到国民经济的各个产业链中,物流系统中的配送,也显示出了越来越重要的作用,而其中的车辆路径问题随之成为了物流配送中的核心问题。本文的重点是根据车辆路径问题的不同方面和侧重点进行分类,在前人的研究基础上对四类车辆路径问题中的多车场多车型问题进行了深入的研究,并用改进的蚁群算法进行求解。蚁群算法虽作为一种全新的仿生优化算法,但研究中更多是依靠试验和经验,而没有定理来确定,因此在改进方法上仍有很大的空间等待完善,比如关于参数的设置等。另外,文中所考虑的实际的随机不确定性因素很少,今后要进一步加强对随机不确定性条件下的车辆路径优化的研究,综合尽可能多的实际因素去考虑最优车辆路径的选择问题。只要积极朝着关键性的问题进行突破,相信蚂蚁算法会有更加广阔的发展空间。

参考文献:

[1] Dantzig G B, Ramser K B. The Truck Dispatch Problem[J]. Operation Research, 1959,6:81-89.

[2] 李相勇. 车辆路径问题模型及算法研究[D]. 上海:上海交通大学,2007.

[3] 齐少安,宋齐军. 基于TSP模型的物流配送中心车辆路径优化[J]. 邮电设计技术,2006(6):62-64.

[4]M Dorigo and L M Gambardella. Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem [J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[5] Reimann M, Doerner K, Hartl RF. D-Ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem[J]. Computers & Operations Research, 2004,31(4):563-591.

[6] 郭倩倩. 蚁群算法的改进及其在车辆路径问题中的应用[D]. 成都:西南交通大学,2007.

[7] 章琦. 蚁群算法在车辆路径问题中的研究[D]. 学位论文,2006.

[8] 叶志坚,叶怀珍,周道平,等. 多车型车辆路径问题的算法[J]. 公路交通科技,2005,22(5):147-151.

[9] 刘敏. 多目标遗传算法在车辆路径优化中的应用研究[D]. 湘潭:湘潭大学,2006.