【摘要】：隨著電子商務(wù)的飛速崛起,快遞企業(yè)如何合理安排運(yùn)輸車輛以降低運(yùn)輸成本成為一個迫切需要解決的問題�？爝f車輛路徑問題是經(jīng)典的車輛路徑問題(Vehicle Routing Problem, VRP)的變種,也是一個NP難問題。因此,快速的啟發(fā)式求解算法及解好壞的評估是研究中的難點(diǎn)和關(guān)鍵。該問題的研究及應(yīng)用,可以顯著地降低快遞行業(yè)的運(yùn)輸成本,同時也減少車輛的二氧化碳排放量,對經(jīng)濟(jì)和環(huán)境產(chǎn)生積極影響。給定分撥中心的網(wǎng)絡(luò)結(jié)構(gòu)及其服務(wù)時間窗口約束和各個分撥中心之間的貨物流量結(jié)構(gòu)及其時效約束的快遞車輛路徑規(guī)劃,是實(shí)際中最為常見的一類問題。本文主要研究了帶時間窗的快遞車輛路徑問題的建模及求解,具體工作包括以下兩項(xiàng)內(nèi)容：1.固定時間窗快遞車輛路徑問題建模及求解固定時間窗快遞車輛路徑問題就是研究在收件時間窗和派件時間窗固定的情況下,如何安排班車路由使得班車花費(fèi)的總成本最小。本文首先建立了此問題的數(shù)學(xué)模型,然后設(shè)計了基于貪心啟發(fā)式方法的快速求解算法,并提出了一種新的班車安排方法：環(huán)線班車+單邊車,以此代替原有的效果較差的對稱班車安排方法,最后還給出了評估該問題解的一個下界模型。通過在不同規(guī)模的真實(shí)數(shù)據(jù)集上進(jìn)行計算實(shí)驗(yàn),將提出算法的求解結(jié)果與下界模型得到的下界進(jìn)行比較,從而表明了求解算法的精確程度。還將兩種班車安排方法得到的結(jié)果進(jìn)行對比,說明了本文提出的新班車安排方法優(yōu)于原有班車安排方法。此外,對于9城市數(shù)據(jù)和21城市數(shù)據(jù),求解算法總的計算時間分別為1秒和54秒。2.可變時間窗快遞車輛路徑問題建模及求解通過分析發(fā)現(xiàn)時間窗對于班車運(yùn)輸成本影響較大,為此需要將時間窗作為可變參數(shù)納入到模型中,我們將該問題稱之為可變時間窗快遞車輛路徑問題。本文在固定時間窗問題的基礎(chǔ)上,采用環(huán)線班車+單邊車的班車安排方法,建立了該問題的數(shù)學(xué)模型。為了評價算法求解結(jié)果的優(yōu)劣,對該問題建立了時間約束松弛的下界模型并加以證明,再采用Lingo軟件求出其一個下界。最后,設(shè)計了一種兩階段的求解算法,該算法包括時間窗求解和固定時間窗問題求解兩個階段,并且在時間窗求解階段設(shè)計了時間窗口好壞的一個評價函數(shù)。在9城市數(shù)據(jù)集和21城市數(shù)據(jù)集上分別進(jìn)行了求解,計算結(jié)果表明,時間窗口的好壞對最終班車安排花費(fèi)有較大的影響,一組良好的時間窗口安排可以有效的降低班車運(yùn)輸成本。
[Abstract]:With the rapid rise of electronic commerce, how to arrange the transportation vehicle reasonably to reduce the transportation cost becomes an urgent problem to be solved by express delivery enterprises. Express vehicle routing problem is a variant of the classic vehicle routing problem (Vehicle Routing Problem, VRP), and is also a difficult NP problem. Therefore, the fast heuristic algorithm and the evaluation of the solution are the difficulties and key points in the research. The research and application of this problem can significantly reduce the transport cost of the express delivery industry, but also reduce the carbon dioxide emissions of vehicles, and have a positive impact on the economy and the environment. It is the most common problem in practice that the network structure of the distribution center and its service time window constraints, the cargo flow structure between the distribution centers and its time-limited express vehicle routing planning are the most common problems in practice. This paper mainly studies the modeling and solution of express vehicle routing problem with time window. The specific work includes the following two parts: 1. Modeling and solving the fixed time window Express vehicle routing problem is to study how to arrange the routing of the shuttle bus to minimize the total cost of the shuttle bus when the pickup time window and the distribution time window are fixed. This paper first establishes the mathematical model of the problem, then designs a fast solution algorithm based on greedy heuristic method, and proposes a new method of arranging the bus: the one-sided car of the loop line bus. A lower bound model for evaluating the solution of the problem is given. Through the calculation experiments on real data sets of different scales, the results of the proposed algorithm are compared with the lower bound obtained by the lower bound model, which shows the accuracy of the algorithm. The results obtained from the two methods are compared and the results show that the new method is superior to the original one. In addition, for 9 city data and 21 city data, the total computation time of the algorithm is 1 second and 54. 2 seconds, respectively. Modeling and solving of variable time window Express vehicle routing problem through analysis, it is found that time window has a great influence on the transportation cost of shuttle bus, so it is necessary to incorporate time window into the model as a variable parameter. We call this problem a variable time window express vehicle routing problem. On the basis of the fixed time window problem, the mathematical model of the problem is established by using the method of arranging the single side car of the circular line bus. In order to evaluate the advantages and disadvantages of the algorithm, a lower bound model of time-constrained relaxation is established and proved, and a lower bound is obtained by using Lingo software. Finally, a two-stage algorithm is designed. The algorithm consists of two stages: time window solution and fixed time window solution, and an evaluation function of time window is designed in the time window solution phase. The results on 9 city data sets and 21 city data sets show that the time window has a great influence on the cost of the final schedule. A good time window arrangement can effectively reduce the transportation costs.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP301.6

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

相關(guān)會議論文 前10條

1 符卓;陳斯衛(wèi);;車輛路徑問題的研究現(xiàn)狀與發(fā)展趨勢[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（下卷）[C];2004年

2 楊世堅;陳韜;;隨機(jī)車輛路徑問題研究綜述[A];中國系統(tǒng)工程學(xué)會決策科學(xué)專業(yè)委員會第六屆學(xué)術(shù)年會論文集[C];2005年

3 李桂平;陳楠;;多中心車輛路徑問題的解決思路[A];中國地理信息系統(tǒng)協(xié)會第四次會員代表大會暨第十一屆年會論文集[C];2007年

4 李大衛(wèi);王夢光;;廣義車輛路徑問題——模型及算法[A];1997中國控制與決策學(xué)術(shù)年會論文集[C];1997年

5 符卓;聶靖;;開放式車輛路徑問題及其若干研究進(jìn)展[A];中國運(yùn)籌學(xué)會第八屆學(xué)術(shù)交流會論文集[C];2006年

6 陳寶文;宋申民;陳興林;單志眾;;應(yīng)用于車輛路徑問題的多蟻群算法[A];第25屆中國控制會議論文集（下冊）[C];2006年

7 戎麗霞;;模糊需求條件下的多車場車輛路徑問題[A];第三屆中國智能計算大會論文集[C];2009年

8 張鳳姣;張興芳;;基于不確定理論的車輛路徑問題[A];第九屆中國不確定系統(tǒng)年會、第五屆中國智能計算大會、第十三屆中國青年信息與管理學(xué)者大會論文集[C];2011年

9 肖雁;符卓;李育安;;帶軟時間窗的車輛路徑問題及其應(yīng)用前景探討[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

10 許鑫;范文慧;馮雅U，

本文編號：2407319