关联运输调度问题的蚁群算法

广东工业大学自动化学院 汤雅连 蔡延光 赵学才

1.引言

车辆路径问题（Vehicle Routing Problem，VRP）最早由Dantzig，Fulkerson和Johnson于1959年提出。VRP问题是一个组合优化问题，而关联物流运输调度问题（Related Vehicle Routing Problem，RVRP）也是车辆路径问题的延伸，所以也属于NP-hard问题。近年来，遗传算法、模拟退火算法、粒子群算法、蚁群算法等现代启发式算法为VRP的求解提供了极大的便利。

蚁群算法[1-3]是解决VRP问题的一种有效的元启发式方法，其中改进的蚂蚁系统[4]有带精英策略的蚂蚁系统（Ant System with elitist strategy，ASelite）、基于优化排序蚂蚁系统（Rank-Based Version of Ant System，SArank）、蚁群系统（Ant Colony System，ACS）、最大-最小蚂蚁系统（Max-Min Ant System，MMAS）以及最优-最差蚂蚁系统（Best-Worst Ant System，BWAS）。蚁群算法[5]的提出，为解决路径规划问题提供了新的思路和解决方法，但是传统蚁群算法与其他进化算法同样存在易于陷入局部最优、早熟收敛等缺陷，为了提高蚁群算法的全局搜索能力，提高其收敛速度，该文提出了保留每代最优解，并自适应改变信息素挥发因子，从而克服传统蚁群算法的不足。

2.问题描述及数学模型的建立

2.1 问题描述

关联物流运输调度问题也是车辆路径问题的延伸，所以具有相似性。问题可以简单描述为，假设给定车场信息以及客户信息（位置和货物需求量等），货物之间的关联系数，车辆信息（载重约束、里程约束和容量约束等），要求合理安排车辆和运输路线，在满足所有客户需求的前提下，使配送成本最低。

2.2 数学模型

第i个客户的货运量为gi（i=1，2，…，l），需要从车场将货物运到客户手中，有车场派出载重量为q的货车若干，已知gi＜q。

预先对需要车辆数进行估计。可以按照式（1）确定车辆数：

式中，[ ]表示不大于括号内数字的最大整数； 0＜α＜ 1，是对装车（或卸车）的复杂程度及约束多少的估计。

以cij表示为从点i到点 j的运输成本（距离、费用、时间等），cij=cji。假设客户i， j之间的距离为：dij。车场编号为0，客户为：i（i=1，2，…，l）。关联系数为：r，rij表示点i处的货物与点j处货物的关联系数。目标为使车辆的总运输距离最短。

定义变量如下：

目标函数式（4）表示总运输距离最短，以cij表示从点i到点j的运输成本并用客户i与 j之间的距离dij作为取值。（5）为车辆行驶距离约束，其中dijk表示车辆k行驶了客户i到 j的路程，n是车辆k服务的客户数目，最大为N。（6）和（7）表示两个变量之间的关系。（8）表示车辆服务客户i后直接行驶到j为其服务。（9）表示每个客户只能由1辆车来服务且每个客户都能得到服务。（10）表示每辆车所运送的货物重量不能超过车辆载重量的限制。（11）表示保证每辆车的客户总数小于等于总客户数目。（12）为关联系数rij的取值约束，当i与j的货物不可用同辆车配送时，应选择其他客户的货物。

3.一种自适应蚁群算法

3.1 基本蚁群算法

设m为蚂蚁数量，dij(i，j=1，2，...，n)表示i与j之间的距离， τij(t)表示t时刻在ij连线上残留的信息素强度。初始时刻，各路径上信息量相等，设τij(0)=C（C为常数）。蚂蚁 k(k =1，2，...， m)在运动过程中，根据各条路径上信息量决定转移方向，Pijk表示t时刻蚂蚁k由位置i转移到j的概率，如式（13）所示。

其中 allowedk为蚂蚁k下一步可选择的城市。 ηijβ为能见度因数，常取ηij(t)=1/dij。α和β分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性，α为信息启发式因子，β为期望启发式因子。

