带硬时间窗车辆路线问题的模拟退火算法研究徐丽蕊1赵姣林晖钢.docVIP

带硬时间窗车辆路线问题的模拟退火算法研究 徐丽蕊 赵姣 林晖钢 胡大伟 (长安大学 汽车学院，陕西 西安 710064) 摘要：本文在对硬带时间窗车辆路线问题进行描述的基础上，建立了该问题的数学模型。针对该模型的NP－hard属性，设计了相应的模拟退火算法；即利用改进节约法构造初始可行解，提高了求解速度；路线内和路线间同时进行邻域搜索，避免了算法陷入局部最优；通过恰当地选择技术参数，实现了快速有效地求得问题的满意解。实例仿真测算表明本文提出的算法求得的解质量较高，从而说明了模拟退火算法解决带硬时间窗的车辆路线问题具有一定的有效性和实用价值。 关键词：车辆路线问题； 硬时间窗； 改进节约法； 模拟退火算法 Study on vehicle routing problem with hard windows by simulated annealing algorithm Xu Lirui Zhao Jiao Lin Huigang Hu Dawei (College of automobile, chang’an university , xi’an, 710064, China) Abstract: This paper describes the vehicle routing problem with hard time window, and sets up the mathematical model of this problem. In view of this model’s NP - hard attribute, the paper designes a kind of simulation annealing algorithm to solve this problem, ie. the initial feasible solution is made up by improved saving algorithm. Neighbour searching between two routes and in two routes are used at the same time so the local optimum solution is avoided. By choosing proper technology parameter, it can obtain satisfied solution quickly and effectively. It is indicated that the results of this paper is better by calculating the simulation example, and the simulation annealing algorithm has certain effective and practical value when solving this kind of problems. Keywords: vehicle routing problem; hard time-windows; improved saving algorithm; simulated annealing algorithm; 1. 引言 车辆路线问题（Vehicle Routing Problem，简称VRP）最早由Dantzig于1959年提出[1]。所谓VRP是指对一系列特定位置和需求量的客户点，调用一定数量的车辆，从中心仓库出发，选择最优的行车路线，使车辆有序地访问各客户点，在满足特定的约束条件（如客户的需求量，车辆载重限制等）下，使得货物尽快达到客户点并且运输总费用最低。 带时间窗的车辆路线问题（Vehicle Routing Problem with Time Windows，简称VRPTW）是在VRP的基础上增加了时间窗约束的一种变化形式，是运筹学和物流管理学科的研究热点问题之一。VRPTW给定了各客户点的需求量和允许服务的时间范围，求车辆从站点出发并回到站点的一组行车路线，满足各车辆不超载，并使总费用最少。VRPTW在实际的物流配送决策中经常遇到，是典型的组合优化问题。 Saveslbergh（1985）已经证明VRPTW是一个NP难题[2]。在规模较小时，用精确解法可以求得问题的最优解；在求解大规模VRPTW时，无法避开指数爆炸问题，而启发式算法总可以在有限时间里，找到满意的次优解或可行解，这是精确算法难以做到的。 求解VRPTW的启发式算法主要可以分为三类：①路线生成算法，包括节约算法和插入算法；②路线改进算法，有2－Swap、2－opt、2－opt*、or－opt