【摘要】：隨著電子商務(wù)的飛速崛起,快遞企業(yè)如何合理安排運(yùn)輸車輛以降低運(yùn)輸成本成為一個(gè)迫切需要解決的問(wèn)題。快遞車輛路徑問(wèn)題是經(jīng)典的車輛路徑問(wèn)題(Vehicle Routing Problem, VRP)的變種,也是一個(gè)NP難問(wèn)題。因此,快速的啟發(fā)式求解算法及解好壞的評(píng)估是研究中的難點(diǎn)和關(guān)鍵。該問(wèn)題的研究及應(yīng)用,可以顯著地降低快遞行業(yè)的運(yùn)輸成本,同時(shí)也減少車輛的二氧化碳排放量,對(duì)經(jīng)濟(jì)和環(huán)境產(chǎn)生積極影響。給定分撥中心的網(wǎng)絡(luò)結(jié)構(gòu)及其服務(wù)時(shí)間窗口約束和各個(gè)分撥中心之間的貨物流量結(jié)構(gòu)及其時(shí)效約束的快遞車輛路徑規(guī)劃,是實(shí)際中最為常見(jiàn)的一類問(wèn)題。本文主要研究了帶時(shí)間窗的快遞車輛路徑問(wèn)題的建模及求解,具體工作包括以下兩項(xiàng)內(nèi)容：1.固定時(shí)間窗快遞車輛路徑問(wèn)題建模及求解固定時(shí)間窗快遞車輛路徑問(wèn)題就是研究在收件時(shí)間窗和派件時(shí)間窗固定的情況下,如何安排班車路由使得班車花費(fèi)的總成本最小。本文首先建立了此問(wèn)題的數(shù)學(xué)模型,然后設(shè)計(jì)了基于貪心啟發(fā)式方法的快速求解算法,并提出了一種新的班車安排方法：環(huán)線班車+單邊車,以此代替原有的效果較差的對(duì)稱班車安排方法,最后還給出了評(píng)估該問(wèn)題解的一個(gè)下界模型。通過(guò)在不同規(guī)模的真實(shí)數(shù)據(jù)集上進(jìn)行計(jì)算實(shí)驗(yàn),將提出算法的求解結(jié)果與下界模型得到的下界進(jìn)行比較,從而表明了求解算法的精確程度。還將兩種班車安排方法得到的結(jié)果進(jìn)行對(duì)比,說(shuō)明了本文提出的新班車安排方法優(yōu)于原有班車安排方法。此外,對(duì)于9城市數(shù)據(jù)和21城市數(shù)據(jù),求解算法總的計(jì)算時(shí)間分別為1秒和54秒。2.可變時(shí)間窗快遞車輛路徑問(wèn)題建模及求解通過(guò)分析發(fā)現(xiàn)時(shí)間窗對(duì)于班車運(yùn)輸成本影響較大,為此需要將時(shí)間窗作為可變參數(shù)納入到模型中,我們將該問(wèn)題稱之為可變時(shí)間窗快遞車輛路徑問(wèn)題。本文在固定時(shí)間窗問(wèn)題的基礎(chǔ)上,采用環(huán)線班車+單邊車的班車安排方法,建立了該問(wèn)題的數(shù)學(xué)模型。為了評(píng)價(jià)算法求解結(jié)果的優(yōu)劣,對(duì)該問(wèn)題建立了時(shí)間約束松弛的下界模型并加以證明,再采用Lingo軟件求出其一個(gè)下界。最后,設(shè)計(jì)了一種兩階段的求解算法,該算法包括時(shí)間窗求解和固定時(shí)間窗問(wèn)題求解兩個(gè)階段,并且在時(shí)間窗求解階段設(shè)計(jì)了時(shí)間窗口好壞的一個(gè)評(píng)價(jià)函數(shù)。在9城市數(shù)據(jù)集和21城市數(shù)據(jù)集上分別進(jìn)行了求解,計(jì)算結(jié)果表明,時(shí)間窗口的好壞對(duì)最終班車安排花費(fèi)有較大的影響,一組良好的時(shí)間窗口安排可以有效的降低班車運(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é)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前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ān)會(huì)議論文 前10條

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

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

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

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

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

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

7 戎麗霞;;模糊需求條件下的多車場(chǎng)車輛路徑問(wèn)題[A];第三屆中國(guó)智能計(jì)算大會(huì)論文集[C];2009年

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

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

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

本文編號(hào)：2407319