【摘要】：作為一類主要的組合優(yōu)化問題,車輛路徑問題(VRP)一直受到了計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)界的廣泛關(guān)注,在實(shí)際工業(yè)生產(chǎn)調(diào)度中發(fā)揮了重要的作用。然而隨著交通線路的日趨復(fù)雜化以及客戶需求的多樣化與個性化,基本VRP模型很難有效指導(dǎo)物流企業(yè)進(jìn)行配送作業(yè)�，F(xiàn)代物流企業(yè)在進(jìn)行配送路線規(guī)劃時,需要考慮方方面面的因素,比如客戶的動態(tài)請求,時間窗限制,還有企業(yè)自身資源的限制。如何從滿足顧客需求和優(yōu)化企業(yè)自身網(wǎng)點(diǎn)角度來研究動態(tài)車輛路徑問題(DVRP)越來越受到理論界的重視并逐漸成為研究熱點(diǎn)。本文是在前人研究的基礎(chǔ)上,重點(diǎn)對DVRP及其擴(kuò)展和元啟發(fā)式求解算法進(jìn)行了研究,主要研究工作總結(jié)如下:(1)研究了基本DVRP問題,提出了一種改進(jìn)的蝴蝶優(yōu)化算法。該算法利用自然數(shù)編碼的方式對DVRP進(jìn)行離散問題連續(xù)編碼;在遷移算子和調(diào)節(jié)算子的操作過程中采用一種貪婪策略接受局部解;每當(dāng)有新解產(chǎn)生時,利用2-opt*算子對新解進(jìn)行擾動,旨在幫助搜索過程避免陷入局部最優(yōu),增加搜索的多樣性,加快搜索速度,從而得到最終的滿意解。在通用的22個基準(zhǔn)測試集上進(jìn)行了實(shí)驗(yàn),算法更新了 12個實(shí)例的已知最好解,與現(xiàn)有文獻(xiàn)中的方法相比平均性能至少提高9.38%,從而驗(yàn)證了算法的有效性。(2)研究了有時間窗DVRP問題,提出一種改進(jìn)的和聲搜索算法。該算法結(jié)合了和聲搜索算法與變鄰域下降算法的優(yōu)勢。與經(jīng)典和聲搜索相比,重新定義了編碼方式、初始解構(gòu)造方式、即興創(chuàng)作新和聲操作及接收方式;設(shè)計(jì)了四種鄰域結(jié)構(gòu)以擴(kuò)大搜索空間;以信息熵評價種群優(yōu)劣,防止過早收斂;動態(tài)對客戶請求進(jìn)行檢查,以提高搜索性能。并在通用的基準(zhǔn)測試數(shù)據(jù)集上將該算法與現(xiàn)有算法進(jìn)行對比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表示,算法的平均拒絕率最少,即使在相同的拒絕率的條件下,車輛行駛距離與車輛使用數(shù)在大部分情況下也優(yōu)于現(xiàn)有算法,從而檢驗(yàn)了算法的有效性。(3)研究了車輛數(shù)受限與帶時間窗DVRP問題,提出了一種基于自適應(yīng)大型鄰域搜索的改進(jìn)算法。設(shè)計(jì)了一系列特殊刪除/修復(fù)策略;并對每一種策略指定初始評分及權(quán)重,在搜索過程根據(jù)當(dāng)前的表現(xiàn)動態(tài)更新評分及權(quán)重,根據(jù)權(quán)重按照輪盤賭的機(jī)制選擇刪除/修復(fù)策略;引入一個周期性的擾動策略,加快了搜索速度;此外,針對動態(tài)客戶的插入,設(shè)計(jì)了一個針對時間窗的提前等待策略。最后通過Lacker基準(zhǔn)數(shù)據(jù)集對算法性能進(jìn)行測試,更新了 19組實(shí)例的最少車輛使用數(shù),檢驗(yàn)算法的有效性。(4)研究了眾包條件下的帶時間窗動態(tài)車輛路徑問題,在該問題中,假設(shè)一部分客戶的需求是通過物流公司自營的車隊(duì)進(jìn)行運(yùn)輸,另一部分則以外包的形式發(fā)布到第三方物流平臺,通過臨時司機(jī)接收任務(wù)的方式完成相關(guān)運(yùn)輸配送。為了求解該問題提出一種貪婪隨機(jī)自適應(yīng)搜索算法。該方法的迭代過程包括構(gòu)造和局部搜索兩個階段。在解的構(gòu)造階段,采用兩種不同的貪婪函數(shù)來構(gòu)造初始解;在局部搜索階段,設(shè)計(jì)了4種鄰域結(jié)構(gòu),擴(kuò)展了解的搜索空間。為了促進(jìn)臨時司機(jī)的積極性,設(shè)計(jì)了兩個不同的補(bǔ)償策略。通過Lackner的基準(zhǔn)實(shí)例驗(yàn)證了算法的有效性,再利用真實(shí)案例對其進(jìn)行測試,驗(yàn)證了眾包策略的優(yōu)越性。(5)開發(fā)基于眾包的包裹配送平臺。從軟件開發(fā)的角度對系統(tǒng)的功能模塊進(jìn)行分析,設(shè)計(jì)眾包條件下包裹配送的業(yè)務(wù)流程,集成本文提出的相關(guān)求解算法,并展示包裹配送平臺的主界面和功能模塊。該平臺可以為物流公司使用眾包進(jìn)行包裹配送提供有效的物流整合方案。
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：TP18
【圖文】：

