车辆路线问题的模拟退火算法应用
胡大伟 朱志强2 胡勇3
（长安大学 汽车学院 ）
Simulated Annealing Algorithm for vehicle routing problem
Hu Dawei1, Zhu Zhiqiang2, Hu Yong3
（Chang’an university ）
摘 要：车辆路线问题（vehicle routing problem, VRP）是组合优化问题中的一个典型NP难题。本文在构造车辆路线问题数学模型后，采用路线间调整和路线内优化方法，结合模拟退火算法策略对该问题进行求解。文章重点阐述了车辆路线问题的模拟退火算法的设计思路，详细分析和编制了求解程序框图，并实现了计算机求解。通过仿真测试表明，采用模拟退火算法解VRP问题效果显著，计算速度较快，与有关算法对比显示了较强的实用性和可操作性，同时对解决大规模车辆路线问题又提供了一种有效算法。
关键词：车辆路线问题，模拟退火算法，2-opt，插入法
Abstract：The vehicle routing problem (VRP) is a typical NP-hard problem in combinatorial optimization. After constructing a mathematical model for the VRP, the paper using the between-route improvement method and within-route improvement method, and combine the strategy of the simulated annealing algorithm to solve VRP problem. The article key-point explains the design thought of the simulated annealing algorithm to solve VRP. It analyses and works out a program flowchart of simulated annealing algorithm for the VRP in detail. And it achieved to solve VRP on computer. The simulated test denotes that the algorithm can solves the VRP efficient and quickly. Comparing with other algorithms, the simulated annealing algorithm has practicability and effectiveness. Simultaneously the article provides an effectively algorithm to solve the vehicle routing problem in large scale.
Key words：vehicle routing problem，simulated annealing algorithm，2-opt，insert method
1、引言
车辆路线问题（Vehicle Routing Problem,VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的[1]。 由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery[2]已证明TSP问题是NP难题，因此，VRP也属于NP难题。
求解VRP问题的方法有精确算法和启发式算法。精确算法如分枝定界法、割平面法、线性规划法、动态规划法等。启发式算法如遗传算法、禁忌搜索算法、模拟退火算法等。精确算法可以对小规模VRP进行精确求解，但其计算量随问题规模的增大呈指数增长，在实际应用中范围有限。启发式算法可以在有限的时间内找到大规模VRP的满意解。在启发式算法中，遗传算法 “爬山”能力差，容易出现“早熟”现象，禁忌搜索算法占用计算机存储量较大，搜索效率较低，收敛速度较慢，而模拟退火算法具有全局搜索能力强，收敛速度快的特点。因此本文在构造VRP数学模型后，通过模拟退火算法进行求解，力图找到满意解。
2、VRP的数学模型
车辆路线优化问题可以描述为：从配送中心用多辆汽车向多个客户进行送货，每个客户的位置和需求量一定，每辆汽车的载重量已知，要求合理安排汽车路线，使得总费用最小，总费用包括运输费用和车辆的固定成本，并满足以下条件：
（1） 每条配送路线上各客户的需求量之和不超过汽车载重量；
（2） 每个客户的需求必须满足，且只能由一辆汽车送货一次。
符号的定义：
：表示客户， ， 为客户的数目，标号 表示配送中心，本文为单配送中心的情形；
：表示配送车辆， ， 为车辆的数目；
：表示客户 之间的距离，可以转化成为运输费用；
：决策变量，表示第 辆车，是否从客户 驶向客户 ，如果是 为1，否则其值为0；
：若车辆 服务客户 ，其值为1，否则为0；
：第 条线路上，车辆的固定成本；
：客户 的货物需求量；
：车辆的载重量；
第 条线路上的支路消去约束向量，表示客户 在线路 中的被访问次序。
其数学模如下：
（1）
， （2）
， ， （3）
， ， （4）
， （5）
， （6）
， （7）
， （8）
， （9）
式中：等式（1）为目标函数，使得总费用最小；约束式（2）表示每个客户都被访问到，且仅能被访问一次；约束式（3），（4）为每条巡回路线上的配送限制；约束式（5）为车辆的载重量限制；约束式（6）为消去支路约束条件；约束式（7），（8）为0，1变量说明；约束式（9）表示支路约束量恒为非负值。
3、算法设计
本文设计的求解VRP的方法是，首先是随机产生一个初始解，然后用模拟退火算法优化初始解。
3.1 模拟退火算法[3]
模拟退火算法最早的思想由Metropolis在1953年提出。KIRKPATRICK等在1983年成功地应用在组合优化问题中，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。在对固体物质进行退火处理时，常先将它加温使其粒子可以自由运动，然后使粒子系统的温度以足够慢的速度下降。若温度下降的速率足够慢，系统近似处于热力学平衡点。随着温度逐渐下降，最后系统将达到本身的最低能量状态，即基态，这相当于能量函数的全局最小点。组合优化问题的目标函数与能量等价，解与微观状态等价，最优解与能量最低状态等价。它是在一个给定温度下，搜索从一个状态随机变化到另一个状态，并用一个随机接受准则（Metropolis准则）进行判断。温度缓慢下降，当温度很低时，它以概率1停留在最优解上。
3.2 线路内2-opt优化[4]
在进行VRP线路内各节点排序优化时，通常采用2-opt法。假设 和 是当前可行解的两条边，则2-opt运算后将得到的两条新边 和 。并对原来 和 之间的路线进行翻转，就得到了新解。参见图1。
图1 2-opt法示意图
Fig.1 2-opt exchange
显然，只有当 （ 是客户 到客户 的距离）时，所得到的解才是新的可行解。
3.3 算法设计
随机给定一个可行解 ，它必须满足：每个配送路线上各客户的总需求量之和不超过汽车载重量；每个客户的需求必须满足，且只能由一辆汽车送货。
邻域解的构造是通过两种方法：路线间调整和路线内优化两部分[5]。路线间调整采用两种方法：插入法和交换法。插入法是随机选取二条不同的路线，从一条路线中随机选取一个客户，插入到另外一条路线中，插入的过程要保证另外一条路线在插入后没有超过其车辆载重量。交换法是随机选取两条不同的路线，然后从两条路线中分别随机选取两个客户进行交换，交换要满足两条路线上车辆的载重量限制。路线内优化本文采用2-opt法。
温度下降规则为按比例下降，即 ， 是在第 次迭代温度， 为衰减系数。退火策略是：
（1）若在温度 时，随机进行 次循环，就认为在该温度下，每个分子都已经有足够的机会达到最佳位置。因而可以将温度下降到 。
（2）若在温度 时，成功地对解改进 次。这相当于退火过程中，已有足够的分子达到了最佳位置。在这时，也将温度下降到 。
算法停止规则是当温度降至终止温度 时，算法停止，表示已经达到最低温度。
模拟退火法的程序框图如图2所示。
图2 模拟退火法求解VRP程序框图
Fig.2 Flowchart of simulated annealing algorithm for VRP
模拟退火算法的详细步骤如下：
Step1：设置控制参数，包括初始温度 、温度衰减系数 、终止温度 ，当前温度迭代次数 ；当前成功迭代次数 ；
Step2：随机产生可行解 ； ；
Step3：构造邻域解，按照上述方法得到一个邻域解 ，且 ；
Step4：比较。如果 ，则转Step5；否则 ，记录当前解为最优解， ，转Step6；
Step5：Metropolis准则检验。计算 ，若 时，则 ， ；否则不接受；转Step6；
Step6：温度下降规则。若 或 时， ， ， ，转Step7；否则返回Step3；
Step7：算法终止规则。若当前温度 时，算法终止；否则返回Step3。
4、算例分析
本文采用文献[6]中的20个客户节点数据进行仿真测试。已知车辆容量为8，车辆固定成本为100，各客户之间运输成本由它们之间的直线距离决定。表1数据为各节点坐标及需求量。
表1 各节点坐标及需求量
Tab.1 the coordinates and demand of points
编号 配送中心 客户1 客户2 客户3 客户4 客户5 客户6
坐标值 (52,4) (15,49) (0,61) (51,15) (25,71) (38,62) (35,45)
需求量 0 1.64 1.31 0.43 3.38 1.13 3.77
编号 客户7 客户8 客户9 客户10 客户11 客户12 客户13
坐标值 (100,41) (10,52) (26,79) (87,7) (24,89) (19,25) (20,99)
需求量 3.48 0.39 0.24 1.03 2.35 2.60 1.00
编号 客户14 客户15 客户16 客户17 客户18 客户19 客户20
坐标值 （73,91) (100,95) (7,73) (69,86） (24,3) (66,14) (9,30)
需求量 0.65 0.58 2.56 1.27 2.69 3.26 2.97
本文采用C++编写了VRP的模拟退火算法程序。在CPU为XP2500+的计算机上经过多次试验，在参数 ， ， ， ， 时，得到结果为1155.68，其中运输费用为855.68，耗时为4.656秒，其测试结果如表2所示。
表2 测试结果
Tab.2 Test Result
目标值 路线
初始解
1525.03 0-1-2-3-4-5-0
0-6-7-8-9-0
0-10-11-12-13-14-0
0-15-16-17-18-0
0-19-20-0
优化解
1155.68 0-15-14-17-4-5-3-0
0-6-18-0
0-9-11-13-16-2-8-0
0-1-20-12-0
0-19-7-10-0
5、结论
本文在随机构造VRP初始解的基础上，采用路线间调整和路线内优化方法，结合模拟退火算法策略，快速有效的对VRP进行了求解，并用模拟数据对模型和算法进行了验证。文献[6]采用蚁群算法，在蚂蚁数为30，最大循环次数为15等条件下求得最优路线与本文结果一致；文献[7]中仅对VRP的特例TSP问题10个节点情形采用模拟退火算法进行了优化，而本文提出VRP的模拟退火算法，采用20个节点数据进行了验证，结果表明优化解比初始解目标函数下降了24.2％，计算时间不足5秒。显然本文提出的算法可以快速有效求解车辆路线问题，对于减少物流配送系统的费用具有较强的实用性。
需要指出的是，模拟退火算法中不同的参数会引起不同的结果。在求解具体问题时，需通过大量的数值模拟计算找出最佳的参数搭配，以求得比较好的结果。
参考文献
[1] Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM[M]。Society for Industrial and Applied Mathematics philadephia. 2002。
[2] 祝崇俊，刘民，吴澄。供应链中车辆路径问题的研究进展及前景[J]。计算机集成制造系统－CMS. 2001,7(11):1-6。
ZHU Chong-jun，LIU Min，WU Cheng。Rewiew of Vehicle Routing Problem in Supply Chain[J].Computer Integrated Manufacturing Systems. 2001,7(11):1-6。
[3] 刑文训，谢金星，现代优化计算方法[M]。北京：清华大学出版社，2003。
XING Wen-xun, XIE Jin-xing。Mordern Optimization Algorithm[M]。Beijing：Tsinghua University Press，2003。
[4] JEAN-YVES POTVIN and JEAN-MARC ROUSSEAU。An Exchange Heuristic for Routing Problems with Time Windows[J]。Journal of the Operational Research society vol.46,1995。
[5] Tai-His Wu, Chinyao Low ,Jiunn-Wei Bai.。Heuristics Solutions to Multi-depot Location-routing Problems[J]。Computer &Operation Research 29(2002) 1393-1415。
[6] 杨瑞臣，周永付，云庆夏。寻找车辆最优化路径的混合算法[J]。交通运输工程学报，2005,3(1):102-105。
YANG Rui-chin, ZHOU Yong-fu, Yun Qing-xia。Hybrid Algorithm of Vehicle’s Optimal Route[J]。Journal of Traffic and Transportation Engineering。2005,3(1):102-105。
[7] 张波，叶家玮，胡郁。.模拟退火法在路径优化问题中的应用[J]。中国公路学报。2004,1(1）：79-81。
ZHANG Bo, YE Jia-wei, HU Yu-cong。Application of Optimizing the Path by Simulated Annealing[J]。China Journal ofHighway and Transport。2004,1(1）：79-81。
(本文参加了第五次中国物流学术年会论文评审工作）
