简谈调度蚁群优化算法在物流车辆调度体系中运用要求

论文导读：时间复杂度过大，用智能优化算法实现优化调度便成为了研究的热点。1蚁群算法以蚁群算法求解旅行商问题（TrellingSaleanProblem，TSP）为例，蚁群算法的应用实现过程描述如下：2蚁群算法改进2.1拥挤扰动策略蚁群算法最主要有易于陷入局部最优解以及收敛速度慢这两个缺点。蚁群算法寻优过程可以分为两
摘 要：根据对蚁群算法进行的深入研究，指出了蚁群算法在解决大型非线性系统优化问题时的优越性。通过仔细分析遗传算法和粒子群算法在解决物流车辆调度系统问题的不足之处，基于蚁群算法的优点，并根据物流车辆调度系统自身的特点，对基本蚁群算法进行适当的改进，给出算法框架。并且以线性规划理论为基础，建立物流车辆系统的数学模型，给出调度目标与约束条件，用改进后的蚁群算法求解物流车辆调度系统的问题，求得最优解，根据最优解和调度准则进行实时调度。使用Ja语言编写模拟程序对比基于改进粒子群算法和改进蚁群算法的调度程序。通过对比证明了所提出的改进蚁群算法解决物流车辆调度优化问题的正确性和有效性。
关键词：物流；蚁群优化算法；车辆调度；最佳路径；仿真验证
0 引言
蚁群优化（Ant Colony Optimization， ACO）算法是一种模拟进化算法，由于具有强鲁棒性、并行性、易于与其他算法融合、全局优化等多个优点，已成为了解决复杂组合优化问题的强有力的工具。本文对传统的优化调度方法以及现已应用在调度系统上的智能优化算法进行深入研究，针对它们在应用中的缺点对基本蚁群算法[3]进行改进，建立适当的物流车辆调度系统数学模型，用改进的蚁群算法对调度系统进行优化，最后进行系统仿真，证明蚁群算法应用到货车调度系统中是合理实用的。应用目标是提高车辆利用率，使资源利用达到最大化，并降低运输成本。
全球定位系统（Global Positioning System， GPS）技术能够对车辆进行实时跟踪，使车辆准确地找到装载点和卸载点的具体位置；GPS还可以对历史数据进行记录，指导实施调度，通过移动终端，把计算机决策运算所需要的数据通过无线电传到调度中心，从而进行实时动态的优化调度。但是传统的优化调度方法都是静态的调度方法，随着问题规模和搜索空间的增大，计算的时间复杂度过大，用智能优化算法实现优化调度便成为了研究的热点。
1 蚁群算法
以蚁群算法求解旅行商问题（Trelling Salean Problem， TSP）为例，蚁群算法的应用实现过程描述如下：
2 蚁群算法改进

2.1 拥挤扰动策略

蚁群算法最主要有易于陷入局部最优解以及收敛速度慢这两个缺点。蚁群算法寻优过程可以分为两个阶段，即：第一阶段主要是为了增加解空间的多样性，避免算法过早收敛造成算法陷入局部最优而不能得到全局最优解；第二阶段主要是为了加快算法收敛速度。本文分别对这两个阶段进行改进。在第一次循环时，由于每条路径上具有相同的信息素浓度，蚂蚁随机选择下一步要路过的节点，这会导致蚂蚁选择的路径不一定是最优路径，并且这些路径上的信息素的量会由于正反馈作用而不断增加，导致算法很快会收敛到这些路径上，而使算法陷入局部最优。针对第一阶段提出拥挤扰动策略，该策略能扩大了算法的搜索空间，避免算法过早收敛。
引入拥挤因子CRi j表示路径（i， j）的拥挤程度，其计算公式为：
式中σ表示拥挤系数。加入拥挤扰动策略之后，算法得到了合理的改进，可以限制初始时某些路径的信息素浓度过大，使算法可以选择更多的路径，蚂蚁在面对不拥挤的路径时可以按照基本蚁群算法中的路径选择策略选择路径，而在面对拥挤路径时，只按照能见度进行路径选择。通过对蚁群算法进行如此改进，不仅有效扩大了算法的搜索范围，拓展了解空间，还可以避免得到误差解以及避免算法过早收敛。拥挤扰动策略只用于第一阶段的寻优过程，第一阶段设置为算法的前g次循环，其中gNCmax。

