货运公司的运输问题.doc

18 货运公司的运输问题 摘 要本文根据货运公司的需求量和所给的运输路线图，对货运公司的出车调度方案进行分析和优化，分别建立了线性规划模型和0-1规划模型，解决了车辆安排问题，得出了运费最小的调度方案。问题一：由于每次出车的出车成本费用是固定的，为了减小运输成本，就要减少出车次数，但同时又要满足各公司对材料的需求，以公司需求为约束条件，以最小出车数为目标函数，建立一个线性规划模型，并用Lingo求解，得出了最少出车次数为27辆。进一步考虑运输车调度问题，由于出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，故建立了一个0-1规划模型，0表示顺时针行驶，1表示逆时针行驶，采用Lingo求解，得出了运输车在运输途中不允许掉头的调度方案。 问题二中允许运输车掉头，我们考虑只会影响运输车卸货后空载的行驶路程，也即影响运输车的空载费用，故通过修改目标函数中的相关系数，仍然建立线性规划模型和0-1规划模型， 问题三中增加了运输车的种类，并区分了运输车空载时的运费，由于运输车装载材料的方式有很多种，在上面分析的基础上，增加约束条件，得出一种新的线性规划模型，通过Lingo解得需出车26趟，具体调度方案见表四、表五。关键词：线性规划模型，0-1规划模型， 一、问题的重述某地区有8个公司（编号至如图一），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见图二）。各个公司对各种材料的需求量（单位/天） 公司 各种材料的需求量编号 A B C 4 1 5 1 5 2 2 0 4 3 1 2 1 2 4 0 4 3 2 2 5 5 3 1 （图 一唯一的运输路线图和里程数） (图二)问题一：货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。问题二：每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？问题三：（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。二、模型的假设1假设每一辆车都发挥其最大装载能力；2假设货运公司在安排如何调度使得运费最小时都是先在出车次数最少的情况下再考虑如何安排运输方式以满足个公司的需求；3假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的作业时间；三、符号说明a 六单位C材料的装载方式；b 一单位B材料和三单位C材料的装载方式；c 两单位B材料的装载方式；d 一单位A材料和两单位C材料的装载方式；e 派车的数量；g 派车的固定费用； A 表示第i趟车到第j个公司的卸载A单位数； B 表示第i趟车到第j个公司的卸载B单位数；C 表示第i趟车到第j个公司的卸载C单位数；a 表示第j个公司对A材料的需求量；b 表示第j个公司对B材料的需求量；c 表示第j个公司对C材料的需求量；F 表示车辆运载的次数；R 表示车辆顺时针、逆时针运载时设置的0-1变量，R=1 表示逆时针；R=0 表示顺时针；u 表示第i趟是否为载重是4吨的车出车时所设置的0-1变量，u=1 表示载重为4吨的车在第i趟出车； u=0表示载重为4吨的车在第i趟不出车；v 表示第i趟是否为载重为6吨的车出车时所设置的0-1变量，v=1 表示载重为6吨的车在第i趟出车；v=0表示载重为6吨的车在第i趟不出车；w表示第i趟是否为载重为8吨的车出车时所设置的0-1变量，v=1 表示载重为8吨的车在第i趟出车；v=0表示载重为8吨的车在第i趟不出车；h 表示第i趟是否出车时所设置的0-1变量，h=1 表示第i趟出车；h=0 表示第i趟不出车；d 顺时针运载时从港口到第j个公司的距离；DS第i辆运载车辆到第j个公司的实际距离；四、模型的建立与求解问题一：货运公司派出6辆载重6吨的运输车，根据各公司对材料的需求，这6辆车必然会被反复的调用。要使其运输的经费最少，我们首先考虑满足每个公司需求量时出车次数最少，在此最少出车次数下再考虑如何调度这些车次。要考虑其最少的出车次数，我们假设运输车辆每次都满载，则此时运输车辆有：（a）6C、（b）B+3C、（c）2B、（d）1A+2C四种装载方式，我们分别设这四种方式需要的调度次数为X、X、X、X，分析图二中八个公司每天对各种材料的需求量，我们可知8个公司每天需A材料18吨、B材料18吨、C材料26吨，1.1我们就可以建立如下数学模型： Min: Z= X+X+X+X ST: X18 X+2 X18 6X+3 X+2 X26用LINGO进行求解可以得到Z=27，X=18，X=9，X=0，X=0；由此可知，若要满足8个公司对A、B、C材料的需求，至少需要出车27次，现在我们假设运载车辆共出车30次即可满足所有公司的需要，在不考虑空载费用的情况下1.2我们考虑车辆的调度方案：目标函数的建立：Min ：Z =eg+10F+（4A+3 B+ C）*1.8* DS（n=1、2、30；m=1、28）(1) 每趟车的装载量不得超过车的最大载重量； 4A+3 B+ C= a B= bC= c （n=1、2、30；j=1、28）(3)每一趟车到第j个公司的实际距离：DS= 60- d R=1 d R=0(4)装载A、B、C材料时不得拆装 AN BNCN在给出了目标函数和约束条件后， 即可得到一个使得运输费用最小的单目标规划 模型如下：Min ：Z =eg+10F+（4A+3 B+ C）*1.8* DS （目标函数）ST： 4A+3 B+ C= a B= b C= cAN BN CN用LINGO（见：附录LINGO代码一）求解得最小费用Z=4386.6，我们对运行结果分析（分析表格见表一）：1） 空载时的总路程为：1245，因此空载总费用为：1245*0.4=498。最终在不考虑大小件的情况下的最小总费用为：Z+498=4884.6。2） 安排6辆车，总共出车次数30次，按车次安排如下： 每辆车分别走5趟； 各车辆及其各趟数运输具体安排按照表格数据进行安排。对于每一辆车的工作时间如下：a) 车辆1：5*60+9*10=390（分钟）480；b) 车辆2：5*60+5*10=350（分钟）480；c) 车辆3：5*60+6*10=360（分钟）480；d) 车辆4：5*60+10*10=400（分钟）480；e) 车辆5：5*60+8*10=380（分钟）480；f) 车辆6：5*60+7*10=370（分钟）480； 根据以上结果可知满足时间的要求。3） 以上的运输方案中有几辆不满足先卸载小件再卸载大件的要求，它们分别是：第7,10,17,22趟。为考虑按大小件的顺序进行卸货，我们对以上不满足要求的趟次进行调整来满足条件：a) 我们分析一下第7,10,17,22趟运输方案：i. 第7趟：R=0; B(7,2)=1;C(7,4)=1;ii. 第10趟：R=1; A(10,8)=1;C(10,5)=1;C(10,7)=1;iii. 第17趟：R=1; B(17,8)=1;C(17,6)=1;iv. 第22趟：R=1;A(22,2)=1;C(22,1)=1;C(22,3)=1;分析可知：C(7,4)=1；C(10,5)=1；C(10,7)=1；C(17,6)=1；C(22,1)=1；是先卸大件再卸小件；b) 对以上不满足条件的5件原材料，我们对此进行重新调整，将其安排在其他车次，以满足先卸小件在卸大件的要求i. 将C(7,4)=1调整到第11趟车次；将C(10,5)=1调整到第14趟车；将C(10,7)=1调整到21趟车；将C(17,6)=1调整到第14；将C(22,1)=1调整到第2趟，调整方案后，见表格二（附：表二）ii. 对以上的调整不会影响原来车次先卸小件在卸大件的原则，并同时考虑使运输路程更短；c) 经调整后所有的车次都满足先卸小件再卸大件的要求，并且此次的调整并没有影响空载时的路程，因此最小运费不会因此次的调整而发生变化，相反调整后卸货的次数反而变小，故满足时间的要求。问题二：车辆可以掉头，但是这只会影响每辆车在运行过程中空车运行回港口的路费，所以求解的模型和第一问中的模型是一样的，不考虑空载费用时，最小费用Z=4386.6。车辆卸载完车上所装的各种材料时，看所处得位置，更具具体的位置决定车辆是否掉头回去，为此我们做如下考虑： 空载费用的变化：空载时的距离进行从新定义：de(i)=min(de(i),60-de(i)。 由第一问可知：当安排6辆车时，各辆车实际运行时间都都远小于预期时间8个小时，于是我们考虑用5辆车，每辆车每天跑6趟（表三）时间验证：1） 第1辆车：6*60+7*10=430480；2） 第2辆车：6*60+7*10=430480；3） 第3辆车：6*60+7*10=430480；4） 第4辆车：6*60+10*10=460480;5） 第5辆车：6*60+9*10=450480;满足时间约束。总费用为：4386.6+509*0.4-20=4570.2问题三：在此问题中增加了运输车辆的种类，并且在此基础上区分了运输车空载时的运费，由于车辆种类的不同，因此装载材料时可装载的方式也有多种，我们不考虑车辆并行的情况，即每一次只有一种类型的一辆车出车，故此我们需对每一次那种车辆是否出车设置0-1变量，同样在暂时不考虑空载费用、在上面分析的基础上，增加约束条件，建立运输费用最小的单目标规划 模型如下：Min ：S =eg+10F+（4A+3 B+ C）*1.8* DS（j=1、8）(1)每趟车的装载量不得超过车的最大载重量； u（4A+3 B+ C）=4; v（4A+3 B+ C）=6;w（4A+3 B+ C）= a B= bC= c （j=1、28） (3)每一趟车到第j个公司的实际距离：DS= 60- d R=1 d R=0(4)装载A、B、C材料时不得拆装 AN BNCN (5)每一趟只有一种类型的一辆车出车；u+ v+ w=1在给出了目标函数和约束条件后， 即可得到一个使得运输费用最小的单目标规划 模型如下：Min ：S =eg+10F+（4A+3 B+ C）*1.8* DS（j=1、8） （目标函数） ST： u（4A+3 B+ C）=4; v（4A+3 B+ C）=6;w（4A+3 B+ C）= a；B= b；C= cAN； BN；CNu+ v+ w=1用LINGO（见：附录LINGO代码二）求解得最小费用S= 4737.600，我们对运行结果整理并分析表四(附：表四)： 1）根据问题一及问题二，我们依旧假设出车30次，在此基础上我们对每一趟是否出车设置了0-1变量h，根据整理的结果可知第5、8、11、14、22、23趟没有出车，也就是说总共出车24次。2）根据先卸载小件再卸载大件的原则可知，在已给出的方案中有几趟车得卸载不满足其原则，它们分别是：13、15、24、27a)我们分析一下第13,15,24,27趟运输方案：i. 第13趟：R=3; A(13,8)=1;B(13,4)=1;ii. 第15趟：R=1; B(15,7)=2;C(15,1)=1;iii. 第24趟：R=0; B(24,2)=1;B(24,6)=1;C(24,2)=2;iv. 第27趟：R=1; A(27,8)=1;B(27,2)=1; 次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元/公里，为使其总运费最少，故当车辆的装载量4且6且=8时，我们用载重为6吨的车运载。4）在满足上述条件的情况下，我们考虑空载时的实际距离，为此我们做两种不同情况下的假设： 车辆在运载的过程中不可掉头 i.根据问题二的时间处理，我们在此假设共派车4辆，则每一辆平均出车6次，依据调整后的方案，我们可按顺序依次出车，下面我们来验证一下这样安排是否符合时间的要求： 验证时间： 第一辆车：6*60+10*8=440480； 第二辆车：6*60+10*10=460480； 第三辆车：6*60+10*8=440480； 第四辆车：6*60+10*9=450480； 通过验证我们可以看到，安排4辆车符合试验的要求。ii.根据调整后的方案可知：载重为8吨的车空载路程为497公里；载重为6吨的车空载的路程为310公里；载重为4吨的车空载的路程为141公里，由此可计算出空载的费用p1=497*0.7+310*0.4+141*0.2=500.1,则总的费用P=S+p1-20=5217.7元。车辆在运载的过程中可掉头i.同上述不可掉头放入方案一样，我们同样安排4辆车，平均每一辆车出车6次，根据上述分析可知，这样的安排符合时间的要求ii.根据调整后的方案可知：载重为8吨的车空载路程为177公里；载重为6吨的车空载的路程为138公里；载重为4吨的车空载的路程为69公里，由此可计算出空载的费用p1=177*0.7+138*0.4+69*0.2=192.9,则总的费用P=S+p1-20=4910.5元。 五、模型的误差分析 本文是针对车辆运输是调运方案的设计问题问题，在解决此问题时我们运用了线性规划模型、0-1规划模型，但是我们在作次模型时都是在理想的状态下考虑满足各个公司的需求量，例如我们假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的作业时间，这在现实的生活中几乎是不可能的条件，由于我们忽略了路况、人员等现实中的好多问题，故此使得所求出的最优运输方案与实际情况有很大的出入。六、模型的评价1. 模型的优点1.1此模型在考虑最少出车次数的基础上考虑满足各个公司需求量的最优调运方案，基本符合现实中的实际情况，为求最小运输成本提供了保证。1.2在假设的基础上，基本满足题目中所有的约束条件，。1.3建立了以最小成本为目标的单目标规划函数2. 模型的缺点2.1忽略了运输车行驶过程中塞车抛锚现象。2.2对于空载费用的处理，我们没有在目标函数中直接给出，而是在我们给出调运方案之后，根据调运方案计算空载时的费用。七、参考文献1 赵可培，运筹学（第二版），上海：上海财经大学出版社，2011. 2 赵静、但琦，数学建模与数学实验（）附录附表一：趟数i车次车号方向标志R(i)运输货物量空载时的距离卸货次数ABC1110A(1,3)=1C(1,3)=2362220A(2,1)=1521330A(3,3)=1361440A(4,4)=1C(4,1)=1312551B(5,5)=1B(5,6)=1372660B(6,1)=1B(6,4)=13127210B(7,2)=1;C(7,4)=1312820B(8,2)=2451931A(9,4)=1C(9,7)=22921041A(10,8)=1C(10,5)=1;C(10,7)=12331150A(11,4)=13111260A(12,1)=152113311A(13,8)=15511421B(14,5)=1C(14,5)=13711530B(15,2)=24511641B(16,8)=25511751B(17,8)=1C(17,6)=14521861B(18,6)=1C(18,6)=2;C(18,8)=145219411A(19,8)=15512021A(20,8)=15512131A(21,7)=14912240A(22,2)=1C(22,1)=1;C(22,3)=13632350A(23,1)=1C(23,1)=25212461A(24,7)=149125510C(25,2)=2;C(25,3)=1;C(25,4)=13132621A(26,5)=AC(26,5)=23712731B(27,7)=24912840A(28,1)=1C(28,1)=15212951A(29,8)=1C(29,7)=24923060B(30,6)=2151合计124545附表二：调整后的方案趟数i车次车号方向标志R(i)运输货物量空载时的距离de(i)卸货次数ABC1110A(1,3)=1C(1,3)=1361220A(2,1)=1C(22,1)=1521330A(3,3)=1361440A(4,4)=1C(4,1)=1312551B(5,5)=1B(5,6)=1372660B(6,1)=1B(6,4)=13127210B(7,2)=1311820B(8,2)=2451931A(9,4)=1C(9,7)=22921041A(10,8)=12311150A(11,4)=1C(7,4)=13111260A(12,1)=152113311A(13,8)=15511421B(14,5)=1C(14,5)=1;C(10,5)=1C(17,6)=13721530B(15,2)=24511641B(16,8)=25511751B(17,8)=1,4511861B(18,6)=1C(18,6)=2;C(18,8)=145219411A(19,8)=15512021A(20,8)=15512131A(21,7)=1C(10,7)=1;4912240A(22,2)=1C(22,1)=1;3622350A(23,1)=1C(23,1)=25212461A(24,7)=149125510C(25,2)=2;C(25,3)=1;C(25,4)=13132621A(26,5)=1C(26,5)=23712731B(27,7)=24912840A(28,1)=1C(28,1)=15212951A(29,8)=1C(29,7)=249230 60B(30,6)=2151合计124540附表三：可掉头的运输方案趟数i车趟数车号方向标志R(i)运输货物量不可掉头时空载时的距离卸货次数可以掉头时的空载距离ABC1110A(1,3)=1C(1,3)=136124220A(2,1)=1C(22,1)=15218330A(3,3)=136124440A(4,4)=1C(4,1)=131229551B(5,5)=1B(5,6)=1372236210B(6,1)=1B(6,4)=131229720B(7,2)=131129830B(8,2)=245115941A(9,4)=1C(9,7)=2292291051A(10,8)=12312311310A(11,4)=1C(7,4)=1311291220A(12,1)=152181331A(13,8)=155151441B(14,5)=1C(14,5)=1;C(10,5)=1C(17,6)=1372231550B(15,2)=24511516411B(16,8)=255151721B(17,8)=1,451151831B(18,6)=1C(18,6)=2;C(18,8)=1452151941A(19,8)=155152051A(20,8)=1551521511A(21,7)=1C(10,7)=1;491112220A(22,2)=1C(22,1)=1;362242330A(23,1)=1C(23,1)=252182441A(24,7)=1491112550C(25,2)=2;C(25,3)=1;C(25,4)(26,5)=AC(26,5)=2371232721B(27,7)=2491112830A(28,1)=1C(28,1)=152182941A(29,8)=1C(29,7)=2492113050B(30,6)=215115合计124540509附表四：趟数i车号方向标志R(i)运输货物量不掉头时空载时的距离卸货次数是否出车h（i）车辆ABC合计（吨）11111A(1,7)=284912121B(2,6)=264513130C(3,3)=443614141A(4,8)=1B(4,8)=17552502500006160A(6,4)=283117111A(7,5)=1B(7,8)=1737280200009131A(9,4)=1C(9,5)=4829210141B(10,6)=1B(10,8)=1645211035000012160B(12,1)=1352113111A(13,8)=1B(13,4)=172921402000015131B(15,7)=2C(15,1)=178216140B(16,2)=1C(16,1)=47452171450A(17,1)=2845118161B(18,5)=2637119110B(19,2)=2645120121C(20,6)=33451211531C(21,7)=5C(21,8)=16492220400002305000024160B(24,2)=1,B(24,6)=1C(24,4)=2815325110A(25,1)=2845126120C(26,2)=22451271631A(27,8)=1B(27,2)=1715228140A(28,3)=2836129150A(29,2)=1445130161A(30,8)=28551合计93835附表五：调整后的方案趟数i车号方向标志R(i)运输货物量不掉头时空载时的距离卸货次数可以掉头时的空载距离是否出车h（i）车辆ABC合计（吨）11111A(1,7)=28491112121B(2,6)=26451153130C(3,3)=44361244141A(4,8)=1B(4,8)=1755255025000006160A(6,4)=28311297111A(7,5)=1B(7,8)=1;737223802000009131A(9,4)=1C(9,5)=482922910141B(10,6)=1B(10,8)=1645215110350000012160B(12,1)=1B(24,2）=164511513111A(13,8)=1A(27,8)=18552514020000015131B(15,7)=264921116140B(16,2)=1C(16,1)=4745215171450A(17,1)=284511518161B(18,5)=263712319110B(19,2)=264511520121B(13,4)=1C(20,6)=3629129211531C(21,7)=5;C(21,8)=1;C(15,1)=1782822040000023050000024160B(24,6)=1C(24,4)=251531525110A(25,1)=28521826120C(26,2)=2245115271631B(27,2)=131521528140A(28,3)=283612429150A(29,2)=144511530161A(30,8)=285515合计94835384LINGO代码一：model:sets:compt/1.8/:d, a, b, c; cars/1.30/:f,right;cost(cars,compt):A1,B1,C1,DS；endsetsdata:d=8 15 24 29 37 45 49 55;a=4 1 2 3 1 0 2 5;b=1 5 0 1 2 4 2 3;c=5 2 4 2 4 3 5 1;e=6;g=20;enddataobjmin=e*g+sum(cars(i):f(i)*10)+sum(cost(i,j):(4*A1(i,j)+3*B1(i,j)+C1(i,j)* DS(i,j)*1.8);! 每趟车的