【摘要】：車輛路徑規(guī)劃問題在很多領域包括物流行業(yè)運用廣泛。隨著各種輔助技術的成熟,比如衛(wèi)星導航技術可以提供路線信息,計算機計算能力和存儲能力的提高,高速信息網(wǎng)絡的建成等都在促使車輛路徑規(guī)劃問題向更加智能更加高效方向發(fā)展。這樣既能減少企業(yè)的物流成本同時能夠提高顧客的體驗�，F(xiàn)實中顧客會隨機提出送貨需求,同時希望倉庫能夠在一個固定時間段將貨物送達,此時間段是一個彈性區(qū)間,所以帶軟時間窗的動態(tài)車輛路徑規(guī)劃問題研究有現(xiàn)實意義�；趯嶋H需求,本課題研究帶軟時間窗的動態(tài)車輛路徑規(guī)劃問題,針對問題中軟時間窗和請求動態(tài)到達的約束條件設計了具體的解決方案。在軟時間窗前一段到達會增加企業(yè)的時間成本,為此設計了一個線性懲罰函數(shù);而在后一段到達會使顧客滿意度降低,設計了一個指數(shù)懲罰函數(shù)。同時將車輛整個工作時間分解成一系列固定時間片來解決請求動態(tài)到達問題。本論文設計兩個智能啟發(fā)式算法:改進大領域搜索算法和混合粒子群算法。兩個算法會對上個時間片到達的請求進行計算規(guī)劃出路線,而將本時間片到達顧客點放在下一個時間片處理。改進大領域搜索算法針對軟時間窗要求設計一個基于活動安排的貪心算法生成初始解,然后采用插入刪除啟發(fā)式策略進行優(yōu)化。混合粒子群算法針對問題設計了針對性的粒子結構,并采用Grasp算法生成初始解,然后使用一個粒子速度位置啟發(fā)式函數(shù)進行迭代求解,最后采用PathRelinking算法優(yōu)化結果。本課題采用Solomon標準數(shù)據(jù),該數(shù)據(jù)依據(jù)顧客點的分布分為六大類型,每個類型包含9到12個數(shù)據(jù)文件每個文件含有100個顧客信息。由于目前還沒有研究相同問題的文獻,所以將和一篇研究帶硬時間窗的動態(tài)車輛路徑規(guī)劃問題文章進行對比。懲罰區(qū)間設定為20,同時計算六大類型數(shù)據(jù)平均結果。從結果來看廢棄率很明顯減少,能夠服務的顧客數(shù)目增多。同時針對本論文提出兩種算法分別在懲罰區(qū)間和廢棄率,懲罰區(qū)間和路程,動態(tài)度和廢棄率,動態(tài)度和路程四個方面進行分析�？梢钥吹搅蟛煌愋蛿�(shù)據(jù)在幾個變量之間的表現(xiàn),進而得出變量之間的關系。為了直觀的展示路徑規(guī)劃效果,本課題設計了基于百度地圖的動態(tài)車輛路徑規(guī)劃系統(tǒng)。該系統(tǒng)分別采用百度地圖API為平臺,前端以JQuery技術為核心,后端以PHP和MySQL調用基于Python實現(xiàn)算法。前端可以采用顧客信息包括時間窗和需求等信息,經(jīng)過處理之后會在前端展示規(guī)劃好的路徑,同時前端各個窗口也會實時顯示整個路徑,車輛以及司機的信息。
[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.
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：U116.2;TP301.6

【參考文獻】

相關期刊論文 前3條

1 孫麗君;胡祥培;王征;;車輛路徑規(guī)劃問題及其求解方法研究進展[J];系統(tǒng)工程;2006年11期

2 郭耀煌,謝秉磊;一類隨機動態(tài)車輛路徑問題的策略分析[J];管理工程學報;2003年04期

3 謝秉磊,郭耀煌,郭強;動態(tài)車輛路徑問題:現(xiàn)狀與展望[J];系統(tǒng)工程理論方法應用;2002年02期

相關博士學位論文 前3條

1 饒衛(wèi)振;大規(guī)模動態(tài)車輛路徑問題優(yōu)化方法研究[D];大連理工大學;2012年

2 潘立軍;帶時間窗車輛路徑問題及其算法研究[D];中南大學;2012年

3 陸琳;不確定信息車輛路徑問題及其算法研究[D];南京航空航天大學;2007年

，

本文編號：2263114