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

基于贪心算法货运公司车辆调度和货物装载问题解决摘要：货运公司在运输货物时，由于货物大小、重 量不一样，为了降低货物损失，必须按照一定顺序摆放；而 位于路线不同点上的公司对货物种类、数量的需求有差异 为了实现货运公司的利润最大化以及客户需求被很好的满 足，必须合理安排车辆以及车上所载货物，争取用最少车辆 满足客户的需求本文使用贪心算法，利用其最优子结构和 贪心选择构造出贪心解，并且该贪心解是足以解决本问题， 从而得出动态规划的最优解，最后使用启发式策略合理分配 派车方案，实现货运公司利润最大化关键词：动态规划；贪心算法；启发式算法；构造解的 结构；最短路径求解1.引言货运公司在运输货物时，由于货物大小、重量不一样， 为了降低货物损失，必须按照一定顺序摆放；而位于路线不 同点上的公司对货物种类、数量的需求有差异为了实现货 运公司的利润最大化以及客户需求被很好的满足，必须合理 安排车辆以及车上所载货物，争取用最少车辆满足客户的需 求和到达相应客户点时卸货的方便本文通过使用贪心算法，利用其最优子结构和贪心选择 构造出贪心解，并且该贪心解是足以解决本问题，从而得出 动态规划的最优解，最后使用启发式策略合理分配派车方O2.实例研究2. 1问题描述某地区有8个公司，某天某货运公司要派车将各公司所 需的三种原材料A, B, C从某港口分别运往这些公司。

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