基于贪心算法的货运公司车辆调度及货物装载问题的解决

李方方

摘 要：货运公司在运输货物时，由于货物大小、重量不一样，为了降低货物损失，必须按照一定顺序摆放；而位于路线不同点上的公司对货物种类、数量的需求有差异。为了实现货运公司的利润最大化以及客户需求被很好的满足，必须合理安排车辆以及车上所载货物，争取用最少车辆满足客户的需求。本文使用贪心算法，利用其最优子结构和贪心选择构造出贪心解，并且该贪心解是足以解决本问题，从而得出动态规划的最优解，最后使用启发式策略合理分配派车方案，实现货运公司利润最大化。

关键词：动态规划；贪心算法；启发式算法；构造解的结构；最短路径求解

1.引言

货运公司在运输货物时，由于货物大小、重量不一样，为了降低货物损失，必须按照一定顺序摆放；而位于路线不同点上的公司对货物种类、数量的需求有差异。为了实现货运公司的利润最大化以及客户需求被很好的满足，必须合理安排车辆以及车上所载货物，争取用最少车辆满足客户的需求和到达相应客户点时卸货的方便。

本文通过使用贪心算法，利用其最优子结构和贪心选择构造出贪心解，并且该贪心解是足以解决本问题，从而得出动态规划的最优解，最后使用启发式策略合理分配派车方案。

2.实例研究

2.1 问题描述

某地区有8个公司，某天某货运公司要派车将各公司所需的三种原材料A，B，C 从某港口分别运往这些公司。路线是唯一的双向道路。货运公司现有一种载重 6 吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次。每辆车平均需要用 15min的时间装车，到每个公司卸车时间平均为10min，运输车平均速度为 60km/h，每日工作不超过8h。车载重运费 1.8 元/吨公里，空载费用 0.4 元/公里。一个单位的原材料 A，B，C分别毛重4t、3t、1t，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量，需求量见下图。 在这些给定的条件下，求最佳的调度方案，使得成本最小。

2.2 问题假设

每辆车装车时彼此独立，不需等待；每辆车进出港口彼此独立，不会堵塞；运输道路充畅，不堵车；车行驶过程不发生突发事件；每家公司对货物种类和数量需求无时间上优先级，即当天满足即可；车辆不调头。

2.3优化方案及方法

2.3.1符号说明：W（i，j）：第i次送货到第j公司货物的重量；D（i，j）：第i次送货到第j公司货物的载重路径；N：出车次数；E（i，j）：第i次送货到第j公司的后产生的空载费用；A（i，j，k）：一辆车上载i单位A，j单位B，k单位C

2.3.2 模型的建立

（1）描述动态规划解的算法：费用组成由载重费用、空载费用、港口出车费用和固定出车费用组成，具体计算公式如下：1）固定出车费：6*20=120元；2）港口出车费：10*N；3）载重费用：1.8*W（i，j）*D（i，j），表示第i次送貨到j公司载重费用，其总费用可在EXCEL里实现。4）空载费用：0.4*（60-D（i，j）），表示第i次送货到j公司后产生空载费用；其总费用可在EXCEL里实现；

（2）最优子结构描述：1）每次派车都应该充分发挥其运载能力；2）、每次派车的货物都尽可能的运往一个公司；3）、载重的路程应尽量按就近原则；4）、每次派车的货物种类或数量应尽量满足大部分的公司的货物种类和数量 需求。

（3）贪心选择：因为公司的位置和所需货物固定，影响其费用的仅为该公司的车次和运载方向；我们可以贪心的选择在最优子结构条件下，是该家公司所需车次最少，并合理选择其出车方向。在运输车满载的情况下有以下方案：A（1，0，2），A（0，0，6），A（0，2，0），A（0，1，3），所特别的是8家公司的B货物需求为18单位，恰可通过派车方案A（0，2，0）9次完成；下面则只讨论A和C货物的，A的需求为18单位C需求为26，若只用A（1，0，2）则C超出，则可以考虑（1，0，1）（1，0，0）（0，0，3）（0，0，2）（0，01），使每家公司可以用最少车次完成所需。下面是通过贪心选择的A和C的派车方案如下表一：

其中的每车次运输方向按载货路程的就近原则，我们通过表格很容易看出最优选择之一总是贪心的选择，那么贪心选择是安全的，可以最终得出最优的贪心解。

（4）合并最优子结构和贪心选择：通过表一我们可以得出5、6、7公司分别需要一辆车次来运2、3、1单位的的C，我们可以将以一车次的A（0，2，0）与之合并产生两次的A（0，1，3）则可以减少车次，最终得出A、B、C的最终运输方案如下（表2）：

（5）求最后贪心解：建立EXCEL表格，利用启发式算法合理安排派车方案，算出贪心解，即最后可以替代的动态规划解

3.结束语

对于本案例的解决，采用了贪心解直接给出了动态规划解。但最后给出的是贪心解的结构，从而得出的优化解只是在满足最优值的条件下一种解的结构，无法给出符合最优值的全部解的结构。在不考虑解的结构约束的情况下，是可取的，并不一定是最优值的解，但确很逼近该最优解，且这种贪心解的结构是合理的。（作者单位：南京农业大学）

参考文献

[1] 算法导论，（美）Thomas.Cormen Charles E.Leiseron Ronald L.Rivest Clifford Stein 著，潘金贵 顾铁成 李成法 译 机械工业出版社。

[2] 百度百科