【摘要】：物流作為企業(yè)的“第三利潤源泉”,已經(jīng)受到人們的廣泛關(guān)注,配送是物流系統(tǒng)中的重要環(huán)節(jié),占物流成本的50%以上,作為物流配送環(huán)節(jié)的核心問題,車輛路徑問題自提出以來,就成為物流配送、運籌學、組合優(yōu)化等領域的熱點問題。合理規(guī)劃配送路線不僅能夠有效的降低物流配送成本,增加企業(yè)效益,而且還能提高服務質(zhì)量,增加顧客滿意度。因此,對車輛路徑問題的研究具有重要的實用價值和科學意義。車輛路徑問題往往具有多個互相制約的目標,是個典型的多目標優(yōu)化問題,但是應用傳統(tǒng)的解決多目標優(yōu)化問題的方法很難收斂到Pareto最優(yōu)解集,因此本文將從多目標角度對車輛路徑問題的模型和算法進行研究。本文主要研究兩類車輛路徑問題：帶時間窗的車輛路徑問題以及帶模糊時間窗的開放式車輛路徑問題,建立多目標數(shù)學模型,并設計不同的多目標進化算法對兩模型進行求解。本文主要研究內(nèi)容如下：(1)帶時間窗車輛路徑問題。本文建立以最小化行駛路程和最小化使用車輛數(shù)量為目標的多目標數(shù)學模型,并提出一種多目標混合差分進化算法進行求解。算法采用了自然數(shù)編碼機制,并重新定義新的個體生成方法；通過引入Pareto支配的概念來評價個體的優(yōu)劣性,并采用擂臺法則構(gòu)造非支配集。在進化過程中,以差分進化算法為求解主體,通過引入雙種群機制和變鄰域下降搜索策略,有效平衡的種群在解空間的全局探索能力和局部開發(fā)能力,以提高算法搜索效率。實驗結(jié)果表明多目標混合差分進化算法是求解帶時間窗車輛路徑問題的有效算法。(2)帶模糊時間窗的開放式車輛路徑問題。本文考慮了車輛容量約束和車輛最大行駛里程約束,建立以最小化總成本和最大化顧客滿意度為目標的多目標數(shù)學模型,并提出一種多目標混合遺傳算法進行求解。算法采用自然數(shù)編碼機制,使用混合方法構(gòu)造初始種群以及適合本文問題的遺傳算子,在進化過程中嵌入一種執(zhí)行模擬退火機制的基于meta-Lamarckian學習策略的局部搜索算法,同時去除重復個體,提高算法的局部開發(fā)能力,運用擂臺法則構(gòu)造非支配解集,降低算法時間復雜度,使用調(diào)和平均距離方法評價個體的擁擠程度,提高非支配集的分布性。實驗結(jié)果表明該算法能夠有效求解帶模糊時間窗的開放式車輛路徑問題,并且與NSGA-Ⅱ算法的對比結(jié)果也驗證了該算法在Pareto解的數(shù)量、解的分布性以及收斂性等方面都具有明顯的優(yōu)勢。本文將兩類車輛路徑問題都作為多目標優(yōu)化問題進行研究,在求解過程中不需要引入偏好,同等的考慮模型中的求解目標,通過設計多目標進化算法進行求解,獲得一組非支配解,有利于物流決策者根據(jù)不同的實際需求選擇不同的決策方案。
[Abstract]:As the "third profit source" of enterprises, logistics has been widely concerned by people. Distribution is an important link in logistics system, accounting for more than 50% of the logistics cost, as the core issue of logistics distribution. Since the vehicle routing problem was proposed, it has become a hot issue in the fields of logistics distribution, operational research, combination optimization and so on. Reasonable planning of distribution routes can not only effectively reduce the cost of logistics distribution, increase the efficiency of enterprises, but also improve the quality of service and customer satisfaction. Therefore, the study of vehicle routing problem has important practical value and scientific significance. The vehicle routing problem is a typical multi-objective optimization problem because it has many mutually restricted objectives. However, it is difficult to converge to the Pareto optimal solution set by applying the traditional method to solve the multi-objective optimization problem. So this paper will study the model and algorithm of vehicle routing problem from multi-objective point of view. In this paper, two kinds of vehicle routing problems are studied: the vehicle routing problem with time window and the open vehicle routing problem with fuzzy time window. The multi-objective mathematical model is established, and different multi-objective evolutionary algorithms are designed to solve the two models. The main contents of this paper are as follows: (1) vehicle routing problem with time window. In this paper, a multi-objective mathematical model with the objective of minimizing the travel distance and minimizing the number of vehicles used is established, and a multi-objective hybrid differential evolutionary algorithm is proposed to solve the problem. The algorithm adopts the encoding mechanism of natural numbers and redefines the new method of individual generation. The concept of Pareto domination is introduced to evaluate the superiority and inferiority of individuals and the non-dominated set is constructed by using the ring rule. In the course of evolution, the differential evolution algorithm is used as the main solution. By introducing the dual population mechanism and variable neighborhood descent search strategy, the global exploration ability and local development ability of the population in the solution space can be effectively balanced, so as to improve the search efficiency of the algorithm. Experimental results show that the multi-objective hybrid differential evolution algorithm is an effective algorithm for solving vehicle routing problems with time windows. (2) Open vehicle routing problems with fuzzy time windows. Considering vehicle capacity constraints and vehicle maximum mileage constraints, a multi-objective mathematical model with the goal of minimizing total cost and maximizing customer satisfaction is established, and a multi-objective hybrid genetic algorithm is proposed to solve the problem. The algorithm adopts the natural number coding mechanism, uses the hybrid method to construct the initial population and genetic operators suitable for the problem in this paper, and embed a local search algorithm based on meta-Lamarckian learning strategy in the evolution process. At the same time, the repetitive individuals are removed, the local development ability of the algorithm is improved, the non-dominated solution set is constructed by using the ring law, the time complexity of the algorithm is reduced, the method of harmonic average distance is used to evaluate the crowding degree of the individual, and the distribution of the non-dominated set is improved. Experimental results show that the algorithm can effectively solve the open vehicle routing problem with fuzzy time window, and the comparison with NSGA- 鈪，

本文編號：2312254