帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑規(guī)劃問題研究與實(shí)現(xiàn)
發(fā)布時(shí)間：2018-10-10 20:19
【摘要】：車輛路徑規(guī)劃問題在很多領(lǐng)域包括物流行業(yè)運(yùn)用廣泛。隨著各種輔助技術(shù)的成熟,比如衛(wèi)星導(dǎo)航技術(shù)可以提供路線信息,計(jì)算機(jī)計(jì)算能力和存儲(chǔ)能力的提高,高速信息網(wǎng)絡(luò)的建成等都在促使車輛路徑規(guī)劃問題向更加智能更加高效方向發(fā)展。這樣既能減少企業(yè)的物流成本同時(shí)能夠提高顧客的體驗(yàn)�，F(xiàn)實(shí)中顧客會(huì)隨機(jī)提出送貨需求,同時(shí)希望倉(cāng)庫(kù)能夠在一個(gè)固定時(shí)間段將貨物送達(dá),此時(shí)間段是一個(gè)彈性區(qū)間,所以帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑規(guī)劃問題研究有現(xiàn)實(shí)意義�；趯�(shí)際需求,本課題研究帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑規(guī)劃問題,針對(duì)問題中軟時(shí)間窗和請(qǐng)求動(dòng)態(tài)到達(dá)的約束條件設(shè)計(jì)了具體的解決方案。在軟時(shí)間窗前一段到達(dá)會(huì)增加企業(yè)的時(shí)間成本,為此設(shè)計(jì)了一個(gè)線性懲罰函數(shù);而在后一段到達(dá)會(huì)使顧客滿意度降低,設(shè)計(jì)了一個(gè)指數(shù)懲罰函數(shù)。同時(shí)將車輛整個(gè)工作時(shí)間分解成一系列固定時(shí)間片來解決請(qǐng)求動(dòng)態(tài)到達(dá)問題。本論文設(shè)計(jì)兩個(gè)智能啟發(fā)式算法:改進(jìn)大領(lǐng)域搜索算法和混合粒子群算法。兩個(gè)算法會(huì)對(duì)上個(gè)時(shí)間片到達(dá)的請(qǐng)求進(jìn)行計(jì)算規(guī)劃出路線,而將本時(shí)間片到達(dá)顧客點(diǎn)放在下一個(gè)時(shí)間片處理。改進(jìn)大領(lǐng)域搜索算法針對(duì)軟時(shí)間窗要求設(shè)計(jì)一個(gè)基于活動(dòng)安排的貪心算法生成初始解,然后采用插入刪除啟發(fā)式策略進(jìn)行優(yōu)化。混合粒子群算法針對(duì)問題設(shè)計(jì)了針對(duì)性的粒子結(jié)構(gòu),并采用Grasp算法生成初始解,然后使用一個(gè)粒子速度位置啟發(fā)式函數(shù)進(jìn)行迭代求解,最后采用PathRelinking算法優(yōu)化結(jié)果。本課題采用Solomon標(biāo)準(zhǔn)數(shù)據(jù),該數(shù)據(jù)依據(jù)顧客點(diǎn)的分布分為六大類型,每個(gè)類型包含9到12個(gè)數(shù)據(jù)文件每個(gè)文件含有100個(gè)顧客信息。由于目前還沒有研究相同問題的文獻(xiàn),所以將和一篇研究帶硬時(shí)間窗的動(dòng)態(tài)車輛路徑規(guī)劃問題文章進(jìn)行對(duì)比。懲罰區(qū)間設(shè)定為20,同時(shí)計(jì)算六大類型數(shù)據(jù)平均結(jié)果。從結(jié)果來看廢棄率很明顯減少,能夠服務(wù)的顧客數(shù)目增多。同時(shí)針對(duì)本論文提出兩種算法分別在懲罰區(qū)間和廢棄率,懲罰區(qū)間和路程,動(dòng)態(tài)度和廢棄率,動(dòng)態(tài)度和路程四個(gè)方面進(jìn)行分析�？梢钥吹搅蟛煌愋蛿�(shù)據(jù)在幾個(gè)變量之間的表現(xiàn),進(jìn)而得出變量之間的關(guān)系。為了直觀的展示路徑規(guī)劃效果,本課題設(shè)計(jì)了基于百度地圖的動(dòng)態(tài)車輛路徑規(guī)劃系統(tǒng)。該系統(tǒng)分別采用百度地圖API為平臺(tái),前端以JQuery技術(shù)為核心,后端以PHP和MySQL調(diào)用基于Python實(shí)現(xiàn)算法。前端可以采用顧客信息包括時(shí)間窗和需求等信息,經(jīng)過處理之后會(huì)在前端展示規(guī)劃好的路徑,同時(shí)前端各個(gè)窗口也會(huì)實(shí)時(shí)顯示整個(gè)路徑,車輛以及司機(jī)的信息。
[Abstract]:Vehicle routing problem is widely used in many fields, including logistics industry. With the maturity of various assistive technologies, such as satellite navigation technology, which can provide route information, computer computing capacity and storage capacity, The establishment of high-speed information network has promoted the development of vehicle routing problem towards more intelligent and more efficient direction. This can not only reduce the logistics costs of enterprises, but also improve the customer experience. In reality, the customer will put forward the delivery demand at random, and hope that the warehouse can deliver the goods in a fixed time period, which is a flexible interval, so the study of dynamic vehicle routing with soft time window has practical significance. Based on the practical requirements, the dynamic vehicle routing problem with soft time window is studied in this paper, and a concrete solution is designed for the soft time window and the constraint condition of requesting dynamic arrival. The arrival in front of the soft time window will increase the time cost of the enterprise. For this reason, a linear penalty function is designed, while in the latter stage, the customer satisfaction is reduced, and an exponential penalty function is designed. At the same time, the whole working time of the vehicle is decomposed into a series of fixed time slices to solve the dynamic arrival problem. This paper designs two intelligent heuristic algorithms: improved large-domain search algorithm and hybrid particle swarm optimization algorithm. The two algorithms calculate and plan the route of the request from the last time slice, and the time slice arrives at the customer point to be processed in the next time slice. The improved large domain search algorithm designs a greedy algorithm based on activity scheduling for soft time window to generate the initial solution, and then optimizes the algorithm by inserting and deleting heuristic strategy. The hybrid particle swarm optimization algorithm is designed to solve the problem, and Grasp algorithm is used to generate the initial solution, then a particle velocity position heuristic function is used to iterate the solution. Finally, the PathRelinking algorithm is used to optimize the results. According to the distribution of customer points, the data is divided into six types. Each type contains 9 to 12 data files, and each file contains 100 customer information. Since there is no literature on the same problem at present, it will be compared with a study on dynamic vehicle routing with hard time window. The penalty interval is set to 20, and the average results of the six types of data are calculated at the same time. As a result, the wastage rate was significantly reduced and the number of customers able to serve increased. At the same time, the two algorithms are analyzed in four aspects: penalty interval and abandonment rate, penalty interval and distance, dynamic degree and abandonment rate, dynamic degree and distance. We can see the performance of six different types of data among several variables, and then get the relationship between variables. In order to show the effect of path planning, this paper designs a dynamic vehicle path planning system based on Baidu map. The system uses Baidu Map API as the platform, the front-end is based on JQuery technology, and the back-end is implemented by PHP and MySQL based on Python. The front end can use customer information, including time window and requirement information. After processing, the planned path will be displayed in the front end. At the same time, every front end window will also display the whole path, vehicle and driver information in real time.
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：U116.2;TP301.6
本文編號(hào)：2263114
[Abstract]:Vehicle routing problem is widely used in many fields, including logistics industry. With the maturity of various assistive technologies, such as satellite navigation technology, which can provide route information, computer computing capacity and storage capacity, The establishment of high-speed information network has promoted the development of vehicle routing problem towards more intelligent and more efficient direction. This can not only reduce the logistics costs of enterprises, but also improve the customer experience. In reality, the customer will put forward the delivery demand at random, and hope that the warehouse can deliver the goods in a fixed time period, which is a flexible interval, so the study of dynamic vehicle routing with soft time window has practical significance. Based on the practical requirements, the dynamic vehicle routing problem with soft time window is studied in this paper, and a concrete solution is designed for the soft time window and the constraint condition of requesting dynamic arrival. The arrival in front of the soft time window will increase the time cost of the enterprise. For this reason, a linear penalty function is designed, while in the latter stage, the customer satisfaction is reduced, and an exponential penalty function is designed. At the same time, the whole working time of the vehicle is decomposed into a series of fixed time slices to solve the dynamic arrival problem. This paper designs two intelligent heuristic algorithms: improved large-domain search algorithm and hybrid particle swarm optimization algorithm. The two algorithms calculate and plan the route of the request from the last time slice, and the time slice arrives at the customer point to be processed in the next time slice. The improved large domain search algorithm designs a greedy algorithm based on activity scheduling for soft time window to generate the initial solution, and then optimizes the algorithm by inserting and deleting heuristic strategy. The hybrid particle swarm optimization algorithm is designed to solve the problem, and Grasp algorithm is used to generate the initial solution, then a particle velocity position heuristic function is used to iterate the solution. Finally, the PathRelinking algorithm is used to optimize the results. According to the distribution of customer points, the data is divided into six types. Each type contains 9 to 12 data files, and each file contains 100 customer information. Since there is no literature on the same problem at present, it will be compared with a study on dynamic vehicle routing with hard time window. The penalty interval is set to 20, and the average results of the six types of data are calculated at the same time. As a result, the wastage rate was significantly reduced and the number of customers able to serve increased. At the same time, the two algorithms are analyzed in four aspects: penalty interval and abandonment rate, penalty interval and distance, dynamic degree and abandonment rate, dynamic degree and distance. We can see the performance of six different types of data among several variables, and then get the relationship between variables. In order to show the effect of path planning, this paper designs a dynamic vehicle path planning system based on Baidu map. The system uses Baidu Map API as the platform, the front-end is based on JQuery technology, and the back-end is implemented by PHP and MySQL based on Python. The front end can use customer information, including time window and requirement information. After processing, the planned path will be displayed in the front end. At the same time, every front end window will also display the whole path, vehicle and driver information in real time.
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：U116.2;TP301.6
【參考文獻(xiàn)】
相關(guān)期刊論文 前3條
1 孫麗君;胡祥培;王征;;車輛路徑規(guī)劃問題及其求解方法研究進(jìn)展[J];系統(tǒng)工程;2006年11期
2 郭耀煌,謝秉磊;一類隨機(jī)動(dòng)態(tài)車輛路徑問題的策略分析[J];管理工程學(xué)報(bào);2003年04期
3 謝秉磊,郭耀煌,郭強(qiáng);動(dòng)態(tài)車輛路徑問題:現(xiàn)狀與展望[J];系統(tǒng)工程理論方法應(yīng)用;2002年02期
相關(guān)博士學(xué)位論文 前3條
1 饒衛(wèi)振;大規(guī)模動(dòng)態(tài)車輛路徑問題優(yōu)化方法研究[D];大連理工大學(xué);2012年
2 潘立軍;帶時(shí)間窗車輛路徑問題及其算法研究[D];中南大學(xué);2012年
3 陸琳;不確定信息車輛路徑問題及其算法研究[D];南京航空航天大學(xué);2007年
，本文編號(hào)：2263114
本文鏈接：http://sikaile.net/kejilunwen/ruanjiangongchenglunwen/2263114.html
最近更新
教材專著
