张瑞锋，汪同三

(中国社会科学院数量经济与技术经济研究所，北京 100732)

0 引言

车辆路径问题[1](Vehide routing problem,VRP)是物流配送优化中关键的一环，也是电子商务活动中不可缺少的内容.自1959年Dantzing和Ramser首次提出VRP以来，很快引起运筹学、应用数学、网络分析、图论及计算机应用等学科的专家与运输计划制定者和管理者的极大重视.历经多年的研究发展，衍生出多种不同类型的问题.VRP一般定义为：对一系列发货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制及时间限制)下，达到一定的目标(如路程最短、费用最小、时间尽量少及使用车辆尽量少).由于VRP已被证明是一个NP难题[2]，求解该问题高效的精确算法存在的可能性不大，为此专家们主要将精力用于构造高质量的启发式算法上.比知一些学者尝试了用一般启发式算法、神经网络、遗传算法、禁忌搜索及模拟退火等智能化启发式算法，均取得了较好的结果[3-4].但是，这些算法在求解问题时都存在“早熟收敛”、搜索效率低和求解速度慢的问题.针对遗传算法的不足，本文中通过将模拟退火的思想引入遗传算法，并对交叉和变异后的个体实施接收策略，不但能有效地缓解遗传算法的选择压力，并且能增强遗传算法的全局收敛性，克服其易限于局部最优的缺陷.实验结果表明该算法具有较强的寻优性能和较快的收……