發(fā)布時間：2018-07-09 19:08

  本文選題：公共交通 + 乘務調度��； 參考：《華中科技大學》2016年博士論文

【摘要】：隨著我國城市化和機動化進程迅猛發(fā)展,道路擁堵等問題日益嚴重,城市交通面臨嚴峻挑戰(zhàn),優(yōu)先發(fā)展公共交通勢在必行,如何建設和管理現(xiàn)代化的公共交通系統(tǒng)已成為我國經(jīng)濟社會發(fā)展中亟待解決的重大理論和現(xiàn)實問題。在公共交通規(guī)劃與運營中,乘務調度與輪班問題是關鍵問題,決定了乘務員的工作方案,有效方案可以提高公共交通運營效率,降低運營成本,保障乘務員真正享受國家勞動法賦予的權益。它包含兩個順序執(zhí)行的子問題：乘務調度問題和乘務輪班問題,其中前者是后者的基礎,它們是NP難問題,其復雜性主要在于大規(guī)模、多目標、特別是有一系列復雜多樣的勞動法規(guī)約束。因此,研制高效的求解算法具有十分重要的現(xiàn)實意義和理論意義。目前,智能優(yōu)化方法是主要求解方法類別之一,但是問題的高度復雜性使得對該類算法的研究仍有很大發(fā)展空間,其中,深刻理解問題的領域知識并將其融入算法設計中是算法設計的關鍵和難點,需要深入研究。此外,乘務調度問題中的班次評價是一個復雜多屬性決策問題,是很多乘務調度方法的基礎,然而現(xiàn)有的多屬性決策班次評價方法研究很少。針對以上問題,本文首先從不同角度研制了四種乘務調度方法,其中,研制了兩種多屬性決策班次評價方法,隨后研制了兩種多目標乘務輪班方法,具體如下：提出了一種自適應演化乘務調度方法,它定義了一個新的染色體表示方法,具有直觀、短小,允許表達非可行乘務方案的特點,其初始長度是專門設計為最優(yōu)班次總數(shù)的下界,有助于保證和分析解的質量,設計了帶增補和刪除策略的交叉和變異操作,使得染色體長度能夠在算法迭代過程中自適應地增大或減小,實驗表明算法的計算速度快、求解質量高。提出了灰關聯(lián)分析(Grey Relational Analysis, GRA)班次評價方法。為了確定GRA班次評價方法中的最優(yōu)參數(shù),進一步提出了一種基于GRA的演化乘務調度算法(Evolutionary crew scheduling algorithm based on GRA, EGRA),最優(yōu)調度方案會隨著這些參數(shù)相應得到。EGRA是一種專門設計的嵌入快速局部搜索的混合遺傳算法,其中的局部搜索是精致設計的,用以提升算法的集中性,實驗測試說明了EGRA的優(yōu)越性。提出了基于GRA的變迭代貪婪乘務調度方法(Variable Iterated Greedy crew scheduling approach based on GRA, GRAVIG), GRAVIG裁剪了變迭代貪婪算法(Variable Iterated Greedy, VIG)求解乘務調度問題,其中嵌入了GRA班次評價方法作為調度過程中班次評價的求解器,較大地提升了VIG的搜索能力,此外,還精心設計了一種基于偏向概率的破壞階段,它能夠使得“好的”班次可以保留在方案中,同時又不丟失隨機性。實驗測試結果表明該方法是有效的。提出了逼近理想解排序(TOPSIS)班次評價方法。同時設計了變鄰域搜索乘務調度方法(Variable Neighbourhood Search crew scheduling approach, VNS), VNS裁剪了變鄰域搜索算法求解乘務調度問題,其中,設計了兩種帶概率的復合鄰域結構,極大地增大了搜索空間的多樣性。在VNS中嵌入了TOPSIS方法以作為調度過程中班次評價的求解器,較大地提升了VNS的搜索能力,在VNS中還嵌入了模擬退火算法(Simulated Annealing, SA)以進行有效的局部探索,最后實驗測試結果表明方法的有效性。提出了兩種多目標乘務輪班方法,即模擬退火乘務輪班方法(Multi-Objective SA crew rostering approach, MOSA)和變鄰域搜索乘務輪班方法(multi-objective Variable Neighbourhood Search crew rostering approach, VNS),它們使用了兩種評價接受函數(shù)來更好地處理用戶偏好。在MOSA中,首先設計了一個啟發(fā)式來構建初始解,接著設計了一個基于SA的可行性修復算法來使該解可行,最后,設計了一個基于SA的非支配解生成算法來獲得非支配解。其中,設計了增量評價策略,鄰域切割技術和偏向精英解重啟策略以分別提升計算速度和搜索能力；在VNS中設計了兩種復合鄰域結構,每一個分別對應一個目標,它們在VNS中依次執(zhí)行,在每個鄰域結構中以SA作為局部搜索的求解器,此外,還專門設計了一種解的改進接受準則以提升VNS的搜索能力。最后實驗結果說明了這些方法的有效性。
[Abstract]:With the rapid development of urbanization and motorization in China, road congestion and other problems are becoming more and more serious. Urban traffic is facing severe challenges. It is imperative to give priority to the development of public transport. How to build and manage the modern public transport system has become a major theoretical and practical problem to be solved in the economic and social development of our country. In planning and operation, the problem of crew scheduling and shift is the key problem, which determines the work plan of the crew. The effective scheme can improve the operation efficiency of the public transportation, reduce the operating cost, and ensure that the crew really enjoy the rights and interests given by the national labor law. It contains two sub problems in order to be carried out in order: the scheduling problem and the crew shift. The former is the basis of the latter. They are NP difficult problems, and their complexity mainly lies in large-scale and multi-objective constraints. In particular, there are a series of complex and diverse labor laws and regulations. Therefore, it is of great practical and theoretical significance to develop an efficient solution algorithm. At present, the intelligent optimization method is one of the main solving methods. However, the high complexity of the problem makes a lot of space for the research of this kind of algorithm, in which it is a key and difficult point to deeply understand the domain knowledge of the problem and integrate it into the algorithm design. In addition, the class evaluation in the scheduling problem is a complex multi attribute decision problem, and it is a large number of problems. The basis of the crew scheduling method, however, there are few studies on the existing multi attribute decision making method. In this paper, four kinds of scheduling methods are developed from different angles. In this paper, two multi attribute decision class evaluation methods are developed, and then two multi target crew shift methods are developed. The following is the following: An adaptive evolutionary traffic scheduling method, which defines a new method of chromosome representation, is intuitive, short, and allows the expression of the non feasible traffic scheme. Its initial length is specially designed to be the lower bound of the total number of the best classes. It helps to guarantee and analyze the quality of the solution, and designs the crossover and mutation with the supplemental and deleting strategies. The operation makes the chromosome length increase or decrease adaptively in the iterative process of the algorithm. The experiment shows that the calculation speed is fast and the quality of the solution is high. The Grey Relational Analysis (GRA) class evaluation method is proposed. In order to determine the optimal parameter in the GRA class evaluation method, a kind of GRA based on the method is proposed. The evolutionary multiplication scheduling algorithm (Evolutionary crew scheduling algorithm based on GRA, EGRA), the optimal scheduling scheme will get.EGRA as a specially designed embedded fast local search hybrid genetic algorithm. The local search is refined and designed to improve the centrality of the algorithm. Experimental test says The superiority of EGRA is clear. A variable iterative greedy scheduling method based on GRA (Variable Iterated Greedy crew scheduling approach based on GRA, GRAVIG) is proposed, and the variable iterative greedy algorithm is tailored to solve the problem of traffic scheduling, which is embedded in the scheduling process as a scheduling process. The middle class evaluation solver greatly improves the search ability of VIG. In addition, a failure phase based on bias probability is designed carefully. It can make the "good" class can be retained in the scheme without losing the randomness. The experimental results show that the method is effective. The approximation of the ideal solution is proposed (TOPSIS At the same time, a variable neighborhood search multiplying scheduling method (Variable Neighbourhood Search crew scheduling approach, VNS) is designed, and VNS cuts the variable neighborhood search algorithm to solve the multiplying scheduling problem. In this, two kinds of complex neighborhood structures with probability are designed, which greatly increases the diversity of the search space. The TOPSIS method is used as the solver of the class evaluation in the scheduling process, which greatly improves the search ability of VNS. The simulated annealing algorithm (Simulated Annealing, SA) is also embedded in VNS for effective local exploration. Finally, the experimental results show the effectiveness of the method. Two kinds of multi target crew shift methods, that is, are put forward. The Multi-Objective SA crew rostering approach (MOSA) and the variable neighborhood search crew shift method (multi-objective Variable Neighbourhood Search crew rostering) use two kinds of evaluation acceptance functions to better handle user preferences. In order to construct the initial solution, a feasibility repair algorithm based on SA is designed to make the solution feasible. Finally, a non dominated solution generation algorithm based on SA is designed to obtain non dominant solutions. Among them, the incremental evaluation strategy is designed, the neighborhood cutting technique and the elite solution reboot strategy are used to improve the computing speed and the search ability respectively. In VNS, two complex neighborhood structures are designed, each of which corresponds to one target, they are executed in VNS, and SA is used as a solver for local search in each neighborhood structure. In addition, an improved acceptance criterion for the solution is designed to improve the search capability of VNS. Finally, the experimental results show the effectiveness of these methods. Sex.
【學位授予單位】：華中科技大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：U492.22;TP18
，

本文編號：2110372