A Two-Phase Algorithm for Tramp Ship Routing.pdf

《A Two-Phase Algorithm for Tramp Ship Routing.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ATwo-PhaseAlgorithmforTrampShipRoutingProblemsbyaColumnGenerationApproachKazuhiroKobayashi1,ToshiyukiKano1,andMikioKubo21CenterforLogisticsResearch,NationalMaritimeResearchInstitute,Tokyo,Japankobayashi@nmri.go.jp2DepartmentofLogisticsandInformationEngineering,TokyoUniversityofMarineScienc

2、eandTechnology,Tokyo,JapanAbstract.Acolumngenerationapproachfortrampershiproutingprob-lemsisstudied.Weshowthatanefficientalgorithmcanbeobtainedbydecomposingtheproblemintotwosimpleproblems.Themasterprob-lemofthecolumngenerationisasetpartitioningproblemandthesubproblemisthetime-dependentshorte

3、stpathproblemswithtimewindows.Numericalresultsofproblemsusinggeneral-purposeinteger-programmingsolverandthedynamicprogrammingalgorithmarein-cludedtodemonstratetheperformanceoftheproposedmethod.Keywords:shiproutingproblem,columngeneration,shortestpathproblem1IntroductionShippingcompanieshav

4、emanycomplex,extensiveplanningproblemsatthreedifferentlevels.Thestrategicplanningproblemsincludethedeterminationofthesizeandthenumberofcompany-ownedshipscomparedwiththecargorequire-ments.Thetacticalplanningproblemsincludethedesignofservicenetworkbycreatingtheshiproutes,andtheassignmentofshi

5、pstotheseroutes.Theop-erationalplanningproblemsincludethedeterminationoftheplantoutilizethefleet.Thispaperinvestigatesthetrampshiproutingproblemforoil-producttransportationintheoperationallevelandshowsasolutionapproachforthisproblem.Ashippingcompanymakescontractswithcargoownerstocarryasetof

6、cargoesintheplanninghorizon.Thecompanytriestominimizetheoperatingcostforcarryingthesecargoesbecause(a)improvingfleetutilizationcanleadtosignificantimprovementsinfinancialresults,and(b)increasingfleetutiliza-tioncanreducedamagetotheenvironmentbecauseofreductionsintransportoperations.Theobjectiv

7、eoftheshiproutingproblemistominimizethesumofthecostsforallshipsinthefleetwhileensuringthatallcargoesarecarried!ThisstudywaspartiallysupportedbytheNewEnergyandIndustrialTechnologyDevelopmentOrganization(NEDO)ofJapan.fromtheirloadingporttotheirdischargingport.Ina