过多残留信息素会引起残留信息素覆盖启发信息，所以在每只蚂蚁走完一步或者完成对所有城市的遍历之后，要对残留信息进行更新处理。t+n时刻在路径(i，j)上的信息量可按式（14）和（15）做调整。

ρ为信息素挥发因子， ρ∈ （0，1）， Δτij(t)表示本次循环中信息素增量。表示第k只蚂蚁在本次循环中留下的信息素，计算方法可以根据计算模型而定，本文采用最常用的蚁周模型，如式（16）所示。

式中Q表示信息素强度，会影响算法的收敛速度，过大会导致局部收敛，过小会影响收敛速度。Lk表示在本次循环中所走路径的长度。

3.2 构造状态转移规则

本文采用将确定性选择组合和随机性选择相结合的策略，为了缩短最好和最差路径上的信息量差距，适当加大随机选择概率，对解空间进行更完全搜索，从而克服传统蚁群算法缺陷。按照下式确定蚂蚁k由i转移到j的状态转移概率。

q是[0，1]内的随机数，q0是一个 参 数 ， q0∈ [0，1]， 一 般 取0.85～0.90。蚂蚁在选择下一客户时，根据先验知识，如式（17）所示来选择最好的边，否则按式（13）来选择一条边，将求得的各个节点的转移概率进行累加，再与产生的随机数相比较，直到满足要求，蚂蚁可转移到下一节点。

3.3 信息素更新

3.3.1 保留最优解

在每次循环结束后，保留最优解。

3.3.2 自适应改变ρ

通过减小ρ虽然可以提高算法的全局搜索能力，但也会使收敛速度降低，因此需要自适应改变ρ。ρ的初始值 ρ( t0)=1；当算法求得最优值在N次循环中无明显改进时，ρ如式（18）所示。其中ρmin可以防止ρ因过小而降低算法收敛速度。

3.4 蚁群算法求解流程

Step1：初始化参数，包括Nc，蚂蚁总数m，信息启发式因子α，期望启发式因子β，信息素挥发因子 ρ( t0)，信息素强度Q；

Step2：将蚂蚁随机置于节点；

Step3：蚂蚁根据转移概率选择下一节点，判断是否超过载重限制，若没有，加入禁忌表中；否则，选择另一个节点进行判断；

Step4：若没有满足条件的节点，则将车场编号加入禁忌表中，表示完成子路径的搜索。重新将载重置0，执行Step3；

Step5：直到所有蚂蚁都访问了所有节点，每条蚂蚁将得到若干条以车场为起终点的回路，回路就是一辆车的路径轨迹；

Step6：计算每条回路的路径长度，得出局部最优解；

Step7：进行信息素全局更新；

Step8：若满足终止条件，达到最大迭代次数，则结束，否则，转Step2。

4.仿真分析

某供应处有1个车场，需给32个客户送货，客户信息表如表1所示。每辆车最大载重为20吨，每辆车最大配送里程为100km。货物与货物之间的关联系数由Matlab7.1随机生成。

本文中的实验是在Intel(R)Core™i3 CPU2.53GHz、内存2.0G的PC机上采用Microsoft Visual C++6.0编程以及Matlab7.1辅助编程实现。利用VC++6.0进行编程，蚁群算法中参数设置：蚁群规模m为100，最大迭代次数Nc=200，α =1，β=2， ，q0=0. 88，Q=100。运行程序30次，得到该算法求解本算例的最优结果，最短运输距离为268.24千米，如表2所示，配送示意图如图1所示。

图1 配送路径示意图

表1 客户信息表

表2 各配送车辆的配送数据

5.结束语

该文对传统的蚁群算法进行改进，通过自适应改变信息量的挥发因子，既保证了收敛速度，又提高了算法的全局搜索能力。运用改进的蚁群算法对建立的单车场单车型无时间窗约束的关联物流运输调度模型进行求解，实验结果证明了算法的可行性和有效性。