摘要：本文在对硬带时间窗车辆路线问题进行描述的基础上，建立了该问题的数学模型。针对该模型的NP－hard属性，设计了相应的模拟退火算法；即利用改进节约法构造初始可行解，提高了求解速度；路线内和路线间同时进行邻域搜索，避免了算法陷入局部最优；通过恰当地选择技术参数，实现了快速有效地求得问题的满意解。实例仿真测算表明本文提出的算法求得的解质量较高，从而说明了模拟退火算法解决带硬时间窗的车辆路线问题具有一定的有效性和实用价值。

关键词：车辆路线问题；  硬时间窗；改进节约法；  模拟退火算法

 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等；③现代优化算法，包括禁忌搜索、遗传算法、模拟退火算法和蚁群算法等。本文设计了一种改进模拟退火算法，它首先应用路线生成方法产生初始解，然后结合2－opt^*、2－Swap和or－opt改进策略用模拟退火算法对初始解进行优化，从而求得VRPTW的优化解；最后用文献[3]的数据对此算法进行验证，说明此算法的有效性. 

2. 数学模型