企業(yè)通勤班車線路優(yōu)化研究.pdf

1、II分類號(hào)密級(jí)單位代碼!Q15l企業(yè)通勤班車線路優(yōu)化研究王云鵬指導(dǎo)教師楊忠振職稱教授學(xué)位授予單位大連海事大學(xué)申請(qǐng)學(xué)位級(jí)別工學(xué)碩士學(xué)科（專業(yè)）物流工程與管理論文完成日期2013年5月答辯日期2013年6月乞戶迭答辯委員會(huì)RouteOptimizationforCorporationShuttleBusRouteOptimizationforCorporationShuttleBusAthesisSubmittedtoDalianMaritimeUniversityInpartialfulfdlmentoftherequirementsforthedegreeofMasterofEngineeri

2、ngWang，Yunpeng(LogisticsManagement)LogisticsEngineeringandManagemenThesisSupervisor：ProfessorYang，ZhongzhenMay2013中文摘要大連海事大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說(shuō)明原創(chuàng)性聲明本人鄭重聲明：本論文是在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果，撰寫(xiě)成碩士學(xué)位論文!么些迤盥垂壘壘熊迭血超越盞除論文中已經(jīng)注明引用的內(nèi)容外，對(duì)論文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均己在文中以明確方式標(biāo)明。本論文中不包含任何未加明確注明的其他個(gè)人或集體已經(jīng)公開(kāi)發(fā)表或未公開(kāi)發(fā)表的成果。本聲明的法律責(zé)任由本人承

3、擔(dān)。學(xué)位論文作者簽名：量三醋學(xué)位論文版權(quán)使用授權(quán)書(shū)本學(xué)位論文作者及指導(dǎo)教師完全了解大連海事大學(xué)有關(guān)保留、使用研究生學(xué)位論文的規(guī)定，即：大連海事大學(xué)有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交學(xué)位論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)大連海事大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，也可采用影印、縮印或掃描等復(fù)制手段保存和匯編學(xué)位論文。同意將本學(xué)位論文收錄到中國(guó)優(yōu)秀博碩士學(xué)位論文全文數(shù)據(jù)庫(kù)（中國(guó)學(xué)術(shù)期刊（光盤(pán)版）電子雜志社）、中國(guó)學(xué)位論文全文數(shù)據(jù)庫(kù)（中國(guó)科學(xué)技術(shù)信息研究所）等數(shù)據(jù)庫(kù)中，并以電子出版物形式出版發(fā)行和提供信息服務(wù)。保密的論文在解密后遵守此規(guī)定。本學(xué)位論文屬于：保

4、密口在年解密后適用本授權(quán)書(shū)。不保密拶（請(qǐng)?jiān)谝陨戏娇騼?nèi)打“丿”）論文作者簽名：王云胡媽導(dǎo)師簽名：伽沙日期：）pJ3年莎月二6日摘要隨著城市規(guī)模的擴(kuò)大及城市功能區(qū)的劃分，企業(yè)員工的職住分離問(wèn)題日益嚴(yán)重，就業(yè)地與居住地的分離使得城市居民的平均通勤時(shí)間和通勤距離不斷增長(zhǎng)，同時(shí)也引發(fā)了大量的交通擁堵問(wèn)題，這一切都使得企業(yè)員工上下班通勤變得異常艱難。在此背景下，企業(yè)通勤班車服務(wù)應(yīng)用而生。通勤班車是城市公共交通的重要組成部分，也是企業(yè)員工上下班的主要通勤方式，但是，許多不合理的通勤班車路線設(shè)計(jì)及班車運(yùn)營(yíng)方式在方便部分出行者的同時(shí)也給城市交通帶來(lái)了一些負(fù)面影響，并在一定程度上影響其他運(yùn)輸方式的運(yùn)營(yíng)?？偠灾?/p>

5、合理的通勤班車路線與站點(diǎn)設(shè)計(jì)不僅對(duì)企業(yè)員工的滿意度有著積極地影響，而且還會(huì)對(duì)城市交通產(chǎn)生積極的協(xié)調(diào)補(bǔ)充作用。本文在分析影響班車服務(wù)質(zhì)量與服務(wù)成本因素的基礎(chǔ)上，將時(shí)間成本引入通勤班車線路設(shè)計(jì)，旨在探求通勤班車更好的服務(wù)模式。文章首先給出了通勤班車線路設(shè)計(jì)的研究背景，分析了通勤班車線路設(shè)計(jì)對(duì)于城市交通以及居民出行的理論意義及實(shí)際價(jià)值；其次，對(duì)國(guó)內(nèi)外的相關(guān)文獻(xiàn)進(jìn)行了剖析，闡述了國(guó)內(nèi)外對(duì)于通勤班車研究的相關(guān)內(nèi)容，并且對(duì)通勤班車線路設(shè)計(jì)的相關(guān)算法進(jìn)行了總結(jié)；隨后，設(shè)計(jì)了通勤班車線路優(yōu)化模型，在這個(gè)過(guò)程中引入了時(shí)間成本的概念，更好地反映通勤班車的運(yùn)營(yíng)服務(wù)質(zhì)量，而后運(yùn)用蟻群算法進(jìn)行模型的求解；最后，選取大連

6、市某企業(yè)進(jìn)行實(shí)例分析，通過(guò)實(shí)際調(diào)查取得企業(yè)員工通勤相關(guān)數(shù)據(jù)，帶入模型求解班車通勤線路。在這之后對(duì)本文進(jìn)行總結(jié)提出本文的結(jié)論以及今后對(duì)于通勤班車線路設(shè)計(jì)的研究方向。文章的研究對(duì)于通勤班車系統(tǒng)理論的豐富和發(fā)展具有一定的貢獻(xiàn)。關(guān)鍵詞：通勤班車線路優(yōu)化，蟻群算法，時(shí)間成本英文摘要AbstractWiththedevelopmentbigcities，theofthesocietyandtheexpansionofseparationofworkplaceandresidenceforcitizensisbecomingsevereandattracts10tofattentionsThissituat

7、ioncausenotonlymakeserioustrafficproblem，butalsocitizenStravelfromhome，toworkplacealotinconvenienceInordertosolvingthisproblemandprovideconvenientservicestotheworkingcitizens，ofalotcompanieshaveworkedonshuttlebusesservicefortheirstaffTechnically,shuttlebusisapartinofpublictransportation,justlikebus，

8、itplaysanimportantroleacityStraffic，andforthosewhotakeshuttlebustoworkeveryday,shuttlebusisanirreplaceablemodeofthecomparedwiththebusmodeHowever,sometimesunreasonablemanagementshuttlebusserviceCallbringnegativeeffecttothetrafficandthereforeaffectsalottoitsservicelevelotherandautomobilesoperationSoin

9、conclusion，appropriateshuttlebusmanagementandroutingCannotonlysatisfythecustomer,butalsogivepositiveeffecttothetraffictheofBasedonthepaststudy,thispaperisworkingonhowtosolveproblemroutinginshuttlebusservice，andinthisprocess，weputtimevalueinthemodelinweordertogetabalancebetweenshuttlebusserviceandcor

10、poratecostAndthenusetheAntcolonyalgorithmtosolvethismodelAtthelastpart，weprovideanexamplemodeltoturnsoutofacompanyinDalianprovethistheory,anditthisisprettyeffectiveandcangetagoodresultforKeywords：Routingoptimizationshuttlebus，timecost，ant-algorism目目錄TOC o 1-5 h z HYPERLINK l bookmark8 摘要1第1章11研究背景12

11、通勤班路研究的理意及價(jià)12.1通勤班的極作用及消極影響12.2研究通勤班路與化的意一31-3通勤班路化描述41.3.1路徑定43.2路徑分5 HYPERLINK l bookmark24 4文章的構(gòu)及技路6 HYPERLINK l bookmark26 第2章國(guó)內(nèi)外研究述81國(guó)內(nèi)外于班路化研究狀81.1國(guó)外研究狀81.2國(guó)內(nèi)研究狀8 HYPERLINK l bookmark38 2國(guó)內(nèi)外于路徑相關(guān)算法研究102.1精確算法102.2.2啟式算法132.3仿生化算法16第3章班路化模型的建立171通勤班路與化的提出172通勤班路化目17 HYPERLINK l bookmark64 3模型建立1

