华中农业大学_瑞恒科技杯_运输(原稿)_汤志高

《华中农业大学_瑞恒科技杯_运输(原稿)_汤志高》由会员分享，可在线阅读，更多相关《华中农业大学_瑞恒科技杯_运输(原稿)_汤志高（19页珍藏版）》请在金锄头文库上搜索。

1、货运公司的运输问题货运公司的运输问题 作者：汤志高 hihihi 【摘要摘要】 本文深入研究了具有供求平衡、有序卸货特点的运输问题，建立最优化模型求 解最小运费，采用启发式算法安排每辆车的运载方案。 在问题一的假设下，可以得出每次出车行程均相同的规律，显然存在贪婪因子 （每次行车费用=运载费用+空载费用） 。采用贪婪算法，在卸货顺序约束下对每次 出车求局部最小费用且尽可能满载，最后得出全局解。通过启发式算法配车得到 6 辆车分别工作 7.2511、 7.0835、 7.4187、 6.1696、 5.8344、 5.8344(小时)， 总费用 4771.2 元，总运次 27 次（具体运载方案见

2、 5.1.3） 。 在问题二的假设下，由于题中路程唯一，车速不变，可以得出如下定理： 一、车辆载重行程是各公司到港口最短路，且载重费用固定不变(5.2.1 证明)； 二、车辆当且仅当运完最后一件货才调头（5.2.1 证明） ； 推论：运载里程与空载里程相同，且每次出车均不绕圈工作。 以所有定理为基础，加入卸货顺序约束，车容量约束，公司需求约束，以每次 运输量 ijk P为决策变量，最小总费用为目标，建立混合动态规划模型，使用 LINGO 软件编程求解最小运费及运次方案，通过启发式算法配车得到 4 辆车分别工作 6.917、7.3838、5.7839、6.5338(小时)，总费用 4485.6

3、元，总运次 29 次（具体运载 方案见 5.2.5） 。 问题三讨论存在多种容量货车时的运载方案，易证定理一、二及推论成立，在 问题二模型基础上，引入 0-1 变量控制每次出车类型、车容量、空载费用，同样以 每次运输量 ijk P为决策变量，最小总费用为目标，建立混合动态规划模型，对求解 结果（最小运费、运次方案，见 5.3.2）按启发式算法配车，需要一辆 6 吨位车，工 作 7.4171（小时） ，运送 5 次；两辆 8 吨位车，工作时间分别为 7.3005、7.135（小 时） ，共运送 16 次（具体运载方案见 5.3.4） 。 通过问题 3 结果分析，存在定理三：当空载运输路程大于 1

4、00 3 公里的条件下才有 可能存在 4 吨位车的使用。本题的空载运输路程都小于 100 3 公里，说明并不需要使 用 4 吨位的车，而且从全局考虑为了个别出车添加派车非常不符合实际情况，同时 也不具有经济优势。 1 问题重述问题重述 某地区有 8 个公司（如图一编号至） ，某天某货运公司要派车将各公司所需的 三种原材料 A,B,C 从某港口（编号）分别运往各个公司。路线是唯一的双向道路（如 图一） 。货运公司现有一种载重 6 吨的运输车，派车有固定成本 20 元/辆，从港口出车 有固定成本为 10 元/车次（车辆每出动一次为一车次） 。每辆车平均需要用 15 分钟的时 间装车，到每个公司卸车

5、时间平均为 10 分钟，运输车平均速度为 60 公里小时（不考 虑塞车现象） ，每日工作不超过 8 小时。运输车载重运费 1.8 元/吨公里，运输车空载费 用 0.4 元/公里。一个单位的原材料 A,B,C 分别毛重 4 吨、3 吨、1 吨，原材料不能拆分， 为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许 卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见图二） 。 问题：1.1.货运公司派出运输车 6 辆，每辆车从港口出发（不定方向）后运输途中不允许 调头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。 2.2. 每辆车在运输途中可随时调头，若要

