中南大学 数学建模 lingo matlab 优化建模论文 货运公司的运输问题

答卷编号（竞赛组委会填写）：答卷编号（竞赛组委会填写）：论文题目：货运公司的运输问题参赛队员：1.郭海良电话：2.林欢电话：3.黎小龙电话卷编号（参赛报名号）：答卷编号（竞赛组委会填写）：评阅情况（评阅专家填写）：评阅1.评阅2.评阅3.货运公司的运输问题摘要本文对有序卸货的运输问题，由于线路唯一，所以将费用最小转化为求车次最少为目标，建立了线性规划，再运用其他算法匹配出具体的车辆调运方案。对于问题一，模型一：首先以各公司总体的需求为约束，以总车次最小为目标的线性规划，再以此为基础，分别同过各公司的单独需求为约束，所需车次为目标的线性规划，运用LINGO,最后利用启发式算法对每车次具体载重以及路线作具体调整得出车次的具体调度，得出总车次为27次，6辆车车工作时间分别为7.083小时、7.083小时、7.083小时、6小时、6小时、6小时，总费用为5187.6元。模型二：通过建立线性规划模型、0—1规划模型得出的结果为：总车次27次，总费5617.2元。对比可得模型一比模型二更优对于问题二，首先通过遍历算法和目标规划模型确定了卸货次数最少（即车次最少）的方案，再通过贪婪算法匹配出最小车次的调度方案，得出需要4辆车，工作时间分别为7.967小时、7.883小时、7.483小时、6.233小时。这里为了简化问题求解，先考虑在每个公司卡车卸货的次数和方案，再考虑路径等问题。对于路径的选择，首先考虑可一次性卸货的车次路径方案，再考虑公司间货物匹配的车次路线方案，最后用贪婪算法得出具体调度方案见表5.2.4。对于公司间匹配运货得出如下：各种卸货方案只有的方案可以匹配，而且匹配只会发生在不同公司之间。对于无法匹配的卸货方案就只能耗费一车次来单独完成。对于问题三，（第一问）分了4，6，8吨载重的三种车，为了卸货效率较高，要求每种车卸货的重量为本车最大载重的一半以上，如问题二中一样通过遍历算法和目标规划模型确定了卸货次数最少（即车次最少）的方案，再通过贪婪算法匹配出最小车次的调度方案，得出需要：4吨位车1辆，2次；6吨位1辆，2次，8吨位2辆，18次，即共用4辆车，出车22次，详细调用如表5.3.1。这里由于所有载重车辆的载重吨位都在最大载重量的一半以上，所有不存在需要匹配的卸货方案。因此每次卸货都要耗费单独一个车次来完成对于第二问我们作为扩展稍微做了探索，由于部分公司间有路相通，因此不但要考虑车次的问题，还要考虑路径问题，即最短路问题，而最短路问题又是图论里一个典型的问题，可以采用迪克斯特拉（Dijkstra）算法来解决，另一个方法就是运用遗传算法。关键字：线性规划，遍历算法，贪婪算法一、问题重述某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。问题：1.货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。2.每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？3.选做（任选一问）：（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。图一图二公司编号各种材料的需求量（单位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531二、问题的分析对于问题一，因为运输的线路唯一，且中途不可调头，相当于围绕线路开一个圈再回到港口。所以为了减少费用，应尽可能的减少出车的车次，为此每一车次尽量实现满载，而满载的组合有1A+2C、2B、B+3C、6C四种情况，在满足各各公司的每日需求的额条件下，建立线性规划模型求出符合要求的最小车次。在此前基础上再以各公司的需求为约束，分别用线性规划求的所需车次，从而得到整体的最优解。对于问题二，因为车辆中间可以调头，在载重路线最短的情况下，载重线路也就是返程线路。为了简化问题求解，先考虑在每个公司卡车卸货的次数和方案。首先，假定所有的卡车只卸货一次，卸完货后立即返程。为了使运送的路程、运费，车次尽可能少，因此，这是一个优化问题，目标函数是卸货总次数最少，而为了保证每次卸货的效率，假设在每个站点卸货的重量必须在其最大载重量的一半以上。由于可返回，这里把6吨车装载的可能性都考虑进去共12种，目标就在这12种搭配中选择对于问题三，问题3的建模思路和问题2基本一致，遵循如下步骤：寻求最优卸货方案寻找最优（成本最低，时间最省）运送路线；寻求最优车辆调度方案（出车最少，同时保证不超时）问题3分了4，6，8吨载重的三种车，为了卸货效率较高，要求每种车卸货的重量为本车最大载重的一半以上；同时注意到，对于低于6吨的货物，可以由6吨载重的卡车运，没有必要用8吨的（空载车费随最大载重量增加而变贵），而4吨以下的就没必要用6吨的车来卸货，这样只会增加卸货的次数，因此只考虑3，4，5，6，7，8吨卸货的方案。三、模型假设1：每趟车运完最后一次原料时，都按时返回港口；2:假设货运公司安排车辆时，尽力使每辆车都在工作，而不是优先让某一辆车工作四、符号说明在J公司卸A种货物的重量；在J公司卸B种货物的重量；在J公司卸C种货物的重量；i方案下卸载a货物的单位数；i方案下卸载b货物的单位数；i方案下卸载c货物的单位数；货车最大载重量五、模型的建立与求解5.1问题一模型的建立与求解模型一：在问题一的假设下，可知每次出车的行程都相同，所以存在贪婪因子，在卸货约束和满载的条件下，即可用贪婪算法求的局部每次出车的最小费用，再得到全局最优解。对于在路程相同的情况下使总费用最小，则出车次数需最小，这里以各公司所需原材料为约束条件，以每种满载组合的车次为决策变量，总车次最小为目标函数，建立线性规划模型。其中满载组合有M1次:1A+2C、M2次:2B、M3次:1B+3C、M4次:6CM1、M2、M3、M4为整数用LINGO求的总车次为27，其中M1=18,M2=9,M3=0,M4=0。在总车次确定的情况下，依次为基础，再对以每一个公司的需求为约束分别建立线性规划模型，确定满足各个公司需求的最小车次与运载组合（这样的好处是既可以确定各个车次也能结合总车次与载重对整体进行调整）其中Ai、Bi、Ci分别为各公司对原料A、B、C的需求量，利用启发式算法对每车次具体载重以及路线作具体调整得出车次具体调度为：一次性卸载有22次公司车次载重123456782*(A+2C）A+2C2*(A+2C)A+2CA+2C2*2B2*(A+2C)A+CA+C2*2B2B2B4*A2B其中多于一次卸载的有5次载重一个（A+2C）原料由港口经7公司卸载一单位C，再经6公司卸载一单位C,最后在4公司卸载A;载重一个(A+2C)经6公司卸载2单位C,再经1公司卸载一单位A；载重一个(A+2C)经5公司卸载2C,再经4公司卸载一单位A;载重2B经1卸载1个单位B,再经2公司卸载1单位B;载重2B经公司8卸载1B,再经4卸载1B.由上可得：公司1运(A+2C)2次，(A+C)的1次，再由2个其他车次分别运载1单位B和1单位A;公司2运2单位B原料2次，（A+2C）1次，再分别由其他1车次提供1单位B；公司3运（A+2C）2次；公司4运(A+2C)1次，再分别由其他3车次各提供2单位A,1单位B；公司5运(A+2C)1次，2B运1次，再由其他车次提供2C;公司6运2B原料2次，再由其他2车次各提供1单位C和2单位C;公司7运(A+2C)2次，2B原料1次，再由其他车次提供1单位C；公司8运(A+C)11次，A原料4次，2B料1次，再由其他车次提供1单位B。总费用=其中m为每车次货物重量，Si为载重所走的路程，（60-Si）为空载的路程。各车次所用具体费用看附录表5.1时间其中Ti1表示第i车次载重所用时间，Ti2表示第i车次空载所用时间，由于这里路程相同，车速相同，所以各车次运载一次所用时间相同，不同的是卸货次数的不同而增加的卸货时间。一共是27车次，即27圈，60公里/圈，所用27小时，加上一次性卸货的有22次，用去220分钟，需两次卸货的4次，为80分钟，3次卸货的1次为30分钟，装载时间为405钟，结论：通过线性规划模型得出总车次为27次，用启发式算法配车6两车分别工作时间为7.083小时、7.083小时、7.083小时、6小时、6小时、6小时，总费用为5187.6元模型二：如模型一一样先用线性规划M1次:1A+2C、M2次:2B、M3次:1B+3C、M4次:6CM1、M2、M3、M4为整数求的整体最少车次为27次。下面用0-1规划模型求解最优的调度方式。对这些运输方式，分别记顺时针的调用车次序为i0（i0=1~27），其中i=1~12为调用方式（A+2C），i=13~14为调用方式A+C，i=15~18为调用方式A，i=19~17为调用方式（2B）；逆时针的调用车次序为i1（i1=1~27），其中i=1~4为调用方式A，i=5~6为调用方式A+C，i=7~18为调用方式（A+2C），i=19~27为调用方式（2B）。对于每个被调用以满足不用公司要求的车次，由于不考虑掉头，故可以得到其运输所需要的经费为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（元）[5]5.2问题二模型的建立与求解为了简化问题求解，先考虑在每个公司卡车卸货的次数和方案。首先，假定所有的卡车只卸货一次，卸完货后立即返程。其余假设与最初假设一致。为了使运送的路程，运费，车次尽可能少，因此，这是一个优化问题，目标函数是卸货总次数最少，而为了保证每次卸货的效率，假设在每个站点卸货的重量必须在其最大载重量的一半以上。则卸货的方案满足以下条件：利用遍历算法可以很快确定各种货物的卸载方案如下表：（表5.2.1）方案号abc组合C1102A+2CC20202BC30066CC4013B+3CC5101A+CC6100AC7010BC8011B+CC9012B+2CC100033CC110044CC120055C那么对于一个载重6吨的货车总共有12种载重方案，使得其载重量在3---6吨之间。设Ci为公司第i种卸货方案的使用次数；那么使用这些方案，要在j公司卸货，使得卸货总次数最小，相当于下面这个规划问题：利用LINGO可以变成求出各个公司对应各种方案的最小次数如下表：（表5.2.2）方案工厂1工厂2工厂3工厂4工厂5工厂6工厂7工厂8C1A+2C20201000C22B02000201C36C00000000C4B+3C00000010C5A+C01020010C6A20010015C7B00010000C8B+C11002011C9B+2C00000000C103C00000100C114C00000000C125C00000000由上表可得各公司最少卸货方案为1公司：2C1+2C6+C8、2公司：2C1+2C6+C8、3公司：2C1、4公司：2C5+C6+C7、5公司:C1+2C8、6公司：2C2+C107公司：C4+C5+C6+C8、8公司：C2+5C6+C8现在每个公司的最少卸货方案已定，在这个优化的基础上，我们考虑尽可能的降低成本，车次，和时间的问题。尽管每个公司的卸货方案已定，但是出动多少车次的车，以及如何安排车上货物，车子的运行路线未定。这里首先考虑减少车次。例如：两个不同公司，如果同时有两个方案x,y它们的卸货重量均为3吨，那么这两个方案完全可以由一部车子一次来完成。那么在不同工厂之间就存在可以“匹配”的方案。根据我们之前的假设，为了提高卸货运输效率，每种卸货方案卸载重量最少，如果要匹配的方案，最少要在两个公司之间匹配，匹配方案的载重；显然，这样一来，可以匹配的方案必然是3吨卸货方案和3吨的卸货方案匹配了。那么一个公司最多有几个3吨的卸货方案呢？答案是最多一个，如果存在2个以上，那么两个3吨的货物完全可以由一个6吨满载卡车一次卸完，这显然不是最优方案，上面我们得出的正是最优卸货方案，所以没有必要再考虑一个公司是否有多个3吨的卸货方案了。综上所述，各种卸货方案只有的方案可以匹配，而且匹配只会发生在不同公司之间。对于无法匹配的卸货方案就只能耗费一车次来单独完成了。路线选择：（1）单车次卸货方案的路线选择本问题中的车子可以倒车返程。由码头到某公司可以顺时针走，也可以逆时针，如果某车次的车去j公司卸货，卸货完成后返程，那么可能的路程就是2L1,2L2。为节省路费和时间，我们对每个车次卸货方案选择最短路线。即路程为。选择路线为L1,L2中最短的一条走。（2）可匹配方案车次的路线选择如有两个公司，它们之间可以匹配货物，根据之前的推断，在公司I,j都存在卸货重量为，它们之间的距离为，到港口间的直接距离为。如何选择路线才是最好呢？我们以成本为最优先考虑，对于这个问题，卡车有以下4种路线选择：港口----I------J-----港口；运费成本：港口----I----J----J----港口；运费成本：港口----J----I----港口；运费成本：港口----J----I----J----港口；运费成本：方案选择：从以上的等式，其中的P1表示载重运费，单位元/吨公里；P2表示空载路费。其中P1=1.8;P2=0.4；所以优先考虑的是系数最大的，即：系数的项，L1或L2，取最小值的那条路线。然后在观察，其项恒等于L0，对于给定的公司，L0为一个定值，没有优化的余地。再看剩下的项，它等于总路线，其选择的回程路线应该是回程最短的路线。可以证明，这里最少运费的路线也是最省时间的路线。匹配方案的选择：如果所有的公司里，总共n个公司可以匹配卸货方案，那么匹配的总方法就有；我们可以把每个可以匹配的公司看做图论里的顶点，他们之间连线形成一个完全图，每条连线上赋上权值表示I,j公司之间在走最优路线下的费用（元）和时间（分）线性组合，其中选择恰当的A,B的值使得路费成本P能够更优先考虑，一般使得AP>=Bt选择最优匹配组合的算法：先选择权值最小的一条连线，把其上的两个顶点（公司）链接起来；记录已经连线的顶点；再选取次小权值的连线，如果连线上的顶点不是记录中已经连线的顶点，则执行（2）步；否则选取下一个次小权值的连线，重复（3）。直至记录中的顶点数与总顶点书的差小于等于1。程序终止。以上实例中，只有4，6公司可以匹配，因此，这里只需要考虑4，6公司匹配的最优路线问题。选择最小车次的调度方案：通过上面的方法，现在已经确定了最小运费和最少时间的方案。还剩下：最少出车的调度方案：车的调度方案应该确定一下变量：出车的数量num；每辆车分别在哪些公司（J）卸货，在每个公司卸货几次。采用贪婪算法来解决匹配方案：（贪婪算法的程序见附录3）初始化车辆数num=1；按照运送时间。从大到小对各个公司进行排序；并定义为公司j的卸货次数；令使用时间q=0初始化；按照排序好的公司做一下工作：从排好序的公司，依次执行其卸货车次的运输，执行完j公司的所有运送后，执行下一公司的运送，每运送一次，q=q+；并使直至q<=t_max（最大时间，这里是480分钟）不成立，然后另j=j+1；指向下一公司，观察q+tj<=t_max是否成立，成立则q=q+tj；否则j=j+1；循环执行至j>n，这里n是公司数量；num=num+1；遍历检测mj，若所有mj==0，则退出程序；否则记录下此时num对应的q值，即为其运送的时间。本问题中，每个公司的运送次数如下表：表5.2.3公司4353，6（匹配）62718时间837371605555474135卸货次数423134457车辆需要4辆，具体车次如下表：表5.2.4车公司1公司2公司3公司4公司5公司6公司7公司83，6匹配12次4次23次3次1次1次31次4次4次44次6次结论：共用4辆车，所用时间分别为，1车7.967小时；2车7.883小时；3车7.483小时；4车6.233小时。5.3问题三模型的建立与求解5.3.1第一问问题3分了4，6，8吨载重的三种车，为了卸货效率较高，要求每种车卸货的重量为本车最大载重的一半以上；同时注意到，对于低于6吨的货物，可以由6吨载重的卡车运，没有必要用8吨的（空载车费随最大载重量增加而变贵），而4吨以下的就没必要用6吨的车来卸货，这样只会增加卸货的次数，因此只考虑3，4，5，6，7，8吨卸货的方案。其中：4吨载重车可以卸货：3吨，4吨；6吨载重车可以卸货：5吨，6吨；8吨载重车可以卸货：7吨，8吨；基于以上假设，卸货方案有以下几种则卸货的方案满足以下条件：利用遍历算法可以很快确定各种货物的卸载方案如下：4吨载重车卸货方案C1AC2B+CC34CC4BC53C6吨载重车卸货方案D1A+2CD2B+3CD32BD46CD5A+CD6B+2CD75C8吨载重车卸货方案E12AE2A+B+CE3A+4CE42B+2CE5B+5CE68CE77CE8A+3CE9A+BE102B+CE11B+4C现在对每一个公司单独求出其卸货次数最低的优化模型：利用LINGO可以求出最优卸货方案如下：4吨载重车的卸货方案4吨方案公司1公司2公司3公司4公司5公司6公司7公司8C1A11C2B+CC34CC4BC53C6吨载重车的卸货方案6吨公司1公司2公司3公司4公司5公司6公司7公司8D1A+2CD2B+3CD32BD46CD5A+CD6B+2C1D75C18吨载重车的卸货方案8吨公司1公司2公司3公司4公司5公司6公司7公司8E12A111E2A+B+C11E3A+4C11E42B+2C1E5B+5CE68CE77CE8A+3CE9A+B1122E102B+C21E11B+4C1由于所有载重车辆的载重吨位都在最大载重量的一半以上，所有这里不存在需要匹配的卸货方案。因此每次卸货都要耗费单独一个车次来完成。根据以上数据，共需要22车次。为了最大程度减少出车次数和尽可能发挥每辆车的使用时间，仍然和问题2一样，采用贪婪算法，得出的结果如下：4吨位车1辆，2次；6吨位1辆，2次，8吨位2辆，18次即公用4辆车，出车22次，详细调用如下表：表5.3.14吨车：1辆车公司1公司2公司3公司4公司5公司6公司7公司811次1次6吨车：1辆车公司1公司2公司3公司4公司5公司6公司7公司811次1次8吨车：2辆车公司1公司2公司3公司4公司5公司6公司7公司811次1次1次2次2次23次2次2次4次6模型的评价对于问题一的模型一，在港口少，送货地点少时能够较轻松的实现最优调度，且相对其他模型费用更低，值得推广。但当港口增多，需求加大，公司增多时则比较难以做到最优的匹配。7模型的扩展对于问题三的第二问，由于各公司间有道路相通，因此不但要考虑车次问题，还要考虑路径的长短。而最短路问题可用迪克斯特拉（Dijkstra）算法该算法为：1给Vs以P标号，P（Vs）=0,其余各点均给T标号，T(vi)=+；2若vs点为刚得到P的点，考虑这样的点vj；（vi，vj）属于E，且vj为T标号。对vj的T标号进行如下改进：3比较所具有T标号的点，把最小者均改为P的标号，即：当存在两个以上最小者时，可同时改为P标号，若全为P标号则停止。否则用代vi转回第2步。对于问题三可把港口标vs，vi即为各公司的点，算出最短距离再用如问题二中的解决方法，即可求出最优调度方案，另外还可用遗传算法实现调度。参考文献[1]周凯，宋军全等编著，数学建模竞赛辅导教程，浙江大学出版社，20XX年8月[2]徐光辉等编著，运筹学基础手册(第一版)，科学出版社，1999年3月[3]谢金星，薛毅，优化模型与LINGO软件，清华大学出版社，20XX年[4]陈杰,MATLAB宝典,电子工业出版社,20XX年[5]武汉理工大学，货运公司的运输问题，/view/5f8f8d6e58fafab069dc0294.html20XX年8月4日[6]胡运权，郭耀煌编著，运筹学教程（第三版），清华大学出版社，20XX年4月附录LINGO代码：1问题3解决代码：MINC1+C2+C3+C4+C5+D1+D2+D3+D4+D5+D6