整车和零担混合物流配载问题的建模与求解

邢航　张新邦　李贵栋　汪恭书

摘 要：研究了物流作业中同时考虑整车和零担混合运输模式的配载问题，决策每个托运物品由哪种运输模式服务以及物品在整车运输模式下如何配载，目标为最小化两种运输模式下的总配载费用。为该问题建立了新型整数规划模型，并提出了强化模型的有效不等式，使用商业优化软件iLog-CPLEX求得了小规模算例的最优解。由于iLog-CPLEX优化软件不能在有限时间内求得大规模问题的最优解甚至可行解，针对大规模问题提出一种基于分组编码方式的离散差分进化算法。实验结果显示所提出的算法明显优于传统启发式算法，验证了离散差分进化算法在求解整车和零担混合物流配载问题的有效性。

关键词：整车运输；零担运输；配载问题；混合整数规划；差分进化

中图分类号：U294 文献标识码：A

Abstract： This paper studies the logistics loading problem with hybrid of full and less-than truck load modes， which is to decide that each consignment is serviced by which transportation model and how to load consignments under full truck load model such that total loading cost under two transportation models is minimized. A novel integer programming model formulated， and valid inequalities are proposed to strengthen the model. Commercial optimization software iLog-CPLEX is used to solve the model to optimization for small-scale instances. Because no optimal or even feasible solution of the large-scale problem can be obtained by iLog-CPLEX optimization software within limited computational time， a discrete differential evolution algorithm based on group coding method is proposed for the large-scale problems. Experimental results show that the proposed algorithm is obviously superior to the traditional heuristic algorithm， which verifies that the discrete differential evolution algorithm is efficient to solve the logistics loading problem with hybrid of full truck load and less-than truck load.

Key words： full truck load； less-than truck load； loading problem； mixed integer programming； differential evaluation

0 引 言

运输按照车辆装载的货物形态分为整车运输与零担运输两种模式[1-2]。零担运输一般指当一批货物的重量或容积不满一辆货车时，可与其他几批甚至上百批货物共用一辆货车装运的运输方式；而整车运输通常是指因一批货物的重量、性质、体积或形状需要以一辆或一辆以上货车装运而按整车条件来运输的运输方式。对比两种运输方式，整车运输具有一次运载量大、运输组织相对简单、单位配载费用较低等特点，而零担物流则具有一次运载量较小、运输组织相对复杂、单位配载费用一般较高的特点。对物流公司来说，当货物数量较多时，其自有车的运输能力有限不能满足用户需求，往往需要外雇其他货运公司的运输车辆。在实际配载过程中需要综合很多因素，比如考虑到公司利益以及外雇车的实际情况，通常对外雇车采用整车运输模式，对自有车采用零担运输模式，这样既可以提高物流的运输效率又能够降低运营成本。另外在实际配载过程中由于运输货物属性多样，出于安全考虑，要求一些有毒有害物品不能与食品等同车运输，所以实际配载时又需要考虑物品的兼容性。本文研究的整车和零担混合物流配载问题，目的在于决策如何配载以使在两种运输模式下的总配载费用最小，具有重要的现实意义。

对于零担运输问题，Chu在文献[3]中提出了一种针对整车和零担物流问题的启发式算法，通过五个算例对算法进行了测试，结果表明他们提出的启发式算法在针对时间及准确性的问题中能得出较好的解决方案；Konur和Schaefer[4]为评估碳排放量，有创意的研究了零担运输问题，通过大量实际的零担物流问题，设计了一个专基于Estes快递网络和操作的、可针对未知运输商的零担物流通用模型。对于整车运输，Jothi等[5]通过大量对整车物流的研究，以及大量相关数据，评价研究了整车物流的重要性、一些典型的模型以及当前的研究趋势等。Doerner等[6]提出了一种新的解决整车物流问题的混合蚁群算法，通过实验得出结论，在解决特定车队规模的整车物流问题时，这种新的混合遗传算法解得的解决方案要优于传统的蚁群算法。

