Logistics Sci-Tech
收稿日期： 2008-10-15
作者简介： 张 坤（1985-）， 男， 安徽蒙城人， 南京航空航天大学经济管理学院硕士研究生， 研究方向： 物流与供应链管理；
江海容（1983-）， 女， 江苏泰州人， 南京航空航天大学经济管理学院硕士研究生， 研究方向： 国防经济。
Logistics Sci-Tech , 2009 物流科技 2009 年第 2 期
·仓储运输·
摘 要： 在现代汽车制造企业中， 循环取货模式在零部件配送中得到越来越广泛的应用。 文章针对汽车零部件循环取货特
点， 建立车辆路径优化模型， 并提出了结合扫描法和禁忌搜索法的两阶段求解算法， 将车辆路径问题转化为多个旅行商问题，
降低了算法的复杂度。
关键词： 循环取货； 车辆路径； 两阶段方法
中图分类号： F252 文献标识码： A 文章编号： 1002-3100 (2009) 02-0069-04
Abstract: Nowadays, milk-run has been widely used by the modern automobile manufacturers. In this paper, a vehicle routing
optimal model was built according to the characteristics of automobile parts milk-run. Combining sweep method and TS algorithm,
a two-phase algorithm has been presented, which could tranform a VRP problem into a lot of TSP problems, and also reduce the
complexity of the algorithm.
Key words: milk-run; vehicle routing problem; two-phase algorithm
0 引 言
汽车零部件的循环取货是指运输车辆通过运用送奶路线 （Milk-Runs）， 按次序到多家零部件供应商取货， 然后直接运输到
零部件配送中心的配送模式。 Milk-Runs 指用一辆车从多个供应商那里提取货物送至一个需求方时所经过的线路， 在这种运送
模式中， 用一辆车从多个供应商那里装载零部件运送到一家需求方。
在每天相应的时间点， 由汽车制造企业或第三方物流公司的运输车辆根据预先设计的取货路线， 从整车厂出发， 按次序到
第一个供应商那里装上准备的零部件， 然后到第二家、 第三家， 依次类推， 最后再返回到整车厂的零部件配送中心， 并在规定
的时间将零部件直接送到装配线上。
循环取货作为一种先进的运输模式， 利于零部件供应商对整车厂的多频次、 小批量的准时供货。 循环取货方式提高了车辆
的装载率和运输效率， 在配送总量一定的情况下， 运输总里程大大下降， 从而节约了大量的运输成本。 在循环取货方式下， 取
货车辆的行驶路线是运输效率的决定性因素， 因此取货车辆的路径优化至关重要。
车辆路径问题一般描述为： 在一个存在供求关系的系统中， 有若干台车辆， 若干个物流中心和客户， 要求合理安排车辆的
行车路线和出行时间， 从而在给定的约束条件下， 把客户需求的货物从物流中心送到客户， 把客户供应的货物从客户取到物流
中心， 并使目标函数取得优化 [1]。
汽车零部件循环取货车辆路径问题可以描述为： 在一个存在供求关系的系统中， 有若干台车辆， 一个零部件配送中心和若
干个零部件供应商， 要求合理安排车辆的行车路线， 从而在给定的约束条件下， 把供应商供应的零部件从供应商取到配送中
心， 并在使用最少车辆的同时， 使运输总成本最低。 由以上分析可知， 汽车零部件循环取货车辆的路线优化属于非满载的集货
车辆路径优化问题。
1 模型描述
为构造数学模型 ， 将零部件配送中心编号为 0， 取货点即零部件供应商编号为 1,2,… ,n。 取货点及配送中心均以点 i
i=0,1,…,, ,n 表示， 设 dij表示从取货点 i 到取货点 j 之间的距离， 目标为使车辆的总运行距离最短。 可得非满载车辆路径优化模
型如下：
目标函数：
Minz=
n
i = 1
Σ
n
j = 1
Σ
K
k = 1
Σdij xijk （1）
张 坤， 江海容 （南京航空航天大学， 江苏 南京 210016）
ZHANG Kun, JIANG Hai-rong (Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)
汽车零部件循环取货车辆路径优化研究
Study on Vehicle Routing Problem of Automobile Parts Milk-Run
69
ghg
高亮
Logistics Sci-Tech
汽车零部件循环取货车辆路径优化研究
约束条件：
n
i = 1
ΣRi yik≤wk k=1,2,…,K （2）
K
k = 1
Σyik i=1,2,…,n （3）
n
i = 0
Σxijk =yik j=1,2,…,n； k=1,2,… ,K （4）
n
j = 0
Σxijk =yik i=1,2,… ,n； k=1,2,… ,K （5）
yik =
1 点 i 的任务由车辆 k 完成；
0 否则≤ 。 （6）
xijk=
1 车辆从 i 行驶到点 j；
0 否则≤ 。 （7）
式 （2） 为车辆的能力约束， 即每辆取货车辆所访问的零部件供应商的供货量不能超过车辆本身的额定体积。 本文取装载
体积作为取货车辆的能力约束， 这是由汽车零部件的自身特点决定的， 因为在实际操作中， 即使在车辆满载的情况下， 零部件
的重量也往往不会达到车辆的额定载重； 式 （3） 表示每一任务必须而且只能由一辆车辆来完成； 式 （4） 表示某一车辆最多只
能从某一取货点发出一次； 式 （5） 表示某一车辆最多只能到达某一取货点一次； 式 （6） 和式 （7） 为整数约束。
2 求解算法分析
由于上述模型属于 NP-Hard 问题 （非确定型的多项式算法难题）， 使用精确的算法是比较困难的， 根据现有的有关 VRP 的
文献， 基本上可将求解方法分成精确算法和启发式算法两类 [2]。
（1） 精确算法： 指可求出其最优解的算法， 主要有： 分枝定界法， 割平面法， 网络流算法和动态规划方法。
（2） 启发式算法： 由于 VRP 问题是 NP-Hard 问题， 精确算法的计算量一般随问题规模的增大呈指数增长， 因此， 其应用
范围十分有限。 寻找近似算法是必要和现实的， 为此， 专家们主要把精力花在构造高质量的启发式算法上， 目前， 绝大部分的
研究成果也是对启发式算法的设计或改进。 启发式算法可以分为如下几种类型：
①构造算法 （Constructive Algorithm）： 根据一定的准则， 每一次将不在线路上的点插入线路， 直到所有的点都被安排进线
路为止。 如节约算法、 插入算法、 最邻近算法等。 这些方法一般速度快， 也很灵活。
②两阶段算法 （Two Phase Algorithm）： 两阶段算法是将一个优化问题分解成两个阶段来完成， 第一阶段构造一个可行解，
第二阶段通过对点的调整， 在始终保持解可行的情况下， 力图向最优目标靠近， 每一步都产生另一个可行解以代替原来的解，
使目标函数值得以改进， 一直继续到不能再改进目标函数值为止。 在两阶段法求解过程中， 常常采用交互式优化技术， 把人的
主观能动作用结合到问题的求解过程中。 如先分组后安排线路的方法 （Cluster First-Route Second）、 先安排线路后分组的方法
（Route First-Cluster Second） 等。
③亚启发式算法： 亚启发式算法包括表搜索法 （Table Search）、 扫描算法 （Sweep Algorigthm）、 模拟退火算法 （Simulated
Annealing）、 遗传算法 （Genetic Algorithm） 和神经网络算法 （Neural Networks Algorithnm） 等。
3 二阶段启发式求解算法
本文拟采用 “先分组再排路线” 的二阶段求解方法， 进行取货路线的安排， 也就是先将所有的零部件供应商进行分组， 然
后再对每一组集中的供应商做最优化路线的处理， 换句话说， 是将车辆路径问题 （VRP） 转换成多个旅行商问题 （TSP）， 然后
运用禁忌搜索方法进一步求更优解。
构造初始解 [3]
为了使每辆货车所负责的供应商尽量相邻， 本文以扫描法 （Sweep Method） 为基础， 修改其演算方法进行初始解的构造，
此方法可以达到先分组的目标， 而且此方法在选择取货点进行求解时， 可以将临近的点选入同一组中， 满足初始解的基本要
求。 而在车辆路线规划方面， 在构造初始解路线时， 加入 “车辆装载体积限制” 的条件， 使初始解的每一群均能满足此限制。
以下为初始解的构造方法与流程：
步骤 1 以零部件配送中心的位置作为原点 0， 依序为每个取货点以 1， 2， 3……顺序编号， 并在地图或方格图中确定所有
取货点的位置。
步骤 2 选取零部件配送中心作为起点， 经过编号 1 的取货点画一条射线。
步骤 3 开始建立第一条配送路线， 编号 1 的点作为第一个取货点， 以逆时针方向旋转该直线， 直到与某一取货点相交，
选取该点作为第二个取货点， 以此类推， 直到满足一台车辆的最大装载限制条件， 即回到零部件配送中心， 完成第一条路线的
构造。
步骤 4 重新开始建立下一条新的配送路线， 再度选取零部件配送中心作为起点， 从不包含上一条路线的取货点开始作为
70
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
Logistics Sci-Tech
2-OPT 交换 （i,i+1,j,j+1）
1-0 节点交换 （Ri,i,Rj）
1-1 节点交换 （Ri,i,Rj,j）
表 2 路线交换禁忌表内容
图 1 一次 2-OPT 交换
2-OPT
第一个取货点， 重复步骤 3 的程序。
步骤 5 重复步骤 4 的程序， 直到所有的供应商都纳入规划的路线中， 即完成一组初始解的路线构造。
以上构造初始解的方法是一种很简单的车辆分组方法， 即使是大规模问题也可以通过人工计算来完成。 如果采用计算机求
解会非常迅速， 而且不需要占用大量的内存资源。 对不同问题求解， 其结果与最优解之间只有平均 15%的误差， 当问题要求为
可行解时， 这个水平的计算误差是可以接受的。 相对于车辆路径精确解方法， 扫描法构造的初始解可以做到更快速的求得接近
最优的可行解 [4]。
禁忌搜索算法设计[5]
禁忌搜索算法要求对求解的问题有很深入的理解， 在解的编码、 解的邻域操作和禁忌对象的选择上等方面， 都需要结合问
题的特征来设计。 具体方法如下：
（1） 初始编码。 这里采用供应商和配送中心共同排列表示解的方法， 这种方法与采用有向边排列的解的表示方法相比，
能更直观反映路线安排， 占用计算机内存较少， 便于操作。 用 0 表示零部件配送中心， 用 1,2,…,L 表示各取货点。 假如有 K 条
取货路线， 为了在编码中反映车辆取货的路线， 可以增加 K+1 个虚拟零部件配送中心。 例如， 有 6 个零部件供应商， 初始解
为两台车辆完成取货任务的问题， 则可用 “012650340” 来表示取货路线的初始解， 包含两条子路线 “0-1-2-6-5-0” 和 “0
-3-4-0”。
（2） 解的评价。 以目标函数作为评价函数， 目标函数越小， 则解越优。 在解的邻域搜索中要保证解的可行性， 即路线
的每一弧段的装载量不能超过车辆的装载体积限制。 目标函数计算过程中需要利用各供应
商之间距离， 因此应建立一个对称矩阵， 目的是为了存放两两取货点之间的距离。 见表
1。
（3） 邻域构造。 禁忌搜索算法是基于邻域搜索技术的算法， 确定邻域操作方法是构
造该算法的一个重要步骤。 本文拟从两个方面来进行搜索。 一是线路内部的搜索， 另一
个是线路间的搜索。
线路内搜索采用 2-OPT 交换法。 2-OPT 交换法就是将互不相邻的两段弧删除， 以新
的两段弧来取替， 表现在解的编
码上就是将一段路线逆转。 一个
典型的 2-OPT 交换如图 1 所示。
线路间搜索采用 shift move 交换法。 本文拟采用 shift move 交换法
中的 1-0 交换法和 1-1 交换法。 1-0 节点交换法就是将一条子路线中
某一取货点插入到另一子路线中， 但要保证可行性。 如下所示：
初始解： 0—1—2—6—5—0—3—4—0
所选位置： * *
交换后的解： 0—1—2—6—0—3—4—5—0
1-1 节点交换法就是在两条子路线中选择两个客户进行交换， 也要保证解的可行性。 如下所示：
初始解： 0—1—2—6—5—0—3—4—0
所选位置： * *
交换后的解： 0—1—2—6—3—0—4—5—0
（4） 禁忌对象的确定。 禁忌对象有三种， 这里采用禁忌解的向量分量作为禁忌对象， 能更好避免重复搜索， 节约时间 [6]。
对每种交换方法建立一个禁忌表， 禁忌表的内容如表 2。
（5） 禁忌长度的确定。 禁忌长度是指被禁对象不允许被选取的迭代步数。 在禁
忌表中采用 tabu（x）=t 记忆， 每迭代一步， 该项指标做运算 tabu（x）=t-1， 直到 tabu
（x）=0 时解禁。 本文取的禁忌长度是常数， 每一种方法有一个禁忌长度， 4 种交换法
的禁忌长度分别在 3~7 之间。
（6） 终止规则的确定。 采用双层终止规则， 外层指定迭代步数为终止规则， 内层的终止规则是目前最好解超过一定的迭
代步数没有被更新， 则终止。
整个求解的完整流程如图 2 所示。
由图 2 可知， 本算法是将 VRP 问题转换成多个旅行商 （TSP） 问题进行求解。 首先用改进后的扫描法建立初始解， 即根据
车辆装载体积限制对所有零部件供应商建立多车辆的取货路线， 然后对每辆车的取货路线用 TS 算法进行 TSP 求解， 最后找到
总运输路线最短的解。
4 实例分析
有一个零部件配送中心， 有装载 20 个单位的车辆 N 辆， 有 8 个零部件供应商， 供应商对取货时间没有要求， 供应商与配
取货点 0 1 2 3 4
0 0 4 7 6 9
1 4 0 3 2 12
2 7 3 0 7 8
3 6 2 7 0 4
4 9 12 8 4 0
表 1 取货点距离矩阵
汽车零部件循环取货车辆路径优化研究
71
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
ghg
高亮
Logistics Sci-Tech
5
42
6
8
1
3
7
0
图 3 零部件配送中心和供应商分布
Cij 0 1 2 3 4 5 6 7 8
0 0 18 4 16 6 17 19 9 7
1 18 0 14 15 18 13 5 14 16
2 4 14 0 12 5 11 14 13 4
3 16 15 12 0 15 14 3 15 17
4 6 18 5 15 0 5 17 7 8
5 17 13 11 14 5 0 12 9 13
6 19 5 14 3 17 12 0 13 14
7 9 14 3 15 7 9 13 0 13
8 7 16 4 17 8 13 14 13 0
取货量 0 8 4 5 6 7 3 6 8
表 3 各供应商之间距离及取货量
送中心以及供应商与供应商之间的距离和取货量已
知 。 配送中心
与供应商如图
3 所示。 0 为配
送 中 心 ， 1 -8
为供应商。
供应商与
配送中心以及
供应商与供应
商之间的距离，
及各供应商的
取货量如表 3 所示。
首先运用扫描法对路线求初始解， 按每辆车的容
量不超过最大容量 q=20 来扫描， 得到三条初始路线
分别是： 0-1-6-8-0、 0-7-5-4-0、 0-2-3-0。 将此初始解进行编码， 把编码结果 （016807540230） 运用禁忌搜索算法进一步优
化， 最后得到最终的结果为 （036104520870）， 其对应的路线为： 0-3-6-1-0、 0-4-5-2-0、 0-8-7-0， 路线总距离为 97。
5 总 结
本文在分析汽车零部件循环取货特点的基础上， 构造了由扫描法与禁忌搜索算法结合的车辆路径优化算法， 它是一种两阶
段的启发式算法结构。 相比随机产生初始解， 利用扫描法产生的初始解能较好地利用供应商分布信息， 在此基础上利用禁忌搜
索算法能有效地提高搜索效率。 同时扫描法将原先规模比较大的 VRP 问题分解成一个相对小规模的 VRP 问题， 降低了算法的
复杂性， 对解类似的优化组合问题有一定的参考价值。
参考文献：
[1] Jean Y Potvin, Samy Bengio﹒The vehicle routing problem with time windows part Ⅱ: genetic search[J].﹒Journal on Comput-
ing， 1996,8(2):165-172.
[2] 刘云忠, 宣慧玉． 车辆路径问题的模型及算法研究综述[J]． 管理工程学报, 2005,1(19):124-128.
[3] 杜文． 物流运输与配送管理[M]． 北京： 机械工业出版社, 2006.
[4] Gillett, B. E. and Miller, L. R. A heuristic algorithm for the vehicle dispatch problem[J]. Ops Res, 1974,22:240-349.
[5] 李建， 张永． 一类集散货物路线问题的禁忌搜索算法设计[J]． 系统工程理论与实践, 2007,6:117-123.
[6] Maria KS. The welfare effects of different pricing schemes for electricity distribution in finland[J]. Energy Policy， 2004,32(12):
1429-1435.
汽车零部件循环取货车辆路径优化研究
更新禁忌表、 当前
解和目前最好解
更新禁忌表、 当前解
和目前最好解
更新禁忌表、 当前解
和目前最好解
1-0 交换法
1-1 交换法
终止准则 输出结果
是否
线
路
内
部
改
善
线
路
内
部
改
善
图 2 二阶段启发式求解流程
计算各取货点的极坐标角度值
以第一个取货点为起点， 将取货点按角度值由小到大排列
以排列顺序将取货点选入路线中
线路中所有取货点的
取货总量是否大于车辆的
装载体积
所有取货点是否都
已纳入路线规划中
将初始解带入 TS 算法
2-OPT 交换法
开启一条新路线
否
是
否
是
72
ghg
高亮
ghg
高亮
