改进蚁群算法求解有时间窗的物流配送路径问题

2015-04-29康燕妮嵇启春李武刚李玲燕

计算机时代 2015年3期

康燕妮　嵇启春　李武刚　李玲燕

摘要：物流配送车辆路径优化问题已被证明是一个NP难题，很难得到最优解。应用蚁群算法对带时间窗的物流车辆路径优化问题进行了算法设计，建立了车辆路径优化问题的蚁群算法数学模型及解决方案。通过对蚁群算法的分析，提出了改进的蚁群算法，并结合实例对该算法进行测试和分析，检验其有效性，结果表明了改进蚁群算法的可行性，符合实际的需要。

关键词：物流配送；车辆路径；蚁群算法；时间窗

中图分类号：TP399 文献标志码：A 文章编号：1006-8228（2015）03-21-04

Abstract： Logistics distribution vehicle routing optimization problem has been proven to be a NP problem， which is difficult to get an optimal solution. The algorithm of logistics vehicle routing with time windows is designed by using ant colony algorithm. Mathematical model and solution of vehicle routing optimization are established. Through analyzing the ant colony algorithm， the improved ant colony algorithm is proposed. The algorithm is tested and analyzed by examples. The validity of the improved ant colony algorithm is ensured， proving the feasibility of the improved ant colony algorithm， which can accord with the actual needs.

Key words： logistics distribution； vehicle routing； ant colony algorithm； time windows

0 引言

随着全球经济的快速发展，物流行业也得到了飞速的发展，物流配送作为物流行业最重要的环节，被越来越多的人关注和研究。首先，物流管理的内容对整个物流运输的成本、效益等起着极其重要的作用；其次，物流向满足顾客类型、数量和时间等方面的发展趋势越来越突出。配送车辆路径安排这一优化问题最初由Dcmtzing & Ramser于1959年提出，一直以来，都是交通货运和物流配送领域的一个核心问题。

在实际应用问题中，带时间窗的车辆路径问题（VRP With Time Windows，VRPTW）作为VRP问题的扩展，已被 Savelsbergh证明是一个NP难题，由于该问题属于求解非常困难的组合优化问题，具有很强的实际应用价值，长期以来吸引着大量的研究人员对其不断地进行研究。研究人员从精确算法开始，逐渐将目光投向启发式算法，如禁忌搜索算法、遗传算法、蚁群算法等。钟石泉等人[1]对软、硬时间窗约束的VRP进行了研究，并用禁忌搜索算法分别进行求解；Chao[2]利用禁忌搜索算法求解了多车型的VRP；Chen等人[3]利用遗传算法来处理钢铁领域采用半挂车运输车辆进行物流配送中的车辆时间表制定及路径选择问题；唐炉亮等人[4]通过对蚁群算法的改进解决了GPS数据的公众出行路径优化问题。这些算法在VRP的求解上取得了显著的成果，但是这些算法也存在着很明显的缺陷，如：禁止搜索算法由于涉及一些复杂领域转换及求解策略，在现实中很难实现；模拟退火法需要结合其他一些局部搜索算法构造混合算法应用；蚁群算法、神经网络和粒子群算法易陷入局部收敛和收敛速度比较慢等。本文将基本蚁群算法进行改进，克服蚁群算中的一些缺点，使蚁群算法性能更好，得到运输效率更高、运算结果更精确。

1 物流车辆路径问题的模型

1.1 有时间窗车辆路径问题的定义

对VRPTW作如下定义：从物流配送中心用多台配送车辆向多个客户送货，车辆总容量一定。每个客户的位置、需求量及需求时间给定，每个客户只能由一台车辆配送并且只能服务一次，要求合理安排车辆线路，使得目标函数最优，即在符合约束条件下行驶路线长度最短。

2 车辆问题改进的蚁群算法

2.1 信息素的改进

2.1.1 信息素的动态改进

在蚁群算法中，蚂蚁能够感觉到信息素并且指导它的行为，这样使得信息素浓度较大的路径被蚂蚁选择的可能性相对比较大，导致该条路径上的信息素进一步被增强，由于蚂蚁的这种正反馈的作用，使得蚁群算法容易产生早熟、停滞现象。因此，本文从选择策略方面进行改进，采用确定性和随机性相结合的选择策略，当搜索陷入局部最优，则通过动态调整信息素和增强随机选择概率，从而有效地克服蚁群算法的早熟现象。

2.1.2 最大最小信息素的限定

为了避免算法过早收敛于非全局最优解，本文提出将各条路径可能的信息素浓度限制于[τmin，τmax]，超出这个范围的值被强制设为τmin或者τmax，初始时刻，各条路径上的信息素的起始浓度设为τmax，它的基本思想是基于最大最小蚂蚁系统[5]，可以有效地避免其中某条路径上的信息素浓度远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散。

2.2 临近候选名单列表

