【摘要】：車輛路徑問(wèn)題是研究如何優(yōu)化物流運(yùn)輸?shù)暮诵膯?wèn)題。研究車輛路徑問(wèn)題對(duì)于降低物流公司的運(yùn)輸成本,提高物流公司的服務(wù)質(zhì)量都有重要意義。本文重點(diǎn)研究了帶時(shí)間窗的車輛路徑問(wèn)題。針對(duì)在物流運(yùn)輸中的實(shí)際情況,本文提出了一種新的帶時(shí)間窗車輛路徑問(wèn)題的雙目標(biāo)規(guī)劃模型。第一個(gè)優(yōu)化目標(biāo)是使配送過(guò)程中總的車輛使用數(shù)目最小。在實(shí)際的貨物運(yùn)輸中,由于汽車的油箱容量限制、司機(jī)的工作時(shí)間等,配送車輛的行駛距離往往會(huì)受到限制。因此,在每輛車都有行駛距離限制的約束下,用最少的車輛來(lái)完成配送任務(wù)能最大程度的節(jié)約運(yùn)輸成本。此外,本文考慮了每個(gè)用戶都有自己的期望服務(wù)時(shí)間。盡可能的使得顧客在自己期望時(shí)間內(nèi)被服務(wù),從而提高物流公司的服務(wù)滿意度,這是本文提出的規(guī)劃模型的另一個(gè)優(yōu)化目標(biāo)�；谏鲜龅囊�(guī)劃模型,本文提出了一種雙標(biāo)準(zhǔn)近似算法。該算法可以在多項(xiàng)式時(shí)間內(nèi)給出上述問(wèn)題的近似最優(yōu)解。本文通過(guò)嚴(yán)格的理論分析證明了該算法的近似比為?O(log1/?),1???,并通過(guò)模擬實(shí)驗(yàn)分析了算法的運(yùn)行效率。本文還設(shè)計(jì)了基于遺傳算法的車輛路徑系統(tǒng)。遺傳算法是一種現(xiàn)代啟發(fā)式算法,在求解整數(shù)規(guī)劃問(wèn)題時(shí)有著廣泛的應(yīng)用。本文介紹了用遺傳算法求解車輛路徑問(wèn)題的方法,并通過(guò)實(shí)驗(yàn)分析了遺傳算法的運(yùn)行效率。實(shí)驗(yàn)結(jié)果表明遺傳算法可以應(yīng)用在實(shí)際的系統(tǒng)設(shè)計(jì)中。隨后,本文介紹了車輛路徑系統(tǒng)用到的相關(guān)技術(shù),并通過(guò)模擬實(shí)例展示了此系統(tǒng)的功能。模擬實(shí)例選擇了深圳20家三甲醫(yī)院作為配送點(diǎn)。運(yùn)行系統(tǒng)后,路徑方案將以可視化的形式顯示在百度地圖上。
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP18
【圖文】：

圖 1-1 物流配送流程1.2 國(guó)內(nèi)外相關(guān)研究和綜述車輛路徑問(wèn)題（VRP）概括的說(shuō)就是如何選取路徑，使得配送貨物總價(jià)最小。圖 1-2 是車輛路徑問(wèn)題的示意圖。VRP 經(jīng)過(guò)多年的研究，形成了較完整的理論體系。車輛路徑問(wèn)題是典型的 NP-Hard 問(wèn)題[2]，也是組合優(yōu)領(lǐng)域的經(jīng)典問(wèn)題。至今，車輛路徑問(wèn)題的研究成果已經(jīng)得到了十分廣泛的用，比如快遞員配送貨物，救護(hù)車選取快捷路徑等。文獻(xiàn)[3]詳細(xì)介紹了車路徑問(wèn)題的各種應(yīng)用場(chǎng)景。Dantzig 和 Ramser 于 1959 年在他們的論文中首次提出了車輛路徑問(wèn)題及相應(yīng)的數(shù)學(xué)模型。隨后，車輛路徑問(wèn)題得到了泛的研究，并且從基本的車輛路徑問(wèn)題衍生出許多的變種問(wèn)題，例如有運(yùn)能力限制的模型，帶時(shí)間窗約束的模型，有總路長(zhǎng)限制的模型等。

車輛路徑問(wèn)題的示意圖。VRP 經(jīng)過(guò)多年的研。車輛路徑問(wèn)題是典型的 NP-Hard 問(wèn)題[2]，至今，車輛路徑問(wèn)題的研究成果已經(jīng)得到了送貨物，救護(hù)車選取快捷路徑等。文獻(xiàn)[3]詳用場(chǎng)景。Dantzig 和 Ramser 于 1959 年在他們徑問(wèn)題及相應(yīng)的數(shù)學(xué)模型。隨后，車輛路徑基本的車輛路徑問(wèn)題衍生出許多的變種問(wèn)題帶時(shí)間窗約束的模型，有總路長(zhǎng)限制的模型

