大規(guī)模車輛路徑問題的優(yōu)化方法研究
發(fā)布時間：2019-05-20 06:44
【摘要】：配送環(huán)節(jié)在大規(guī)模的物流網(wǎng)絡(luò)系統(tǒng)中有著重要的地位，根據(jù)國外權(quán)威數(shù)據(jù)顯示，超過一半的物流成本來自于配送環(huán)節(jié)，尤其是在大規(guī)模物流配送網(wǎng)絡(luò)中。而隨著交通線路的日趨復(fù)雜以及更高的客戶響應(yīng)需求，對科學(xué)規(guī)劃路徑也提出了很高的要求。因此，大規(guī)模車輛路徑問題的優(yōu)化研究成為合理降低物流成本的關(guān)鍵。 本文針對大規(guī)模的車輛路徑問題，考慮客戶的靜態(tài)和動態(tài)需求來研究車輛路徑問題。主要包括兩個方面：一是在考慮客戶靜態(tài)需求基礎(chǔ)上，根據(jù)客戶需求是否可以分割配送來研究車輛路徑問題的優(yōu)化方法，并基于啟發(fā)式方法求解了需求允許分割下的車輛路徑問題；二是考慮客戶隨機(jī)需求的基礎(chǔ)上，應(yīng)用馬爾科夫過程和啟發(fā)式算法來給出一對車輛實(shí)時動態(tài)路徑規(guī)劃的策略。本文的主要工作內(nèi)容和創(chuàng)新點(diǎn)如下： 首先，針對大規(guī)模配送系統(tǒng)中的客戶需求進(jìn)行客戶聚類子問題的研究，以便在每個聚類集上的車輛配送問題研究。提出了一種新的基于人工免疫系統(tǒng)的聚類算法。為了得到較好地初始解，引入自組織映射方法來生成初始抗體群；在迭代聚類算法過程中，設(shè)計(jì)了一系列優(yōu)化和控制進(jìn)化的策略，如聚類滿意度、種群規(guī)模的閾值、學(xué)習(xí)率、聚類監(jiān)測點(diǎn)和聚類評價指標(biāo)等。這些策略可以使得聚類參數(shù)閾值實(shí)現(xiàn)自適應(yīng)量化來減少用戶的主觀因素影響；并通過策略的綜合作用，來同時得到一種取得局部聚類和全局聚類的方法。最后，仿真實(shí)驗(yàn)和分析比較說明了本文方法的有效性。 其次，，考慮了靜態(tài)客戶需求下的大規(guī)模車輛路徑問題。在前一部分的研究基礎(chǔ)上，提出了一個基于人工免疫系統(tǒng)(AIS)的啟發(fā)式算法來求解車輛路徑問題。通過引入一種新的路徑覆蓋方法，設(shè)計(jì)了一種新的編碼和算法結(jié)構(gòu)。配送路徑通過先聚類后路徑的方法產(chǎn)生，并通過網(wǎng)絡(luò)更新機(jī)制來產(chǎn)生初始抗體，以機(jī)會均等下的雙向?qū)W習(xí)來擴(kuò)增抗體。進(jìn)一步，發(fā)展了同心圓建造策略來識別不同客戶類，以便形成更多的配送路徑以供選擇；而提出的兩種精英策略(AB)和(R)來去掉較差的抗體以保持配送路徑庫中路徑的多樣性。然后，再通過求解更新后路徑庫中的集合覆蓋模型，使得VRP解隨著不斷增加的路徑選擇而逐步實(shí)現(xiàn)優(yōu)化過程。最后，還設(shè)計(jì)了路徑合并策略來進(jìn)一步增加更優(yōu)的路徑。這樣，最終的VRP最優(yōu)解通過在最終路徑庫中選擇成本最優(yōu)的路徑來得到。仿真實(shí)驗(yàn)分析說明了所提算法的有效性。 第三，在考慮客戶靜態(tài)需求下，針對一類客戶需求允許分割的集成裝載問題進(jìn)行研究。分析該問題的特點(diǎn)，建立了一個雙層規(guī)劃模型來進(jìn)行描述。為求解該問題，提出了一種雙層的聚類算法，即把客戶需求進(jìn)行子聚類的算法和針對每個聚類的客戶需求，再進(jìn)行車輛配載聚類的算法。算法綜合應(yīng)用了人工免疫系統(tǒng)、啟發(fā)式規(guī)則和偽系統(tǒng)聚類算法等，逐步迭代得出整個系統(tǒng)的最優(yōu)解。最后，設(shè)計(jì)了仿真數(shù)值實(shí)驗(yàn)，并進(jìn)一步與現(xiàn)有文獻(xiàn)的研究成果進(jìn)行了比較分析，得出了所提算法性能的優(yōu)異性。 最后，對于隨機(jī)客戶需求下的車輛路徑問題，提出了一個成對合作重新規(guī)劃路徑的策略問題。該策略可以實(shí)現(xiàn)配送的一對車輛相互配合，通過兩者之間觸發(fā)有效的通訊，基于實(shí)時的客戶需求更新車輛指派，來實(shí)現(xiàn)配送中路徑重優(yōu)化的動態(tài)規(guī)劃效果。本章提出了一個雙層馬爾科夫過程來描述此策略，同時設(shè)計(jì)了啟發(fā)式算法來根據(jù)實(shí)時信息動態(tài)改變車輛的訪問順序以及車輛的指派方案。仿真數(shù)值實(shí)驗(yàn)同樣證明：本章方法與最新的文獻(xiàn)研究成果相比較，所提算法顯示出了較好的效果，有著20%-30%的成本節(jié)約。
[Abstract]:The distribution link plays an important role in the large-scale logistics network system. According to the foreign authoritative data, more than half of the logistics cost is from the distribution link, especially in the large-scale logistics distribution network. Along with the increasing complexity of the traffic line and the higher customer response, the scientific planning path has also made a very high request. Therefore, the optimization of the large-scale vehicle routing problem becomes the key to the reasonable reduction of the logistics cost. In view of the problem of large-scale vehicle routing, this paper studies the vehicle path by considering the customer's static and dynamic demand The paper mainly includes two aspects: one is to study the optimization method of the vehicle path problem based on the customer's static demand and whether the customer's demand can be divided and distributed, and the method is based on the heuristic method to solve the problem of the vehicle's path. The second is to use the Markov process and the heuristic algorithm to give the idea of the real-time dynamic path planning of a pair of vehicles on the basis of the stochastic demand of the customers. The main contents and innovation points of this paper are as follows: Next: First, a study of the customer's sub-questions for the customer's needs in a large-scale distribution system is carried out in order to ask for the distribution of the vehicles on each cluster In this paper, a new model of artificial immune system based on artificial immune system is proposed. In order to get a better initial solution, the self-organizing mapping method is introduced to generate the initial antibody population. In the iterative clustering algorithm, a series of strategies to optimize and control the evolution, such as the cluster satisfaction, the threshold of population size, the learning rate, the cluster monitoring points and the clustering evaluation, are designed. The strategy can make the clustering parameter threshold realize the self-adaptive quantization to reduce the influence of the user's subjective factors, and simultaneously obtain a local clustering and global clustering through the comprehensive action of the strategy. Finally, the simulation experiment and the analysis show the method in this paper. Effectiveness. Second, a large-scale vehicle under static customer needs is considered In this paper, a heuristic algorithm based on artificial immune system (AIS) is proposed to solve the vehicle routing problem. A new method of path coverage is introduced to design a new code. and a network updating mechanism is adopted to generate the initial antibody, so that the two-way learning under the equal opportunity Further, a concentric construction strategy is developed to identify different customer classes in order to form more distribution paths for selection; the proposed two elite strategies (AB) and (R) are used to remove the poor antibodies in order to maintain the distribution path library middle Diversity of the path. Then, by solving the set overlay model in the updated path library, the VRP solution is gradually augmented with the increasing path selection the process is now optimized. Finally, a path merge policy is also designed to further increase A better path. In this way, the final VRP best solution is optimized by selecting the cost in the final path library The path is obtained. The simulation results show that the proposed method The effectiveness of the method. Third, under consideration of the customer's static demand, an integrated package that allows segmentation for a class of customer needs The problem is studied. The characteristics of the problem are analyzed and a two-layer plan is established. The model is described. In order to solve the problem, a double-layer clustering algorithm is proposed, that is, the algorithm of sub-clustering and the customer demand for each cluster are carried out, and then the vehicle In this paper, the artificial immune system, the heuristic rule and the pseudo-system clustering algorithm are applied to the algorithm. In the end, the simulation numerical experiment is designed and compared with the research results of the existing literature, and the calculated results are obtained. In the end, a pair of cooperation is proposed to solve the problem of vehicle routing under the demand of the random customer. the strategy of the planning path is that a pair of vehicles distributed can be matched with each other, an effective communication is triggered between the two vehicles, the vehicle assignment is updated based on the real-time client demand, and the route weight in the distribution is realized In this chapter, a double-layer Markov process is proposed to describe this strategy, and a heuristic algorithm is designed to dynamically change the access sequence of the vehicle according to the real-time information The simulation results also show that the method of this chapter is compared with the latest literature research results, and the proposed algorithm shows a good effect, with 20%.
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：U116.2;F252
[Abstract]:The distribution link plays an important role in the large-scale logistics network system. According to the foreign authoritative data, more than half of the logistics cost is from the distribution link, especially in the large-scale logistics distribution network. Along with the increasing complexity of the traffic line and the higher customer response, the scientific planning path has also made a very high request. Therefore, the optimization of the large-scale vehicle routing problem becomes the key to the reasonable reduction of the logistics cost. In view of the problem of large-scale vehicle routing, this paper studies the vehicle path by considering the customer's static and dynamic demand The paper mainly includes two aspects: one is to study the optimization method of the vehicle path problem based on the customer's static demand and whether the customer's demand can be divided and distributed, and the method is based on the heuristic method to solve the problem of the vehicle's path. The second is to use the Markov process and the heuristic algorithm to give the idea of the real-time dynamic path planning of a pair of vehicles on the basis of the stochastic demand of the customers. The main contents and innovation points of this paper are as follows: Next: First, a study of the customer's sub-questions for the customer's needs in a large-scale distribution system is carried out in order to ask for the distribution of the vehicles on each cluster In this paper, a new model of artificial immune system based on artificial immune system is proposed. In order to get a better initial solution, the self-organizing mapping method is introduced to generate the initial antibody population. In the iterative clustering algorithm, a series of strategies to optimize and control the evolution, such as the cluster satisfaction, the threshold of population size, the learning rate, the cluster monitoring points and the clustering evaluation, are designed. The strategy can make the clustering parameter threshold realize the self-adaptive quantization to reduce the influence of the user's subjective factors, and simultaneously obtain a local clustering and global clustering through the comprehensive action of the strategy. Finally, the simulation experiment and the analysis show the method in this paper. Effectiveness. Second, a large-scale vehicle under static customer needs is considered In this paper, a heuristic algorithm based on artificial immune system (AIS) is proposed to solve the vehicle routing problem. A new method of path coverage is introduced to design a new code. and a network updating mechanism is adopted to generate the initial antibody, so that the two-way learning under the equal opportunity Further, a concentric construction strategy is developed to identify different customer classes in order to form more distribution paths for selection; the proposed two elite strategies (AB) and (R) are used to remove the poor antibodies in order to maintain the distribution path library middle Diversity of the path. Then, by solving the set overlay model in the updated path library, the VRP solution is gradually augmented with the increasing path selection the process is now optimized. Finally, a path merge policy is also designed to further increase A better path. In this way, the final VRP best solution is optimized by selecting the cost in the final path library The path is obtained. The simulation results show that the proposed method The effectiveness of the method. Third, under consideration of the customer's static demand, an integrated package that allows segmentation for a class of customer needs The problem is studied. The characteristics of the problem are analyzed and a two-layer plan is established. The model is described. In order to solve the problem, a double-layer clustering algorithm is proposed, that is, the algorithm of sub-clustering and the customer demand for each cluster are carried out, and then the vehicle In this paper, the artificial immune system, the heuristic rule and the pseudo-system clustering algorithm are applied to the algorithm. In the end, the simulation numerical experiment is designed and compared with the research results of the existing literature, and the calculated results are obtained. In the end, a pair of cooperation is proposed to solve the problem of vehicle routing under the demand of the random customer. the strategy of the planning path is that a pair of vehicles distributed can be matched with each other, an effective communication is triggered between the two vehicles, the vehicle assignment is updated based on the real-time client demand, and the route weight in the distribution is realized In this chapter, a double-layer Markov process is proposed to describe this strategy, and a heuristic algorithm is designed to dynamically change the access sequence of the vehicle according to the real-time information The simulation results also show that the method of this chapter is compared with the latest literature research results, and the proposed algorithm shows a good effect, with 20%.
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：U116.2;F252
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 曹二保;賴明勇;張漢江;;模糊需求車輛路徑問題研究[J];系統(tǒng)工程;2007年11期
2 唐連生;梁劍;;突發(fā)事件下的車輛路徑問題研究綜述[J];鐵道運(yùn)輸與經(jīng)濟(jì);2008年12期
3 劉紅梅;陳楊;;車輛路徑問題的形式化方法研究[J];科技資訊;2008年05期
4 徐俊杰;;利用微正則退火算法求解車輛路徑問題[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2009年02期
5 寧曉利;;車輛路徑問題的組合優(yōu)化算法[J];物流技術(shù);2009年06期
6 黃敏芳;胡祥培;王征;Amy Z. Zeng;;車輛路徑問題的三階段求解方法研究[J];管理科學(xué);2009年03期
7 孫中悅;關(guān)忠良;范高賢;;面向?qū)ο蟮能囕v路徑問題仿真研究[J];物流技術(shù);2010年07期
8 李琳;劉濤;;帶收益的車輛路徑問題研究綜述[J];沈陽航空工業(yè)學(xué)院學(xué)報(bào);2010年05期
9 王科峰;葉春明;唐國春;;節(jié)點(diǎn)具有雙重需求的車輛路徑問題及其性質(zhì)[J];系統(tǒng)科學(xué)與數(shù)學(xué);2011年10期
10 謝秉磊;胡小明;張一U
本文編號：2481444
本文鏈接：http://sikaile.net/kejilunwen/jiaotonggongchenglunwen/2481444.html
最近更新
教材專著
