本文選題：VRP　切入點：分布估計算法　出處：《昆明理工大學》2017年碩士論文

【摘要】：隨著市場競爭越來越激烈,科學技術的快速發(fā)展和物流的專業(yè)水平不斷提高,大量企業(yè)已經(jīng)把先進的物流理論技術引入到了企業(yè)管理中來,并且把物流作為提高市場競爭力與核心競爭水平的一個重要的手段。怎樣對配送系統(tǒng)的車輛路徑進行優(yōu)化來降低企業(yè)物流成本是此問題主要研究內(nèi)容。物流配送中的車輛路徑優(yōu)化問題(Vehicle Routing Problem,VRP)屬于典型的NP-hard問題,其計算時間也會隨著問題規(guī)模的變大而越來越長,應用傳統(tǒng)精確算法求解該問題復雜性較大。因此,目前大部分研究學者主要用智能優(yōu)化算法對車輛調(diào)度問題進行求解。分布估計算法(Estimation of Distribution Algorithm,EDA)是一種基于概率分布模型的進化算法,在近年來也得到了普遍的關注和發(fā)展,并且成功的應用于多個工業(yè)發(fā)展領域,取得了良好效果。故而本文主要針對不同約束條件的車輛路徑優(yōu)化問題,對其進行了三種改進,并分別采用改進算法進行仿真來驗證算法的有效性。首先,針對總行駛距離指標下的車輛載重約束的經(jīng)典車輛路徑優(yōu)化問題,設計了合適的編碼機制和概率模型,將傳統(tǒng)的二進制編碼改為十進制編碼方式,減少了編碼之間轉換的繁瑣過程,根據(jù)車輛調(diào)度問題特點,將普通的二維概率矩陣改為三維矩陣,即每輛車對應一個單獨的二維矩陣,最后加入了局部搜索機制,對優(yōu)質(zhì)個體進行更加細致的搜索,進而提出了一種解決此問題的改進分布估計算法(Improved Estimation of Distribution Algorithm,IEDA)。通過Matlab應用IEDA算法對容量約束車輛調(diào)度問題進行仿真,表明提高了算法全局搜索能力,降低了總的配送費用(路程),從而驗證了該算法的有效性。其次,對隨機需求的多車型車輛調(diào)度問題將隨機需求問題利用時間軸轉換成一系列的的靜態(tài)車輛調(diào)度問題,另外對于多車型問題考慮以裝載率為選擇車輛的依據(jù),建立了考慮裝載率和油耗等綜合成本的優(yōu)化目標的車輛調(diào)度問題。針對隨機需求多車型VRP問題特點,在上一章算法的基礎上,將分布估計算法與并行節(jié)約算法相混合,提出了混合分布估計算法(HEDA)。然后,對考慮綜合成本低碳車輛調(diào)度問題,提出一種自適應分布估計算法(Adaptive Estimation of DistributionAlgorithm,AEDA)。對初始概率模型機制進行改進,使得概率模型能夠積累更多的優(yōu)質(zhì)信息,以便算法初期的搜索范圍更加廣泛,又設計了基于信息熵的自適應更新機制來更新學習速率和變異率,增強算法的搜索能力。
[Abstract]:With the increasingly fierce market competition, the rapid development of science and technology and the continuous improvement of the professional level of logistics, a large number of enterprises have introduced advanced logistics theory and technology into enterprise management.And logistics as an important means to improve market competitiveness and core competition level.How to optimize the vehicle routing of distribution system to reduce the logistics cost is the main research content.Vehicle Routing problem in logistics distribution is a typical NP-hard problem, and its computational time will become longer and longer with the increase of the size of the problem. The application of traditional accurate algorithm to solve the problem is more complex.Therefore, at present, most scholars mainly use intelligent optimization algorithm to solve vehicle scheduling problem.Estimation of Distribution algorithm (EDAA) is an evolutionary algorithm based on probabilistic distribution model. It has been widely concerned and developed in recent years, and has been successfully applied in many industrial development fields, and has achieved good results.Therefore, this paper mainly aims at the vehicle routing optimization problem with different constraints, and makes three improvements to it, and uses the improved algorithm to simulate to verify the effectiveness of the algorithm.First of all, aiming at the classical vehicle path optimization problem with vehicle load constraints under the total driving distance index, an appropriate coding mechanism and probability model are designed to change the traditional binary code to the decimal coding method.According to the characteristics of vehicle scheduling problem, the ordinary two-dimensional probability matrix is changed to three-dimensional matrix, that is, each vehicle corresponds to a separate two-dimensional matrix. Finally, a local search mechanism is added.An improved Estimation of Distribution algorithm is proposed to solve this problem.The simulation of the capacity constrained vehicle scheduling problem using Matlab IEDA algorithm shows that the algorithm improves the global search ability and reduces the total distribution cost, thus validates the effectiveness of the algorithm.Secondly, for the multi-model vehicle scheduling problem with random demand, the stochastic demand problem is transformed into a series of static vehicle scheduling problems by using the time-axis. In addition, the loading rate is considered as the basis for vehicle selection for the multi-vehicle model problem.The vehicle scheduling problem considering the comprehensive cost such as loading rate and fuel consumption is established.In view of the characteristics of stochastic demand multi-vehicle VRP problem, a hybrid distribution estimation algorithm is proposed based on the algorithm in the previous chapter, which combines the distributed estimation algorithm with the parallel saving algorithm.Then, an adaptive Estimation of distribution algorithm is proposed to solve the problem of low carbon vehicle scheduling with integrated cost.The mechanism of initial probabilistic model is improved so that the probabilistic model can accumulate more high quality information so that the search range of the initial algorithm can be more extensive. An adaptive updating mechanism based on information entropy is designed to update the learning rate and mutation rate.Enhance the search ability of the algorithm.
【學位授予單位】：昆明理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：U492.22

