货运公司的运输问题

封一答卷编号（竞赛组委会填写）：答卷编号（竞赛组委会填写）：论文题目：B题：货运公司的运输问题参赛队员：1.朱远鹏电话：86599912.贾利攀电话：134675178553.李雯电话：8659991封二答卷编号（参赛报名号）：答卷编号（竞赛组委会填写）：评阅情况（评阅专家填写）：评阅1.评阅2.评阅3.货运公司的运输问题1摘要本文根据货运公司需要完成的运输量和确定的运输路线图，对货运公司的出车调度方案进行分析和优化，分别建立了线性规划模型和0-1规划模型，解决了车辆安排问题，得出了运费最小的调度方案。首先，由于每次出车的出车成本费是固定的，为了减小运输成本，就要减少出车次数，但同时又要满足各公司对材料的需求，以公司需求为约束条件，以最小出车数为目标函数，建立一个线性规划模型，并用Lingo求解，得出了最少出车次数为27辆。进一步考虑运输车调度问题，由于出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，故建立了一个0-1规划模型，0表示顺时针行驶，1表示逆时针行驶，采用Lingo求解，得出了运输车在运输途中不允许掉头的调度方案（见表一）。问题二中允许运输车掉头只会影响运输车卸货后空载的行驶路程，也即运输车的空载费用，故通过修改目标函数中的相关系数，仍然建立线性规划模型和0-1规划模型，采用Lingo求解，得出需要安排的运输车为3辆，运输途中允许掉头的调度方案见表二。问题三中增加了运输车的种类，并区分了运输车空载时的运费，由于运输车装载材料的方式有很多种，在上面分析的基础上，增加约束条件，得出一种新的线性规划模型，通过Lingo解得需要安排的车辆数为5辆，调度方案见表三。第（2）小问中，考虑部分公司有道路相通，采用Dijkstra算法来解决这类最短路问题。关键字：线性规划模型，0-1规划模型，Dijkstra算法2问题重述某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见图二）。问题：1.货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。2.每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？3.（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。（图一）唯一的运输路线图和里程数⑨⑧⑦⑥⑤④③②①8公里7公里9公里5公里8公里8公里4公里6公里5公里港口（图二）各个公司对每种材料的需求量（单位/天）公司编号各种材料的需求量（单位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧5313模型假设1．假设每辆车装载时发挥其最大的装载能力；2．假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；3．假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的作业时间。4符号说明C1一单位A材料和二单位C材料的装载方式；C2二单位B材料的装载方式；C3六单位C材料的装载方式；C4一单位B材料和三单位C材料的装载方式；Pij被调用车的运输经费；Sij所运载的区间的路程；Xij第i辆列车的调度情况；Xi0=1表示第i辆车采用顺时针运输；Xi0=0表示第i辆车不采用顺时针运输；Xi1=1表示第i辆车采用逆时针运输；Xi1=0表示第i辆车不采用顺时针运输；t0装载时间；t1路途行程时间；t2卸载时间；Gni（n=1—8，i=1，2，3）表示第n个公司分别对A，B，C产品的需求量；5问题分析对于这个货运公司的运输问题，问题一中给出了6辆可以使用的运输车，根据各公司对材料的需求，这6辆车必然会被反复的调用。要减少运输经费，首先要减少出车的次数，但是究竟要出车几次才可以满足公司对材料的需求呢？由于每辆车只能装载6吨的货物，所以每辆车的装载方案有：6个C，2个B，1个A2个C，1个B3个C四种（每次出车都优先考虑发挥每辆运输车最大的装载能力），这样再根据八个公司对A，B，C三种材料总的需求量就可以建立一个线性规划模型求出出车的最少次数S。在满足最少出车次数S的前提下，还要考虑运输车的调度问题，由于出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，这属于0-1规划问题，解决的方法是令Xi0等于1表示采用第i辆车次按顺时针来运行，Xi0等于0表示不采用第i辆车次顺时针运行。Xi1等于1表示采用第i辆车次逆时针运行，等于0表示不采用这辆车次逆时针运行，再结合题目中的其他相关数据便可以建立一个0-1规划模型求解。问题二中的解决方法和第一问中的解决方法是一样的，不过由于这时候运输车可以掉头，故可以减少由于运输车在途中空载的路程，而这只会影响模型中目标函数的中的价值系数的改变，其他和第一问的求解方法是一致的。在第三问中给出了三种不同的运输车，对于这三辆不同的运输车，每次出车时可以用来装载不同单位的A，B，C材料（这时我们不像第一问那样来考虑，每次出车可以不装载完每辆车），对于这三种不同的运输车可以得出很多不同的装载方式，比如对于装载量为8吨的运输车，可以为每次装载2个A或者1个A和B等。根据每个公司对A，B，C不同材料的要求，我们再建立一个线性模型，使得这八个公司可以从这些不同的运输方式中选择最为合适的运输方式的组合以满足要求，然后对这些公司所选择的不同的运输方式再根据题目中每辆车每天最大的作业时间，可以确定出在保证完成任务的情形下，所需要不同类型运输车的最少数目。这样就可以减少指派运输车的支出，然后对不同的运输车次在途中的运输，都考虑其在途中是按最少经费的运输方式来运行（考虑在保证完成了本次出车的任务后，在返回港口中时，是继续或掉头更节省经费），再结合前面的不同运输方式的组合，就可以安排出车辆数和调度方案了。6模型的建立与求解6.1问题一的求解首先考虑求解出满足每个公司的需求所需的最少出车次数，再在此情形下考虑如何调度这些车次，使得整个运输作业所需的经费最少。模型的建立与求解根据题目中给定的各个公司对A，B，C三种不同的材料的需求，可以计算出这些公司每天所需A，B，C三种材料的总数分别为18单位，18单位，26单位，由于每辆车的载重都是6吨，在假设一的前提下我们可以得出每辆车的装载方式有如下四种方式：（a）1A+2C，（b）2B，（c）6C，（d）B+3C。我们分别设这四种方式需要调度的次数为C1，C2，C3，C4这样我们就可以建立如下数学模型：MINS=C1+C2+C3+C4C1〉=182C2+C4〉=182C1+6C3+3C4〉=26C1~~C4为正整数；用LINGO进行求解可以得到S=27，C1=18，C2=9，C3=0，C4=0；对于这个结果可以进一步分析可知，只需要（a）的运输方式为13个再加上单独运输A材料的5车次和9车次（b）运输方式即可满足条件，但是这未必是最好的方式。因为在卸货的时候必须先卸小件，而且不允许卸下来的材料再装上车，所以对某些公司来说，如公司（1）通过分析可以知道用装载方式（a）和（b）及单独运输A的图三方式进行运载不能满足公司一的条件，还需要A+C这种方式。那么究竟需要运载方式（1），（2）及A和A+C的方式多少个才合适呢，我们不妨以全是顺时针的方式来进行考虑，比如对于公司（1）需要2个（a）的运输方式，1个（b）的运输方式和一个单独运输A方式。如图三，按顺时针方式对每个公司进行综合的考虑可以得到需要方式（a）12个，运输A+C方式2个，单独运输A方式4个以及方式（b）9个可以较好的满足体设条件。对这些运输方式，分别记顺时针的调用车次序为i0（i0=1~27），其中i=1~12为调用方式（a），i=13~14为调用方式A+C，i=15~18为调用方式A，i=19~17为调用方式（b）；逆时针的调用车次序为i1（i1=1~27），其中i=1~4为调用方式A，i=5~6为调用方式A+C，i=7~18为调用方式（a），i=19~27为调用方式（b）。对于每个被调用以满足不用公司要求的车次，由于不考虑掉头，故可以得到其运输所需要的经费为Pij=∑（1.8w*Sij+0.4*sj0）（i=1~27，j=0或1），其中w为运输车的载重，Sij为所运载的区间的路程，Sj0则表示空车回到港口的距离，总费用为：P=∑Pij+S*10+20*K，其中K为所调用的车辆的个数；其中Pij的计算所得的结果参看表（1），表（2）中列出各个公司所需的材料是由哪些车次所负责运输的。根据这两个表中的数据设Xij（其中i=1~27，j=0或1）为第i辆列车的调度情况：其中Xi0=1表示第i辆车次采用顺时针运行，Xi0=0则表示不采用第i辆车次顺时针运输，Xi1=1则表示第i辆车采用逆时针运输，Xi1=0表示第i辆车不采用顺时针运输。由上可以对这个问题建立一个0-1规划模型：Min∑Pij*XijS.T∑Xij〉=27x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1;（对于公司（1）两种不同运输方式中只能选择一种）……….（其他公司的处理方法一样，其中如：x141-x151=0，这是说明如过采用141，则也采用151的车次，其他各处同理）Xij=0或1结论：对上0-1模型，代入数据，用Lingo求解可得∑Pij=5227.2，又由于S=27，K=6，所以总费用为P=5617.2（元），其中所调用的车次以及每个车次的所花的经费参见表（3），对于所得的结果，由于车的速度为60公里/时，那么每辆车运行一周回到港口刚好需要1小时，而现在需要共需要转27圈，又每辆车的每天的工作时间是8小时，所以这6辆车一天的能力是运转48圈，所以即使再考虑装载时间和卸货时间所得结果也是合理的。6.2问题二的求解问题二中的车辆可以掉头，但是这只会影响每辆车在运行过程中空车运行回港口的路费，所以求解的模型和第一问中的模型是一样的，只不过这时候的Pij已经有所变化，这时候的Pij的求解是这样计算的：在每辆车完成了该车的装载任务后，看所处的位置在何处，如果掉头回港口更近的话，则掉头，否则继续前进，其他的计算方式则和第一问中的一样，具体的计算结果参见表（4）；结论：仍然使用Lingo进行求解，可以得到这时候的∑Pij=4615.2，这时候S仍为27，而K的确定是这样的：把所有车次的时间按时间公式∑（t0+t1+t2），求出总的时间为：1711分钟。每一辆车的最大工作时间为：60*8=480分钟，粗略计算，需车数：1711/480≈4辆，综合考虑装载和卸货时间用的时间，这个值也是合理的。那么这时的总费用P=4965.2（元），6．3问题三的求解以尽可能装满车为原则，4，6，8吨三种车型有以下装法，并编好序。每辆车尽可能一次性卸完分析出每个公司所需车次。4吨（车型）6吨8吨Y1=B+CY4=2BY8=2AY2=AY5=A+2CY9=A+4CY3=4CX6=6CX10=A+B+CY7=B+3CY11=8CY15=B+CY12=2B+2CY16=B+2CY13=B+5C