货运公司的运输问题

《货运公司的运输问题》由会员分享，可在线阅读，更多相关《货运公司的运输问题（19页珍藏版）》请在金锄头文库上搜索。

1、 11货运公司的运输问题货运公司的运输问题摘摘 要要本文根据货运公司的需求量和所给的运输路线图，对货运公司的出车调度 方案进行分析和优化，分别建立了线性规划模型和 0-1 规划模型，解决了车辆 安排问题，得出了运费最小的调度方案。 问题一：由于每次出车的出车成本费用是固定的，为了减小运输成本，就 要减少出车次数，但同时又要满足各公司对材料的需求，以公司需求为约束条 件，以最小出车数为目标函数，建立一个线性规划模型，并用 Lingo 求解，得 出了最少出车次数为 27 辆。进一步考虑运输车调度问题，由于出车方向不定， 分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，故建 立了一个

2、 0-1 规划模型，0 表示顺时针行驶，1 表示逆时针行驶，采用 Lingo 求 解，得出了运输车在运输途中不允许掉头的调度方案。问题二中允许运输车掉头，我们考虑只会影响运输车卸货后空载的行驶路 程，也即影响运输车的空载费用，故通过修改目标函数中的相关系数，仍然建 立线性规划模型和 0-1 规划模型，问题三中增加了运输车的种类，并区分了运输车空载时的运费，由于运输 车装载材料的方式有很多种，在上面分析的基础上，增加约束条件，得出一种 新的线性规划模型，通过 Lingo 解得需出车 26 趟，具体调度方案见表四、表五 。关键词：线性规划模型，0-1 规划模型， 2一、问题的重述某地区有 8 个公

3、司（编号至如图一） ，某天某货运公司要派车将各公司 所需的三种原材料 A,B,C 从某港口（编号）分别运往各个公司。路线是唯一 的双向道路（如图一） 。货运公司现有一种载重 6 吨的运输车，派车有固定成 本 20 元/辆，从港口出车有固定成本为 10 元/车次（车辆每出动一次为一车次） 。 每辆车平均需要用 15 分钟的时间装车，到每个公司卸车时间平均为 10 分钟， 运输车平均速度为 60 公里小时（不考虑塞车现象） ，每日工作不超过 8 小时。 运输车载重运费 1.8 元/吨公里，运输车空载费用 0.4 元/公里。一个单位的原 材料 A,B,C 分别毛重 4 吨、3 吨、1 吨，原材料不能

4、拆分，为了安全，大小件同 车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材 料再装上车，另外必须要满足各公司当天的需求量（见图二） 。8公里7公里9公里5公里8公里8公里4公里6公里5公里港港口口（图 一唯一的运输路线图和里程数） (图二)问题一：货运公司派出运输车 6 辆，每辆车从港口出发（不定方向）后运输途 中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。 问题二：每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安 排车辆数？应如何调度？ 问题三：（1）如果有载重量为 4 吨、6 吨、8 吨三种运输车，载重运费都是 1.8 元/吨公里，空载

5、费用分别为 0.2，0.4，0.7 元/公里，其他费用一样，又 如何安排车辆数和调度方案？ （2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在， 给出你的解决问题的想法（可结合实际情况深入分析） 。二、模型的假设1假设每一辆车都发挥其最大装载能力； 2假设货运公司在安排如何调度使得运费最小时都是先在出车次数最少的情况 下再考虑如何安排运输方式以满足个公司的需求； 3假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最 大的作业时间；各个公司对各种材料的需求量（单位/天）公司 各种材料的需求量 编号 A B C 4 1 5 1 5 2 2 0 4 3 1 2 1

6、 2 4 0 4 3 2 2 5 5 3 13三、符号说明a 六单位 C 材料的装载方式； b 一单位 B 材料和三单位 C 材料的装载方式； c 两单位 B 材料的装载方式； d 一单位 A 材料和两单位 C 材料的装载方式； e 派车的数量； g 派车的固定费用；A 表示第 i 趟车到第 j 个公司的卸载 A 单位数；ji,B 表示第 i 趟车到第 j 个公司的卸载 B 单位数；ji,C 表示第 i 趟车到第 j 个公司的卸载 C 单位数；ji,a 表示第 j 个公司对 A 材料的需求量；jb 表示第 j 个公司对 B 材料的需求量；jc 表示第 j 个公司对 C 材料的需求量；jF 表示

7、车辆运载的次数；iR 表示车辆顺时针、逆时针运载时设置的 0-1 变量，R =1 表示逆时针；R =0 iii表示顺时针；u 表示第 i 趟是否为载重是 4 吨的车出车时所设置的 0-1 变量，u =1 表示载ii重为 4 吨的车在第 i 趟出车； u =0 表示载重为 4 吨的车在第 i 趟不出车；iv 表示第 i 趟是否为载重为 6 吨的车出车时所设置的 0-1 变量，v =1 表示载ii重为 6 吨的车在第 i 趟出车；v =0 表示载重为 6 吨的车在第 i 趟不出车；iw 表示第 i 趟是否为载重为 8 吨的车出车时所设置的 0-1 变量，v =1 表示载ii重为 8 吨的车在第 i