【參考文獻】

相關期刊論文 前10條

1 趙燕偉;李文;張景玲;任設東;;多車型同時取送貨問題的低碳路徑研究[J];浙江工業(yè)大學學報;2015年01期

2 許茂增;余國印;周翔;葛顯龍;;綜合成本最小的低碳車輛調(diào)度問題及算法[J];計算機集成制造系統(tǒng);2015年07期

3 李鋒;魏瑩;;求解隨機旅行時間的C-VRP問題的混合遺傳算法[J];系統(tǒng)管理學報;2014年06期

4 孟祥虎;胡蓉;錢斌;;求解帶時間窗車輛路徑問題的有效混合PBIL算法[J];系統(tǒng)工程理論與實踐;2014年10期

5 李子輝;錢斌;胡蓉;張長勝;;自適應混合EDA求解一類三階段裝配流水線調(diào)度問題[J];計算機集成制造系統(tǒng);2015年07期

6 羅鴻斌;;多車場多車型車輛調(diào)度問題的改進粒子群算法[J];計算機工程與應用;2014年07期

7 金濤;;多配送中心物流車輛調(diào)度的改進差分進化算法[J];計算機工程與應用;2014年03期

8 蹇潔;王旭;葛顯龍;;云自適應遺傳算法有能力約束的車輛調(diào)度優(yōu)化[J];重慶大學學報;2013年08期

9 張景玲;王萬良;趙燕偉;;基于沿途補貨的多配送中心動態(tài)需求VRP建模及優(yōu)化[J];計算機集成制造系統(tǒng);2013年04期

10 陳憶群;周如旗;林淑金;李志業(yè);;有車輛數(shù)限制的開放式車輛調(diào)度問題研究[J];小型微型計算機系統(tǒng);2013年03期

相關博士學位論文 前1條

1 葛顯龍;面向云配送模式的車輛調(diào)度問題及算法研究[D];重慶大學;2011年

相關碩士學位論文 前7條

1 張紅豆;基于蟻群算法的物流系統(tǒng)配送車輛路徑優(yōu)化問題研究[D];昆明理工大學;2015年

2 李文;物流配送同時取送貨低碳車輛調(diào)度模型及其QEA研究[D];浙江工業(yè)大學;2015年

3 蘇艷;帶限制條件的車輛路徑問題的現(xiàn)代啟發(fā)式算法研究[D];西安電子科技大學;2014年

4 安潔;基于MOEA/D和局部搜索策略的多目標車輛路徑規(guī)劃方法[D];西安電子科技大學;2013年

5 史春陽;同時取送貨的車輛路徑問題中的低碳研究[D];清華大學;2011年

6 陳磊;基于隨機需求的城市公交車輛調(diào)度問題的研究[D];北京交通大學;2011年

7 丁曉林;物流企業(yè)車輛調(diào)度管理系統(tǒng)的設計與實現(xiàn)[D];山東大學;2008年

，

本文編號：1727091