航运公司的运输调度问题

航运公司的运输调度问题信息与计算科学系02级2班廖干才向高操i=j苏傲雪向高操i=j一.摘要在经济高速发展的现代社会，如何提高效率，如何使有限的资源得到最优的使用越来越受到人们的重视。本文就是针对某航运公司的运输，制定合理的驳船调度计划，使公司的利润达到最大。在问题一中我们根据题目的约束和假设用C++编写了程序，该程序能够输出用于某运单的所有驳船和直航驳船以及该直航驳船的赢利。接着提出了解决驳船一天调度的三条原则。（见正文）进而得到如下最优解：运单No.1No.3No.4No.5No.6No.7No.8No.9No.10运输的船a2blb3a3clb6b4b2al在问题二中根据题意和问题一的结论给出了多日调度（N天）的四条原则。（见正文）。根据该四条原则，进而得到如下最优解：运单第天第二天第三天No.lNo.3No.7No.l0No.4No.8No.9No.2No.5No.6运输的船a2alcla3b3b4b2a3a2cl关键字：三条原则，四条原则，直航，调度，枚举法。二.问题的分析与求解总体假设：（1）每条船一天至多只能运行一条航线，即每张运单要么由一条驳船承运要么不运，不能把一张运单分给几条船来运。（2）所有的运输尽量是直航，若要从a运到c,而起始港a没有船，应调用其它港b的船来运（调来的空船必须在该港口④和目的港口c有航线许可证）。（3）20寸集装箱的重量为2.5吨，40寸集装箱的重量为3吨。航船的重量只包括集装箱重和货物重。我们查出20寸集装箱的体积为，40寸集装箱的体积为，故20寸集装箱的体积是40寸的一半，我们把20寸集装箱按1：2全部折算为40寸集装箱。（4）每个运单在港口所需的港口费（吊车费、装箱费、工本费、提单费、额外附加费等）费用一样，共小于1000元，当盈利〉1000时，我们就运此运单。解题思路：我们利用题设中的约束，运用C++语言编写了程序1。通过程序1（见附录），我们可以处理任意的在以上六个港口之间运行的运单，从中得到如下几个结果：输出能够用于该运单的所有驳船。输出可以用于该运单的直航驳船。输出该运单用直航驳船运送的利润。由程序可以直接得到下表：（能够用于该运单的所有驳船和航驳船）No.1No.2No.3No.4No.5No.6No.7No.8No.9No.l0al,al,b3,a2,clbl,b2,b2,al,a2,a3,alb4,a3,b3,b4,b3,a3,b2h1a2b6b2b5r1b5h1首先判断某直航是不是承运该运单的最优航线。此时只要考虑调船情况。并且只能够调用比直航驳船成本低的驳船类（例如，直航驳船是B类，则只要考虑能够用于该运单的A类驳船）。接着判断直航驳船被调用承运其他运单时是否比承运运单获利多。如果少，则确定该驳船直航承运其运单。否则，该驳船用于调度。最后考虑如何放弃某份运单。放弃运单的原则1没有能够用于该运单驳船。2承运该运单亏本。3当运单与驳船发生冲突时，放弃利润小。如果利润相当时（或者差额很小），我们优先直航运单。问题一：由上表可以看出直航有一些冲突，如No.1和No.8都需要b4,No.3和No.10都可以选择al或b1,No.3和No.5都可以选择b5,No.6和No.7都可以选择cl.由于No.8只能用b类船来运，故用b4船运No.8；No.3和No.10可以由任意一个用al,另一个用b1,我们取b1运No.3,a1运No.10；用b5运No.5;No.6只能够用c1来运，故用c1运No.6.得：运单No.1No.2No.3No.4No.5No.6No.7No.8No.9No.10可通行的船a1,a2,b2,b4b6b1b3b5c1b1,b3,b5,b6b4b2,b3,b5a1说明：蓝字表示该驳船已被其它航线所运输。从上表可以看出，除了No.1未确定之外，其余的运单都已经确定了下来。然后，我们计算每个订单的利润，看是否都满足条件，但在上表中，No.2的利润很低，只有3600，若用b船来运，运费为3750〉3600，显然不能用b6运，若改用a船，运费为2500，但湛江没有a类船，al和a3中a3离得最近，在汕头，调度过来的运费为2000，此时2000+2500〉3600，所以a船也不能运No.2，即No.2这个订单始终是亏本的，我们选择不运。此时，No.7就可以选择b6,WNo.9可