6、使得成本最小，货运公司怎么安排车辆数？应 如何调度？ 3.3.（1）如果有载重量为 4 吨、6 吨、8 吨三种运输车，载重运费都是 1.8 元/吨公里， 空载费用分别为 0.2，0.4，0.7 元/公里，其他费用一样，如何安排车辆数和调度方案？ （2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出 你的解决问题的想法（可结合实际情况深入分析） 。 2 模型假设模型假设 (1) 港口的容量足够大，多辆运输车同时到达港口时不会发生阻塞现象； (2) 多辆运输车可以在港口同时装车，不必等待； (3) 双向道路上没有塞车现象； (4) 8 个公司之间没有优先级别，货运公司只要满

7、足他们的需求量就可以； (5) 运输车完成当日的运输任务之后，回到港口； 3 符号说明符号说明和名词约定和名词约定 ijk P 第 i 次送货到第 j 个公司的第 k 种货物的单位数 单位 k W 1 单位第 k 种货物的重量 吨 1jD 从港口到第 j 个公司的顺时针距离 公里 2jD 从港口到第 j 个公司的逆时针距离 公里 i B 第 i 车次的空载费用 元 jk G 第 j 个公司第 k 种货物的需求量 单位 顺时针距离：运输车从港口出发，按顺时针方向沿着环形路线达到某公司经过的距离； 逆时针距离：运输车从港口出发，按逆时针方向沿着环形路线达到某公司经过的距离； 最短距离： 港口和公司

8、的最短路的路程。 4 问题分析问题分析 运输过程的最大特点是三种原料重量不同，分为大小件，当大小件同车，卸货时必 须先卸小件，而且不允许卸下来的材料再装上车，要区别对待运输途中是否可以调头的 费用。在问题一中，运输途中不能调头，整个送货路线是一个环形闭合回路，如果沿着 某一方向同时给多家公司送货时，运输车必须为距离港口近的公司卸下小件，为距离港 口远的公司运送大件；而在问题二中，运输途中可以调头，可以首先为远处公司运送小 件，在返回途中为距离较近的公司卸下大件。 运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、 载重费用和空载费用。 建立模型时，要注意以下几方面的问题

9、： 目标层： 如果将调度车数、车次以及每车次的载重和卸货点都设为变量，模型中变量过多， 不易求解。由于各辆运输车之间相互独立，可以将目标转化为两个阶段的求解过程，第 一阶段是规划车次阶段， 求解车次总数和每车次的装卸方案； 第二阶段是车辆调度阶段， 安排尽量少的车辆数，每车次尽量满载，使总的运费最小。 约束层： (1) 运输车可以从顺时针或者逆时针方向送货，要考虑不同方向时的载重费用； (2) 大小件的卸车顺序要求不同原料搭配运输时，沿途必须有序卸货； (3) 每车次的送货量不能超过运输车的最大载重量； (4) 满足各公司当日需求。 5 建立模型建立模型 5.1 问题一问题一 5.1.1 车次

10、规划模型的分析车次规划模型的分析 车次规划阶段只涉及到载重费用、空载费用和港口出车费用。运输途中不能掉头， 所以每车次都是沿闭合回路绕圈行驶。 第一、约束分析第一、约束分析 (1)(1) 大小件卸货顺序的限制：大小件卸货顺序的限制： 运输途中不能掉头，所以为某些公司送货时，运输车从港口出发，按顺时针方向沿 闭合回路绕行，为其它公司送货时，按逆时针方向沿闭合回路绕行。公司和港口之间存 在顺时针距离和逆时针距离，如下： 公司编号公司编号 顺时针距离顺时针距离 8 15 24 29 37 45 49 55 逆时针距离逆时针距离 52 45 36 31 23 15 11 5 根据 3 种原料的重量和运