圖２．２單個車輛動態(tài)路線事件的時間軸逡逑Ｆｉｇ．邋２．２邋Ｔｉｍｅｌｉｎｅ邋ｏｆ邋ｅｖｅｎｔｓ邋ｆｏｒ邋ｔｈｅ邋ｄｙｎａｍｉｃ邋ｒｏｕｔｉｎｇ邋ｏｆ邋ａ邋ｓｉｎｇｌｅ邋ｖｅｈｉｃｌｅ逡逑在圖２．１揭示ＤＶＲＰ如何以持續(xù)的方式進(jìn)行路徑調(diào)整，在這一過程中需要在逡逑車輛和調(diào)度中心之間進(jìn)行實(shí)時通信。圖２．２說明了這種實(shí)時通信方案，其中環(huán)境逡逑指的是真實(shí)世界，調(diào)度員是向車輛發(fā)送調(diào)度指令的有關(guān)人員。一旦車輛準(zhǔn)備就緒逡逑（第一個虛線箭頭），調(diào)度員做出決策，并指示車輛履行客戶Ａ的請求（第一雙頭逡逑箭頭）。當(dāng)車輛到達(dá)客戶Ａ邋（第二個虛線箭頭）并開始服務(wù)時，它會通知調(diào)度員并逡逑－８－逡逑

．４．１策略算法逡逑通常，策略是指系統(tǒng)應(yīng)對當(dāng)前狀態(tài)和動態(tài)問題的屬性（例如出現(xiàn)的位置、事逡逑頻率、事先已知的訂單數(shù)、工作日長度、規(guī)劃周期的持續(xù)時間等）所進(jìn)行的一逡逑列操作［３（＾１］。在有些文獻(xiàn)中［３２－３７］策略定義為單一或多個車輛條件，他們考慮動逡逑請求的特殊性和時間分布，并使系統(tǒng)在每次問題發(fā)生變化時對服務(wù)進(jìn)行規(guī)劃。逡逑為了向車輛發(fā)送請求和建造路線，策略被反復(fù)應(yīng)用。我們概述了其中的一些：逡逑（１）先到先得（ＦＣＦＳ）：請求是按照調(diào)度程序接收到的順序執(zhí)行的；逡逑（２）隨機(jī)隊(duì)列中值（ＳＱＭ）：車輛位于在服務(wù)區(qū)域的正中位置，根據(jù)ＦＩＲ）策逡逑為客戶服務(wù)。當(dāng)服務(wù)完成后，車輛返回到中間位置。逡逑（３）最近的鄰居（ＮＮ）：它是一種貪婪的策略。在該策略中，車輛在服務(wù)當(dāng)逡逑客戶后，選擇靠近當(dāng)前客戶最近的未被服務(wù)的客戶作為下一服務(wù)對象。逡逑（４）旅行推銷員（ＴＳ）：請求被收集到一個給定大小的集合中。一旦一組需逡逑被批量處理，ＴＳＰ就被解決了。這些需求的服務(wù)是按照最佳的路線，從配送中逡逑

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 寧濤;郭晨;陳榮;金花;;一種動態(tài)車輛路徑問題解決策略仿真研究[J];系統(tǒng)仿真學(xué)報;2015年12期

2 任為;;基于快遞眾包的城市配送模式初探[J];物流工程與管理;2015年06期

3 陳洪滿;雷斌;馬超;;一類帶時間窗動態(tài)車輛路徑優(yōu)化[J];洛陽理工學(xué)院學(xué)報(自然科學(xué)版);2014年04期

4 于宏濤;高立群;呂勇軍;;基于混合和聲搜索算法求解競爭選址問題[J];控制與決策;2013年07期

5 田軍;馬文正;汪應(yīng)洛;王刊良;;應(yīng)急物資配送動態(tài)調(diào)度的粒子群算法[J];系統(tǒng)工程理論與實(shí)踐;2011年05期

6 劉志敏;王愛虎;余高輝;;改進(jìn)和聲算法在產(chǎn)業(yè)集群物流選址中的應(yīng)用[J];工業(yè)工程與管理;2011年02期

7 韓紅燕;任立群;;求解批量流水線調(diào)度問題的和聲算法[J];計(jì)算機(jī)應(yīng)用研究;2011年01期

8 錢艷婷;王鵬濤;魏國利;;動態(tài)車輛路徑問題的算法研究[J];天津理工大學(xué)學(xué)報;2010年06期

9 汪勇;丁凡;吳志華;;協(xié)同進(jìn)化遺傳算法求解帶時間窗的車輛路徑問題[J];統(tǒng)計(jì)與決策;2010年10期

10 劉霞;齊歡;;基于禁忌搜索的動態(tài)車輛路徑問題研究[J];武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版);2010年02期

相關(guān)博士學(xué)位論文 前1條

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

相關(guān)碩士學(xué)位論文 前4條

1 劉洋;和聲搜索算法演化計(jì)算理論及其在復(fù)雜車間調(diào)度中的應(yīng)用[D];蘭州理工大學(xué);2016年

2 顏騰威;求解VRP問題的改進(jìn)和聲搜索算法的研究[D];浙江師范大學(xué);2015年

3 朱航;基于改進(jìn)和聲搜索算法的車間作業(yè)調(diào)度問題研究[D];南京理工大學(xué);2015年

4 王華;改進(jìn)和聲搜索算法在車輛路徑問題中的應(yīng)用研究[D];遼寧工程技術(shù)大學(xué);2011年

本文編號：2724865