组号一二三四五六七八九运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号a2No1b2No9c1No6b4No8b3No4a1N10a3No5b1No3b6No7始出港口江门黄埔广州江门广州广州黄埔黄埔汕头汕头香港香港汕头香港香港香港湛江广州运输方式a2（江门）--->（黄埔）转运b2（广州）——>（江门）转运直运直运直运直运a3（汕头）--->（香港）转运直运b6（湛江）--->（广州）转运运单重量㈤乾775〈10001460〈15001690〈1800930<15001290<1500780<1000595<1000938<15001010<1500运单收入7000820013200900096006000550075008000运输问题二以N天为周期的四条原则和解题思路：可以用A类驳船运输的运单尽可能用A类驳船运输。只能够用B类驳船运输的运单，选取直航驳船运输。对于NO.6运单我们只能够选取C1驳船运输。用枚举法具体解决第二天固定航线的选取问题。对于以上原则的前三条进行最优性的证明：用A类驳船运输最优的可能性。由于我们为简化问题把驳船每公里耗费的成本作为整体航行的成本，因此很容易得到A类成本最少，在不高于或者远高于相应的B类驳船运输时的成本下。用A类驳船运输最优的可能性是很显然的了。该条的证明也是显而易见。首先它只能够用B类驳船运输，就不存在成本之间的差异，因此直航成本最低。此条和第二条的证明一样。（省略）由第一问可知：只有No.1,No.2,No.3,No.5,No.10可以用A类船承运，有所制定的三天驳船调度计划，第二天运得No.4,No.8,No.9都需用B类船来承运，第三天中的No.2用B或C类船承运时亏本，故只能用A类船承运，而No.6只能用c1承运。其中No.2,No.10在同一航线，只是运输方向不一样，故第一天承运No.10的船在第三天应该用来承运No.2.考虑到前面的原则：能够用A船运的就尽量用A船运，并且能够用直航运的就尽量用直航，所以第一天中No.3就用直航al承运。No.10用A3转航调运，同时在第三天把A3用于直航运输No・2。而对与No.1和No.5可以由A2通过转航和直航运输。即A2转航运输No.1，到第三天A2直航No.5。这样满足了我们已经证明的原则1-----即可以用A类驳船运输的运单尽可能用A类驳船运输。用原则2和原则3可以很简单的处理No.4,No.6,No.8，即选取它们各自的直航驳船运输。从前两天的运单知道：没有任何的B类驳船到达No.9的起始港口江门，因此而No.9的承运沿用问题一的结论，即从广州调度B2承运No・9。所有驳船在不同天数的起始港口名称:港口香港汕头黄埔广州江门湛江湛江B6江门A2No.3:(A1,A2,B2,B3,B5,C1)NO.7:(B2,B3,B5,CNo.6N0(C1)』说明：红色表小第一天需运的航线，棕色表小第二天需运的航线，蓝色表小第二天需运的航线。得到运输结果:运单第天第二天第三天No.1No.3No.7No.10No.4No.8No.9No.2No.5No.6运输的船a2alcla3b3b4b2a3a2cl组号第一-天第二天第三天运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号运输船只运单编号A2NolA1No3C1No7A3No10B3No4B4No8B2No9A3No2A2No5C1No6始出港江黄香香广广汕香汕汕黄黄广江香香香广香广口门埔港港州州头港头头埔埔州门港港港州港州运输方式a2（江门）--->（黄埔）转运直运直运a3（汕头）--->（香港）转运直运直运B2（r州）——>（江门）转运直运直运直运运单重量（约束）730〈10001000〈15001690〈1800930<15001290<1500750<1000560<1000900<1500970<1500970<1500运单收70007500800060009600900082003600550013200入运输费用4*5003*5003*9006*5001*7502*7505*7505*5004*5003*900赢利50006000530030008850750044501100350010500总计55200用上面的总利润减去第二天的固定航线C1成本费2700元，得52500元为三天内的总利润。三：模型的改进方向针对问题二应建立更一般的模型以满足更加广泛的需要。四：附录相关资料：集装箱的规格：（/logs/2004/10/456344.html20’GP:20’X8’X8’6“5898X2352X239140’GP:40’X8’X8’6'T3032X2352X239240’HQ:40'X8'X9'6'T2031X2352X2698集装箱载重量和容积：20’GP:24850KG,33CBM

40’GP:28800KG,67CBM40’HC:30200KG,76CBM45’GP:27820KG,86CBM源程序：#include<stdio.h>#include<iostream.h>classbook{intsmh,smo,lmh,lmo,heavy,s,e,income;public:book(){smh=0;smo=0;lmh=0;lmo=0;heavy=0;s=0;e=0;income=0;}voidsetsmh(intsh){smh=sh;}voidsetsmo(intsh){smo=sh;}voidsetlmh(intsh){lmh=sh;}voidsetlmo(intsh){lmo=sh;}voidsetheavy(intsh){heavy=sh;}voidsets(intsh){s=sh;}voidsete(intsh){e=sh;}voidsetincome(intsh){income=sh;}intgetsmh(){returnsmh;}intgetsmo(){returnsmo;}intgetlmh(){returnlmh;}intgetlmo(){returnlmo;}intgetheavy(){returnheavy;}intgets(){returns;}intgete(){returne;}intgetincome(){returnincome;}};//smh小型重箱子,smo小型空箱子,lmh大型重箱子,lmo大型空箱子,//heavy总重,s起始港口,e目的港口,income收入classship{intmaxboxes,maxhboxes,heavy;public:ship(intmb,intmhb,inth){maxboxes=mb;maxhboxes=mhb;heavy=h;}intgetmaxboxes(){returnmaxboxes;}intgetmaxhboxes(){returnmaxhboxes;}intgetheavy(){returnheavy;}};//maxboxes最大集装箱个数maxhboxes最大重箱个数heavy最大重量〃汕头-1黄浦-2广州-3江门-4湛江-5香港-6//da[][]A类驳船通行证db[][]B类驳船通行证dno[][]定单数据//shipinti[10]驳船的初始港口//驳船编号规则A类1to3B类4to9C类10voidmain(){inti=0,j=0,profit=0;intda[3][3]={{5,3,2},{2,3,4},{1,4,5}},shipinit[10]={6,4,1,6,3,1,2,6,5,3};intdb[6][3]={{5,3,0},{4,2,0},{4,3,1},{5,2,1},{4,3,0},{5,3,1}};intflag[10]={0,0,0,0,0,0,0,0,0,0};intdist[6][6]={{0,50,100,150,200,50},{50,0,50,100,150,100},{100,50,0,50,100,150},{150,100,50,0,50,200},{200,150,100,50,0,250},{50,100,150,200,250,0}};intdno[10][8]={{50,40,0,0,550,2,6,7000},{0,0,0,60,0,5,6,3600},{75,0,0,0,750,6,3,7500},{0,0,80,0,1050,1,6,9600},{40,30,0,0,420,6,4,5500},{0,0,90,40,1300,3,6,13200},{80,0,0,0,810,3,6,8000},{0,0,60,30,660,2,6,9000},{0,20,50,20,750,4,6,8200},{60,0,0,0,630,6,5,6000}};bookno[2];shipa(80,50,1000),b(120,80,1500),c(150,100,1800);for(i=1;i<=10;i++){no[i-1].setsmh(dno[i-1][0]);no[i-1].setsmo(dno[i-1][1]);no[i-1].setlmh(dno[i-1][2]);no[i-1].setlmo(dno[i-1][3]);no[i-1].setheavy(dno[i-1][4]);no[i-1].sets(dno[i-1][5]);no[i-1].sete(dno[i-1][6]);no[i-1].setincome(dno[i-1][7]);}for(i=1;i<=10;i++){if((0.5*no[i-1].getsmh()+no[i-1].getlmh())>a.getmaxhboxes()||(no[i-1].getlmh()+no[i-1].getlmo()+0.5*no[i-1].getsmh()+0.5*no[i-1].getsmo()>a.getmaxboxes())||3*(no[i-1].getlmh()+no[i-1].getlmo())+2.5*no[i-1].getsmh()+2.5*no[i-1].getsmo()+no[i-1].getheavy()>a.getheavy());else{{if((no[i-1].gets()!=6&&(no[i-1].gets()==da[0][0]||no[i-1].gets()==da[0][1]||no[i-1].gets()==da[0][2]))||(no[i-1].gets()==6&&(no[i-1].gete()==da[0][0]||no[i-1].gete()==da[0][1]||no[i-1].gete()==da[0][2]))){flag[0]=1;printf("no%da1\n",i);}elseflag[0]=-1;}{if((no[i-1].gets()!=6&&(no[i-1].gets()==da[1][0]IIno[i-1].gets()==da[1][1]llno[i-1].gets()==da[1][2]))ll(no[i-1].gets()==6&&(no[i-1].gete()==da[1][0]||no[i-1].gete()==da[1][1]||no[i-1].gete()==da[1][2]))){flag[1]=1;printf("no%da2\n",i);}elseflag[1]=-1;}{if((no[i-1].gets()!=6&&(no[i-1].gets()==da[2][0]||no[i-1].gets()==da[2][1]||no[i-1].gets()==da[2][2]))||(no[i-1].gets()==6&&(no[i-1].gete()==da[2][0]||no[i-1].gete()==da⑵[1]||no[i-1].gete()==da⑵[2]))){flag[2]=1;printf("no%da3\n",i);}elseflag[2]=-1;}}if((no[i-1].getsmh()+no[i-1].getlmh())>b.getmaxhboxes()||(no[i-1].getlmh()+no[i-1].getlmo()+no[i-1].getsmh()+no[i-1].getsmo()>b.getmaxboxes())||no[i-1].getheavy()>b.getheavy());else{{if((no[i-1].gets()!=6&&(no[i-1].gets()==db[0][0]||no[i-1].gets()==db[0][1]||no[i-1].gets()==db[0]⑵))||(no[i-1].gets()==6&&(no[i-1].gete()==db[0][0]||no[i-1].gete()==db[0][1]||no[i-1].gete()==db[0][2]))){flag[3]=1;printf("no%db1\n",i);}elseflag[3]=-1;}{if((no[i-1].gets()!=6&&(no[i-1].gets()==db[1][0]||no[i-1].gets()==db[1][1]||no[i-1].gets()==db[1][2]))||(no[i-1].gets()==6&&(no[i-1].gete()==db[1][0]||no[i-1].gete()==db[1][1]||no[i-1].gete()==db[1][2]))){flag[4]=1;printf("no%db2\n”,i);}elseflag[4]=-1;}{if((no[i-1].gets()!=6&&(no[i-1].gets()==db[2][0]||no[i-1].gets()==db[2][1]||no[i-1].gets()==db[2][2]))||(no[i-1].gets()==6&&(no[i-1].gete()==db[2][0]||no[i-1].gete()==db[2][1]||no[i-1].gete()==db[2][2]))){flag[5]=1;printf("no%db3\n",i);}elseflag[5]=-1;}{if((no[i-1].gets()!=6&&(no[i-1].gets()==db[3][0]||no[i-1].gets()==db[3][1]||no[i-1].gets()==db[3H2]))||(no[i-1].gets()==6&&(no[i-1].gete()==db[3][0]||no[i-1].gete()==db⑵[1]||no[i-1].gete()==db[3][2]))){flag[6]=1;printf("no%db4\n",i);}elseflag[6]=-1;}{if((no[i-1].gets()!=6&&(no[i-1].gets()==db[4][0]||no[i-1].gets(