8、 趟出车；v =0 表示载重为 8 吨的车在第 i 趟不出车；ih 表示第 i 趟是否出车时所设置的 0-1 变量，h =1 表示第 i 趟出车；h =0 iii表示第 i 趟不出车；d 顺时针运载时从港口到第 j 个公司的距离；jDS第 i 辆运载车辆到第 j 个公司的实际距离；ji,4四、模型的建立与求解问题一： 货运公司派出 6 辆载重 6 吨的运输车，根据各公司对材料的需求，这 6 辆车必 然会被反复的调用。要使其运输的经费最少，我们首先考虑满足每个公司需求 量时出车次数最少，在此最少出车次数下再考虑如何调度这些车次。要考虑其 最少的出车次数，我们假设运输车辆每次都满载，则此时运输车辆

9、有：（a）6C 、（b）B+3C、（c）2B、（d）1A+2C 四种装载方式，我们分别设这四种方式需要的调度次数为 X 、X 、X 、X ，分析图二中八个公司每天对各种材料的需1234求量，我们可知 8 个公司每天需 A 材料 18 吨、B 材料 18 吨、C 材料 26 吨， 1.1 我们就可以建立如下数学模型： Min: Z= X +X +X +X 1234ST: X 184X +2 X 18236X +3 X +2 X 26124用 LINGO 进行求解可以得到 Z=27，X =18，X =9，X =0，X =0；由此可知，若4312要满足 8 个公司对 A、B、C 材料的需求，至少需要

10、出车 27 次，现在我们假设运 载车辆共出车 30 次即可满足所有公司的需要，在不考虑空载费用的情况下 1.2 我们考虑车辆的调度方案： 目标函数的建立：Min ：Z =eg+10F +（4A+3 B+ C）*1.8* DS ni 1i ni 1 mj 1ji,ji,ji,ji,（n=1、2、30；m=1、28 ） (1)每趟车的装载量不得超过车的最大载重量；4A+3 B+ C= a ni 1ji,jB= b ni 1ji,jC= c （n=1、2、30；j=1、28） ni 1ji,j5(3)每一趟车到第 j 个公司的实际距离：DS= 60- d R =1ji,jid R =0ji(4)装载

11、 A、B、C 材料时不得拆装ANji,BNji,CNji,在给出了目标函数和约束条件后， 即可得到一个使得运输费用最小的单目标规 划 模型如下：Min ：Z =eg+10F +（4A+3 B+ C）*1.8* DS ni 1i ni 1 mj 1ji,ji,ji,ji,（目标函数）ST： 4A+3 B+ C= a ni 1ji,jB= b ni 1ji,jC= c ni 1ji,jAN BN CNji, ji, ji,用 LINGO（见：附录 LINGO 代码一）求解得最小费用 Z=4386.6，我们对运行结 果分析（分析表格见表一）： 1）空载时的总路程为：1245，因此空载总费用为：124

12、5*0.4=498。最终在不考 虑大小件的情况下的最小总费用为：Z+498=4884.6。 2）安排 6 辆车，总共出车次数 30 次，按车次安排如下： 每辆车分别走 5 趟； 各车辆及其各趟数运输具体安排按照表格数据进行安排。 对于每一辆车的工作时间如下： a) 车辆 1：5*60+9*10=390（分钟）= a ni 1ji,jB= b ni 1ji,jC= c （j=1、28） ni 1ji,j(3)每一趟车到第 j 个公司的实际距离：DS= 60- d R =1ji,jid R =0ji(4)装载 A、B、C 材料时不得拆装ANji,BNji,CNji,(5)每一趟只有一种类型的一辆车

13、出车；u + v + w =1iii8在给出了目标函数和约束条件后， 即可得到一个使得运输费用最小的单目标规 划 模型如下：Min ：S =eg+10F +（4A+3 B+ C）*1.8* ni 1i ni 1 mj 1ji,ji,ji,DS（j=1、8）ji,（目标函数）ST： u （4A+3 B+ C）= a ； ni 1ji,jB= b ； ni 1ji,jC= c ni 1ji,jAN ； BN ；CNji, ji, ji,u + v + w =1iii用 LINGO（见：附录 LINGO 代码二）求解得最小费用 S= 4737.600，我们对运行 结果整理并分析表四(附：表四)：1）

14、根据问题一及问题二，我们依旧假设出车 30 次，在此基础上我们对每一趟是否出车设置了 0-1 变量 h ，根据整理的结果可知第i5、8、11、14、22、23 趟没有出车，也就是说总共出车 24 次。 2）根据先卸载小件再卸载大件的原则可知，在已给出的方案中有几趟车得卸载 不满足其原则，它们分别是：13、15、24、27 a)我们分析一下第 13,15,24,27 趟运输方案：i.第 13 趟： R=3; A(13,8)=1;B(13,4)=1;13ii.第 15 趟： R=1; B(15,7)=2;C(15,1)=1;15iii.第 24 趟： R=0; B(24,2)=1;B(24,6)=

15、1;C(24,2)=2;24iv.第 27 趟： R=1; A(27,8)=1;B(27,2)=1;279次 4 趟车卸载时先卸大件，而后在卸小件b)故此我们对此 4 趟车的装载进行调整，使其符合先卸小件再卸大件的要求i. 将第 13 趟车上的 B(13,4)=1 装载到第 20 趟车上；ii. 将第 15 趟车上的 C(15,1)=1 装载到第 21 趟车上；iii.将第 24 趟车上的 B(24,2)=1 装载到第 12 趟车上；iv. 将第 27 趟车上的 A(27,8)=1 装载到第 13 趟车上； 调整后的运载方案见表五（附：表五） 3）根据其题目要求可知，车辆的载重量有 4 吨、6 吨、8 吨三种不同的类型， 载重量不同，空载时的运费也不同，分别为：0.2、0.4、0.7 元/公里，为 使其总运费最少，故当