12、83.1班路化基本模型18 HYPERLINK l bookmark82 3.2引入成本后的模型化20第4章群算法求解班路化22 HYPERLINK l bookmark100 1基本群算法概述221.1群算法描述2324412群算法研究狀TOC o 1-5 h z2群算法原理.:253群算法在通勤班路化中的用273.1描述274.3.2改群算法求解通勤班路274.3.3新站點(diǎn)的引入及站點(diǎn)合并29第5章例分析3151A公司介31 HYPERLINK l bookmark114 52A公司通勤班路徑化模型求解333果分析39第6章與未來(lái)展望406.1文章-40 HYPERLINK l bookm

13、ark124 2文章存在的不足及未來(lái)研究方向展望-40 HYPERLINK l bookmark126 參考文獻(xiàn)-4245第1章緒論第1章緒論企業(yè)通勤班車線路優(yōu)化研究1第1章緒論11研究背景隨著社會(huì)經(jīng)濟(jì)的發(fā)展，城市規(guī)劃與城市交通劃分的完善，城市道路擁堵問(wèn)題日趨嚴(yán)重，在這樣的背景下，企業(yè)員工上班不僅面臨著因道路擁堵問(wèn)題而產(chǎn)生的遲到風(fēng)險(xiǎn)，而且其上班的成本也會(huì)顯著地增加。針對(duì)這種情況，企業(yè)通勤班車服務(wù)應(yīng)用而生。通勤班車定義為；企事業(yè)單位為滿足本單位員工上下班的通勤需求，在綜合考慮他們的上下車地點(diǎn)后，由所在單位負(fù)責(zé)開(kāi)行多條線路的班車。每一條通勤班車線路都具有定時(shí)、定點(diǎn)、定線、定班的特點(diǎn)，最大程度上滿足

14、員工的通勤出行的需求。通勤班車屬于輔助公共交通系統(tǒng)，是城市公共交通方式的重要組成部分。在以前的城市交通規(guī)劃編制過(guò)程中，通勤班車一般被納入其他類出行方式，或納入單位車(單位車包括通勤班車和單位小汽車)做比較，通勤班車自身并不獨(dú)立出來(lái)分析，通常處于被忽視的地位。近幾年來(lái)，由于城市規(guī)模的擴(kuò)大，職住分離問(wèn)題的日益突出，通勤班車、單位小汽車在城市中的數(shù)量的急劇增加，與此同時(shí)，乘客選擇通勤班車其出行比例也隨之提高，部分城市和地區(qū)在制定相應(yīng)規(guī)劃方案和管理對(duì)策的時(shí)候，也會(huì)將通勤班車和單位小汽車在居民出行方式調(diào)查中單獨(dú)列出，但在隨之而來(lái)的規(guī)劃編制中卻大都并未深入分析。另外，“通勤班車”的種類多種多樣，包括大客車

15、、廠車、通勤客車、單位交通車等，但實(shí)際上屬于同一出行方式，本文統(tǒng)一將此類運(yùn)輸方式命名為“通勤班車”12通勤班車線路研究的理論意義及實(shí)際價(jià)值121通勤班車的積極作用及消極影響(1)通勤班車的積極作用企事業(yè)單位所開(kāi)通的通勤班車一般會(huì)有多條線路，為居住在不同區(qū)位的員工提供通勤服務(wù)，同時(shí)，通勤班車線路還具有定點(diǎn)、定時(shí)、定線、定班的特點(diǎn)，這在一定程度上提高了企事業(yè)單位員工的出行效率以及居民公共交通的出行比例。隨著社會(huì)的發(fā)展，城市化規(guī)模的擴(kuò)大以及城市功能區(qū)劃分的完善，城市居民的職住分離問(wèn)題愈發(fā)嚴(yán)重，隨之而來(lái)的通勤班車出行比率也在逐漸提高。通勤班車是城市公共交通優(yōu)先戰(zhàn)略的積極補(bǔ)充，對(duì)城市交通有著不可忽視的影

16、響。公共交通優(yōu)先的對(duì)象主要包括大容量的公共交通，公共汽(電)車交通以及軌道交通，近年來(lái)，通勤班車在很多城市的出行分擔(dān)比例逐步提高，這在一定程度上豐富了城市公共交通的出行方式，同時(shí)也提高了輔助公共交通在城市公共交通系統(tǒng)中的地位和作用。因此，通勤班車逐步被納入公共交通優(yōu)先行駛對(duì)象，在政策優(yōu)惠、城市規(guī)劃、道路交通等方面獲得了支持。通勤班車屬于集約化運(yùn)輸模式，它能以較少的空間資源提供較大的有效運(yùn)輸效率以及能源利用率。目前，大部分通勤班車都采用大型客車，額定載客量三十到五十人不等，通勤班車與常規(guī)公交服務(wù)類似，是一種運(yùn)輸能力強(qiáng)、運(yùn)輸效率高、交通資源利用率高的運(yùn)輸方式，其在相同的能源和空間消耗下，能夠提供比

17、小汽車等交通方式更大的運(yùn)輸能力以及運(yùn)輸效率。通常情況下，一輛普通通勤班車其運(yùn)輸能力相當(dāng)于小汽車的二十倍，而相比之下，要完成相同的運(yùn)輸量，小汽車所占用的道路資源則是公共汽車的4倍。并且，通勤班車相比于個(gè)體交通方式而言，屬于一種大眾化的交通運(yùn)輸方式，其通過(guò)這種方式為大眾不同的交通需求提供多樣化的交通運(yùn)輸服務(wù)。通勤班車不僅可以再很大程度上提高道路利用率，而且還能節(jié)省大量的能源。從能源消耗來(lái)看，計(jì)算每百公里的人均能耗，通勤班車只有小汽車能耗的84；從環(huán)境污染的角度來(lái)看，計(jì)算單位客運(yùn)量，通勤班車要比小汽車低90左右。通勤班車相對(duì)于其他運(yùn)輸方式來(lái)說(shuō)更加方便、更加省時(shí)，而且在很大程度上提高了員工出行效率。隨

18、著越來(lái)越多的企事業(yè)單位員工選擇乘坐通勤班車上下班，許多班車的接送站點(diǎn)能直接深入社區(qū)小區(qū)，居民從出發(fā)點(diǎn)到班車站點(diǎn)并不需長(zhǎng)時(shí)間便可到達(dá)。因此，與公交運(yùn)輸方式相比，通勤班車服務(wù)區(qū)域更加有針對(duì)性也更加合理，因此也更加方便企事業(yè)單位員工的通勤出行。(2)通勤班車對(duì)城市的消極影響近年來(lái)，許多企事業(yè)單位開(kāi)設(shè)了通勤班車，深受員工們歡迎。通勤班車在一定程度上方便了員工，但讓他們更方便、更省時(shí)的同時(shí)，也給城市道路交通帶來(lái)了很多不利影響。首先，由于沒(méi)有缺乏合理的交通管制制度，很多城市通勤班車亂停亂放的現(xiàn)2企業(yè)通勤班車線路優(yōu)化研究企業(yè)通勤班車線路優(yōu)化研究象較為普遍，這不僅會(huì)影響其他車輛運(yùn)營(yíng)，還會(huì)妨礙城市交通的正常運(yùn)行

19、。目前很多通勤班車其班車站點(diǎn)標(biāo)志不清晰，缺少規(guī)范的停車站牌。有的通勤班車選擇將班車站牌懸掛于路燈上，而更多的通勤班車則挺車站牌都沒(méi)有，只是對(duì)某一地點(diǎn)進(jìn)行描述便作為停車站點(diǎn)；即使企事業(yè)單位為通勤班車設(shè)計(jì)了站點(diǎn)和站牌，班車也常常為了貪圖方便利用常規(guī)公交站點(diǎn)、出租車臨時(shí)停車點(diǎn)作為其班車站點(diǎn)，這種現(xiàn)象會(huì)在很大程度上影響常規(guī)公交、出租車的正常進(jìn)出站與?？?。在道路資源相對(duì)緊張的路段通勤班車亂停亂放的現(xiàn)象最為明顯，其不合理的?？糠绞酵ǔ?huì)使常規(guī)公交站點(diǎn)停靠車輛過(guò)多，因此導(dǎo)致其他車輛無(wú)法正常運(yùn)行，進(jìn)而更容易引起道路擁堵，影響城市交通的正常運(yùn)營(yíng)。其次，很多通勤班車車況較差，安全隱患大。目前，大部分企事業(yè)單位通常

