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

1、整车和零担混合物流配载问题的建模与求解： 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

2、 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 solut

3、ion 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

4、 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.0 引 言 运输按照车辆装载的货物形态分为整车运输与零担运输两 种模式 1-2 。零担运输一般指当一批货物的重量或容积不满一 辆货车时，可与其他几批甚

5、至上百批货物共用一辆货车装运的运 输方式；而整车运输通常是指因一批货物的重量、性质、体积或 形状需要以一辆或一辆以上货车装运而按整车条件来运输的运 输方式。对比两种运输方式，整车运输具有一次运载量大、运输 组织相对简单、 单位配载费用较低等特点， 而零担物流则具有一 次运载量较小、 运输组织相对复杂、 单位配载费用一般较高的特 点。对物流公司来说，当货物数量较多时，其自有车的运输能力 有限不能满足用户需求，往往需要外雇其他货运公司的运输车 辆。在实际配载过程中需要综合很多因素， 比如考虑到公司利益 以及外雇车的实际情况， 通常对外雇车采用整车运输模式， 对自 有车采用零担运输模式， 这样既可以

6、提高物流的运输效率又能够 降低运营成本。另外在实际配载过程中由于运输货物属性多样， 出于安全考虑，要求一些有毒有害物品不能与食品等同车运输， 所以实际配载时又需要考虑物品的兼容性。 本文研究的整车和零 担混合物流配载问题， 目的在于决策如何配载以使在两种运输模 式下的总配载费用最小，具有重要的现实意义。对于零担运输问题， Chu 在文献 3 中提出了一种针对整车 和零担物流问题的启发式算法，通过五个算例对算法进行了测 试，结果表明他们提出的启发式算法在针对时间及准确性的问题 中能得出较好的解决方案； Konur 和 Schaefer4 为评估碳排放 量，有创意的研究了零担运输问题， 通过大量实

7、际的零担物流问 题，设计了一个专基于 Estes 快递网络和操作的、 可针对未知运 输商的零担物流通用模型。对于整车运输， Jothi 等 5 通过大 量对整车物流的研究， 以及大量相关数据， 评价研究了整车物流 的重要性、一些典型的模型以及当前的研究趋势等。 Doerner 等 6 提出了一种新的解决整车物流问题的混合蚁群算法，通过实 验得出结论， 在解决特定车队规模的整车物流问题时， 这种新的 混合遗传算法解得的解决方案要优于传统的蚁群算法。本文针对整车和零担混合物流配载问题， 建立了整数规划模 型，并使用商业优化软件 iLog-CPLEX 求得了小规模算例的最优 解。由于 iLog-CP

8、LEX 无法求解大规模问题，本文选择智能优化 算法进行求解。 智能优化算法能够在较短时间内获得近优解， 不 受问题结构规模的限制， 适合求解较大规模问题。 本文则是选用 一种较好的智能优化算法差分进化算法来求解整车和零担 混合物流配载问题。 差分进化算法是一类基于种群的启 发式算法，对于实值参数的优化有较好的鲁棒性。应用DE求解整车和零担混合物流配载问题需要合理设计编码方式、 交叉和变 异过程等。本文针对此类问题的特点，对DE的编码、变异以及交叉过程进行设计， 提出了一种基于分组编码方式的离散差分进 化算法。通过和 iLog-CPLEX 软件的结果对比，验证了本文提出 的改进差分进化算法在求解

9、整车和零担混合物流配载问题上的 有效性。1 整车和零担混合物流配载问题 本文研究的整车和零担混合物流配载问题可以描述如下： 给 定货物集合N,任意货物i N的重量记为w,车厢最大装载量记 为B,整车运输模式的单车配载费用记为入，零担物流模式下单位重量配载费用记为 卩，可外雇采用整车运输的车厢集合记为 K;不兼容的货物对集合记为 A,在满足车厢容量限制和货物兼 容性约束的前提下， 决策每个托运物品由哪种运输模式服务以及 物品在整车运输模式下如何配载， 从而使得总配载费用最小。 令 二元变量 x 定义货物 i 的装载模式， 即 x=1 表示货物采用零担运 输模式， x=0 表示货物采用整车运输模式

