毕业设计（论文）外文资料翻译--海洋枢纽规划 14页

淮阴工学院毕业设计(论文)外文资料翻译学院：交通工程学院专业：交通运输姓名：殷琪学号：1071501134外文出处：JournalofMarineScienceandTechnology附件：1.外文资料翻译译文；2.外文原文。指导教师评语：2011年2月22日签名： 附件1：外文资料翻译译文海洋枢纽规划海洋枢纽和辐射网络应用于发送集装箱船已经有二十多年了,但很少有人注意到这些网络上。海运网络问题作为一个解决中心位置的问题,所涉及的包括最优区位的辐射和在运输网络中的分配,当然分配也可以在辐射路线之间。在本文中提出了令人满意的解决方法。二次整数模型由两阶段组成:一个中心选址模型，一个辐分配模型。我们就应用一个基于最短路径规则和试验性路径的基础上的启发式方案，验证了该模型的正确性和提出解决问题的方法。结果表明,所建立的模型是一个凹函数,这是利用开发方面的中心数利润总额的规模经济得出的。这样辐射分配可能变化为一个枢纽的最佳选择位置。最近进行了对枢纽和辐射的网络设计模型的研究，尽管海洋枢纽和辐射网络用于发送集装箱船已经有二十年了，但是只有少数文章重视到这些网络。一些文章制订数学规划模型来发送集装箱船，但这些模型忽视集装箱船的特征路线。不同的系统需要不同的模型描述情景模式并且需要充分根据其自身特点。这篇论文的目的是建立一个更适合的模型来获得海洋运输的特征网络，同时最大化运输网络的利润。在交通运输网络中,从它的起源节点移动到其目的节点,通常能组成枢纽系统。在这种系统中,运输枢纽作为特殊节点巩固和交换连接着许多的原始地和目的地。这些相互联系的枢纽就有了很多的应用，例如航空旅行，通信网络，邮政的交货系统，集装箱船。使用枢纽和辐射系统的主要原因是因为枢纽更加适合于从大的联合交通向小数目的枢纽连接枢纽的规模经济。因此降低了在这些连接中的运输成本。枢纽和辐射网络系统通常由至少两个等级的系统做成，他们是枢纽层和辐射层。枢纽定位问题是要确定一个最佳数值使交通运输枢纽布局以及其辐射定位在一个网络上。通常，总的运输成本总是最低的。自从欧凯利第一次提出一个二次的整数规划，二次启发式算法去解决枢纽定位问题，越来越多的研究已经涉及到 原型的问题,。比如坎贝尔，偶凯利和米勒的研究。坎贝尔提出将这个问题分成四个类别：设计枢纽中位数问题、可行的枢纽选址问题、枢纽中心问题和枢纽覆盖面问题。其中前两个为研究重点。如果枢纽的数量没有给定，那么枢纽定位问题就是设计枢纽中位数问题。不一样的假设可能导致不一样的问题结构和网络模式。例如单一的分配意味着每一辐射对应着一个枢纽，而一个多重分配则允许辐射连接一个以上的枢纽。在某些情况下，允许辐射之间存在直接的路径，这将导致“非严格中心枢纽策略”问题。尽管它有广泛的使用，但是设计枢纽和辐射系统仍然是一个挑战性任务，主要困难在于模型提法和算法的解为特征的一个特别系统。作为解决枢纽定位问题的需要，以前的论文主要地关注启发式算法比较多一些。欧凯利第一次建立了基于距离原则解决设计枢纽选址问题的假说，这就将所有辐射和一个一个的枢纽相互关联起来了。柯林斯维茨提出了两套基于多目标距离和流动原则的思维，而不是单一的距离。柯林斯维茨首先先确定中心枢纽的位置，然后将辐射线分配到确定的枢纽上，然后通过分配到枢纽的辐射线来进行优化。其他的启发式聚类分成一些节点，然后把枢纽分配到每一个组。在之后的工作中，柯林斯维茨考虑用禁忌搜索，贪婪搜索程序寻求外局部最优。阿金是第一个考虑用拉格朗日松弛解决设计枢纽的规模问题，此外阿金还提供一个分支定界算法和一个以贪婪为依据德交换启发式模型来解决枢纽定位问题的不严密性。在严格的枢纽中，所有的交通量必须通过枢纽进行转运，柯林斯维茨提出了无容量限制的双上升过程来解决枢纽定位问题。欧凯利提出算法来解决方案的两个下界。坎贝尔是第一个制定贪婪的交换的启发式搜索来解决容量限制多路径枢纽定位问题的人。最大流动启发式由最大流准则来分配辐射线到枢纽。而全流量的目的是为了将量减少整个网络的成本。斯科林-科波夫首次提出混合整数配方来寻求单一和多任务的分配问题的解决方法。恩斯特和肻斯穆斯里还制定了分两个阶段产生的确切解决方案。思恩和帕克提出了一个解决单一和多个设计枢纽的定位问题的模型。恩斯特提供了基于无容量限制的启发式算法来解决枢纽定位问题。而恩波利为了解决多枢纽分配问题而提出了基于基于最短路径的混合整数分支定界算法。而博兰等人利用预处理程序和受约束的混合整数模型来解决多重分配任务。海洋集装箱船是由枢纽和辐射决定，其中集装箱运输船携带货物从始发港，通过运输网络中的枢纽到达目的港。在这篇文章中，正如以前研究枢纽定位问题那样，但是也有三点不同： 1)在过去的枢纽定位问题中，枢纽是完全的相互联系的，但是在实际的海洋问题中，枢纽并没有得到充分的网络，他们更像是穿梭的部分，枢纽的连接是按顺序直接连接的。2)在过去的枢纽定位问题中，交通是通过建立枢纽运行的，每个辐射线必须连接到一个枢纽，在海洋问题中，某些辐射线可能绕过其他的辐射线连接到枢纽，按照这样的分配海洋网络问题可以说是不严密的枢纽分法。3)在过去的枢纽定位问题中，中间枢纽的成本只是根据中心环节计算，但是在海洋问题中，中间枢纽的成本包括中间枢纽之间的连接的费用之和，他放映了枢纽的层次结构。因此，在本文中添加了这些特征作为问题的一部分，也就是不严密的枢纽定位问题。这些问题先前的文献中尚未研究过。由于交通枢纽港口的增加，海洋运输经营者可受益于枢纽港口船舶形成的规模经济。为了充分的利用这个优势，海洋运输经营者必须解决海洋运输的不严密的枢纽定位问题。然而这些问题只是在某些文献中得到了有限的重视。罗能回顾过去十年的文献发现了路线和调度的问题，并且只有少数涉及到发送集装箱运输船。拉娜和维克森提出了混合整数非线性规划的分解来解决最佳路径问题。哈拉米略和帕拉卡斯以及鲍威尔开发了线性规划来描述航线集装箱船和部署方案。克里斯提森和纳格林提出了一种基于最优解分支定界和容量限制来解决船舶航线问题。弗格霍斯特通过为每个船舶类型编号以及相关的班轮航运线路问题来确定最佳船舶类型。陆提出了一个与周期和船舶限制的分支界定算法来寻求船舶的最佳路径。楚等人提出了用混合整数模型来确定集装箱港口调用和受周期限制的港口需求之间的最优序列。阿扎荣和肯法采用了基于随机动态规划半马氏决策过程和网络流理论找到船舶的动态最短路径问题。这些路径都忽视了真实的海洋路径，那些复杂的模型结果中会产生不切实际解决方案。最近毛柔等人开发了整数规划模型来解决基于枢纽和辐射网络的船舶分配问题。谢和常提出了一个整数规划模型，其中部分修改了欧凯利的模型以解决不严密的海洋枢纽定位问题。在以后的工作中，谢和王提出了基于同一问题的距离规则的启发式算法的二次整数最小化模型。在本文中我们提出了一个有广泛应用的途径来解决不严密的海洋枢纽定位问题，该模型比谢和王的成本最小化模型更大更复杂，这是因为:(1)成本最小化模型只考虑运输成本，而这个模型同时考虑收入之间的权衡及相关费用（固定成本，航行成本，港口成本，营运成本，燃油成本） (2)在成本最小化模型，没有船的分类是考虑在内。在这种模式中，不同大小的船分成两个层次的系统，引进了更多的限制条件（负载能力，当运载货物时船舶出发和返回，计划时限）(3)在此模型中，服务的频率和船的数量只被视为决策变数。有了这些考虑，该模型可以更充分地代表在现实中存在的问题。以我们最好的知识，这是第一次提出在枢纽定位问题中收入和成本如何权衡，即使我们看到有许多相似的应用。我们的方法是从跨越太平洋航线上得到数据。部分的交通流从各个资源中估计，这是因为真实的数据并不是都是可用的。 MarinehublocationproblemsMarinehub-and-spokenetworkshavebeenappliedtoroutingcontainershipsforovertwodecades,butfewpapershavedevotedtheirattentiontothesenetworks.Themarinenetworkproblemsareknownassingleassignmentnonstricthublocationproblems(SNHLPs),whichdealwiththeoptimallocationofhubsandallocationofspokestohubsinanetwork,allowingdirectroutesbetweensomespokes.InthispaperwepresentasatisfactoryapproachforsolvingSHNLPs.Thequadraticintegerprofitprogrammingconsistsoftwo-stagecomputationalalgorithms:ahublocationmodelandaspokeallocationmodel.WeapplyaheuristicschemebasedontheshortestdistanceruleandanexperimentalcasebasedontheTrans-PacificRoutesispresentedtoillustratethemodel’sformulationandsolutionmethods.Theresultsindicatethatthemodelisaconcavefunction,exploitingtheeconomiesofscalefortotalprofitwithrespecttothenumberofhubs.Thespokeallocationmaychangeanoptimalchoiceofhublocations.Anumberofstudieshaverecentlybeendoneonthenetworkdesignproblemforhub-and-spokepatterns.Althoughmarinehub-and-spokenetworkshavebeenappliedtoroutingcontainershipsforovertwodecades,fewpapershavesofardevotedtheirattentiontothesenetworks.Somepapersformulatedmathematicalprogrammingmodelsforrouting containerships,butthesemodelsneglectthecharacteristicsofcontainerships’routes.Differentsystemsrequiredifferentmodelstoadequatelyportrayscenariopatternsbasedupontheircharacteristicfeatures(O’Kelly,1998;BryanandO’Kelly,1999).Theaimofthispaperistodevelopamoreadequatemodelforcapturingtheparticularcharacteristicsofmarinenetworks,whilemaximizingthetotaltransportationprofitofthenetwork.Transportationnetworks,inwhichtrafficmovesfromitsoriginnodetoitsdestinationnode,areoftenconfiguredashub-and-spokesystems.Insuchsystems,hubsarespecialnodesthatserveasconsolidationandswitchingpointsthatconnectmanyoriginsanddestinations.Theconceptoftheseinteractinghubsarisesfrequentlyinmanyapplications,suchasairpassengertravel,telecommunicationnetwork,postaldeliverysystems,andcontainerships.Themajorincentiveforemployingahub-and-spokesystemsisthathubsenjoyeconomiesofscaleachievedbylargerconsolidatingtrafficintosmallernumberofhub-to-hublinks,thusgeneratinglowerunittransportationcostonthoselinks.Hub-and-spokenetworksusuallyconsistofatleastatwo-levelsystem:hublevelandspokelevel.Thehubto-hubportionisusuallydiscountedbyafactorá(0<á≤1)toaccountfortheconceptofhubbingeconomies。Thehublocationproblems(HLPs)aretodetermineanoptimalnumberandlocationofhubs,andallocationofspokes(non-hubs)tothesehubsinanetworksuchthat,typically,thetotaltransportationcostisminimized.Since O’Kelly(1986a,1986b,1987)firstproposedaquadraticintegerprogrammingandtwoheuristicalgorithmsforsolvingtheHLPs,anincreasingnumberofstudieshavebeendoneonthisprototypeofheproblems,suchasCampbell(1994)andO’KellyandMiller(1994).Campbell(1994)presentedtheHLPsintofourdifferentbasiccategories:thep-hubmedianproblem,theuncapacitatedhublocationproblem,phubcenterproblems,andhubcoveringproblems.MostofworkonHLPshasfocusedontheformertwoproblems.Ifthenumberofhubsisnotgiveninanetwork,thephubmedianproblemisusuallytheHLP.InuncapacitatedHLPs,thereisafixedcostforestablishingahub,butnoconstraintonthenumberofhubs(Campbell,1994;Klincewicz,1996;Eberyetal.,2000).Differentassumptionsmayresultindifferentproblemstructuresandnetworkpatterns.Forexample,asingleassignmentisstructuredsothateachspokeisassignedtoonlyonehub(O’Kelly,1987,1992;Klincewicz,1991,1992;Campbell,1994,1996;Skorin-KapovandSkorin-Kapov,1994;Skorin-Kapovetal.,1996;Aykin,1990,1995;ErnstandKrishnamoorthy,1996;Kara,etal.2003).Amultipleassignmentallowsspokestointeractwithmorethanonehub(Campbell,1994;O’KellyandLao,1991;Klincewicz,1996;Skorin-Kapovetal.,1996;Krishnamoorthyetal.,1998,2000).Occasionally,thereisalsoafixedcosttoestablishahub(O’Kelly,1992;Campbell,1994;Aykin,1995;O’Kellyetal.,1996;SohnandPark,1998).Insomecases,itispossibletoallowdirectroutesbetweensomespokes,resultinginaproblemcalled“Nonstrict HubbingPolicy”(Aykin,1994,1995).Despiteitswidespreaduse,designingefficienthub-and-spokesystemsremainsachallengingtask.Aprimarydifficultyliesinmodelformulationsandsolutionalgorithmsforthecharacteristicofaparticularsystem.AsaresultofthecomputationalneedsinsolvingHLPs,previousstudiesprimarilyfocusedonheuristicalgorithmsratherthanexactsolutionsformodels.O’Kelly(1987)wasfirsttodeveloptwoenumeration-basedheuristicsusingdistanceruleforsolvingthesingleassignmentp-hubmedianproblem,inwhicheveryspokeisallocatedtoexactlyonehubandallhublinkagesarefullyinterconnected(i.e.,apurehub-and-spokenetwork).Klincewicz(1991)proposedtwosetsofheuristicsforlargerproblemsbasedonamulti-criteriadistanceandflowruleratherthanondistancealone.Klincewicz’sexchangeheuristicsfirstdeterminethehublocations,andthenassignmentofspokestohubs,withchangesthesolutionmadebytheassignmentofhubstospokes.Theotherclusteringheuristicsdividethenodesintoseveralgroupsandassignahubforeachgroup.Inlaterwork,Klincewicz(1992)consideredtabusearchandgreedysearchprocedurestoexploresolutionsbeyondlocaloptima.Skorin-KapovandSkorin-Kapov(1994)developedothertabusearchheuristic,assigningequalimportancetothelocationandallocationportionsoftheproblem.Aykin(1994)wasfirsttoconsidertheLangrangianrelaxationforthep-hubmedianproblemwithhubcapacity.Aykin(1995)providedabranch-and-boundalgorithmandasimulatedannealingbasedongreedy interchangeheuristicforinvestigatingtheeffectsofstrictandnonstrictontheHLPs.Instricthubbing,alltrafficmustshipviaasetofhubs;nonstricthubbingallowssomedirecttripsbetweensomespokes.Klincewicz(1996)proposedadualascentprocedureforasequenceofuncapacitatedHLPs.O’Kellyetal.(1995)presentedalgorithmtodeterminetwolowerboundsontheoptimalsolution.Skorin-Kapovetal.(1996)developedeffectivemixedintegerformulationswithtightlinearprogrammingrelaxationslaxationsfortheHLPs.Campbell(1996)wasfirstonetoformulateagreedyexchangeheuristictosolveuncapacitated,multipleassignmentHLPs.TheMAXFLOheuristicassignsspoketohubbymaximumflowrule,whereastheALLFLO’spurposeistominimizethetotalnetworkcost.BymodifyingCampbell’smodel(Campbell,1996),Skorin-Kapovetal.(1996)werefirsttoproposemixedintegerformulationsforfindingexactsolutionsforthesingleandmultipleassignmentproblems.ErnstandKrishnamoorthy(1996)alsodevelopedatwo-stageapproachtoproduceexactsolutions.SohnandPark(1998)providedareducedsizeformulationmodelforuncapacitatedsingleandmultiplep-hublocationproblems.ErnstandpresentedexactandheuristicalgorithmsfortheuncapacitatedmultipleassignmentHLPs,whileEberyetal.(2000)presentedmixedintegerformulationsusingbranchand-boundalgorithm,basedontheshortestpathrule,forthecapacitatedmultipleassignmentproblem.Bolandetal.(2004)consideredpre-processingproceduresandtighteningconstraintswithexistingmixedintegerlinear programmingmodelformultipleassignmentproblem.Marinecontainershiproutesarehub-and-spokestructures,inwhichcontainershipscarrycargofromtheiroriginports,throughhubportsinthenetwork,totheirdestinationports.Inthispaper,theproblemistheHLPaspreviouslystudied,butfordifferentapplications.Therearethreefundamentaldifferences:(1)InpastHLPs,hubsarefullyinterconnected,whereasinmarineproblems,hubsarenotfullynetworks;rathertheyaremorelikeshuttlepatterns.Thehubconnectionsaresequentialandinthesamedirectionalorder(HsiehandChang,2001).(2)InpastHLPs,trafficisshippedviasetofhubs,andeachspokeconnectstoahub.Inmarineproblems,however,somespokesmaybypassotherstoconnecttoahub(seeGilman,1981;PearsonandFossey,1983).Insuchanallocation,marinenetworkproblemscanbeclassifiedasnonstricthubbingpolicy,asdefinedbyAykin(1995).(3)InpastHLPs,theinterhubcostcountsbyonlycostwithhublink.Inmarineproblems,theinterhubcosthastoaccumulateallcostoneachinterhublink,reflectingthehublevelstructure.Consequently,thedefinitionofourproblemhavingsuchfeaturestobediscussedinthispaperisreferredtoassingleassignment,nonstricthublocationproblems(SNHLPs).Theseproblemshavenotyetbeenstudiedinpreviousliterature.Duetotheincreasedtrafficathubports,marinelineroperatorscanbenefitfromthescaleeconomiesofshipcapacityutilizedathubports(Chadwinetal.,1990).Inordertotakefulladvantageofthis,however,itis criticalforlineroperatorstosolvemarineSNHLPs.Yettheseproblemshavereceivedlimitedattentionintheliterature.Ronen(1993)reviewedliteraturefromthelastdecaderegardingroutingandschedulingproblemsandidentifiedonlyafewthatpertainedtoroutingcontainerships.RanaandVickson(1998,1991)proposedamixedintegernonlinearprogrammingcombinedwithdecompositiontosolvetheoptimalroutingproblem.JaramilloandPerakis(1991),ChoandPerakis(1996),andPowellandPerakis(1997)developedlinearprogrammingtodescribetheroutingcontainershipsanddeploymentscenario.ChristiansenandNygreen(1998)presentedanoptimalsolutionbasedonbranch-andboundsearchwithinventoryconstraintsforshiproutingproblems.Fagerholt(1999)identifiedoptimalshiptypes,thenumberforeachtype,andcoherentroutesforthelinershippingproblem.Lu(2002)proposedabranch-andboundalgorithmwithcycletimeandvesselconstraintsforanoptimalshiprouting.Chuetal.(2003)proposedamixedintegermodeltodetermineanoptimalsequenceofportcallsandcontainerflowbetweendemandportswithcycletimeconstraints.AzaronandKianfar(2003)appliedastochasticdynamicprogrammingbasedonsemi-Markovdecisionprocessesandnetworkflowtheorytofindthedynamicshortestpathforshiproutingproblem.Thesestudiesneglectedtherealityofmarineroutingproblem,resultinginmodelsthatwerecomplicatedandpossiblygeneratedunrealisticsolutionstomarineSNHLPs.Recently,Mouraoetal.(2002)developedan integerprogrammingmodeltosolveshipfleetassignmentwithdefinedvoyagesbasedonhub-andspokenetworks.HsiehandChang(2001)proposedanintegerlinearprogramming,whichmodifiedO’Kelly’smodel(O’Kelly,1987),tosolvemarineSNHLPs.Inlaterwork,HsiehandWong(2003)proposedaquadraticintegercostminimizationmodelwithheuristicalgorithmsbasedondistanceruleforthesameproblem.InthispaperweproposeanextensiveapproachformarineSNHLPs.ThemodelislargerandmorecomplicatedthanthecostminimizationmodelofHsiehandWong(2003)because:(1)thecostminimizationmodelconsideredonlytransportationcost,whereasthismodelconsiderssimultaneouslythetradeoffsbetweenrevenueandrelatedcosts(e.g.,fixedcost,sailingcost,portcost,operationalcost,andbunkercost).(2)Incostminimizationmodel,noshipassignmentisincluded.Inthismodel,however,differentshipsizesaredeployedtothetwo-levelsystem,introducingadditionalsetsofconstraints(e.g.,loadcapacity,cargocarriedwhenvesseloutgoingandreturning,planninghorizon).(3)Inthismodel,thefrequencyofserviceandthenumberofvesselsareviewedasdecisionvariables.Withtheseconsiderations,themodelcanmoreadequatelyrepresenttherealityoftheexistingproblems.Tothebestofourknowledge,thisisthefirstworktoprovideameanstoexplicitlyaddresstradeoffsbetweenrevenueandcostontheHLPsintheliterature;evenwecanimaginemanysimilarapplications.OurapproachesaretestedonadatasetfromTrans-PacificRoutes.Parts oftrafficflowareestimatedfromvarioussourcesbecauserealdataarenotgenerallyavailable.