點(diǎn)的距離分成若干部分。對(duì)于每一部分求解無(wú)源 VRP，然庫(kù)節(jié)點(diǎn)組合，最后成為 DVRPTW 的一組合法路徑。分割區(qū)據(jù)倉(cāng)庫(kù)節(jié)點(diǎn)的距離來(lái)進(jìn)行區(qū)域劃分。圖 3-1 為 DVRPTW 分 描述 DVRPTW 的求解算法。
【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 唐加福;孔媛;潘震東;董穎;;基于劃分的蟻群算法求解貨物權(quán)重車輛路徑問(wèn)題[J];控制理論與應(yīng)用;2008年04期

2 鐘雪靈;王雄志;;開(kāi)放式車輛路徑問(wèn)題的混合算法[J];計(jì)算機(jī)仿真;2011年08期

3 熊浩;符卓;鄢慧麗;;動(dòng)態(tài)車輛路徑問(wèn)題的隱分區(qū)靈活分批策略[J];同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年05期

4 婁山佐;吳耀華;肖際偉;廖莉;;基于增強(qiáng)學(xué)習(xí)解決隨機(jī)需求車輛路徑問(wèn)題[J];系統(tǒng)仿真學(xué)報(bào);2008年14期

5 徐俊杰;;車輛路徑問(wèn)題的改進(jìn)微正則退火算法[J];信息化縱橫;2009年06期

6 吳斌;邵建峰;方葉祥;;基于客戶滿意度的開(kāi)放式車輛路徑問(wèn)題研究[J];計(jì)算機(jī)工程;2009年17期

7 王江晴;張瀟;;復(fù)雜環(huán)境下動(dòng)態(tài)車輛路徑問(wèn)題的建模與求解[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2010年04期

8 陸琳;蔡紹洪;;一類隨機(jī)顧客車輛路徑問(wèn)題及其算法[J];南京航空航天大學(xué)學(xué)報(bào);2010年04期

9 溫惠英;孫博;;協(xié)同車輛路徑問(wèn)題的模糊規(guī)劃模型和算法[J];計(jì)算機(jī)應(yīng)用研究;2011年02期

10 楊皎平;高雷阜;王俊;;裝卸聯(lián)盟車輛路徑問(wèn)題及兩階段優(yōu)化方法[J];計(jì)算機(jī)工程與應(yīng)用;2011年14期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 劉霞;車輛路徑問(wèn)題的研究[D];華中科技大學(xué);2007年

2 陸琳;不確定信息車輛路徑問(wèn)題及其算法研究[D];南京航空航天大學(xué);2007年

3 陳寶文;蟻群優(yōu)化算法在車輛路徑問(wèn)題中的應(yīng)用研究[D];哈爾濱工業(yè)大學(xué);2009年

4 唐連生;突發(fā)事件下的車輛路徑問(wèn)題研究[D];西南交通大學(xué);2008年

5 謝秉磊;隨機(jī)車輛路徑問(wèn)題研究[D];西南交通大學(xué);2003年

6 符卓;開(kāi)放式車輛路徑問(wèn)題及其應(yīng)用研究[D];中南大學(xué);2003年

7 呂雄偉;郵政物流車輛路徑問(wèn)題研究[D];西南交通大學(xué);2009年

8 潘立軍;帶時(shí)間窗車輛路徑問(wèn)題及其算法研究[D];中南大學(xué);2012年

9 彭碧濤;三維裝載約束下車輛路徑問(wèn)題研究[D];華南理工大學(xué);2013年

10 馬華偉;帶時(shí)間窗車輛路徑問(wèn)題及其啟發(fā)式算法研究[D];合肥工業(yè)大學(xué);2008年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 李文忠;有捎帶的車輛路徑問(wèn)題的研究[D];西南交通大學(xué);2010年

2 曹高立;基于求解車輛路徑問(wèn)題的混合智能優(yōu)化算法研究[D];昆明理工大學(xué);2015年

3 杜濤濤;仿生智能算法在逆向物流選址與車輛路徑問(wèn)題中的應(yīng)用研究[D];上海工程技術(shù)大學(xué);2015年

4 羅敖翔;基于實(shí)時(shí)交通信息的快遞企業(yè)車輛路徑問(wèn)題研究[D];西南交通大學(xué);2015年

5 鄧璇;考慮貨物類別的多車型車輛路徑問(wèn)題優(yōu)化研究[D];長(zhǎng)安大學(xué);2015年

6 焦云龍;基于行程時(shí)間預(yù)測(cè)的物流運(yùn)輸車輛路徑優(yōu)化研究[D];大連海事大學(xué);2015年

7 陳瑞杰;取送一體化多配送中心車輛路徑問(wèn)題的研究[D];大連海事大學(xué);2015年

8 董蕊;具有時(shí)間窗約束的累積性車輛路徑問(wèn)題研究[D];上海交通大學(xué);2015年

9 史春燕;帶車輛時(shí)間窗的多車場(chǎng)車輛路徑問(wèn)題研究[D];重慶工商大學(xué);2015年

10 徐騰飛;危險(xiǎn)化學(xué)品選址及車輛路徑問(wèn)題研究[D];北京化工大學(xué);2015年

本文編號(hào)：2880044