開(kāi)放式車(chē)輛路徑問(wèn)題及其應(yīng)用研究.pdf

1、交通運(yùn)輸是國(guó)民經(jīng)濟(jì)的動(dòng)脈,它對(duì)社會(huì)經(jīng)濟(jì)發(fā)展和人民生活起著極為重要的作用.各種運(yùn)輸方式在日常運(yùn)輸營(yíng)運(yùn)管理工作中都要面對(duì)這樣一個(gè)共同的問(wèn)題:如何為其載運(yùn)工具(汽車(chē)、列車(chē)、輪船和飛機(jī),以下統(tǒng)稱(chēng)為車(chē)輛)確定行駛路線及其時(shí)刻表,才能有效地運(yùn)送各站點(diǎn)間的旅客和貨物.運(yùn)籌學(xué)界將此類(lèi)問(wèn)題統(tǒng)稱(chēng)為車(chē)輛路徑問(wèn)題.可見(jiàn),車(chē)輛路徑問(wèn)題是運(yùn)輸組織優(yōu)化中的核心問(wèn)題.在過(guò)去三十年間,以物流配送運(yùn)輸線路優(yōu)化選擇為背景的車(chē)輛路徑問(wèn)題得到了廣泛的研究,并取得了豐富的研究成果

2、.該文將首先對(duì)此類(lèi)問(wèn)題的特點(diǎn)、分類(lèi)以及求解算法的研究現(xiàn)狀等進(jìn)行綜述.開(kāi)放式車(chē)輛路徑問(wèn)題,是另一種類(lèi)型的車(chē)輛路徑問(wèn)題,同時(shí)也是交通運(yùn)輸運(yùn)籌學(xué)的一個(gè)新的研究領(lǐng)域,有著廣泛的應(yīng)用前景.它與基本的車(chē)輛路徑問(wèn)題的主要不同點(diǎn)是不要求車(chē)輛完成運(yùn)輸任務(wù)后返回原出發(fā)點(diǎn),或者是若要求返回原出發(fā)點(diǎn),則沿原去程路線返回.該文對(duì)帶路程長(zhǎng)度和裝載能力約束的開(kāi)放式車(chē)輛路徑問(wèn)題從理論上進(jìn)行了研究.通過(guò)利用所研究的問(wèn)題的特點(diǎn),提出了新的鄰域結(jié)構(gòu)、并在搜索過(guò)程中引入一種隨

3、機(jī)多樣性等,從而構(gòu)造了一個(gè)求解該問(wèn)題的禁忌搜索算法.在理論研究的基礎(chǔ)上,對(duì)帶裝載能力約束的開(kāi)放式車(chē)輛路徑問(wèn)題的一個(gè)案例,校車(chē)路徑問(wèn)題進(jìn)行了研究.通過(guò)分析,將該問(wèn)題歸結(jié)為一個(gè)多目標(biāo)組合優(yōu)化問(wèn)題.根據(jù)問(wèn)題的特殊結(jié)構(gòu),提出了求解該問(wèn)題的一個(gè)基于最優(yōu)化方法的啟發(fā)式算法.用香港的一所幼兒園的數(shù)據(jù)對(duì)算法進(jìn)行了測(cè)試,結(jié)果表明,用該算法所求出的校車(chē)線路與現(xiàn)有的手工方法相比,學(xué)生所花費(fèi)的總乘車(chē)時(shí)間減少了29％;校車(chē)載有學(xué)生時(shí)的總行駛時(shí)間平均縮短22.8％