20、會(huì)將通勤班車服務(wù)外包給租賃公司、旅游公司或公交企業(yè)，而這些公司由于缺乏統(tǒng)一的規(guī)范標(biāo)準(zhǔn)，其所使用的客車狀況良莠不齊，有的班車車況較差、尾氣排放不達(dá)標(biāo)且存在一定的安全問(wèn)題，這都給交通與環(huán)境帶來(lái)了負(fù)面影響。更有甚者，某些車輛由于年代久遠(yuǎn)或平時(shí)疏于維護(hù)，故障較多，拋錨現(xiàn)象時(shí)有發(fā)生，這種事故一旦發(fā)生，通常會(huì)造成嚴(yán)重的道路堵塞以及交通事故。最后，針對(duì)通勤班車的交通規(guī)劃編制與管理體系還有所欠缺。目前，許多城市的政府職能部門對(duì)通勤班車得運(yùn)營(yíng)缺乏相應(yīng)的規(guī)劃設(shè)計(jì)、管理控制及扶持帶動(dòng)，也沒(méi)有對(duì)通勤班車的管理制訂相應(yīng)的法律法規(guī)條文，使得通勤班車處于一種放任自流狀態(tài)。122研究通勤班車線路設(shè)計(jì)與優(yōu)化的意義綜上所述，通勤

21、班車作為公共交通的重要組成部分，補(bǔ)充了城市交通的一部分空白，在城市交通以及企業(yè)員工的工作出行擁有不可替代的作用；而與此同時(shí)，不合理的通勤班車路線設(shè)計(jì)及運(yùn)營(yíng)方式在方便部分人群的同時(shí)也對(duì)城市交通造成了一些負(fù)面的影響，使得城市交通更加地復(fù)雜多變，同時(shí)會(huì)在一定程度上影響其他運(yùn)輸方式的運(yùn)營(yíng)。因此，合理的通勤班車路線設(shè)計(jì)與運(yùn)營(yíng)不僅對(duì)相關(guān)企業(yè)的員工滿意度，班車運(yùn)營(yíng)成本，企業(yè)形象等問(wèn)題產(chǎn)生巨大的影響，同時(shí)還會(huì)從側(cè)面對(duì)城市交通產(chǎn)生積極的協(xié)調(diào)補(bǔ)充作用。第1章緒論第1章緒論13通勤班車線路優(yōu)化問(wèn)題描述通勤班車路徑選擇與優(yōu)化問(wèn)題可歸類為車輛路徑問(wèn)題(VehicleRoutingProblem,VRP)，其實(shí)質(zhì)是在滿足

22、企業(yè)內(nèi)部員工上下班通勤需求的前提下，盡力減少企業(yè)開(kāi)設(shè)通勤班車服務(wù)的成本，具體表現(xiàn)在使用最少的班車，選擇最短的通勤路徑滿足企業(yè)內(nèi)部員工的需求。131車輛路徑問(wèn)題定義車輛路徑問(wèn)題(vehicleroutingproblem，VRP)屬于物流調(diào)度問(wèn)題的一種，它是運(yùn)籌學(xué)中的一個(gè)經(jīng)典問(wèn)題，也是一個(gè)典型的NP-hard問(wèn)題。車輛路徑問(wèn)題最早由Dantzing和Ramser于1959年提出，當(dāng)時(shí)解決了如何將汽油送往分布于不同位置的加油站的實(shí)際問(wèn)題。隨后，車輛路徑問(wèn)題在交通領(lǐng)域獲得了快速的發(fā)展，上世紀(jì)90年代以來(lái)，人工智能算法在解決車輛路徑問(wèn)題上顯出了非常強(qiáng)大的功能，隨后很多學(xué)者在此基礎(chǔ)上構(gòu)造了大量的啟發(fā)式算

23、法。時(shí)至今日，關(guān)于車輛路徑問(wèn)題的研究依然對(duì)交通運(yùn)輸、物流配送及其他相關(guān)領(lǐng)域產(chǎn)生著巨大的影響。VRP問(wèn)題可以描述為：配送中心組織車隊(duì)給一定數(shù)量的客戶配送貨物，每個(gè)客戶的需求不同，要求車隊(duì)選擇合適的行車線路，選擇各自的配送目標(biāo)，在滿足客戶需求的前提下，達(dá)到使用配送車輛數(shù)最少，車隊(duì)總行車路程最短，總配送時(shí)間最少，總消耗成本最少等目標(biāo)。具體情況如下圖所示，參見(jiàn)圖11：中心點(diǎn)0用來(lái)表示配送中心，1一lO節(jié)點(diǎn)用來(lái)表示需要配送的客戶，箭頭則表示車輛行駛的路徑與方向。第1章緒論第1章緒論根據(jù)約束條件的種類，可以將VRP問(wèn)題劃分為帶容量限制的VRP問(wèn)題(CVRP)、帶距離約束的VRP問(wèn)題(DVRP)以及帶有時(shí)間

24、窗的VRP問(wèn)題(VRPTW)等；根據(jù)車輛載貨的情況，可以將VRP問(wèn)題劃分為滿載車VI沖問(wèn)題和非滿載VRP問(wèn)題；根據(jù)配送中心的數(shù)量的多少，可以將VRP問(wèn)題劃分為單車場(chǎng)VRP問(wèn)題(SVRP)和多車場(chǎng)VRP問(wèn)題(MW心)，在這其中；根據(jù)行駛車輛的類型的不同，可以將VI沖問(wèn)題劃分為單車型VRP問(wèn)題和多車型VRP問(wèn)題；根據(jù)優(yōu)化目標(biāo)的數(shù)量的多少，可以將VRP問(wèn)題劃分為單目標(biāo)的VI沖問(wèn)題和多目標(biāo)VRP問(wèn)題；根據(jù)任務(wù)類型的性質(zhì)，可以將VRP問(wèn)題劃分為純裝車VI沖問(wèn)題、純卸車VRP問(wèn)題及裝卸混合VRP問(wèn)題。14文章的結(jié)構(gòu)及技術(shù)路線本文以對(duì)車輛路勁問(wèn)題的研究為基礎(chǔ)，開(kāi)展了針對(duì)通勤城市通勤班車線路設(shè)計(jì)與優(yōu)化的研究，

25、并通過(guò)引入時(shí)間成本的概念進(jìn)一步研究引入新的班車站點(diǎn)以及相鄰站點(diǎn)合并的可能性，而后利用蟻群算法求解模型，獲得較好的一個(gè)通勤班車線路方案，進(jìn)而在滿足乘客乘車需求的前提下提高企業(yè)班車的運(yùn)作效率、提升通勤班車服務(wù)質(zhì)量。圖12為本文的技術(shù)路線圖。第2章國(guó)內(nèi)外研究綜述第2章國(guó)內(nèi)外研究綜述企業(yè)通勤班車線路優(yōu)化研究7圖12文章技術(shù)路線圖TherouteoftheFig12techniquepaper第2章國(guó)內(nèi)外研究綜述21國(guó)內(nèi)外對(duì)于班車線路優(yōu)化問(wèn)題研究現(xiàn)狀211國(guó)外研究現(xiàn)狀相比國(guó)內(nèi)來(lái)說(shuō)，國(guó)外對(duì)于通勤班車問(wèn)題研究較早，對(duì)于其相關(guān)的車輛路徑問(wèn)題也有較多的涉獵。其中具有代表性的有：Seliaman在其2001年的研

26、究“AsimulationmodelfortheshuttlebustrafficduringNafrahperiod”提出了如何利用仿真的方法來(lái)確定通勤班車的行車線路及停車站點(diǎn)，文章以一年一度的麥加朝圣為例，指出每年朝圣的這一天都會(huì)有超過(guò)兩百萬(wàn)信徒聚集，這對(duì)當(dāng)?shù)氐慕煌ㄊ且粋€(gè)很大的負(fù)擔(dān)，文章通過(guò)對(duì)實(shí)際數(shù)據(jù)的調(diào)查以及模擬仿真，以平衡各線路的交通流量為主要目標(biāo)，最終得到了一個(gè)相對(duì)均衡的結(jié)果；Kim在2004年發(fā)表的文章“Animprovedbussignalprioritysystemfornetworkswithnearsidebusstops中扌疋出女d何采用交通信號(hào)戰(zhàn)略在復(fù)雜的交通條件下提高

