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),所以决策值,该优先级考虑完毕。此时:
Table 1. Distribution of goods information
表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的实际配装数:
Table 2. Actual delivery
表2. 实际配送货物
额定载重完全被占用,配装结束。
最优配装方案为:,目标函数最大价值。
实际配送货物情况,如表2所示。
基金项目
中国物流学会与中国物流与采购联合会计划项目(2015CSLKT3-199);全国高校物流教研课题(JZW2014048, JZW2014049)和国家级大学生创新创业训练计划项目(201510452007)。
参考文献