在蚁群算法中，当蚂蚁在节点i选择下一个节点j时，通过分析多个节点的图，选择离节点i最近的节点j，因此本文采用选择最近节点的策略以改进蚁群算法的收敛速度。这种策略的基本思想是分配候选名单，每个节点i对应的候选列表存放的就是距离节点i最近的若干节点j的编号，也就是最近邻列表。

，一只位于节点i的蚂蚁将在节点i的候选列表中选择一个它未访问过的节点作为它下一步要访问的节点，仅当候选列表中的所有节点都被该蚂蚁访问过后，它才会访问不在候选列表中的其他节点，由于候选列表明显降低了蚂蚁的选择范围，所以可以显著加快求解的速度[6]。同时，由于候选列表相对地加大了蚂蚁选择信息素浓度较低路径的几率，使得算法不容易因为信息素在局部路径上的快速累积而过快陷入局部最优。根据Bullnheimer[7]等人研究，候选名单的数量一般为总的客户数量的四分之一。

3.3 其他参数

参数蚂蚁的数量m的值一般取城市数量的2/3，候选名单一般为总的顾客数的1/4。

4 算法的实现

⑴ 初始化

设置蚁群算法参数，设置迭代次数Nc=0，将m只蚂蚁置于配送中心，分别为各蚂蚁做一个禁忌表，做一个候选名单，设定每条路段的初始信息素强度值为τij（0）。然后采用“蚁周模型更新规则[10]，对各路段的信息素进行更新。

⑵ 通过蚂蚁的移动，形成配送路径，并对局部信息素进行更新

每个蚂蚁从配送中心出发，蚂蚁根据转移概率选择下一个节点，若满足容量和时间窗约束，则选择该节点，并且将该节点记录到禁忌表中；否则，返回到配送中心，重新开始新的路径，直至所有客户节点都被访问，该蚂蚁就完成了一次周游。局部更新，是指蚂蚁从当前节点移动到下一个节点，就对经过的路段进行一次信息素更新。

⑶ 局部搜索操作

在每只蚂蚁构造完配送路径以后，对配送路径进行局部搜索操作。局部搜索操作采用2-opt方法，对可行解进行邻域搜索，以便获得更优的解。

⑷ 全局更新信息素

全局更新，当所有蚂蚁都完成周游以后，对最优路径的组成路段进行信息素更新。

⑸ 判断终止条件

判断Nc是否为最大迭代次数，若符合，则进入下一步；否则，返回到Step 2。

⑹ 输出最优解

输出最优解，计算结束。为了避免蚁群算法出现“过早收敛”的问题，本文采用“最大-最小蚂蚁系统”[10-11]的信息素更新策略，将路段信息素量限制在[τmin，τmax]以内。

5 案例分析

为了验证算法的可行性，对一个随机生成的VRPTW问题进行求解，车场和用户均分布在100 km×100 km的范围内，客户点的数据见表1，车辆的允许容量为20t，车速60km/h。采用蚁群算法参数设置如下：Q=0.9，U=100，NC=200。

三种算法测试结果如表2。200次测试中，比较三种算法的总距离与车辆数，结果表明，本文改进的蚁群算法总距离最小，并且用的车辆数也相对较少，最大最小算法次之，基本蚁群最低。平均运算时间比较，本文算法时间最短，效率最高，最大最小蚁群算法次之。综合来看，本文提出的改进类蚁群算法车辆数最少，总距离最小，同时计算时间最短，计算效率最高。

6 结束语

本文构造了具有最小总行驶距离目标函数的VRPTW数学模型，提出了改进蚁群算法，此模型和算法有效的避免了其他方法的盲目搜索，且能达到求解质量和效率两者的很好统一。通过实例验证，该改进蚁群算法对提高求解质量和效率是很有效的。算法具有较高的正确率和较快的收敛速度，能有效地避免基本蚁群算法中存在的早熟和在局部停滞的现象，提高了物流配送车辆路径系统的实用性。进一步的研究将考虑各客户点的重要性权重不同、道路交通障碍不同等条件下的VRPTW问题，使之更贴近于实际应用。

参考文献：

[1] 钟石泉，贺国光.有时间窗约束车辆调度优化的一种禁忌算法[J].系

统工程理论方法应用，2005.14（6）：523-527

[2] Chao Yiming. A tabu search method for the truck and trailer

routing problem[J]. Computer and Operations Research，2002.29（1）：33-51

[3] Chen Yaorong， Liang Bo， Zhou Meihua.Optimization for vehicle

scheduling in iron and steel works based on semi-trailer swap transport[J].中南大学学报：英文版，2010.17（4）：873-879

[4] 唐炉亮，常晓猛，李清泉等.基于蚁群优化算法与出租车 GPS数据的

公众出行路径优化[J].中国公路学报，2011.24（2）：89-95

[5] T.Stutzle， H.H.Hoos， The MAX-MIN ant system and local search

for the traveling salesman problem， in：Proceedings of the IEEE International Conference on Evolutionary Computation，1997：309-314

[6] Dorigo M，Cambardella L M.Ant colony system： a cooperative