11、输车的最大运载量可以看出，A 和 C 可以搭配运输，B 和 C 可以搭配运输，而 A 与 B 不能同车运输。不论是以顺时针方向送货还是以逆时针方向送 货，当大小件搭配运输时，必须首先卸下小件，在后续公司卸下大件。我们把这种特点 总结如下： 特点特点I I 若在第 j 个公司卸下的是大件 A，说明本车次的货物已经卸完，不能够再为后续公 司运送小件 C（A 与 B 不能同车运输，更不可能有 B） ； 特点特点IIII 若在第 j 个公司卸下的是 B，说明本车次的货物已经卸完，不能够再为后续公司运 送小件 C。 基于以上特点，基于以上特点，提取遍历思想提取遍历思想： 将 8 个公司看作闭合回路上的

12、8 个点，对送货顺序的制定，根据卸货时必须先卸小 件的原则，第 j 个点之前的情况不予研究，只要符合“先小件后大件”的原则就可以。 而每次卸货对后续公司的影响就必须满足特点和特点。以 4 号公司为例，在此处卸 下 1 单位的原料 A，若本车次是以顺时针方向送货的，可以在 13 公司卸下原料 C，但 是不能为 4 号公司的后续公司提供任何原料。 这样通过对每一点的遍历控制，达到本车次在整个回路中不发生卸货大小顺序紊乱 的目的。假设 ijk P表示第 i 车次送货到第 j 个公司的第 k 种货物的单位数，k=1、2、3 依 次代表原料 A、B、C，那么遍历思想的特点和特点，以数学语言描述如下： 如

13、果顺时针方向送货，如右图所示。从 1 号公 司依次往后遍历，直到第 7 个公司。而第 8 个 公司之后是港口，就没有必要判断 8 号公司的 卸货情况对后续公司的影响。对第 j（j17） 个公司来说，它的后续公司是 j18 号公司， 因此 当第 j 个公司卸下原料 A 时，约束方程为 8 13 1 ijiJ Jj PP 当第 j 个公司卸下原料 B 时，约束方程是 8 23 1 0 ijiJ Jj PP 顺时针行驶示意图 原料 A 和 B 不能同车，所以将、两种情况归一： 8 123 1 0 ijijiJ Jj PPP 如果逆时针方向送货，如右图所示。从 8 号公司开始遍历， 直到 1 号公司。

14、 对第对第 j（j82）个公司来说，它的后续公司是 1j1 号公司，因此 当第 j 个公司卸下原料 A 时，约束方程为 1 13 1 j ijiJ J PP 当第 j 个公司卸下原料 B 时，约束方程是 1 23 1 0 j ijiJ J PP 逆时针行驶示意图 8 公里 7 公里 9 公里 5 公里 8 公里 8 公里 4 公里 6 公里 5 公里 港口港口 8 公里 7 公里 9 公里 5 公里 8 公里 8 公里 4 公里 6 公里 5 公里 港口港口 原料 A 和 B 不能同车，所以将、两种情况归一： 1 123 1 0 j ijijiJ J PPP 由于运输途中不能掉头，每车次只能以

15、一种方向绕行闭合回路，上述分析的顺时针 和逆时针的遍历不可能同时发生。引入 01 变量1iX、2iX 1iX1 表示顺时针方向送货，2iX1 表示逆时针方向送货 8 123 1 1 123 1 10 20 121 iijijiJ Jj iijijiJ Jj ii XPPP XPPP XX 这样就很好地实现了每车次单向运输，并且有序卸货的目的。 (2)(2)每车次的载重不超过运输车的最大载重量每车次的载重不超过运输车的最大载重量 假设 ijk P表示第 i 车次送货到第 j 个公司的第 k 种货物的单位数， k W表示第 k 种货物 1 单位的重量，那么第 i 车次的载重必须小于运输车的最大载重量 6 吨 83 11 6 ijkk jk P W (3)(3)送货量满足送货量满足公司公司当日需求当日需求 假设运载次数为 N, 运输完毕后，每个公司各种货物的需求都得到满足，设第 j 各 公司需要第 k 种货物的单位数为 jk G,则 1 N ijkjk i PG 第二、目标分析第二、目标分析 (1) 港口出车费用 港口出车有固定成本为 10 元/车次，设一共出车 N 次就可以完成运输任务