27、班車的運(yùn)輸效率，文章指出，在之前的研究中對(duì)于BusSignalPriority(BSP)問(wèn)題的研究中很少考慮班車掛靠站點(diǎn)的時(shí)間，導(dǎo)致站點(diǎn)附近信號(hào)燈調(diào)節(jié)不能夠有效地方便班車的運(yùn)行，而文章則首先預(yù)測(cè)了班車到站時(shí)刻，而后通過(guò)預(yù)測(cè)的數(shù)據(jù)實(shí)時(shí)地去調(diào)節(jié)站點(diǎn)附近的信號(hào)燈，以達(dá)到有效促進(jìn)班車運(yùn)營(yíng)的目的；Baker在2008年的研究“AnevaluationofvisitordecisionsregardingalternativetransportationinGlacierNationalPark以及Wadsworth在隨后的研究“Shuttletoserenity：thehistoryandimpacto

28、fZionNationalparkstransportationsystem”中共同探索了免費(fèi)班車服務(wù)是如何影響人們的出行行為的，文章以美國(guó)國(guó)家冰川公園為例，通過(guò)對(duì)2007年國(guó)家冰川公園開(kāi)通免費(fèi)班車后游客的游覽行為研究，指出免費(fèi)班車行駛線路以及停車點(diǎn)很大程度上影響了公園各個(gè)區(qū)域的游客數(shù)量；這些研究從各個(gè)方面探索了班車服務(wù)在城市交通中的重要性以及如何合理運(yùn)營(yíng)通勤班車及設(shè)計(jì)班車路線以提升通勤班車的服務(wù)效率。212國(guó)內(nèi)研究現(xiàn)狀相比國(guó)外對(duì)于通勤班車的相關(guān)研究，我國(guó)對(duì)于班車運(yùn)輸服務(wù)的研究相對(duì)落8企業(yè)通勤班車線路優(yōu)化研究后，且研究水平與研究深度都比較低，對(duì)于班車運(yùn)輸服務(wù)所屬的VRP問(wèn)題的研究也是從上世紀(jì)9

29、0年代以后才逐漸興起和發(fā)展。而隨著經(jīng)濟(jì)的發(fā)展以及社會(huì)的進(jìn)步，城市交通擁堵問(wèn)題愈發(fā)嚴(yán)重，交通問(wèn)題也越來(lái)越引發(fā)人們的關(guān)注。在這樣的背景下，我國(guó)對(duì)于車輛路徑問(wèn)題的研究逐漸發(fā)展和興起，關(guān)于解決車輛路徑問(wèn)題的算法也取得了許多較為顯著的成果，但是，從總體方面來(lái)看，我國(guó)對(duì)于車輛路徑問(wèn)題的研究與國(guó)外相比還有很大的差距，還需要不斷地提高。車輛優(yōu)化調(diào)度是我國(guó)在VRP研究領(lǐng)域的首部著作，由郭耀煌于上世紀(jì)90年代編寫(xiě)，主要講述VRP問(wèn)題的基本理論與解決VRP伺題的一些方法。隨后，李軍、李大衛(wèi)等人則在在求解物流配送問(wèn)題的時(shí)候使用了遺傳算法；劉浩等學(xué)者將模擬退火算法引入了VRP問(wèn)題的求解；蔡延光等學(xué)者則在研究車輛滿載問(wèn)題

30、過(guò)程中使用了禁忌搜索算法以及模擬退火算法相結(jié)合進(jìn)行求解；李寧等學(xué)者在隨后提出了針對(duì)車輛路徑問(wèn)題的粒子群算法；張濤等學(xué)者則使用了遺傳算法及禁忌搜索算法想結(jié)合的方法求解車輛路徑問(wèn)題；袁鍵等學(xué)者則在解決車輛路徑問(wèn)題的時(shí)候構(gòu)建了神經(jīng)網(wǎng)絡(luò)模型；方霞等學(xué)者則提出了一種全新的啟發(fā)式算法，通過(guò)使用免疫遺傳算法求解了車輛路徑問(wèn)題：王莉針對(duì)有時(shí)間窗限制的車輛路徑問(wèn)題提出了獨(dú)特的啟發(fā)式算法；郭耀煌等學(xué)者則對(duì)物流配送問(wèn)題中的車輛路徑優(yōu)化問(wèn)題進(jìn)行了仔細(xì)深入的研究，并同時(shí)提出了多種求解這種問(wèn)題的算法；張建勇等學(xué)者在研究多目標(biāo)車輛優(yōu)化調(diào)度問(wèn)題的同時(shí)通過(guò)引入模糊預(yù)約時(shí)間的概念考慮了顧客滿意度的問(wèn)題。近年來(lái)，關(guān)于VRP問(wèn)題的研

31、究則更是如雨后春筍般發(fā)展起來(lái)。但盡管如此，我國(guó)對(duì)于VI心問(wèn)題的研究仍然處于起步階段，對(duì)于通勤班車路徑優(yōu)化問(wèn)題的研究更是遠(yuǎn)遠(yuǎn)未達(dá)到成熟的水平綜合來(lái)看，我國(guó)對(duì)于車輛路徑優(yōu)化問(wèn)題的研究有如下特點(diǎn)：國(guó)內(nèi)所研究的車輛路徑問(wèn)題的研究多為確定性問(wèn)題，確定的配送中心，確定的配送點(diǎn)，確定的配送需求，即使有關(guān)于不確定性問(wèn)題的研究，也與實(shí)際問(wèn)題有一定的差距。國(guó)內(nèi)關(guān)于車輛路徑問(wèn)題的研究雖然不少，但是缺乏統(tǒng)一的規(guī)范，尤其是對(duì)于一些專有名詞的定義更是五花八門，這在車輛路徑問(wèn)題的研究領(lǐng)域產(chǎn)生了不好的影響，對(duì)于后學(xué)者更是有一定的誤導(dǎo)作用國(guó)內(nèi)研究車輛路徑問(wèn)題的研究群體較少，大部分為高校的科研工作者，這個(gè)現(xiàn)象雖然在近年來(lái)有所改觀

32、，但是就車輛路徑問(wèn)題的研究理論和實(shí)際應(yīng)用來(lái)q第2章國(guó)內(nèi)外研究綜述第2章國(guó)內(nèi)外研究綜述說(shuō)，還遠(yuǎn)不能滿足需求。22國(guó)內(nèi)外對(duì)于車輛路徑問(wèn)題相關(guān)算法研究求解車輛路徑問(wèn)題的算法大致可以歸納為三類：精確算法、啟發(fā)式算法以及仿生優(yōu)化算法。其中，精確算法立足于較為嚴(yán)格的數(shù)學(xué)方法，在模型可以求解的前提下，其求得的結(jié)果大都質(zhì)量較好。但是同時(shí)，精確算法也有自身的一些不足之處，比如由于精確算法本身算法嚴(yán)格，運(yùn)算量也一般較大，用其來(lái)解決規(guī)模較大的車輛路徑問(wèn)題并不可行，也由于這個(gè)原因，精確算法經(jīng)常用來(lái)解決規(guī)模較小的車輛路徑問(wèn)題；啟發(fā)式算法是解決車輛路徑問(wèn)題常用的方法，相比精確算法來(lái)說(shuō)，啟發(fā)式算法并不精確，但由于其本身的特