本文针对整车和零担混合物流配载问题，建立了整数规划模型，并使用商业优化软件iLog-CPLEX求得了小规模算例的最优解。由于iLog-CPLEX无法求解大规模问题，本文选择智能优化算法进行求解。智能优化算法能够在较短时间内获得近优解，不受问题结构规模的限制，适合求解较大规模问题。本文则是选用一种较好的智能优化算法——差分进化算法来求解整车和零担混合物流配载问题。

差分进化算法是一类基于种群的启发式算法，对于实值参数的优化有较好的鲁棒性。应用DE求解整车和零担混合物流配载问题需要合理设计编码方式、交叉和变异过程等。本文针对此类问题的特点，对DE的编码、变异以及交叉过程进行设计，提出了一种基于分组编码方式的离散差分进化算法。通过和iLog-CPLEX软件的结果对比，验证了本文提出的改进差分进化算法在求解整车和零担混合物流配载问题上的有效性。

1 整车和零担混合物流配载问题

本文研究的整车和零担混合物流配载问题可以描述如下：给定货物集合N，任意货物i∈N的重量记为w，车厢最大装载量记为B，整车运输模式的单车配载费用记为λ，零担物流模式下单位重量配载费用记为μ，可外雇采用整车运输的车厢集合记为K；不兼容的货物对集合记为A，在满足车厢容量限制和货物兼容性约束的前提下，决策每个托运物品由哪种运输模式服务以及物品在整车运输模式下如何配载，从而使得总配载费用最小。令二元变量x定义货物i的装载模式，即x=1表示货物采用零担运输模式，x=0表示货物采用整车运输模式；二元变量y表示是否将货物i装入第k个箱子；二元变量z表示第k个车箱是否启用。基于上述参数和变量的定义，整车和零担混合物流配载问题可以表示为以下的整数规划模型：

目标函数（1）为最小化两种运输模式下的总配载费用；约束（2）要求每个货物要么使用零担运输模式，要么使用整车运输模式且必须被装载到一个车厢；约束（3）定义了整车运输模式下车载容量的上限和下限；约束（4）是对物品装载的兼容性要求，即当两个货物不兼容时，就不能同时装载到一个车厢；约束（5）～（7）定义了变量的取值范围。

注意到，约束（3）的左端项属于有效不等式约束，即使省去左端项的约束也不影响模型的最优解，因为当一个车厢的装载量小于λ/μ时，在最优解中是不用采用整车运输模式，这是由于此时将整车运输模式转换为零担运输模式不会增加装载费用。虽然不影响最优解，但是增加约束（3）左端项的有效不等式可以缩减可行解空间，由此可以提高模型的求解效率。另外，为了降低模型结构的对称性，增加以下有效不等式（8）～（9）来削减解空间。

当问题规模较小时，上述MIP模型可以使用商业优化软件iLog-CPLEX直接求解。以开发环境visual studio2008为例，具体实现过程如下：（1）启动visual studio 2008，创建一个win32控制台应用程序。在C/C++下选择常规，在附加包含目录中添加iLog-CPLEX软件所包含的concer和cplex文件夹下的include文件夹，目的是确定需要引用iLog-CPLEX相关函数的头文件的位置；在C/C++下选择预处理器，在预处理器定义中添加IL_ STD；在C/C++下选择代码生成，在运行时库中选择多线程

（/MT），在左侧的配置属性中选择链接器，将cplex125.1ib，ilocplex.lib，concert.lib三个静态链接库所在的文件夹位置信息配置到附加库目录中，同时在附加依赖项中添加上述三个静态链接库。（2）在程序代码中定义参数常量，包括：货物重量数组IloNumArray w，不兼容货物对数组IloArrayA，以及int N；int B；int K；double lambda；double miu。从外部数据文件中将数据读入上述定义的参数中。（3）在程序代码中定义决策变量，包括：IloBoolVarArray x；IloArrayy；IloBoolVarArray z；基于定义的常量和变量，将目标函数和约束添加到模型IloModelMIPmodel（env_）；定义求解器IloCplexcplex（env_），并将模型装载到求解器cplex.extract（MIPmodel）；运行求解器cplex.solve。（4）基于求解器运行的结果，得到决策变量x，y，z的最优值和最优目标函数值。

