车辆配载问题的动态规划

子任务4.2　车辆配载问题的动态规划

4.2.1　任务引入

【任务4-2】　某物流公司在某一条运输路线上发运一辆汽车，汽车的载重上限为10t。如果该条路线上有3种物品需要发运且可以选择性装载，物品单位质量和效益值如表4-9所示。问此时应如何选择装载物品的数量，使该次运输为公司创造效益最大。

表4-9

4.2.2　任务分析

这是一种变量为正整数的动态规划典型问题。当有N种运价不同的货物需要装载在运载量为W的运输工具上。货物装载问题就是寻求最佳装载方案，使货物的装载总量不超过运输工具允许装载量W，而获得的运量为最大。

可以将该问题按3种货物分为3个阶段，分别在每一阶段根据该货物的运价，确定其装运件数，最终使得总的运量最高。这是现代物流中较为实际的一个规划算例。

4.2.3　任务实施

步骤一　分阶段建立模型

设第i种货物的件数为u_i（i=1，2，3，…，n），则问题可表述为：

maxz=4u₁+5u₂+6u₃

下用动态规划逆序解法建模求解：

阶段k：将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分为3个阶段，即k=1，2，3。

状态变量s_k：表示第k段开始时到第3阶段可供装载的总质量。允许状态集合为

S_k=｛0，1，2，…，10｝，S₁=｛10｝

决策变量u_k：装入第k种物品的件数，且u_k要取正整数。

状态转移方程：

s_k+1=s_k-a_ku_k（k=1，2，3）

其中a_k表示第k种货物的单件质量，允许决策集合为

D_k（s_k）=｛u_k|0≤u_k≤s_k/a_k，u_k要取正整数｝

边界条件f₄（s₄）=0。

步骤二　递推过程

（1）k=3时

当s₃=0，1，2，3，4时，u₃=0；s₃=5，6，7，8，9时，u₃=0或者1件；s₃=5，6，7，8，9，10时，u₃=0，1或者2件。由此确定f₃（s₃），第三阶段决策见表4-10。

表4-10

（2）第二阶段，k=2时

第二阶段决策见表4-11。

表4-11

（3）第一阶段，k=1时

第一阶段决策见表4-12。

表4-12

步骤三　结论

由上述计算可知，A货物装2件，B货物装1件，C货物不装，此时满载，且创造效益最大，为13。