33、質(zhì)，能夠使大規(guī)模的車輛路徑問(wèn)題快速收斂到一個(gè)相對(duì)較優(yōu)的解，并且這樣的解一般也在可以接受的程度，在實(shí)際應(yīng)用上，啟發(fā)式算法則要比精確算法應(yīng)用更為廣泛；仿生優(yōu)化算法是近幾年來(lái)發(fā)展迅速的一種算法，其廣泛用于解決組合優(yōu)化問(wèn)題，而且相對(duì)于其他的算法來(lái)說(shuō)，在求解模型時(shí)具有自身獨(dú)特的優(yōu)勢(shì)。221精確算法精確算法主要包含K度中心樹(shù)算法、分支定界算法、動(dòng)態(tài)規(guī)劃法、列生成和集分割法、二下標(biāo)車輛流方程以及三下標(biāo)車輛流方程等。K度中心樹(shù)算法K度中心樹(shù)算法是由Christofides等人提出的一種求解車輛路徑問(wèn)題的精確算法3。其核心內(nèi)容是求解K度中心樹(shù)，通過(guò)消去約束條件來(lái)將問(wèn)題化為子問(wèn)題求解。該算法是求解車輛路徑問(wèn)題所常

34、用的精確算法動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法是由Eilon等人提出的一種解決車輛路徑問(wèn)題的精確算法【6】。該方法主要針對(duì)求解小心規(guī)模的且車輛數(shù)固定的車輛路徑問(wèn)題，它將車輛路徑問(wèn)題視為一個(gè)多階段的決策問(wèn)題通過(guò)遞歸的方法求解，以縮小需要計(jì)算的規(guī)模，最終轉(zhuǎn)換為依次求解多個(gè)具有遞推關(guān)系的單階段決策問(wèn)題。在這之后，Cllristofides則利用空間狀態(tài)松弛的方法在很大程度上減少了模型狀態(tài)數(shù)7。使用該方法求解車企業(yè)通勤班車線路優(yōu)化研究輛路徑問(wèn)題的前提條件是：擁有易于求出模型解的轉(zhuǎn)換函數(shù)以及較小的映射范10圍，以此能夠求出滿意的下界。分支定界算法分支定界法屬于隱枚舉法的一種，最初是fljLaporte等人提出的4】。

35、將問(wèn)題持續(xù)地將目標(biāo)問(wèn)題分為相關(guān)的子問(wèn)題，直到得到最終解為止。但遺憾的是，這種方法只能用于求解規(guī)模較小的車輛路徑問(wèn)題。列生成和集分割與其他精確算法相比，列生成和集分割算法的原理是最開(kāi)始先確定一個(gè)可行解，而隨后再針對(duì)這個(gè)可行解進(jìn)行進(jìn)一步的優(yōu)化。但是，這種算法存在著不可忽略的缺陷，那就是由于列生成和集分割算法的原理使得那些約束條件不夠嚴(yán)格的車輛路徑問(wèn)題問(wèn)題產(chǎn)生相當(dāng)大的解空間，這使得計(jì)算頗為困難。此外，使用這種方法的時(shí)候要確定可行解的最小成本比較困難。而對(duì)于規(guī)模較小并且具有嚴(yán)格約束的車輛路徑問(wèn)題來(lái)說(shuō)，則可以通過(guò)進(jìn)行線性的松弛處理以及引入割平面的來(lái)求解。隨后，Rao等人采用了列生成方法簡(jiǎn)化此問(wèn)題，它的原

36、理是將考慮的范圍從可行解的集合縮小到范圍較小的可行解子集，隨后在該子集上重復(fù)進(jìn)行求解，最后引入其對(duì)偶問(wèn)題的變量向量，對(duì)簡(jiǎn)化了的問(wèn)題進(jìn)行松弛處理，再通過(guò)來(lái)計(jì)算每一個(gè)列的邊際成本的最小值確定問(wèn)題的最優(yōu)解8】。此算法的核心思想是最短路徑法，它還同時(shí)結(jié)合了分支定界法的基本思路。Desrocher曾使用該算法，解決了擁有100個(gè)客戶的帶時(shí)間窗的車輛路徑問(wèn)題9】。f5)-下標(biāo)車輛流方程Fisher等人提出的三下標(biāo)車輛流方程是用于解決帶能力約束、時(shí)間窗口以及沒(méi)有可以停留時(shí)間的車輛路徑問(wèn)題10】。在這個(gè)算法中設(shè)定有三個(gè)下標(biāo)，兩個(gè)下標(biāo)分別表示邊和弧，剩下的一個(gè)下標(biāo)則用來(lái)表示車輛的序號(hào)。三下標(biāo)車輛流方程的核心基于

37、Benders等人所提出的分解方法，它用啟發(fā)式算法使得算法在一定的步驟內(nèi)找到了最優(yōu)解。在這之后，Martellol1和Desrochers12等人則對(duì)三下標(biāo)車輛流算法進(jìn)行了改進(jìn)。(6)-下標(biāo)車輛流方程二小標(biāo)車輛流方程相比三下標(biāo)車輛流方程來(lái)說(shuō)少了車輛序號(hào)的下標(biāo)，它由Laporte4等人在求解對(duì)稱車輛路徑問(wèn)題的時(shí)候提出。其原理基于線性規(guī)劃，通過(guò)最少車輛數(shù)，使得方程更為緊湊下面把求解VRP的精確算法及其適用范圍列在表2.1中1】第2章國(guó)內(nèi)外研究綜述第2章國(guó)內(nèi)外研究綜述表2.1求解VRP的精確算法及其適用范圍Tab21VRPandtheiralgorismapplicationscope精確算法適應(yīng)范

38、圍給定下界和相關(guān)的分支定該算法是從所訪問(wèn)的點(diǎn)的角度出發(fā)建立的，不能用于解決對(duì)稱界算法VRP，可以解決不對(duì)稱VRP模型中有具有時(shí)間窗的變量，并可用于解決通用的任務(wù)分配問(wèn)三下標(biāo)車輛流方程題(GAP)和具有時(shí)間窗限制的TSP(TSPTW)二下標(biāo)車輛流方程是通過(guò)對(duì)TSP的SYM方程的擴(kuò)展而得來(lái)。車輛序號(hào)的下標(biāo)被刪除，方程比較緊湊，且約束條件也相對(duì)較二下標(biāo)車輛流方程少，所以可以用于解決對(duì)稱的CVRP和DVRP，而且特別適用于這兩種VRP中約束條件比較寬松的問(wèn)題。k度中心樹(shù)算法這三種算法在對(duì)應(yīng)的模型中，給出了不同形式的能力約束及子動(dòng)態(tài)規(guī)劃法回路約束等條件，適用于約束條件相對(duì)較為嚴(yán)格的模型。集分割和列生成綜

39、上所述，精確算法的特點(diǎn)便是擁有嚴(yán)格的數(shù)學(xué)手段，也正因?yàn)槿绱?，在模型較小且可以求解的情況下，精確算法所求出的解通常要優(yōu)于啟發(fā)式算法所求出的解，這也是該算法得以廣泛的應(yīng)用于商業(yè)軟件的原因。但同時(shí)引入嚴(yán)格的數(shù)學(xué)方法也帶來(lái)了明顯的缺陷，它無(wú)法避開(kāi)指數(shù)爆炸問(wèn)題，因此該類算法只能應(yīng)用于求解中小規(guī)模的確定性VRP。具體到算法本身，精確算法中每一種算法都有各自特定的特點(diǎn)以及適用范圍。給定下界的分枝定界算法是從所要訪問(wèn)的點(diǎn)的角度出發(fā)而建立的一種精確算法，它不僅可以用來(lái)求解對(duì)稱車輛路徑問(wèn)題，還可以用來(lái)求解非對(duì)稱的車輛路徑問(wèn)題；三下標(biāo)車輛流方程則在模型中引入了時(shí)間窗的相關(guān)變量，因此可用來(lái)解決通用任務(wù)分配問(wèn)題(GAP

40、)以及帶時(shí)間窗的旅行商問(wèn)題(TSPTW)；二下標(biāo)車輛流方程是由于去掉了代表車輛序號(hào)的下標(biāo)，從形式上來(lái)看較三下標(biāo)車輛流方程更為緊湊，其約束條件也相對(duì)較少，從適用范圍來(lái)講僅能適用于對(duì)稱的DVRP和CVRP，而且如果這兩種問(wèn)題的約束條件比較寬松，實(shí)用二下標(biāo)的車輛流問(wèn)題更加方便。而動(dòng)態(tài)規(guī)劃、集分割、k度中心樹(shù)等方法也都適用于約束條件嚴(yán)格的問(wèn)題。當(dāng)前，精確算法領(lǐng)域內(nèi)幾乎己沒(méi)有改進(jìn)的空間，真正能夠長(zhǎng)足發(fā)展且具有研究意義的是接下來(lái)所介紹的啟發(fā)式算法。企業(yè)通勤班車線路優(yōu)化研究222啟發(fā)式算法近年來(lái)，啟發(fā)式算法在求解VRP問(wèn)題時(shí)得到了廣泛的發(fā)展與應(yīng)用，啟發(fā)式算法一般與其所求解的問(wèn)題密切相連，且一般都來(lái)自于生活經(jīng)