2.2 最优路径策略

最优路径策略相当于一个动态的、确定性的最短路径策略问题，即一个动态的路径规划算法。当设定了一个起点以及一个相应的终点时，最优路径策略将帮助我们计算出一条距离相对最短的而且最优的路径。这可以通过算法第一寻优阶段得到m（蚂蚁数目）条路径，然后在第二阶段运用最优路径策略来缩小解空间并提高解质量，提高算法的收敛速度。具体改进过程如下：
依据问题规模设置一个长度为len的列表L，把得到的m条路径中信息素含量最大的len条路径按信息素含量由多到少存到L中，第一个位置存放的是信息素含量最大的路径，其他路径依次进行排列。对信息素重新初始化，即只对L中的路径的信息素进行初始化，其他路径的信息素含量清零。采用全局论文导读：
更新策略，在给定的时间段T，计时结束就自动进行下一次循环，每过时间T，对信息素进行一次更新，改进的更新公式如下：
其中fk表示蚂蚁k在本次循环中的总的运输费用。然后增大转移概率中参数α的取值，让信息素的相对重要程度增加。在每一次算法迭代循环中，计算每条路径的信息素总含量并进行比较，依据信息素含量由大到小的顺序将最优的len条路径存放到L中。对L中的信息素浓度根据式（3）和（4）进行更新，在蚁群算法完成迭代循环之后，对列表L中的所有路径进行路径长度（目标函数）的计算，如果列表L中的第一个元素优于其他所有的元素（L中第一个位置的路径长度大于其他所有路径的路径长度），则说明该算法取得了全局最优解；但是如果在列表L中，第一个元素只是信息素含量最大的元素，而不是路径长度（目标函数）最大的元素，那么选出L中的路径最长（目标函数取得最适值）的路径作为最优解。
该改进策略不但可以提高蚁群算法的收敛速度，还可以提高蚁群算法的寻找最优解的成功率，只要在寻优第二阶段中，有蚂蚁在任意一次循环中找到全局源于：论文的基本格式www.7ctime.com
最优解，那么该算法就可以在最优路径策略的帮助下找到全局最优解。

2.3 改进后的蚁群算法

通过对基本蚁群算法采用拥挤扰动策略、最优路径策略[5-6]进行算法改进，改进后的蚁群算法流程比基本蚁群算法复杂，以求解TSP为例对改进蚁群算法的流程描述如下：
1） 算法初始化。用n表示城市数目（问题规模），并将n个城市存于集合C，循环次数与最大循环次数分别用NC和NCmax表示，用m表示蚂蚁总数，设前g次循环为算法第一阶段，在算法初始执行时，时间t=0，NC=0，所有路径的信息素浓度τi j（t）=const，const为常数，Δτi j（0）=0，将m只蚂蚁随机置于n个城市上。 2） 增加循环次数，即NC=NC+1。
3） 增加蚂蚁数目，即k=k+1，初始化蚂蚁禁忌表tabuk。
4） 如果NC==g，计算所得到m条路径的信息素浓度，并取浓度最大的len条按浓度由大到小的顺序存入列表L，清空所有路径的信息素含量，只对L中的路径的信息素进行重新初始化，转到2）。
5）如果NC6）如果NC>g，根据转移式（2）计算蚂蚁下一步选择的城市，并把j（ j∈{C-tabuk}）移入该蚂蚁的禁忌表中。
7）如果该蚂蚁的禁忌表中的元素个数小于n，则转到4）。
8）若k9）若NC>g，计算每条路径的信息素总含量并进行比较，依据信息素含学术论文下载www.7ctime.com
量由大到小的顺序将最优的len条路径存放到L中。
10）对所有路径上的信息素浓度进行更新。
11）如果NC12） 对列表L中的所有路径进行路径长度进行计算，求得最优解。

2.4 与基本蚁群算法的比较

