1 引言
车辆路径问题(VRP, Vehicle Routing Problem)是由 Dantzig 和 Ramser 于
1959 年提出的
[1]
。该问题一直是运筹学与组合优化领域的前沿与热点问题。在现实生
产和生活中,邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电
力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。
研究车辆路径问题具有重要的理论和现实意义。
车辆路径问题作为一个 NP 难题,随着客户数量的增加,可选的车辆路径方案数
量将以指数速度急剧增长。因此,用启发式算法求解该问题就成为人们研究的一个重
要方向。求解车辆路径问题的方法很多,常用的有旅行商法、动态规划法、节约法
[2]
、扫描法、分区配送算法
[3]
、方案评价法等。
禁 忌 搜 索 算 法 的 出 现 , 为 求 解 车 辆 路 径 问 题 提 供 了 新 的 工 具 。
Gendreau、Jiefeng、Barbarosoglu、蔡延光等都曾利用禁忌搜索算法求解车辆路
径问题
[4]
,并取得了一些研究成果。但现有研究成果多将车辆路径问题描述为一个网
络图问题,因此在设计其禁忌搜索算法时多采用有向边排列的解的表示方法,基于这
种解的表示方法所构造的禁忌搜索算法具有以下缺点:(1)由于解的表示不太直观,使
得算法策略不仅较为复杂,而且不易理解;(2)解中的元素较多,不仅占用的计算机存
储量较大,而且求解时计算时间较长,搜索效率较低;(3)算法迭代过程中产生的解中
不可行解很多,从而大大影响了算法的收敛速度。为了克服现有禁忌搜索算法的缺点,
本文在对车辆路径问题进行简单描述的基础上,提出了一种新的解的表示方法——客
户直接排列的解的表示方法,并基于这种解的表示方法构造了求解车辆路径问题的一
种新的禁忌搜索算法,并通过实验计算证明了这种新的禁忌搜索算法的良好寻优性能。
2 问题描述
车辆路径问题的研究目标是对一系列送货点或取货点,确定适当的配送车辆行驶
路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量交发
货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程
最短、费用最小、时间尽量少、使用车辆尽量少等)。参见下图 1 所示:其中 0 表示配
送中心,1~8表示客户编号。
为了使问题易于理解,本文用一个配送车辆调度问题描述车辆路径问题。该问题
可以描述为:从某物流中心用多台配送车辆向多个客户送货,每个客户的位置和需求
量一定,每台配送车辆的载重量一定,其一次配送的最大行驶距离一定,要求合理安
排车辆配送路线,使配送总里程最短
[5]
,并满足以下约束条件:(1)每条配送路径上各
客户的需求量之和不超过配送车辆的载重量;(2)每条配送路径的长度不超过配送车辆
一次配送的最大行驶距离;(3)每个客户的需求必须满足,且只能由一台配送车辆送货。
1