41、驗(yàn)，在很多的問(wèn)題中，使用啟發(fā)式算法能夠得到意想不到的效果，即使得不到最優(yōu)的結(jié)果，也一般都在可以接受的范圍內(nèi)，且與精確算法相比，啟發(fā)式算法在求解大規(guī)模車輛路徑問(wèn)題的時(shí)候，可以在相對(duì)較短的時(shí)間內(nèi)，獲得一個(gè)滿意解，不僅如此，啟發(fā)式算法應(yīng)用范圍較廣，由于其基于現(xiàn)實(shí)的特性，啟發(fā)式算法能夠解決許多精確算法無(wú)法解決的問(wèn)題。啟發(fā)式算法在求解車輛路徑問(wèn)題的過(guò)程中，能夠在很大程度上減少模型的計(jì)算時(shí)間以及復(fù)雜度，使復(fù)雜的問(wèn)題變得簡(jiǎn)單。啟發(fā)式算法主要包括：掃描法、遺傳算法，節(jié)約法，禁忌搜索算法以及模擬退火算法等等。節(jié)約法節(jié)約法是flaClarke和Wright于1964年提出來(lái)的解決車輛路徑問(wèn)題的一種方法，這種方法主

42、要用來(lái)解決模型車輛的數(shù)量不確定的車輛路徑問(wèn)題，屬于構(gòu)造算法13】。節(jié)約法的基本思想是：車輛路徑的安排按節(jié)約值從大到小構(gòu)造，按這種方法將某一點(diǎn)添加到車輛路線中，直到最后所有的點(diǎn)都被添加到路線中間為止。節(jié)約法從創(chuàng)立之初就被廣泛應(yīng)用于解決車輛路徑問(wèn)題，而之后Paessens等學(xué)者又將節(jié)約法做了進(jìn)一步的擴(kuò)展，大大增加了節(jié)約法的適用范圍。Fisher-Jaikum鄱眄階段啟發(fā)式算法Fisher和Jaikumar兩人于1981年提出了一種全新的兩階段算法，通過(guò)分組后調(diào)整線路的順序來(lái)求解車輛路徑問(wèn)題；隨后，Bramel等學(xué)者在此研究基礎(chǔ)上提出先得到模型可行解，然后調(diào)節(jié)節(jié)點(diǎn)的方法，以此來(lái)使最終的解集達(dá)到最優(yōu)。

43、Gillett.Miller掃描法掃描法求解車輛路徑問(wèn)題時(shí)主要是基于平面幾何的相關(guān)知識(shí)，它首先由Gillett和Mille于1974年提出，并在后來(lái)的研究中得到了廣發(fā)的應(yīng)用14。其基本思想是：在平面圖中，將配送中心設(shè)為原點(diǎn)，將所有的客戶節(jié)點(diǎn)在此平面上用坐標(biāo)表示，車輛從配送中心出發(fā)，從角度最小的客戶開(kāi)始，沿一個(gè)方向掃描，直到掃描的節(jié)點(diǎn)超出車輛限制條件為止，以此方法確定車輛行駛線路，直到所有的節(jié)點(diǎn)被訪問(wèn)為止。下圖給出掃描法的圖形描述：第2章國(guó)內(nèi)外研究綜述14圖21由掃描法劃分的區(qū)域dividedthemethodFig21Regionbyscanning最鄰近算法Rosenkrantz和Stear

44、ns于1977年提出最鄰近法，此算法的算法原理是：以配送中心為第一個(gè)節(jié)點(diǎn)，尋找離這個(gè)節(jié)點(diǎn)路徑最短且未被服務(wù)的點(diǎn)作為第一個(gè)配送點(diǎn)，且將此點(diǎn)狀態(tài)設(shè)置為已被服務(wù)，而后以此點(diǎn)為基準(zhǔn)，尋找下一個(gè)離此節(jié)點(diǎn)最近的且并未被服務(wù)的點(diǎn)，以此不斷循環(huán)，直到所有的節(jié)點(diǎn)被服務(wù)完為止。模擬退火算法Metropolis等人于1953年提出了模擬退火算法，它是一種隨機(jī)搜索算法，且其原理基于熱力學(xué)的相關(guān)研究171。隨后，Kirkpatrick-于年將模擬退火算法應(yīng)用于組合優(yōu)化問(wèn)題，它能以一定概率選擇客戶中目標(biāo)函數(shù)值最差的形式。在之后的研究中，Laporte和Teodorovic將此算法應(yīng)用于車輛路徑問(wèn)題，并取得了良好的效果。插

45、入法插入法是在1976年由Mole和Jameson提出的一種將最鄰近法和節(jié)約法結(jié)合起來(lái)的解決車輛路徑問(wèn)題的方法，其方法原理是：依次挑選未服務(wù)的合適節(jié)點(diǎn)，插入車輛路線的最佳位置中，直到所有的節(jié)點(diǎn)都被服務(wù)，這時(shí)候，模型就增加了一條新的初始行車路線。Gendreau禁忌搜索算法企業(yè)通勤班車線路優(yōu)化研究禁忌搜索算法最初是f掃Glover于1986年提出的，它屬于一種全局逐步尋優(yōu)算法，此算法的提出主要是為了避免模型陷入局部最優(yōu)解【15】：隨后，Gendreau等人創(chuàng)造性地將該方法應(yīng)用于車輛路徑問(wèn)題。其主要思想是：首先，構(gòu)造一系列的初始解，而后針對(duì)這些初始解進(jìn)行優(yōu)化。而后Tailand和Barbaroso

46、glu等人對(duì)禁忌搜索算法的研究進(jìn)行了延伸。(8)遺傳算法Holland于1975年提出了遺傳算法，它通過(guò)模擬自然界生物的繁衍方式進(jìn)行個(gè)體間的選擇，交叉，變異操作直接對(duì)解空間進(jìn)行搜索18。隨后，Thangiah于1991年在解決車輛路徑問(wèn)題的時(shí)候首次引入了遺傳算法；李嘉等學(xué)者則將禁忌搜索算法與遺傳算法結(jié)合起來(lái)解決車輛路徑問(wèn)題；張濤等學(xué)者則設(shè)計(jì)了一種專門針對(duì)車輛路徑問(wèn)題的混合算法，此算法對(duì)于求解大規(guī)模的車輛路徑問(wèn)題十分有效。下表提供的是遺傳算法與優(yōu)化問(wèn)題之間的關(guān)系。表22生物遺傳算法與優(yōu)化問(wèn)題對(duì)應(yīng)Tab22Thecorrespondingrelationsoftheandbiologicalgen

47、eticconcepts基因解中每一個(gè)量的特征(如各分量的值)個(gè)體的適應(yīng)度解的目標(biāo)函數(shù)值或所對(duì)應(yīng)的適應(yīng)函數(shù)目標(biāo)函數(shù)值越好的解，被選擇作為下一迭代過(guò)程適者生存的當(dāng)前解的可能性越大遺傳算法的基本思想是：模擬自然界中生物的繁衍規(guī)律，根據(jù)適者生存和優(yōu)勝劣汰的法則，對(duì)某個(gè)初始種群進(jìn)行選擇，交叉及變異的操作，逐步演化，逐步優(yōu)化，最終產(chǎn)生一個(gè)相對(duì)較好的種群，而最優(yōu)解就是在整個(gè)過(guò)程中所出現(xiàn)的最好的個(gè)體。第2章國(guó)內(nèi)外研究綜述第2章國(guó)內(nèi)外研究綜述1616223仿生優(yōu)化算法近年來(lái)，在求解組合優(yōu)化問(wèn)題領(lǐng)域，仿生優(yōu)化算法發(fā)展較為迅速，其中最具代表性的便是蟻群算法。蟻群算法是基于對(duì)螞蟻覓食行為的理解進(jìn)而進(jìn)行現(xiàn)實(shí)模擬的一種

