越库中心选址模型与启发式算法
毛道晓，徐克林，张志英，侯丽清
(同济大学 机械与能源工程学院，上海，201804)
摘要：考虑客户服务水平，以运输成本、越库中心作业和固定成本、延迟交货惩罚成本总和最小化为目标，建立越库中心选址的混合整数规划模型。在中小规模情形下，运用lingo求问题的精确解，同时根据模型中目标函数的不同特征，构建2种启发式算法求问题的近优解。实验结果表明：在所测的20组数据中，性能较优的启发式算法H2求得的解与精确解的平均误差分别为0.28%和3.24%，接近于精确解，这表明启发式算法H2是有效的。
关键词：越库；选址；混合整数规划；启发式算法
中图分类号：TP301；F252 文献标志码：A 文章编号：1672-7207(2013)02-0564-07
Site selection model of cross-docking centers and heuristics
MAO Daoxiao, XU Kelin, ZHANG Zhiying, HOU Liqing
(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)
Abstract: Considering customer service level, a mixed integer programming model was presented for sit selection of Cross-docking centers with the objective to minimize the cost including transportation cost, operational and fixed cost, and backordering penalty cost. Lingo was used to find the optimal solution, while two heuristics were described to solve the problem approximately according to its different characteristics under small and medium scale situations. Numerical experiment results show that compared with optimal solution, 0.28% and 3.24% gaps are gained respectively in small and medium scale situations by H2 in 20 groups of test data that are tested, which indicates the proposed heuristics H2 is efficient.
Key words: cross-docking; location; mixed integer programming; heuristics
越库(cross-docking)作为一种相当有效的物流技术，可以快速地合并来自不同资源的货物，降低库存，实现对外运输的规模经济效益[1-2]。其定义是指在物流的任何中间点(仓库或配送中心)只实现收发货的功能而消除货物存储与订单获取的功能[3]。越库是配送系统中的准时制策略，货物从不同的供应商运往越库中心，在越库中心完成卸载、分拣、存储、拣选和装运，然后送往不同的客户，该过程一般不超过24 h[4-5]。近些年，由于越库的这些优点使得它越来越受人们的关注，并被广泛地应用于不同领域的许多公司，如零售公司和零担运输公司等[6-7]。尽管越库的概念相对简单，但实施却十分复杂，国内外关于越库技术的研究尚不多见。根据决策水平不同，对越库的研究大致可以分为3类：战略层、策略层和运作层[8]。战略层主要考虑公司长期的计划，如越库中心选址[1]和越库中心最佳形状确定[9]等；策略层主要考虑中期计划，如仓门分配[10]和车辆路径优化[11]等；运作层主要考虑越库中心作业优化，如作业时间优化[12]和作业调度[13]等。本文研究的内容属于战略层，目前，国内外对于战略层的越库中心选址研究很少，主要有：Jayaraman等[14]提出了两阶段网络规划模型，并运用模拟退火算法决定在供应链网络中开设哪些越库中心和配送中心。Gumus等[15]针对中小规模系统构建了优化模型使多梯度成本最小化。Ross等[1]在文献[14]的基础上运用2种控制机制更为复杂的启发式算法对越库中心和配送中心的选址进行研究，并对算法进行了评估。然而，上述研究在构建选址模型的时候主要考虑运输成本、越库中心作业和固定成本，并没有考虑客户服务水平。由于越库技术是物流在准时制方面的重要应用，通过该技术配送的货物一般对时间的要求非常高，因此，其客户服务水平主要体现在能否按时交货。在实际的运作过程中，若不能保证准时交货，将会产生很高的延迟交货惩罚成本，因此，在构建选址模型的时候仅考虑运输成本、越库中心作业和固定成本不能有效降低总成本，而增加考虑延迟交货成本，其选址布局结果将更接近实际，越库中心的作业也将更加有效。本文作者在传统配送中心选址模型的基础上，增加延迟交货成本，构建0-1混合整数规划模型，然后提出2种启发式算法来获得近优解，并通过数值实验检验算法的有效性。
1 建立模型
1.1 问题描述
本文研究的问题描述如下：在一个三级供应链网络中，假设有l个供应商区域，m个备选越库中心和n个客户区域，共有q种货物在该网络中流通。供应商根据客户的订单将一定数量的货物用卡车运送到越库中心，并在越库中心按照目的地进行分装，最后配送到各客户区域。本文的目标是通过合理地选择越库中心并安排货物流通以降低总成本。为突出问题的特性，假设：
(1) 供应商的供货能力和客户的需求稳定且已知，供应商能满足所有客户的需求，且同种货物的生产成本一样。
(2) 越库中心的容量有限，当超过其容量时，超过的部分不能实现从该越库中心配送；越库中心的固定成本随其容量的增加而增加。
(3) 货物在越库中心进行简单的拆分和拼装，其操作时间较运输时间短很多，可忽略不计；各结点间运输条件相当，即运输费用越高，其运输时间也相应地越长。
(4) 客户在其发出订单的期望时间内没有收到货物，其订单不会取消，将采用延迟交货成本作为惩罚。货物提早达到的现象可以通过调节发货时间来避免，因此，不产生提早达到惩罚成本。
1.2 越库中心选址模型
为了使问题更加清晰化，同时考虑采用lingo求得问题的精确解，本文以运输成本、越库中心作业和固定成本、延迟交货惩罚成本总和最小化为目标，建立了越库中心选址的0-1混合整数规划模型。模型中用到的符号说明如下：
为第s种产品从供应商区域i经过备选越库中心k配送到客户区域j的数量；aik为单位数量的货物从供应商区域i到备选越库中心k的运输费用；bkj为单位数量的货物从备选越库中心k到客户区域j的运输费用；hk为备选越库中心k单位数量货物的作业成本，包括临时存储、搬运等成本；fk为备选越库中心k的固定成本，包括越库中心基础建设和设备购买等成本；uik为从供应商区域i到备选越库中心k所需的运输时间；vkj为从备选越库中心k到客户区域j所需的运输时间；tj为客户区域j发出订单到收到货物的平均期望时间；Tikj为从供应商区域i经备选越库中心k到客户区域j的延迟时间；g为单位数量货物单位时间延迟交货的惩罚成本；
为供应商区域i能提供第s种货物的数量；
为客户区域j对第s种货物的需求量；ek为备选越库中心k允许的最大流量；M为充分大的数；zk为0-1变量，1表示选中备选越库中心k，0则相反；wikj为0-1变量，1表示从供应商区域i经备选越库中心k到客户区域j所需的运输时间大于tj，0则相反。根据上述符号构建混合整数规划模型如下：
；
s=1，2，…，q；i=1，2，…，l (1)
；
s=1，2，…，q；j=1，2，…，n (2)
；k=1，2，…，m (3)
；
i=1，2，…，l；k=1，2，…，m；j=1，2，…，n (4)
；
i=1，2，…，l；k=1，2，…，m；j=1，2，…，n (5)
；
i=1，2，…，l；k=1，2，…，m；j=1，2，…，n (6)
(7)
(8)
目标函数中的第1项为运输成本，第2项是越库中心作业成本，第3项是越库中心固定成本，第4项是延迟交货惩罚成本，目标是各项成本总和最小。约束(1)为供应商能力约束；约束(2)为客户区域需求约束；约束(3)为越库中心容量约束；约束(4)，(5)和(6)确保只考虑延迟交货时间；当wikj=0时约束(5)起作用，当wikj=1时约束(6)起作用；约束(7)为越库中心选择个数约束；约束(8)为非零约束。
2 启发式算法
由于选址问题的NP难特性，精确求解将消耗大量时间，为了在一定时间内找到比较优的可行解，需要从问题的不同特征出发，构建相应的启发式算法。启发式算法的一个特点是求解的近似性，是在求解时间和质量间的抉择，在实际生产中有着广泛的应用[16]。本文受上述模型目标函数的启发，构建了2种启发式算法。
2.1 STT算法(最小运输时间算法)
通过尽量减少各结点间的运输时间来降低延迟交货成本，构建了STT算法。该算法首先计算各结点之间的运输时间和，并从小到大进行排序。然后在运输时间和最小的结点间先安排货物流通，直到所有客户区域的需求都得到满足，停止安排并计算成本。具体步骤如下。
步骤1：计算各结点间的运输时间和，从小到大进行排序并存放入集合R；
步骤2：令Rmin=min{R}，取Rmin对应的路径安排货物流通，同时更新R，R=R\Rmin；
步骤3：如果相应的＞0，＞0，ek＞0，即路径上的3个结点都能接受此次安排，则转入步骤4，否则返回步骤2；
步骤4：取，和ek中的最小值作为此次安排流通的货物的数量，记为，同时更新，和ek，
，
，
；
步骤5：对 s=1，2，…，q和j=1，2，…，n，若=0，则算法结束，计算最终成本记为h1，否则返回步骤2。
数值实验表明：单纯以运输时间和最小构建的启发式算法求解精度不是很理想，故在其基础上通过增加一定的约束构建启发式算法H2，以提高求解精确度。
2.2 启发式算法H2
该算法的核心思想是在尽量减少各结点间运输时间的基础上，通过增加一些约束，缩减或限制解空间，以达到剔除劣解提高求解质量的目的。在算法中，每种增加的约束都对应一种规则，每种规则形成相应的求解模块，各求解模块的最优值即为H2的解。算法针对越库中心的作业成本和固定成本制定4种规则构建4个模块，具体步骤如下。
步骤1：初始化当前解h2；
步骤2：计算各结点间的运输时间和，从小到大进行排序并存放入集合R；
步骤3：判断模块求解是否结束，若是，则算法结束，输出h2，否则，模块继续求解；
步骤4：增加作业成本最高的越库中心最后安排的规则构建模块1进行求解；
步骤4.1：对k=1，2，…，m比较hk的大小，其中最大的记为hmax并标记相应的越库中心为kmax；
步骤4.2：在集合R中提取经过剩余越库中心的各路径运输时间和依次存放入集合R1，
；
步骤4.3：若
，则令Rmin=min{R1}，取Rmin对应的路径安排货物流通，同时更新R1，R1=R1\Rmin，否则，，转步骤4.6；
步骤4.4：若相应的＞0，＞0，ek＞0，即路径上的3个结点都能接受此次安排，则转入步骤4.5，否则返回步骤4.3；
步骤4.5：取，和ek中的最小值作为此次安排流通的货物的数量，记为，同时更新，和ek，，，；
步骤4.6：对 s=1，2，…，q，j=1，2，…，n，若=0，则模块求解结束，其解记为h21，否则返回步骤4.3；
步骤4.7：比较h21与h2，取较优的作为当前解h2，更新模块集返回步骤3；
步骤5：增加固定成本最高的越库中心最后安排的规则构建模块2进行求解；
步骤5.1：对k=1，2，…，m比较fk的大小，其中最大的记为fmax并标记相应的越库中心为kmax；
步骤5.2至步骤5.5同步骤4.2至步骤4.5；
步骤5.6：对 s=1，2，…，q和j=1，2，…，n，若=0，则模块求解结束，其解记为h22，否则返回步骤5.3；
步骤5.7：比较h22与h2，取较优的作为当前解h2，更新模块集返回步骤3；
步骤6：增加从作业成本最低的越库中心开始安排的规则构建模块3进行求解；
步骤6.1：对k=1，2，…，m比较hk的大小，并从小到大进行排序并存放入集合H；
步骤6.2：令hmin=min{H}，对应的越库中心标记为kmin，同时更新集合H，H=H\hmin；
步骤6.3：在集合R中提取经过越库中心kmin的各路径运输时间和，依次存放入集合Rmin，
，同时更新集合R，R=R\Rmin；
步骤6.4：令
，取
对应的路径安排货物流通，同时更新Rmin，
；
步骤6.5：如果相应的＞0，＞0，ek＞0，即路径上的3个结点都能接受此次安排，则转入步骤6.6，否则返回步骤6.4；
步骤6.6：取，和ek中的最小值作为此次安排流通的货物的数量，记为，同时更新，和ek，，，；
步骤6.7：对 s=1，2，…，q和j=1，2，…，n，若=0，则模块求解结束，其解记为h23，否则返回步骤6.2；
步骤6.8：比较h23与h2，取较优的作为当前解h2，更新模块集返回步骤3；
步骤7：增加从固定成本最低的越库中心开始安排的规则构建模块4进行求解；
步骤7.1：对k=1，2，…，m比较fk的大小，并从小到大进行排序并存放入集合F；
步骤7.2：令fmin=min{F}，对应的越库中心标记为kmin，同时更新集合F，F=F\fmin；
步骤7.3至步骤7.6分别同步骤6.3至步骤6.6；
步骤7.7：对 s=1，2，…，q和j=1，2，…，n，若=0，则模块求解结束，其解记为h24，否则返回步骤7.2；
步骤7.8：比较h24与h2，取较优的作为当前解h2，更新模块集返回步骤3；
图1所示为该算法的流程图，其中虚线框内为模块求解过程。
图1 启发式算法H2的流程图
Fig.1 Flow chart of H2
3 数值实验
数值实验包括2个部分：启发式算法之间的比较以及启发式算法求解与商业优化软件lingo求解的比较。
实验数据产生方式如下：在[40 000，90 000]间随机生成，在[10 000，30 000]间随机生成，hk在[2,5]间随机生成，g=5。越库中心总容量视问题规模适当调整，并保持其约为总需求量的1.8倍，固定成本随越库中心容量变动。各结点间运输费用在[1，9]均匀分布，根据各结点间运输条件相当的假设，取相应结点间运输时间为2~3倍运输费用，并使得
。根据以上方法在5-2-3-5规模(5个供应区域，2种产品，3个备选越库中心，5个客户区域)和15-4-5-15规模(数字意义同上)各产生10组不同的数据，进行运算。算法采用Visual Basic 6.0语言编程实现，并在1.73 G主频的Pentium(奔腾) CPU的个人计算机上进行实验测试。
3.1 启发式算法间的比较分析
H2与STT算法的比较见表1；2种规模下H2与STT算法性能比较见图2。从表1和图2可以发现：在给定的2种规模情形下，实测的20组数据中，H2在每次实验中求得的解都比STT算法的好，10次实验的平均差距分别为17.5%和18.7%。这表明在STT算法基础上增加一定约束构建的启发式算法H2对STT算法的性能有很大的提高。
表1 H2与STT算法的比较
Table 1 Comparison of H2 and STT %
3.2 启发式算法求解与lingo求解的比较分析
在给定的2种规模情况下，进一步比较启发式算法与lingo求得的最优解Sopt之间的差距。STT算法和H2求解与最优解的比较见表2；小、中规模下启发式算法的解与最优解的比较分别见图3和图4。由表2、图3和图4可以看出：在2种规模情况下STT算法和启发式算法H2的性能均比较稳定。其中，h1与Sopt的差距较大，平均为21.58%和26.95%。这表明在实际的选址过程中，降低延迟交货成本而忽略越库中心作业成本和固定成本，虽然可以提高客户服务水平，但无法有效降低总成本。小规模下，h2与Sopt非常接近，平均差距仅为0.28%，除第6点外，整体差距保持在1%以内；中规模下，h2与Sopt差距不是很大，平均差距仅为3.24%，整体差距大致保持在5%以内。这表明：通过增加一定约束构建的H2性能确实不错，可以有效地求解越库中心选址问题。值得注意的是：尽管小规模时lingo，STT算法和启发式算法H2求解的时间都几乎为0 s，大规模时lingo约为STT算法的31倍，H2的13倍，但此时lingo求解耗时并不长，处于可接受范围，所以，启发式算法的优势并未完全体现。本文作者认为随着规模继续增大，lingo的求解速度将变得很慢，可以采用启发式算法H2。
图2 2种规模下H2与STT算法性能比较
Fig.2 Performance comparison of H2 and STT for two scale problems
表2 STT算法和H2求解与最优解的比较
Table 2 Comparison of h1, h2 and Sopt %
图3 小规模下启发式算法所得解与最优解比较
Fig.3 Performance comparison of heuristics and optimal solution for small scale problem
图4 中规模下启发式算法所得解与最优解比较
Fig.4 Performance comparison of heuristics and optimal solution for medium scale problem
4 结论
(1) 在越库中心的选址布局问题中，考虑客户服务水平，以运输成本、越库中心作业和固定成本、延迟交货惩罚成本总和最小化为目标建立越库中心选址的0-1混合整数规划模型。根据模型中目标函数的特征，提出2种启发式算法。以运输时间最小为出发点建立STT算法，以降低延迟交货成本。在STT算法的基础上增加约束构建启发式算法H2。该算法采用模块求解取优的方式，可以有效剔除劣解，提高求解质量。
(2) 通过lingo求解混合整数规划模型，并将启发式算法求解的结果与之对比验证算法的有效性。基于STT算法构建的启发式算法H2性能较STT算法有很大提升，平均超过17%；在给定的2种规模情况下H2与最优解都比较接近，平均差距分别为0.28%和3.24%。这表明本文构建的启发式算法H2能有效地解决越库中心选址问题。
参考文献：
[1] Ross A, Jayaraman V. An evaluation of new heuristics for the location of cross-docks distribution centers in supply chain network design[J]. Computers & Industrial Engineering, 2008, 55: 64-79.
[2] Boloori Arabani A R, Fatemi Ghomi S M T, Zandieh M. Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage[J]. Expert Systems with Applications, 2011, 38: 1964-1979.
[3] 俞亮, 陈峰. 最小化误工个数的越库调度模型与启发式算法[J]. 上海交通大学学报, 2009, 43(12): 1984-1988.
YU Liang, CHEN Feng. Cross docking scheduling model and heuristics to minimize the number of tardy jobs[J]. Journal of Shanghai Jiaotong University, 2009, 43(12): 1984-1988.
[4] 马东彦, 陈峰. 以总加权完工时间为目标的两台机越库排序的动态规划算法[J]. 上海交通大学学报, 2007, 41(5): 852-856.
MA Dongyan, CHEN Feng. Dynamic programming algorithm on two machines cross docking scheduling with total weighted completion time[J]. Journal of Shanghai Jiaotong University, 2007, 41(5): 852-856.
[5] Alpan G, Larbi R, Penz B. A bounded dynamic programming approach to schedule operations in a cross-docking platform[J] Computers & Industrial Engineering, 2011, 60: 385-396.
[6] Boysen N. Truck scheduling at zero-inventory cross docking terminals[J]. Computers & Operations Research, 2010, 37: 32-41.
[7] Belle J V, Valckenaers P, Cattrysse D. Cross-docking: State of the art[J]. Omega, 2012, 40: 827-846.
[8] Larbi R, Alpan G, Baptiste P, et al. Scheduling cross docking operations under full, partial and no information[J] Computers & Operational Research, 2011, 38: 889-900.
[9] Bartholdi J J, Gue K R. The best shape for a crossdock[J]. Transportation Science, 2004, 38(2): 235-244.
[10] 强瑞, 缪朝炜, 吴为民. 供应链网络中越库转运中心仓门分配问题研究[J]. 管理工程学报, 2011, 25(1): 209-214.
QIANG Rui, MIAO Zhaowei, WU Weimin. Truck dock assignment problem for crossdocks in supply networks[J]. Journal of Industrial Engineering and Engineering Management, 2011, 25(1): 209-214.
[11] Musa R, Arnaout J, Jung H. Ant colony optimization algorithm to solve for the transportation problem of cross-docking network[J]. Computers & Industrial Engineering, 2010, 59: 85-92.
[12] 但斌, 刘波. 物流配送中心直通配送运作时间优化研究[J]. 管理学报, 2010, 7(2): 233-237.
DAN Bin, LIU Bo. Operation time optimization under cross docking in logistics distribution center[J]. Chinese Journal of Management, 2010, 7(2): 233-237.
[13] Alpan G, Ladier A, Larbi R, et al. Heuristic solutions for transshipment problems in a multiple door cross[J]. Computers & Industrial Engineering, 2011, 61: 402-408.
[14] Jayaraman V, Ross A. A simulated annealing methodology to distribution network design and management[J]. European Journal of Operational Research, 2003, 144: 629-645.
[15] Gumus M, Bookbinder J H. Cross-docking and its implication in location-distribution systems[J]. Journal of Business Logistics, 2004, 25: 199-228.
[16] 陈杰, 陈峰. 非对称不确定性越库调度算法[J]. 上海交通大学学报, 2010, 44(9): 1302-1306.
CHEN Jie, CHEN Feng. Algorithm on cross docking scheduling in asymmetrically uncertain environment[J]. Journal of Shanghai Jiaotong University, 2010, 44(9): 1302-1306.
(编辑 杨幼平)
收稿日期：2012-05-11；修回日期：2012-07-02
基金项目：国家自然科学基金资助项目(70872076)；上海市科技创新行动计划项目(11dz1121803)
通信作者：徐克林(1945-)，女，上海人，教授，博士生导师，从事工业工程、物流工程与管理研究；电话：13661629810；E-mail：tjklxu@163.com