10、;二元变量y 表示是否将货物 i 装入第 k 个箱子;二元变量 z 表示第 k 个车箱是否启用。 基于上述参数和变量的定义， 整车和零担混合物流配载问题可以 表示为以下的整数规划模型：目标函数（ 1）为最小化两种运输模式下的总配载费用;约 束（ 2）要求每个货物要么使用零担运输模式，要么使用整车运 输模式且必须被装载到一个车厢;约束（ 3）定义了整车运输模 式下车载容量的上限和下限;约束（ 4）是对物品装载的兼容性 要求，即当两个货物不兼容时，就不能同时装载到一个车厢;约 束（5）（7）定义了变量的取值范围。注意到，约束（ 3）的左端项属于有效不等式约束，即使省去左端项的约束也不影响模型的最优

11、解， 因为当一个车厢的装载 量小于入/ U时，在最优解中是不用采用整车运输模式，这是由于此时将整车运输模式转换为零担运输模式不会增加装载费用。 虽然不影响最优解，但是增加约束（ 3）左端项的有效不等式可 以缩减可行解空间，由此可以提高模型的求解效率。另外，为了 降低模型结构的对称性，增加以下有效不等式（8 ）（9）来削减解空间。当问题规模较小时，上述 MIP模型可以使用商业优化软件 iLog-CPLEX 直接求解。以开发环境 visual studio2008 为例， 具体实现过程如下：（ 1）启动 visual studio 2008 ，创建一个 win32控制台应用程序。在 C/C+下选择

12、常规，在附加包含目录 中添加 iLog-CPLEX 软件所包含的 concer 和 cplex 文件夹下的 include 文件夹，目的是确定需要引用 iLog-CPLEX 相关函数的 头文件的位置；在 C/C+下选择预处理器，在预处理器定义中添 加IL_ STD ;在C/C+下选择代码生成，在运行时库中选择多线 程（/MT）,在左侧的配置属性中选择链接器，将cplex125.1ib ,ilocplex.lib ， concert.lib 三个静态链接库所在的文件夹位置 信息配置到附加库目录中， 同时在附加依赖项中添加上述三个静 态链接库。（ 2）在程序代码中定义参数常量，包括：货物重量 数组

13、lloNumArray w,不兼容货物对数组lloArrayA ,以及int N； int B ； int K ； double lambda ； double miu 。从外部数据文件 中将数据读入上述定义的参数中。( 3)在程序代码中定义决策 变量， 包括： IloBoolVarArray x；IloArrayy ；IloBoolVarArray Z；基于定义的常量和变量，将目标函数和约束添加到模型 lloModelMIPmodel (env_)；定义求解器 lloCpIexcpIex (env_), 并将模型装载到求解器 cplex.extract ( MIPmodel);运行求解 器

14、cplex.solve 。( 4)基于求解器运行的结果， 得到决策变量 x， y， Z 的最优值和最优目标函数值。2 差分进化算法由于 iLog-CPLEX 只能求得小规模算例的最优解，对于大规 模问题， 在有限时间内不能求解最优解甚至可行解。 因此需要设 计更有效的算法。DE算法的本质是一种基于实数编码的具有保 优思想的进化算法， 其基本思想是： 对当前种群进行变异和交叉 操作，产生另一个新种群， 然后利用贪婪算法对这两个种群进行 选择，从而产生最终的新一代种群。编码方式： 针对零担与整车物流的配载问题， 本文采用了一 种基于分组的编码方式。 在这种编码方式中， 个体的基因表示一 组物品的子

15、集， 子集中物品的重量不超过箱子的容量。 该编码方 式使得种群空间与解空间一一对应， 解决了传统编码方式放大解 空间的缺陷，提高了算法的搜索速率与鲁棒性。由于编码方式的差异，传统的变异与交叉操作已不再适用， 因此本文设计了新的变异与交叉操作方法。交叉操作： 首先计算两亲代各基因的装载量， 再将两亲代的 基因按照等位基因顺序与装载量的大小进行重新排序， 其中等位 基因按照装载量大小排序， 装载量大的基因位于装载量小的基因 前，非等位基因按照基因的顺序进行排序。 再从基因排序的第二 个基因位开始，将含有之前基因已存在物品的基因删除，并用BFD启发式算法将未装入箱子的个体编入个体，最后根据各基因 的装载量大小对各基因进行排序