48、仿生優(yōu)化算法，現(xiàn)已廣泛應(yīng)用于求解路徑優(yōu)化等問(wèn)題。蟻群算法是仿生優(yōu)化算法的一種，也屬于人工智能研究領(lǐng)域中的一部分。意大利學(xué)者DorigoM于1991年首次提出蟻群算法，并在之后的研究中得到了廣泛的應(yīng)用與發(fā)展，蟻群算法本質(zhì)上屬于一種較為復(fù)雜的智能系統(tǒng)，它擁有較強(qiáng)的魯棒性，還擁有良好的分布式計(jì)算機(jī)制，而更可貴的是，相比于其他仿生優(yōu)化算法來(lái)說(shuō)更加易于與其他方法結(jié)合。當(dāng)前，蟻群算法已經(jīng)成為人工智能研究領(lǐng)域中的一個(gè)研究熱點(diǎn)。目前蟻群算法的應(yīng)用已經(jīng)滲透到很多領(lǐng)域，并且它從最開(kāi)始的只解決一維靜態(tài)優(yōu)化問(wèn)題發(fā)展到了當(dāng)前能夠解決多維動(dòng)態(tài)的組合優(yōu)化問(wèn)題。蟻群算法的原理是基于對(duì)自然界中螞蟻覓食的行為的理解提出的。研究人

49、員通過(guò)仔細(xì)觀察發(fā)現(xiàn)，蟻群在整個(gè)覓食過(guò)程中，其不同個(gè)體之間是通過(guò)一種稱為“外激素”的螞蟻?zhàn)陨淼膬?nèi)分泌物質(zhì)來(lái)傳遞信息進(jìn)行交流的。具體來(lái)說(shuō)，每一只螞蟻在覓食過(guò)程中，都會(huì)將自身分泌的外激素釋放在自己所經(jīng)過(guò)的路徑上，其他螞蟻則能夠在運(yùn)動(dòng)過(guò)程中敏感地察覺(jué)到這種外激素，并以此指導(dǎo)自己的運(yùn)動(dòng)行為。正因如此，蟻群的集體行為便表現(xiàn)出一種信息正反饋的現(xiàn)象：具體來(lái)說(shuō)就是如果一條路徑上所經(jīng)過(guò)的螞蟻越多，那么后來(lái)的螞蟻選擇該路經(jīng)的概率也就越大。自然界中，蟻群就是通過(guò)這種方式達(dá)到搜索蟻穴與食物之間最短路徑的目的。蟻群算法本身具有正反饋以及分布式計(jì)算的特性。在實(shí)際應(yīng)用中，若能與某種啟發(fā)式算法相結(jié)合，正反饋過(guò)程就會(huì)使得該方法能

50、夠較快地發(fā)現(xiàn)比較好的解：而分布式計(jì)算則使得蟻群算法易于并行實(shí)現(xiàn)與啟發(fā)式算法相結(jié)合，使該方法易于發(fā)現(xiàn)較好解。大量的研究顯示，蟻群算法具有許多其他算法所不具備的優(yōu)良性質(zhì)，能夠方便合理地求解復(fù)雜的組合優(yōu)化問(wèn)題。企業(yè)通勤班車線路優(yōu)化研究第3章班車線路設(shè)計(jì)優(yōu)化模型的建立31通勤班車線路設(shè)計(jì)與優(yōu)化問(wèn)題的提出近年來(lái)，由于城市化的發(fā)展，職住分離問(wèn)題愈發(fā)嚴(yán)重，一方面，大型企業(yè)，尤其是制造型企業(yè)由于當(dāng)?shù)卣咭蛩匾约白陨沓杀究刂频目紤]，將公司選址定于開(kāi)發(fā)區(qū)或者郊區(qū)等離城市較遠(yuǎn)的地域；另一方面，企業(yè)所招聘的員工大多居住于市區(qū)，上下班通勤十分地不便。在這樣的背景下，通勤班車應(yīng)用而生。通勤班車的出現(xiàn)大大緩解了企業(yè)員工由于

51、職住分離問(wèn)題而產(chǎn)生的通勤不便，通勤時(shí)間過(guò)長(zhǎng)，上下班遲到等問(wèn)題，深受員工們的歡迎。但不得不提得是，通勤班車在提供方便服務(wù)的同時(shí)也帶了一些不可忽視的問(wèn)題：首先，不合理的班車線路設(shè)計(jì)，重復(fù)掛靠同一站點(diǎn)，不同班車路段重復(fù)，亂停亂放問(wèn)題較為普遍，這種現(xiàn)象大大降低了通勤班車的服務(wù)效率，在提高了服務(wù)成本的同時(shí)，也給班車運(yùn)營(yíng)管理帶來(lái)了許多麻煩；其次，從大的方面來(lái)講，不合理的班車線路與站點(diǎn)設(shè)計(jì)也會(huì)間接地造成城市交通的擁堵，使得城市交通更加的復(fù)雜多變，甚至?xí)绊懫渌\(yùn)輸方式的運(yùn)營(yíng)。通勤班車線路與站點(diǎn)的設(shè)定不僅影響著班車的服務(wù)效率與成本揉入，而且從一定程度上影響城市交通狀況，因此，通勤班車線路的設(shè)計(jì)與優(yōu)化便顯得尤為

52、重要。32通勤班車線路優(yōu)化目標(biāo)通勤班車線路優(yōu)化問(wèn)題屬于VRP問(wèn)題的一種，主要研究的是如何有效地利用班車在企業(yè)員工上班之前掛靠各站點(diǎn)將員工接到公司，以及下班后將員工送往各站點(diǎn)。由此，通勤班車線路優(yōu)化問(wèn)題可以定義為：已知一組已經(jīng)確定或待確定的停車站點(diǎn)以及各個(gè)站點(diǎn)相應(yīng)的上車人數(shù)，確定合理的班車數(shù)量，在滿足車輛運(yùn)載能力以及時(shí)問(wèn)限制等條件下，合理地分配班車與行車路線，使得班車運(yùn)輸成本與班車的服務(wù)水平到達(dá)均衡。因此，通勤班車線路優(yōu)化的目標(biāo)主要包括兩個(gè)部分：】817第3章班車線路設(shè)計(jì)優(yōu)化模型的建立滿足乘客通勤需求乘客利用班車出行的總時(shí)間可以分為兩部分：乘客從出發(fā)點(diǎn)到班車站點(diǎn)的時(shí)間，以及班車從此站點(diǎn)致目的地的

53、運(yùn)行時(shí)間。其中乘客從出發(fā)點(diǎn)到班車站點(diǎn)時(shí)間的長(zhǎng)短很大程度上決定了通勤班車的服務(wù)水平，本文引入時(shí)間成本的概念，將這部分時(shí)間作為優(yōu)化目標(biāo)的一部分。企業(yè)開(kāi)通通勤班車服務(wù)的成本最小企業(yè)開(kāi)通通勤班車服務(wù)所付出的成本包括兩個(gè)部分：固定成本與可變成本，其中，固定成本包括車輛租賃成本，班車司機(jī)的薪酬；可變成本包括燃油消耗，車輛維修等。要達(dá)到班車服務(wù)的成本最小，就需要盡量減少投入運(yùn)營(yíng)的班車數(shù)量，以及合理安排班車線路使得班車一次服務(wù)的行駛距離最短。33模型建立構(gòu)建通勤班車路線優(yōu)化模型的基本思想是：在一定的條件限制下(時(shí)間限制和車容量限制)，確定每輛車的發(fā)車時(shí)間和行車線路，使得通勤班車的服務(wù)水平(乘客從出發(fā)地到達(dá)班車

54、站點(diǎn)所花費(fèi)時(shí)間)和運(yùn)營(yíng)成本達(dá)到均衡。本文研究的通勤班車線路均為開(kāi)放式線路，即在一次運(yùn)營(yíng)中，所有班車的起點(diǎn)為某一站點(diǎn)，目的地為中心站點(diǎn)，也就是開(kāi)通通勤班車服務(wù)的企業(yè)。同時(shí)，我們假設(shè)班車運(yùn)營(yíng)成本與班車的行駛距離正相關(guān)331班車線路優(yōu)化基本模型綜合考慮以上因素，我們給出通勤班車線路設(shè)計(jì)的基本模型，模型中各個(gè)變量的具體含義表示如下：B表示投入運(yùn)營(yíng)的班車數(shù)量；P表示使用班車服務(wù)的員工數(shù)量；n表示系統(tǒng)中有n個(gè)停車站點(diǎn)；H表示所用通勤班車的最大承載量；D表示企業(yè)站點(diǎn)，也是班車運(yùn)營(yíng)的起始點(diǎn)和終點(diǎn)；o表示第P個(gè)乘客從出發(fā)點(diǎn)到達(dá)班車站點(diǎn)所用的時(shí)間；，表示班車從i站點(diǎn)行駛至IJj站點(diǎn)所用的時(shí)間；企業(yè)通勤班車線路優(yōu)化