本文采用求解TSP的测试库TSPLIB中的Eil51、 Oliver30、Kroal100、Ts225[7]作为算法的算例，通过Matlab语言进行算法的编程测试，对基本蚁群算法与改进蚁群算法进行比较。为了得出科学合理的比较结果，改进蚁群算法与基本蚁群算法在计算算例时给出相同的参数设定，即α=1，β=2，ρ=0.5，Q=150，α、β为信息素和启发因子的重要性，ρ为路径上信息素的挥发系数，Q为蚂蚁在路径上释放信息素的增量，改进蚁群算法与基本蚁群算法对每一个算例都计算10次，并且每次迭代次数为1000。实验结果如表1所示。
通过表1可以看出，改进后的蚁群算法不论是在收敛速度上还是在寻优能力上都优于基本蚁群算法，并且随着问题规模的增大，这种优势越来越明显。在实验过程中还发现通过拥挤扰动策略扩大了解空间，解决了基本蚁群算法过早陷入局部最优解的问题，并且在每个算法执行的40次中，改进蚁群算法具有较好的稳定性，寻优失败次数只有2次，而基本蚁群算法则有6次寻论文导读：果需要，则在调整完设备后就调整数据，调用优化计算程序，给出最佳运输方案。
优失败。综上所述，改进蚁群算法性能优于基本蚁群算法。

2.5 改进算法应用于车辆调度

2.5.1 车辆调度的数学模型

为降低物流车调度问题的复杂度，在给出物流车调度系统的数学模型之前，针对本文研究目标而对模型作出如下假设[8]：
1）所有的车辆在工作时间内都可以正常运行。
2）对车的运行状态只考虑在道路网上情况。
3）装载点与卸载点之间的距离在一个班次内保持不变。
4）同一时刻同一地点只能给一辆货车进行装载。
5）货车装卸时间为定值。
6）在同一卸载点处，同一时刻只能对一辆货车进行卸载。
7）忽略运输过程中的损耗。
8）采用同型号的货车，货车必须是满载运输。
仿真程序凭借低投入、无安全风险、可重用性等优点为车辆调度系统的优化提供了有效的研究办法，本文通过使用Ja语言编写仿真程序来指导车辆的调度，仿真过程简单、直观、有效，该仿真成功验证了应用蚁群算法求解物流车辆调度系统问题[10]的实用性与正确性。仿真程序可以根据输入数据直接求出每个车辆具体的行车路线，从而得到最佳的运输方案。

2.5.2 模型求解

对于算法的寻优求解还是采用两个阶段来说明，第一阶段为增加解空间阶段，第二阶段为加速收敛阶段。算法过程具体描述如下所示：
1）参数初始化。在装载点处随机放置m只蚂蚁。
2）给出U表和S表。
3）递增循环次数，即NC=NC+1。
4）递增蚂蚁个数，即k=k+1。
5）若k6）如果NC7）判定该蚂蚁所在节点是装载点还是卸载点，如果是装载点，则转到8）；如果是卸载点，则转到9）。
8）计算出蚂蚁下一步要从集合U中选择的卸载点，转到10）。
9）计算出蚂蚁下一步要从集合S中选择的装载点。
10）给出蚂蚁到达j点的时间并且i=j。
11）判定该蚂蚁运行时间是否超过T，如果超过则转到4）；否则转到7）。
12）对所有路径上的信息素浓度进行更新，然后转到3）。
13）得到m条路径，结束求解。

2.5.3 优化计算

优化计算的进行主要有两种触发方式：第一种触发方式是计时自动触发，该种方式指根据给定时间段长度，每到达该时间段长度，系统就会自动进行优化计算，给出最佳的货车实时调度的运输方案；第二种触发方式是设备调整触发，该种方式是指当增加或减少运输设备，对装载点与卸载点间的距离表进行更新，修改货车参数，对装载点、卸载点的任务量进行修改等设备状态更改时，进行优化计算来给出指定时间段内最佳运输方案[11]。
本文只考虑第一种触发方式，而不对第二种触发方式进行深入研究。优化计算的主要过程如下所示：
1）对系统是否被初次使用做出判断：若是初次使用，输入初始数据；否则给出上次调度结果。
2）开启调度主页面，实时监控优化计算进行的时刻。
3）判断是否该进行下次优化，如果到了进行下次优化的时刻，则通过优化计算程序进行优化计算，给出最佳行车线路。
4）通过调整数据为下次计算提供初始数据。
5）判断是否要对设备进行调整，如果需要，则在调整完设备后就调整数据，调用优化计算程序，给出最佳运输方案。 6）循环上述过程直到满足结束条件。
优化计算过程的流程如图1所示。
3 实验与分析

