0 引言
如今不少企业采用的JIT生产都存在着一定的矛盾现象。汽车生产企业因为要最大限度地减少零部件的库存数量，所以就需要供应商进行多频次、小批量送货，这就造成运输车辆经常以较低的装载率运行，而且这种直送模式还会造成空车返回的运能浪费，导致运输效率低下，并且增加了运输成本。为了改善这一现象，比较高效的循环取货开始得到了众多企业的关注。
对于循环取货而言，路径规划问题至关重要，只要能设计出好的路线，就能提高循环取货的效率，大大减少企业的物流成本。车辆路径规划问题起初由Dantzig以及Ramser等人在1959年提出[1]，它属于NP-Hard难题，通常用启发式算法来解决。董蕊和刘冉等人设计出了一种新型的带有时间窗约束累积性车辆路径问题，用TS算法进行求解，并运用了Nagata时间窗违反量计算[2] 。廖大强等对于物流部门中的时间窗和车辆限制的开放性车辆路径问题，使用禁忌搜索算法求解路线 [3]。
该文主要根据多约束条件抽象出数学模型，将路径规划问题转变为旅行商问题，以总路径最短为目标函数。根据提出的数学模型设计适用于该模的禁忌搜索算法，利用计算机随机生成的算例进行验证并分析。
1 循环取货的路径规划
循环取货是一种物流中常用的配送模式。承运商携带须从客户返还给供应商的货物出发，依次到达每个供应商，将返还给供应商的货物卸下并装载上须从供应商处收集的货物回到客户处。
1.1 循环取货路径规划的数学建模
1.1.1 循环取货路径规划问题分析
想要顺利运作循环取货需要考虑以下3个方面：1）路径规划。循环取货是按照既定的时间和线路进行取货作业，合理规划路径是进行循环取货的基础，而路径规划的好坏会直接影响到物流成本。2）车辆装载率的提高。提高运输车辆装载率也是实施循环取货要考虑的关键问题之一，能改善这个问题就能解决JIT供应和成本之间存在的矛盾。3）合理安排司机。要做好司机的调度工作，避免司机疲劳驾驶，也要保证司机不违反交通法规。
在上述三个问题中，路径规划是循环取货的重点，因为路径规划的好坏直接影响着总物流成本。想要研究汽车生产企业的循环取货路径规划问题，需要确定某辆卡车负责哪几个供应商，以及路线上各供应商的取货顺序，还有运输车辆的总数等问题。
该文需要对模型进行以下限制：1）供应商。供应商对取货时间无限制条件，并已知所有供应商的需求量和位置。该文在计算距离时只考虑他们的坐标位置，不考虑其他因素。2）区域分拨中心。该模型只
存在一个且位置确定的区域分拨中心，它既是路线的起点也是路线的终点，并且所有循环取货涉及零部件全都运往区域分拨中心。3）运输车辆。只存在一种规格的卡车，载重固定且能满足需求，并禁止卡车的超限超载等行为。4）料箱。在该循环取货模型中涉及的所有零部件均由标准化的料箱装配。5）费用成本不计。该文不考虑库存成本、订货成本和操作成本等，而单位距离的运输成本相同，所以只需考虑总运行距离，以车辆的总运行距离作为循环取货线路规划模型的优化目标。
1.1.2 模型构建
数学模型的目标函数及约束条件如下。
Minz d x
i
n
j
n
k
k
ij ijk
¦¦¦
111（1）
¦Z
i
n
i ik k
R y k k
d
1
infiniti g35
12
;,,...,（2）
¦k k ik y i k
1
112
;,,...,（3）¦i n ijk ik
x y j n
搜汽车有惊喜k K
1
1212
;,,...,;,,...,（4）¦j n ijk ik
x y i j nk K
1
1212
;,,,...,;,,...,（5）
i由路径k完成
否则
i V k K
,（6）
汽车零部件入厂物流循环取货路径规划
王红梅  段则光  周万礼  郝 梁
（东北林业大学交通学院，黑龙江  哈尔滨  150036）
摘 要：该文采用禁忌搜索算法对汽车零部件入厂物流的循环取货作业进行路径规划。基于循环取货的要求设计数学模型，并根据问题的特点来设计禁忌搜索算法中的编码、搜索邻域、选择禁忌表等，对路径进行求解。运用禁忌搜索算法求解循环取货问题的路径，通过比较可知，禁忌搜索得出总路径长度比扫描法得出的路径缩短了8.83%，比传统直送模式缩短了64.72%，并大大提高了汽车装载率。通过对数据结果的分析表明，循环取货能大幅降低物流成本，实现准时化生产；该文设计的数学模型和构造禁忌搜索算法是可行的，能高效地解决路径规划问题。
关键词：循环取货；JIT采购；车辆路径规划；禁忌搜索算法
中图分类号：F 252.21  文献标志码：A
基金项目：2021年黑龙江省大学生创新创业训练计划项目（项目编号：S202110225240）。
车辆从i 行驶到j 否则
x ijk  ­®
¯10;;    i j V k K ,,
（7）
式中：
V 表示RDC（区域分拨中心）与n 个供应商点的集合，V ={i |i =0,1,2,…,n },i =0表示RDC ；
K 表示m 条路径的集合，K ={k |k =1,2,3,…,m }；
Z 表示总运输距离；d ij 表示供应商i 到j 的距离；
R i 表示供应商i 的运送量，用体积表示；ωk 表示路径k 上车的容量限制；
x ijk 和y ik 为决策变量。式（1）表示数学模型的的优化目标，表现为总运输距离最短；式（2）
表示每辆卡车前往的供应商的取货量之和不可以超过车辆的容积限制（该文不采用质量限制是因为考虑到汽车零部件的特点，即使满载也达不到车辆的最大载重）；式（3）表示一条路径只允许由一辆车辆完成；式（4）表示某辆卡车只可以从某一个取货点出发一次；式（5）表示某辆卡车只可以到达某一取货点一次；式（6）和（7）为整数约束。
1.2 禁忌搜索算法
禁忌搜索算法（TS）是一种模拟人体脑部记忆过程的智能优化算法，最初由美国工程院院士Fred Glov
er 于1986年发明，TS 算法的计算流程主要包括：首先随机生成一个初始解，接着搜索当前解的邻域，选出其中的最优解更换为新的当前解，不断重复迭代直至达到终止准则后输出最终结果。禁忌搜索算法为了避免求解过程陷入局部最优，设计出一张禁忌表来储存已搜索过的局部最优解，防止反复计算。TS 算法需要设计初始解、适配值函数、领域、禁忌表、禁忌长度、候选解、特赦准则、终止准则等。TS 算法的关键问题就在于构造领域、设计禁忌表和特赦准则等。
1.3 禁忌搜索算法设计
TS 算法需要对问题深入了解，根据问题的特点设计编码、搜索邻域、选择禁忌表。具体的方法如下。1）构造初始解。该模型随机生成一个初始解，解得编码用供应商和RDC 共同排列的方式来表示，这种编码方式更直观，易操作。用0来表示RDC，用1,2,3……，L 表示各供应商。假如存在M 条路径，为了用一个编码表示路线，可以假定有M +1个虚拟的RDC。比如说用两辆车解决8个供应商的Milk-run 问题时，可以用“01234056780”来表示路径的解，其中包括“0-1-2-3-4-0”和“0-5-6-7-8-0”这两条子路线。2）解的评价。用目标函数来衡量解的优良，目标函数越小代表解越优秀。在寻解的领域时要保证可行性。计算目标函数需要用到各供应商间和供应商与RDC 之间的距离，所以要设计一个距离矩阵，来放置可能存在的单次取货的距离。3）邻域搜索。邻域搜索是TS 算法在实际操作过程中较关键的一个步骤。该文主要从两方面来搜索邻域：一种是在路径内部搜索，另一种是在路径之间搜索。线路内部的搜索采用2-OPT 交换法。2-OPT 交换法的原理就是将两段互不相邻的弧线删掉，用两段互相
相邻的弧线代替。在编码上表现为将一段线路翻转，2-OPT 交换法的流程如图1所示。线路之间的搜索使用shift move 交换法。该文主要使用shift move 交换法中的1-0交换法和1-1交换法。1-0交换法就是在确保解的可
行性的条件下把某条子线路中任一供应商插入至另一条子
线路，具体方法如图2所示。而1-1交换法就是在任意两条子路线内选取两个供应商进行变换，但也要确保可行性，方法如图3。4）确定禁忌对象。禁忌对象有三种，这里使用禁忌解的向量分量来当做禁忌对象，可以避开反复搜索，节省时间[4]。该文需要对所有交换法设立禁忌表，禁忌表的内容如表1所示。5）确定禁忌长度。禁忌长度是指被禁对象被禁止重复迭代的步数，每迭代一次，表就更新一次，原来禁忌表中的解向上移一次，直到达到禁忌长度后被移出tabu list，此解被解禁。6）确定终止规则。给出一个最大迭代步数，计算这个步数时输出结果。
表1 路线交换禁忌表内容
交换方式在编码上的体现2-OPT交换(i ，i +1，j ，j +1)1-0节点交换R i ，i ，R j 1-1节点交换
R i ，i ，R j ，j
2 数值实例和结果分析2.1 数值实例
该文使用一个由计算机随机产生的循环路径规划问题进行试验验算。供应商随机分布在100km*100km 的平面上，取货中心为（50, 50），具体供应商之间的距离如表2所示；供应商与RDC 之间距离如表3所示；每个供应商的计划取货量为2~5的一个随机整数，各供应商计划取货量如表4所示。设置各供应商之间以及RDC 与供应商之间的距离使用
初始解
1
23456780
所选位置**交换后解
1
2
3
6
5
4
7
8
图3 1-1交换法
初始解
1
2
3
4
5
6
7
8
所选位置**交换后解
1
2
3
5
6
4
8
图2 1-0交换法
图1 2-OPT 交换
直线距离，此长度根据供应商和RDC的坐标计算得出。
车辆的最大装载容量q为20，车辆最大数目为8，总迭代步数不超过60步，禁忌长度取10。
最终TS算法输出的解为0-12-17-13-0-3-5-1-16-0-10-19-7-6-18-14-0-15-11-4-8-20-9-0，得出的路线视图如图4所示，运输长度与迭代次数曲线如图5所示。
2.2 结果分析
考驾照要多久最终禁忌搜索算法得出的优化路线如表5所示，通过扫描法人工得出的路径如表6所示。
当采用供应商直送取货模式且要满足JIT生产的要求时，总运输距离为746.73×2=1493.46km，并且车辆装载率都在40%以下。
由上可知，采用传统供应商直送这一供货模式时，汽车装载率低，且总运输路径过长，如果供应商等装满整车再发货又不能实现JIT生产，会导致生产厂产生库存积压，增加库存成本；采用扫描法人工安
排的路线虽然装载率和禁忌搜索算法得出的路径相同但具体路径存在略微差异，总路径长度不如禁忌搜索得出的结果优秀；禁忌搜索算法得出的结果，装载率和总路径均为最优，禁忌搜索得出的总路径较直送模式缩短了64.72%，较扫描法缩短了8.83%。由此可见，禁忌搜索得出的结果要优于人工安排的路线，该文设计的模型也是科学有效的。
3 结论
该文对汽车零部件入厂物流的Milk-run路径规划问题
表2 各供应商之间距离（km）
供应商12345678910 1053.24 38.90 85.73 38.28 57.14 50.09 70.77 62.17 39.96 253.24 038.33 61.03 62.65 60.21 50.61 18.25 9.22 27.51 338.90 38.33 046.84 25.61 80.26 70.71 48.83 43.38 48.70 485.73 61.03 46.84 061.40 118.83 108.93 55.66 58.14 84.86 538.28 62.65 25.61 61.40 092.44 83.95 74.40 68.60 66.00 657.14 60.21 80.26 118.83 92.44 09.90 74.85 67.08 33.97 750.09 50.61 70.71 108.93 83.95 9.90 065.79 57.78 24.08 870.77 18.25 48.83 55.66 74.40 74.85 65.79 09.06 44.41 962.17 9.22 43.38 58.14 68.60 67.08 57.78 9.06 035.69 1039.96 27.51 48.70 84.86 66.00 33.97 24.08 44.41 35.69 0 1182.86 59.36 43.97    3.00 58.42 116.67 106.78 54.82 56.86 82.73 1276.58 27.31 65.46 78.75 89.96 62.39 55.00 23.09 23.09 40.31 1352.80 22.67 54.23 83.60 74.81 3
9.00 30.08 35.85 28.30 13.60 1427.46 42.05 50.45 92.91 61.13 31.32 23.09 60.01 51.00 17.46 1549.01 26.08 16.28 40.80 41.77 78.57 68.68 33.12 28.86 44.82 1619.24 35.61 23.43 68.94 35.06 58.69 49.65 52.35 44.10 31.06 1768.48 37.70 72.11 98.11 92.78 37.12 31.62 45.25 40.22 28.64 1843.29 55.03 69.20 110.42 79.38 14.04 10.63 71.59 63.06 27.51 1938.08 33.53 51.89 89.94 67.27 29.07 19.21 50.49 41.77    6.08 2065.39 13.04 44.42 55.54 69.89 71.11 61.85    5.39    4.12 39.81
续表2 各供应商之间距离（km）供应商11121314151617181920 182.86 76.58 52.80 27.46 49.01 19.24 68.48 43.29 38.08 65.39 259.36 27.31 22.67 42.05 26.08 35.61 37.70 55.03 33.53 13.04 343.97 65.46 54.23 50.45 16.28 23.43 72.11 69.20 51.89 44.42
4  3.00 78.7
5 83.60 92.91 40.80 68.94 98.11 110.42 89.94 55.54
558.42 89.96 74.81 61.13 41.77 35.06 92.78 79.38 67.27 69.89 6116.67 62.39 39.00 31.32 78.57 58.69 37.12 14.04 29.07 71.11 7106.78 55.00 30.08 23.09 68.68 49.65 31.62 10.63 19.21 61.85 854.82 23.09 35.85 60.01 33.12 52.35 45.25 71.59 50.49    5.39 956.86 23.09 28.30 51.00 28.86 44.10 40.22 63.06 41.77    4.12 1082.73 40.31 13.60 17.46 44.82 31.06 28.64 27.51    6.08 39.81 11077.88 81.84 90.44 38.42 66.21 96.65 108.07 87.73 54.42 1277.88 027.20 57.78 51.79 61.07 26.
93 63.39 45.54 24.08 1381.84 27.20 030.89 46.24 41.11 18.03 37.01 18.38 32.25 1490.44 57.78 30.89 052.15 27.78 43.28 18.87 12.81 55.01 1538.42 51.79 46.24 52.15 030.27 63.06 69.66 49.52 29.15 1666.21 61.07 41.11 27.78 30.27 058.69 46.65 32.25 47.01 1796.65 26.93 18.03 43.28 63.06 58.69 041.63 30.81 43.42 18108.07 63.39 37.01 18.87 69.66 46.65 41.63 021.54 67.19 1987.73 45.54 18.38 12.81 49.52 32.25 30.81 21.54 045.89 2054.42 24.08 32.25 55.01 29.15 47.01 43.42 67.19 45.89 0
进行了研究，建立了一个数学模型，并根据模型设计了相应的禁忌搜索算法，利用MATLAB 软件编程，用软件随机生成数据，验证模型的可行性。现得到以下结论：1）循环取货可以有效解决汽车生产企业进行JIT 生产后出现的零库存和运能浪费之间的矛盾，既降低了生产企业的库存水平，也杜绝了空车返回的运能浪费现象。不仅能大大节约运输路径，在Milk-run 到货准点率高的基础上可以将企业的库存降至零，可以省去绝大部分的库存费用，这样做降低大量的物流成本，并直接影响到终端价格，提升产品竞争力。
2）禁忌搜索这种算法十分高效，不会陷入局部最优，
可以在较短的时间内计算出一个近似最优解。笔者将TS 算法得出的路径与扫描法路径做对比，结果表明禁忌搜索算法十分适合解决循环取货车辆路径问题。
参考文献
[1]Glover， F.， Taillard， E. a user’s guide to tabu search [J]. annals of Operations Research， 199
3（41）：： 3-28.
汽车租赁网[2]董蕊，刘冉，江志斌，任盼. 具有时间窗约束累积性车辆路径问题的禁忌搜索优化算法[J]. 工业工程与管理，2015（01）：49-55.
[3]廖大强，邬依林，印鉴. 基于禁忌搜索算法的线路规划方案求解[J]. 计算机工程与设计，2015（05）
：1368-1374.[4]  Maria KS. The welfare effects of different pricing，schemes for el
ectricity distribution in Finland [J]. Energy Policy，2004, ，32（12）：1429-1435.
图4 路线视图
图5 运输长度与迭代次数曲线
表5 禁忌搜索算法路线表
线路总运行距离/km
单次取货量/m ³
装载率禁忌搜索
计算结果
2-12-17-13
120.871260%3-5-1-16125.821260%10-19-7-6-18-14131.8920100%15-11-4-8-20-9
148.4020100%合计
526.98
64
—
表6 扫描法路线表
线路总运行距离/km
单次取货量/m ³
装载率扫描法计算结果
2-12-17-13
120.871260%3-5-16-1141.511260%10-7-6-19-18-14167.2620100%15-11-4-8-20-9
148.4020100%合计
578.04
64
—
表3 供应商与RDC 之间距离（km）
供应商0123456距离038.6017.202357.6345.8861.62供应商78910111213距离51.7432.7624.8428.0255.3244.2931.40供应商14151617181920距离
35.78
16.97
19.70
q74.2
49.16
52.80
32.56
27.46
表4 供应商计划取货量（m ³）
供应商0123456取货量0324333供应商78910111213取货量2434235供应商14151617181920取货量
5
5
布加尼2
2
2
4
3