55、研究v表示表示將乘客從出發(fā)點(diǎn)到班車站點(diǎn)所花費(fèi)的時(shí)間轉(zhuǎn)化為費(fèi)用的轉(zhuǎn)換系數(shù)：3j!,表示站點(diǎn)i到站桶的距離；G表示為班車單位行駛里程的運(yùn)營(yíng)成本；C2表示每輛班車一年的租賃管理成本；正表示班車一次運(yùn)營(yíng)的最長(zhǎng)服務(wù)時(shí)間；正表示乘客從出發(fā)點(diǎn)到班車站點(diǎn)所花費(fèi)的最長(zhǎng)時(shí)間限制；m洫(善B善n否n%S：fCl+互B木C362尹(3m目標(biāo)函數(shù)所代表的意義為：班車線路的設(shè)計(jì)要使得班車的運(yùn)營(yíng)成本與班車的租賃成本達(dá)到最小，其中EEE%JS：,C1表示的是通勤班車運(yùn)營(yíng)一次所花費(fèi)的費(fèi)D，T用，此項(xiàng)費(fèi)用與運(yùn)行距離有關(guān)；2*136L5表示的是班車一年的租賃成本分配到每一次運(yùn)營(yíng)服務(wù)的費(fèi)用。耽一巧一/行Z蘆(6=1,2,.召)%ll

56、tl匕虼一矽(6=1,2,-B)P工斟廳工日九工蘆工D=1(6=1州2B)(3.2)(3.3)(3.4)(3.5)工。=1b=1i=1(/=1,2刀，/Mf)(3.6)f1,乘客p選擇在i點(diǎn)乘車(3.7)10,乘客P不在i點(diǎn)乘車f1，第P個(gè)乘客所乘坐的班車經(jīng)過(guò)路段由i點(diǎn)行駛至IJj點(diǎn)（38）（38）-10，否則第3章班車線路設(shè)計(jì)優(yōu)化模型的建立第3章班車線路設(shè)計(jì)優(yōu)化模型的建立fl,第6輛班車經(jīng)過(guò)路段弘且由i點(diǎn)行駛至|Jj點(diǎn)%o210,否則(39)其中,約束條件(32)是對(duì)班車行駛時(shí)間的限制,表示的是某一輛班車一次運(yùn)營(yíng)的最大行駛時(shí)間不能超過(guò)某一個(gè)定值Z；約束條件(3.3)表示的是，通勤班車服務(wù)要確

57、保所有需要班車服務(wù)的乘客都可以乘車；約束條件(34)是對(duì)車輛容量的限制,它要求一輛班車的載客數(shù)量不得超過(guò)班車的最大承載量,一旦某輛班車達(dá)到其最大承載量,此班車不在掛靠其他站點(diǎn),立即停止服務(wù)；約束條件(3.5)表示的是每一輛班車終點(diǎn)都為D,也就是開(kāi)通班車服務(wù)的企業(yè)；約束條件(3.6)表示一個(gè)站點(diǎn)只能被一輛班車服務(wù)；約束條件(3.7)、(3.8)、(3.9)均為0.1變量，(3.7)表示乘客P是否在i站點(diǎn)乘車；(3.8)表示乘客P所乘坐的班車經(jīng)過(guò)路段i-j;(3.9)表示班車b經(jīng)過(guò)路段ij。3.3.2引入時(shí)間成本后的模型轉(zhuǎn)化通勤班車線路優(yōu)化的目標(biāo)包含兩個(gè)方面：第一,在滿足乘客需求的條件下,使開(kāi)通班

58、車服務(wù)所投入的成本達(dá)到最?。坏诙?提升班車服務(wù)質(zhì)量,使得乘客從出發(fā)點(diǎn)到班車站點(diǎn)所花費(fèi)的時(shí)間最小。本文通過(guò)通過(guò)設(shè)定這一時(shí)間值的上限正,也就是規(guī)定乘客從出發(fā)地到班車站點(diǎn)所花費(fèi)的時(shí)間不得大于五,限定了通勤班車的服務(wù)水平,在這樣的條件下,對(duì)于不能滿足這一條件的乘客,就需要開(kāi)設(shè)新的站點(diǎn)；同時(shí),本文引入時(shí)間成本的概念,將乘客總的前端時(shí)間值轉(zhuǎn)化為成本與班車成本共同作為優(yōu)化目標(biāo)的一部分,通過(guò)服務(wù)范圍重疊的相鄰班車站點(diǎn)的合并以及引入新的班車站點(diǎn),共同對(duì)班車線路進(jìn)行優(yōu)化。引入時(shí)間成本后的模型轉(zhuǎn)化為：nA出若薈1oV+善B善n若II%毛l害蠡)p=1f=l6=1l蘭l,=1(310)Ju-J(311)(311)(6

59、=1,2,，B)第4章蟻群算法求解班車線路優(yōu)化問(wèn)題企業(yè)通勤班車線路優(yōu)化研究工=1（p=1II2P）i=1虼kpz硝療工洶工蘆1%由=i日一妒一（6=1，2，B）（6=1，2，B）i=1BzzYb，=1（,=1,2櫛，/f）b-1i=1Zt%,%W正（p=1，2尸）YJ1,乘客P選擇在i點(diǎn)乘車【0,乘客p不在i點(diǎn)乘車tpifi,第p個(gè)乘客所乘坐的班車經(jīng)過(guò)路段由i點(diǎn)行駛至Jj點(diǎn)卻”【0,否則ofl,第6輛班車經(jīng)過(guò)路段擴(kuò)，Kfl3i點(diǎn)行駛至Jj點(diǎn)%。1o,否則相比之前的班車路線優(yōu)化基礎(chǔ)模型來(lái)說(shuō),新增的約束條件（3。16）是對(duì)通勤班車服務(wù)水平的最低值限定,如果某一乘客從出發(fā)地到達(dá)某一站點(diǎn)所花費(fèi)的時(shí)間超

60、過(guò)了上限值正,則班車服務(wù)對(duì)這一乘客來(lái)說(shuō)并沒(méi)有提供便利。在這種情況下,就需要重新設(shè)定停車站點(diǎn)以滿足乘客需求。另一方面,對(duì)于距離相近的停車站點(diǎn)來(lái)說(shuō),它們的服務(wù)范圍有一定的重復(fù)性,這種情況的出現(xiàn)就為停車站點(diǎn)的合并提供了可能。在實(shí)際調(diào)查中,對(duì)于相鄰的兩個(gè)班車站點(diǎn)來(lái)說(shuō),如果它們所服務(wù)的乘客從出發(fā)點(diǎn)到達(dá)這兩個(gè)站點(diǎn)所花費(fèi)的時(shí)間都沒(méi)有超過(guò)瓦,那么,理論上來(lái)說(shuō),這兩個(gè)站點(diǎn)就是可以合并的,也就是班車可以只掛靠其中一個(gè)站點(diǎn)就可以滿足乘客的服務(wù)需求,我們可以通過(guò)模型計(jì)算出的結(jié)果得出保留哪個(gè)站點(diǎn)。顯而易見(jiàn),要達(dá)到班車服務(wù)水平與班車服務(wù)成本的均衡,重點(diǎn)在于時(shí)間費(fèi)用轉(zhuǎn)化系數(shù)v,以及乘客從出發(fā)點(diǎn)到達(dá)班車站點(diǎn)所花費(fèi)的吋間上限互