車輛路徑問題(VRP)是企業(yè)開展物流活動過程中的重要問題之一,隨著配送時效在物流經(jīng)濟活動中發(fā)揮著重要的作用和客戶時間意識增強,快速響應、安全可靠的車輛路徑問題研究顯得愈加重要,特別是隨著電商的蓬勃發(fā)展和推動,區(qū)域內(nèi)大規(guī)�？蛻粲唵蔚募磿r配送問題出現(xiàn)頻率越來越高,并逐漸成為城市配送研究的重要方向,因此該類問題的研究變得更有必要。但現(xiàn)有的理論應用到該問題存在難點:精確算法或者啟發(fā)式算法的求解時間隨著研究問題的規(guī)模增大呈指數(shù)式增加,顯然求解時間太長,并不適用,本文采用兩階段算法,先聚類后排程,降低問題求解規(guī)模的同時使用高效的算法實現(xiàn)客戶訂單配送,不僅可以提供更快捷、準時、有效的配送服務,而且有助于企業(yè)節(jié)約成本,合理利用車輛和人力資源,因此該問題研究具有現(xiàn)實意義和必要性。本文在查閱國內(nèi)外VRP和聚類理論研究文獻后,結合即時配送行業(yè)背景和H公司存在的問題,將兩階段啟發(fā)式算法引入到大規(guī)模即時配送問題研究中:第一階段,訂單聚類處理,分別用貪婪聚類(最近鄰算法)和最大最小距離聚類對區(qū)域內(nèi)的所有訂單劃分,降低問題規(guī)模、計算量,提高求解效率,同時對兩種聚類方式從類內(nèi)聚合度CP、類間間隔性SP等兩個聚類有效指標上進行分析,初步評定聚類效果好壞;第二階段,前一階段聚類處理將車輛問題轉化成TSP問題,為了量化控制時間對客戶滿意度的影響,論文引入時間懲罰系數(shù),進而建立帶時間窗的車輛調(diào)度模型(TSPSTW),使用全局搜索能力較強的遺傳算法求解模型,以動態(tài)交叉、變異算子替代傳統(tǒng)靜態(tài)算子,使得求解更快、結果更優(yōu),從而為快速、有效地優(yōu)化時間窗問題創(chuàng)造條件�？蛻粲唵尉垲惡团渌途ㄟ^MATLAB仿真實現(xiàn),以算例C401為例,仿真運行算例TSPSTW模型,得到訂單配送計劃表,包括配送路線、總成本、總里程、訂單時刻表等,依此得到所有訂單的配送計劃。從運行效率上,只需7-8分鐘完成501個訂單聚類和配送,進一步驗證了兩階段算法的高效性,最后結合聚類指標和配送經(jīng)濟指標對比兩種聚類方案的優(yōu)劣,為H公司選擇適合的調(diào)度計劃提供參考。
【學位單位】：東華大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：F252
【部分圖文】：

1 緒論1.1 研究背景及意義隨著經(jīng)濟發(fā)展和消費結構快速升級，人們的時間意識愈加敏感，近年來“懶人經(jīng)濟”和“生活快節(jié)奏”很大程度上催生了即時配送行業(yè)的發(fā)展，傳統(tǒng)意義上的，今天訂貨，隔天到貨的配送模式已經(jīng)逐漸滿足不了當下客戶對時間苛刻的要求。根據(jù)中國最近 3 年即時配送行業(yè)客戶規(guī)模的數(shù)據(jù)(圖 1-1)，用戶規(guī)模去年高達 3.24 億，比 2016 年增長 40.3%，自從 2014 年起，以每年超過 30%的增長率激增，這反應了我國用戶對即時配送的需求持續(xù)走高；從即時訂單比例來看，電商行業(yè)代表企業(yè)京東2016年四個季度的即時訂單比例(圖1-2)以超過20%的增長率呈現(xiàn)穩(wěn)健增長的態(tài)勢，這種良好的趨勢會在未來很長一段時間維持，可以預見該行業(yè)具有很好的發(fā)展前景。

圖 1-3 A 門店 7 月下單高峰期水平曲線(2) 難點二：大規(guī)模 VRP 問題對算法提出了極高的要求。傳統(tǒng) VRP 算法引到大規(guī)模訂單閃送問題存在理論應用難點。拿一般的 VRP 問題求解，難以在效時間內(nèi)得到有效解，精確算法只能有效求解小規(guī)模車輛路徑問題，但當訂單模達到上百個時，求解時間呈指數(shù)式遞增，顯然實用性不大；啟發(fā)式算法雖能理大規(guī)模復雜的車輛問題，但直接求解，也花費時間長，違背客戶時間要求。(3) 難點三：兩階段算法求解大規(guī)模車輛問題有著獨特的優(yōu)勢和很強的實用，但第一階段聚類方法的好壞嚴重影響有效解。國內(nèi)專家引用劃分法 K-means法居多，主要因為該算法對于大規(guī)模數(shù)據(jù)型數(shù)據(jù)有獨特的優(yōu)勢，運算速度快，輸入數(shù)據(jù)順序不敏感，但是該算法有明顯的局限性，對聚類數(shù)的選取大多依賴為經(jīng)驗，缺乏科學的理論依據(jù)。2.2 論文思路結合即時配送行業(yè)背景，配送時效在物流活動中愈加重要，快速響應、安全靠的車輛路徑問題研究逐漸成為城市配送領域的熱點問題。但是，傳統(tǒng) VRP

法求解模型；選擇時，按照群體個體適應度大小排列保護最優(yōu)個體并使用輪盤賭的選擇；值得注意的是，使用動態(tài)交叉、變異算子取代靜態(tài)算子，并通過實驗驗證，發(fā)現(xiàn)收斂更快、結果更優(yōu)。(3) 指標分析以類內(nèi)聚合度、類間間隔性作為聚類指標選取指導原則，分別對比了兩種聚類結果的CP、SP指標，初步判斷聚類效果好壞，然后結合配送成本、資源利用率等經(jīng)濟指標判斷兩種方案的優(yōu)劣情況，最后為H公司提供合理的調(diào)度方案。(4) 利用 Matlab 軟件求解，并進行分析。通過聚類和路徑仿真實驗，獲取運行時間數(shù)據(jù)，以貪婪聚類為例，平均每類客戶訂單排程只需 17 秒左右，從而說明該算法在求解大規(guī)模即時配送問題具有高效性，基本滿足大規(guī)模訂單閃送問題。1.3.2 論文組織結構
【參考文獻】

相關期刊論文 前7條

1 孫小軍;;求解帶時間窗車輛路徑問題的混合智能算法[J];大連理工大學學報;2015年02期

2 譚峻強;楊萍;何曉彤;譚振江;;用動態(tài)規(guī)劃法解決最優(yōu)路徑問題的相關研究[J];信息系統(tǒng)工程;2015年01期

3 李波;邱紅艷;;基于雙層模糊聚類的多車場車輛路徑遺傳算法[J];計算機工程與應用;2014年05期

4 洪聯(lián)系;;帶時間窗口動態(tài)車輛路徑規(guī)劃模型及其求解算法[J];計算機工程與應用;2012年04期

5 葛金輝;;有時間窗的車輛路徑問題及改進禁忌搜索算法[J];吉林大學學報(理學版);2011年01期

6 傅成紅;符卓;;一種毗鄰信息改進的車輛路徑問題禁忌搜索算法[J];系統(tǒng)工程;2010年05期

7 朱錦新;;基于空間聚類和蟻群算法的車輛路徑問題的研究[J];鹽城工學院學報(自然科學版);2009年04期

本文編號：2856405