2 差分进化算法

由于iLog-CPLEX只能求得小规模算例的最优解，对于大规模问题，在有限时间内不能求解最优解甚至可行解。因此需要设计更有效的算法。DE算法的本质是一种基于实数编码的具有保优思想的进化算法，其基本思想是：对当前种群进行变异和交叉操作，产生另一个新种群，然后利用贪婪算法对这两个种群进行选择，从而产生最终的新一代种群。

编码方式：针对零担与整车物流的配载问题，本文采用了一种基于分组的编码方式。在这种编码方式中，个体的基因表示一组物品的子集，子集中物品的重量不超过箱子的容量。该编码方式使得种群空间与解空间一一对应，解决了传统编码方式放大解空间的缺陷，提高了算法的搜索速率与鲁棒性。

由于编码方式的差异，传统的变异与交叉操作已不再适用，因此本文设计了新的变异与交叉操作方法。

交叉操作：首先计算两亲代各基因的装载量，再将两亲代的基因按照等位基因顺序与装载量的大小进行重新排序，其中等位基因按照装载量大小排序，装载量大的基因位于装载量小的基因前，非等位基因按照基因的顺序进行排序。再从基因排序的第二个基因位开始，将含有之前基因已存在物品的基因删除，并用BFD启发式算法将未装入箱子的个体编入个体，最后根据各基因的装载量大小对各基因进行排序，得到交叉个体。

3 仿真实验

针对零担与整车物流混合配载问题进行仿真实验，对小规模算例分别采用iLog-CPLEX软件和改进的离散差分进化（IDE）算法进行求解，对较大规模算例采用改进的离散差分进化算法进行求解。IDE算法利用Microsoft Visual studio编程实现，在Intel（R）Core（TM）i5-4210M CPU@2.60GHz， 4.00GB内存物理地址扩展，Microsoft Windows 8.1系统电脑上运行。

从表2可以看出，BFD算法虽然求解速度快，但是解的质量较差，甚至全都差于IDE算法的最差解，说明IDE在求解大规模问题上具有很大优势，采用IDE求解大规模零担与整车物流混合配载问题是可行的，并且值得推广使用。

4 结 论

本文研究了一类广泛存在于物流运输过程中的整车和零担混合物流配载问题，建立了该问题的混合整数规划模型，提出了一种基于分组编码方式的离散差分进化算法，并通过和iLog-CPLEX优化软件结果以及传统启发式算法BFD结果进行比较，验证了本文的改进的离散差分进化算法在求解此类问题的有效性，可以在实际中推广使用。

参考文献：

[1] 张婷. 零担物流业回顾与发展[J]. 中国储运，2011（9）：66-69.

[2] 杨怀珍，熊炜，董欢欢. 整车物流研究现状述评与趋势展望[J]. 生产力研究，2012（9）：242-244.

[3] Chu C W. A heuristic algorithm for the truckload and less-than-truckload problem[J]. European Journal of Operational Research， 2005，165（3）：657-667.

[4] Konur D， Schaefer B. Integrated inventory control and transportation decisions under carbon emissions regulations： LTL vs. TL carriers[J]. Transportation Research Part E Logistics & Transportation Review， 2014，68（4）：14-38.

[5] Basu R J， Subramanian N， Cheikhrouhou N. Review of Full Truckload Transportation Service Procurement[J]. Transport Reviews， 2015，35（5）：599-621.

[6] Doerner K， Hartl R F， Reimann M. A hybrid ACO algorithm for the Full Truckload Transportation Problem[J]. Institute of Management University of Vienna， 2001（5）：137-145.

[7] Storn R， Price K. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces[J]. Journal of Global Optimization， 1997，11（4）：341-359.