ABSTRACT

In this paper, we study on freight loading problem. A cargo loading integer programming model based on time priority is established. We also give an algorithm for it by dynamic programming, and the loading plan can be optimized. Finally, numerical experiment is reported to show the efficiency of the new method.

Keywords:Cargo Loading, Time Priority, the Integer Programming Model, Algorithm

基于配装优先级的零担货物配装模型与算法

陈佳宁，孙洪春，周厚春

临沂大学数学与统计学院，山东 临沂

收稿日期：2017年4月21日；录用日期：2017年5月9日；发布日期：2017年5月12日

摘 要

本文，研究了货物配装问题。建立了基于时间优先级的货物配装整数规划模型，利用动态规划给出了求解算法，使配装方案得以优化。最后，通过数值算例验证了算法的有效性。

关键词 :货物配装，时间优先级，整数规划模型，算法

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

近年来，物流配送中的货物配装问题成为物流研究领域的热门课题，国内外很多学者进行了相关的研究( [1] [2] [3] )。其中在研究中涉及引入斯皮尔曼(Spearman)等级相关系数，对不同的无量纲化方法进行比较，从中选择出最适合的配送车辆方案( [4] )，但在模型中给出的约束条件和评价指标过少，难以解决实际问题。在配送过程中利用变约束问题选择送货的最佳路径( [5] )，但由于算法过于复杂，论文中缺乏对具体项目必要的可行性分析。运用数据库原理和SQL语言完成了物流配货系统的设计( [6] )。对零担物流调度优化领域当中的货物装箱、路线规划和司机排班三类典型问题展开研究，分别将其建模为不同形式的图着色问题进行表示和求解( [7] )，该方法能够对不同规模的货物装箱实现高效计算，并获得近似最优解。通过给出配装优先级函数来解决配装优先级问题( [8] )。本文，基于货物的时间优先级和实际问题的需要，给出了配装问题的一种动态规划新算法；也给出了算法的数值算例，算例验证了算法的有效性。

2. 配装模型建立

现有一辆运货车，额定载重，容积。对种货物进行配装，第种货物的单位质量，单位体积，单位价值系数，客户对货物的需求量，第种货物的实际装载件数 ()。各种货物的时间优先级不完全相同，所有货物共有种配装优先级为， (，表示第种货物的配装优先级为；，表示第种货物的配装优先级不为)。确定装载货物的种类和数量，在不超过车辆额定载重和容积的前提下，使货车满足货物优先级且装载货物的总价值最大。

目标函数为满足优先级的条件下货车装载货物的总价值达到最大：

同时装载货物的总质量不能超过货车的额定载重，装载货物的总体积不能超过货车的总容积:，；装载货物的件数不超过客户对该货物的需求量：；货物只有一种优先级；装载货物的件数是整件(为自然数)；，当时，表示第种货物的优先级为；当时，表示第种货物的优先级不为；货物配装优先级。因此，基于优先级的货物配装模型：

3. 算法设计

基于动态规划思想，将种货物按照优先级进行分类，先在每个优先级里求出最优装载量，之后通过动态规划的方法求出整体最优解。

基于以上建立的模型，给出下面的求解算法。

Step 1. 第阶段的决策对象是位于时间优先级的货物，该阶段的指标函数记为。表示第阶段的可用的剩余载重量。其中，。表示第阶段的可用的剩余体积。其中，。表示第级货物种类数，

。

表示第1级到第级货物种类数，,其中，。

Step 2. 判断：从第一级到第级所有货物是否达到货车额定载重和额定体积

(1)

(2)

当(1)、(2)同时满足，则该阶段考虑完毕。此时，目标函数为该优先级货物的总价值加前面优先级中货物的总价值，得到递推公式：

当(1)、(2)不同时满足时，货物种类数应满足的条件

在第阶段对该优先级中的货物按照单位价值从大到小逐次检验，满足条件(1)、(2)的逐次累加并取最大值，得到以下递推公式：

Step 3. 重复Step 2，直至配装完最后一件货物或货车已达到额定载重或额定体积。

Step 4. 输出各个货物的实际配装数，结束。

4. 数值算例

某物流中心现有一批货物需要配送，货物共十种，分别采用矩形木箱包装，货物相关信息见表1。运输车辆为一辆，额定载重九吨，容积为二十立方米。根据货物要求运达的时间不同，将货物分为了三种配装优先级。求在满足配装优先级的条件下选择配装货物的品种和数量，使单车的配送价值最大。

求解思路：根据货物的所属优先级不同，3个配装优先级依次计算，再利用动态规划法求解出问题最优解。即在价值系数的情况下，先计算级，再逐级向下计算。

具体求解过程：

Step 1. 初始状态：

在配装优先级1，优先级价值系数为，有1、2两种货物

对和进行决策，判断(1)、(2)式：

(3)

(4)

因为(3)、(4)满足(1)、(2)，所以决策值，该优先级考虑完毕。此时：

表1. 配送货物信息

Step 2. 优先级有3、4、5、6四种货物

对、、、进行决策判断：

(5)

(6)

由(5)、(6)知，不满足(1)、(2)。按照货物的单位价值大小依次对货物5、6、4、3进行计算：

其中即

Step 3. 同理，

Step 4. 同理可求出优先级3中的货物7、8、9、10的实际配装数：

表2. 实际配送货物

额定载重完全被占用，配装结束。

最优配装方案为：，目标函数最大价值。

实际配送货物情况，如表2所示。

基金项目

中国物流学会与中国物流与采购联合会计划项目(2015CSLKT3-199)；全国高校物流教研课题(JZW2014048, JZW2014049)和国家级大学生创新创业训练计划项目(201510452007)。

文章引用

陈佳宁,孙洪春,周厚春. 基于配装优先级的零担货物配装模型与算法
Based on Cargo Loading Priority Scattered Goods Loading Model and Algorithm[J]. 运筹与模糊学, 2017, 07(02): 45-50. http://dx.doi.org/10.12677/ORF.2017.72006

参考文献 (References)