求解VRP的一种改进模拟退火算法

李珊珊

【摘 要】建立车辆路径问题（Vehicle Routing Problem， VRP）的数学模型，在传统模拟退火算法的基础上提出三方面的改进，通过算例验证模型和改进算法的有效性。

【Abstract】The mathematical model of VRP is established， and 3 improvements are put forward on the basis of traditional simulated algorithm. The validity of the model and the improved algorithm are proved by an example.

【关键词】VRP；数学模型；改进模拟退火算法

【Keywords】VRP； mathematical model； improved simulated annealing algorithm

【中图分类号】F503 【文献标志码】A 【文章编号】1673-1069（2018）02-0147-02

1 引言

车辆路径问题（Vehicle Routing Problem， VRP）由Dantzig等[1]提出后，便使运筹学理论和生产生活实际联系在一起，因此很快便引起运筹学、数学、物流学、计算机应用等学科专家的广泛关注。VRP问题的求解算法一直是国内外专家研究的重点问题，目前最主要的求解算法是启发式算法[1]，包括：模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法和伊藤算法等。

Kirkpatrick等人发现数学中的组合优化问题和物理上固体退火过程之间所存在的相似性，于是他们把固体物理退火的思想引入组|合优化问题中，再基于Monte-Carlo迭代策略提出了模拟退火算法（Simulated Annealing， SA）。在计算过程中，SA能够以一定的概率收敛至全局最优解，因此，SA在这种意义上说是一种全局优化算法，并善于求解高复杂度的问题，以上观点已经在理论上被证明。SA求解效率快而且求解质量很高[2]，所以本文采用对传统SA进行改进，并求解VRP问题。

2 VRP问题模型

VRP问题可描述为：一个配送中心，多位顾客，并且已知每位顾客的位置和需求量，用一定数量的车辆从配送中心出发，规划车辆行驶路径，满足每位顾客的需求且每位顾客仅能由1辆车服务，不能超过车辆相关的约束，目标是使距离最短或者运输费用最少[3]。

本文相关符号说明：

C：表示每辆车的最大装载能力；

ci：表示顾客i的需求量，且max（ci）≤C（1≤i≤n）；

D：表示每辆车的最大行驶距离；

dij：表示顾客与顾客或者顾客与配送中心之间的距离；

n：表示配送过程中出现的顾客总数；

r：表示配送中心具有的车辆数；

hijk：表示车辆k从顾客i到j，经过为1，不經过为0；

gik：表示顾客i由车辆k服务，经过为1，不经过为0。

此问题数学规划模型为：

式（1）为目标函数，表示所有配送车辆的总行驶路径长度最短；式（2）表示每辆车的装载能力约束；（3）表示每辆车的行驶距离约束；式（4）、（5）、（6）表示每个客户仅能被1辆车服务1次；式（7）约束了所有车辆的起始点和终点都在配送中心；式（8）表示每辆车行驶的路径轨迹恰好为一个简单圈，式（9）、（10）分别为决策变量。

3 改进模拟退火算法

SA是一种随机寻优算法，从某一较高初始温度开始，随着温度参数的逐渐下降，结合概率突跳特性在解空间里随机找寻目标函数的全局最优解[3]。

本文对传统SA的改进包括以下三个方面：

①邻域操作方法。传统SA采取的邻域操作是两点置换法（也称为2-swap交换法）。该方法的思想是：在每一次迭代中只交换两个节点，这种邻域操作方法简单易行，但其对解空间的搜索能力不强[4]。因此在每一个温度参数下，若要保证得到当前温度参数下的一个优解，就需要比较长的时间对解空间进行搜索。随着温度参数的逐渐降低，外循环的次数增多，执行算法的时间便成倍增加，进而使得算法整体的搜索时间过长。本文将邻域操作分为两步：第一步先进行线路内交换，对线路内交换采用2-swap、2-opt及2-insert三种交换方法随机协作的方式实施邻域操作，产生一新的可行解。即基于概率论的方法来决定使用某一种具体的交换法来实施邻域操作，这样一来便大大增加了产生新解空间的随机性，为算法跳出局部最优提高了可能性。第二步是在第一步线路内的节点交换产生可行解后，对产生的可行解进行线路间节点的交换，线路间节点的交换是引入Osman的λ-interchange交换思想，并规定每一温度下邻域操作的次数=λ，从而保证在一定的时间内，能够获得相对较高质量的优解。

②记忆装置的设计。在改进SA中内嵌一个记忆数组，用来存储各优解的值，从而构成一种具有记忆功能的SA，进而使得算法的输出为本次搜索的最优解。

③终止准则的确定。采用混合停止准则，即当温度低于某值时或者记忆数组连续γ次无变化时，算法终止。本文取γ=20，就能保证所获得的值为本次计算的最优解。

4 结语

本文随机选择Solomon标准测试数据[5]中的R101中的50个顾客点进行了测试（如图）。

如图1所示，节点代表顾客的位置，线代表车辆路线，箭头代表车辆行驶方向。图2是增加了记忆数组存储的每次迭代的各个解的值，记录每次的数值，从而能够保证最终输出值为搜索解空间后本次计算的最优解。通过对算例进行求解，证明改进后的SA能较好的解决VRP问题，且求解质量较高，求解速度很快。

【参考文献】

【1】Dantzig GB， Ramser JH. The truck dispatching problem[J]. Management Science， 1959， 6（1）： 80-91.

【2】辛振铭. 一种改进的模拟退火算法在TSP问题中的研究与应用[D].长春：东北师范大学，2010.

【3】K. Lund， O. B. C. Madsen， and J.M. Rygaard， Vehicle routing problems with varying degrees of dynamism. Technical report， Institute of Mathematical Modelling， Technical University of Denmark，1996.

【4】Chen， H.K.， Hsueh， C.F.， Chang， M.S. The real-time time-dependent vehicle routing problem[J]. Transportation Research Part E ，2006.42（5）：383-408.

【5】Solomon，M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research ，1987.35（2）：254-265.endprint