3.1 车辆调度系统的仿真

本文的仿真系统是直接通过蚁群算法求出具体每辆车的运输路线，用其指导系统调度。对装载点、卸载点、车辆的实时状态进行记录，如果运输设备发生参数改变、增加或删除设备等变动，则系统在调整之后进行重新优化计算，进而得出新的调度方案。仿真系统得到的运输方案[12]是通过严格的时间计算而得出的，主要考虑的时间有车辆在道路网中的走行时间，该时间主要由各路线的长度与车速决定，为了对调度情况进行实时了解，仿真程序对调度运行过程进行了界面论文导读：，29（6）：2031-2034.DORIGOM，GAMBARDELLALM.Antcolonysystem：acooperativelearningapproachtothetrelingsaleanproblem.IEEETransactionsonEvolutionaryComputations，1997，1（1）：53-66.张翠军，张敬敏，王占锋.基于车辆路径问题的蚁群遗传融合优化算法.计算机工程与应用，2008，44（4）：233-23
仿真输出，如图2所示。

3.2 仿真结果的分析

对调度系统评价指标的选取应该结合物流公司的具体情况，单一指标不能完成对调度系统的全面评价，本文仿真环境是在Windows 7下，13辆物流车，仿真时长8h，对物流车辆调度系统分别用改进蚁群算法和固定配车法进行模拟仿真。
实验对比结果显示出基于改进蚁群算法的物流车辆调度系统在评价指标上都明显优于基于固定配车法的调度系统，因此得出结论：应用改进蚁群算法求解物流车辆调度系统是可行的，并且可以取得预期的应用效果。
制定完整的配送计划，路径的选择很重要。应用合理的调度，使货车总里程数缩短，可以看出优化后里程数比原有里程数少10%左右，如图4所示可以提高配送效率，节约配送成本。
4 结语
本文对蚁群算法以及物流车辆调度系统进行了分析与研究，提出了改进的蚁群算法，不仅克服了蚁群算法易于陷入局部最优的缺点，还提高了其收敛速度。将改进后的蚁群算法应用于物流车辆的管理调度之中，对以运费最少为目标的优化模型进行求解，通过求解所得到的运输方案指导车辆实时调度。实验结摘自：学年论文www.7ctime.com
果表明，新方案有效且可行。
参考文献：
陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究，2012， 29（6）：2031-2034.
DORIGO M，GAMBARDELLA L M. Ant colony system： a cooperative learning approach to the treling salean problem [J]. IEEE Transactions on Evolutionary Computations，1997，1（1）： 53-66.
[3] 张翠军，张敬敏，王占锋.基于车辆路径问题的蚁群遗传融合优化算法[J].计算机工程与应用，2008，44（4）： 233-235.
[4] 徐少游.基于三维可视化模型的露天矿安全高效生产关键技术研究[D].长沙：中南大学，2011.
[5] 黎田.基于改进蚁群算法的移动机器人路径规划[D].西安：西安科技大学，2011.
[6] 陈子侠，叶庆泰.基于GIS景区快速反应系统最佳路径算法研究与应用[J].计算机应用，2006，26（5）： 1190-1192.
[7] EBERHART R C， SHI Y. Guest editorial special issue on particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）：201-203.
[8] BIANCHI R A C， COSTA A H R. AntViBRA： A swarm intelligence approach to learn task coordination[C]// Proceedings of the 16th Brazilian Symposium on Artificial Intelligence： Advances in Artificial Intelligence. Berlin： SpringerVerlag， 2002： 195-205.
[9] 李娅，王东.基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题[J].计算机应用，2012，32（2）： 444-447.
[10] BABAEE H， KHOSRI A. An improve PSO based hybrid algorithms[C]// Proceedings of the 2011 International Conference on Management and Service Science. Piscataway： IEEE， 2011：1-5.
[11] 杜立宁，张德珍，陈世峰.蚁群算法求解复杂集装箱装载问题[J].计算机应用，2011，31（8）： 2275-2278.
[12] 尚旭静，许道云.基于蚁群算法的货车调度问题[J].计算机工程与科学，2009，29（9）：80-8

2.论文导读：上一页12345