资源描述:
《# 2003 kluwer academic publishers. printed in the netherlands. a flexible system for schedu》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、JournalofScheduling6:437±455,2003.#2003KluwerAcademicPublishers.PrintedintheNetherlands.AFLEXIBLESYSTEMFORSCHEDULINGDRIVERSANTHONYWREN,SARAHFORES,ANNKWAN,RAYMONDKWAN,MARGARETPARKER,ANDLESPROLLSchoolofComputing,UniversityofLeeds,UKABSTRACTAsubstantialpartoftheop
2、eratingcostsofpublictransportisattributabletodrivers,whoseefficientusethereforeisimportant.Thecompilationofoptimalworkpackagesisdifficult,beingNP-hard.Inpractice,algorithmicadvancesandenhancedcomputingpowerhaveledtosignificantprogressinachievingbetterschedules.H
3、owever,differencesinlaborpracticesamongmodesoftransportandoperatingcompaniesmakeproductionofatrulygeneralsystemwithacceptableperformanceadifficultproposition.TRACSIIhasovercomethesedifficulties,beingusedwithsuccessbyasubstantialnumberofbusandtrainoperators.Manyt
4、heoreticalaspectsofthesystemhavebeenpublishedpreviously.Thispapershowsforthefirsttimehowtheoryandpracticehavebeenbroughttogether,explainingthemanyfeatureswhichhavebeenaddedtothealgorithmickerneltoprovideauser-friendlyandadaptablesystemdesignedtoprovidemaximumfle
5、xibilityinpractice.Wediscusstheextenttowhichusershavebeeninvolvedinsystemdevelopment,leadingtomanypracticalsuccesses,andwesummarizesomerecentachievements.KEYWORDS:driverscheduling;publictransport;mathematicalprogramming;heuristics1.INTRODUCTIONTheproblemofschedu
6、lingpublictransportanditsdrivershasreceivedmuchattention,particularlyamongtheORcommunity,overmanyyears.Wren(1998)hasbeeninvolvedsince1967inexploringmanydifferentsolutiontechniqueswhichcanbeappliedtoNP-hardpublictransportschedulingproblems,and,inparticular,tothed
7、riverschedulingproblem.Themostsuccessfulcommercialdriverschedulingpackages,forexample,TRACSII(Fores,Proll,andWren,2002)andHASTUS(HamerandSeguin,1992),modeltheproblemusingmathematicalprogramming.Mathematicalprogrammingapproachesarebasicallyoftwotypes.Generate-and
8、-Selecttechniques,includingTRACSII,relyonapre-generatedsetofshifts.As,forcomputationalreasons,thissetcanonlybeasmallsubsetofthosepotentiallyavailable,suchtechniquesca