本文選題：公共交通 + 乘務(wù)調(diào)度��； 參考：《華中科技大學(xué)》2016年博士論文

【摘要】：隨著我國(guó)城市化和機(jī)動(dòng)化進(jìn)程迅猛發(fā)展,道路擁堵等問(wèn)題日益嚴(yán)重,城市交通面臨嚴(yán)峻挑戰(zhàn),優(yōu)先發(fā)展公共交通勢(shì)在必行,如何建設(shè)和管理現(xiàn)代化的公共交通系統(tǒng)已成為我國(guó)經(jīng)濟(jì)社會(huì)發(fā)展中亟待解決的重大理論和現(xiàn)實(shí)問(wèn)題。在公共交通規(guī)劃與運(yùn)營(yíng)中,乘務(wù)調(diào)度與輪班問(wèn)題是關(guān)鍵問(wèn)題,決定了乘務(wù)員的工作方案,有效方案可以提高公共交通運(yùn)營(yíng)效率,降低運(yùn)營(yíng)成本,保障乘務(wù)員真正享受?chē)?guó)家勞動(dòng)法賦予的權(quán)益。它包含兩個(gè)順序執(zhí)行的子問(wèn)題：乘務(wù)調(diào)度問(wèn)題和乘務(wù)輪班問(wèn)題,其中前者是后者的基礎(chǔ),它們是NP難問(wèn)題,其復(fù)雜性主要在于大規(guī)模、多目標(biāo)、特別是有一系列復(fù)雜多樣的勞動(dòng)法規(guī)約束。因此,研制高效的求解算法具有十分重要的現(xiàn)實(shí)意義和理論意義。目前,智能優(yōu)化方法是主要求解方法類(lèi)別之一,但是問(wèn)題的高度復(fù)雜性使得對(duì)該類(lèi)算法的研究仍有很大發(fā)展空間,其中,深刻理解問(wèn)題的領(lǐng)域知識(shí)并將其融入算法設(shè)計(jì)中是算法設(shè)計(jì)的關(guān)鍵和難點(diǎn),需要深入研究。此外,乘務(wù)調(diào)度問(wèn)題中的班次評(píng)價(jià)是一個(gè)復(fù)雜多屬性決策問(wèn)題,是很多乘務(wù)調(diào)度方法的基礎(chǔ),然而現(xiàn)有的多屬性決策班次評(píng)價(jià)方法研究很少。針對(duì)以上問(wèn)題,本文首先從不同角度研制了四種乘務(wù)調(diào)度方法,其中,研制了兩種多屬性決策班次評(píng)價(jià)方法,隨后研制了兩種多目標(biāo)乘務(wù)輪班方法,具體如下：提出了一種自適應(yīng)演化乘務(wù)調(diào)度方法,它定義了一個(gè)新的染色體表示方法,具有直觀(guān)、短小,允許表達(dá)非可行乘務(wù)方案的特點(diǎn),其初始長(zhǎng)度是專(zhuān)門(mén)設(shè)計(jì)為最優(yōu)班次總數(shù)的下界,有助于保證和分析解的質(zhì)量,設(shè)計(jì)了帶增補(bǔ)和刪除策略的交叉和變異操作,使得染色體長(zhǎng)度能夠在算法迭代過(guò)程中自適應(yīng)地增大或減小,實(shí)驗(yàn)表明算法的計(jì)算速度快、求解質(zhì)量高。提出了灰關(guān)聯(lián)分析(Grey Relational Analysis, GRA)班次評(píng)價(jià)方法。為了確定GRA班次評(píng)價(jià)方法中的最優(yōu)參數(shù),進(jìn)一步提出了一種基于GRA的演化乘務(wù)調(diào)度算法(Evolutionary crew scheduling algorithm based on GRA, EGRA),最優(yōu)調(diào)度方案會(huì)隨著這些參數(shù)相應(yīng)得到。EGRA是一種專(zhuān)門(mén)設(shè)計(jì)的嵌入快速局部搜索的混合遺傳算法,其中的局部搜索是精致設(shè)計(jì)的,用以提升算法的集中性,實(shí)驗(yàn)測(cè)試說(shuō)明了EGRA的優(yōu)越性。提出了基于GRA的變迭代貪婪乘務(wù)調(diào)度方法(Variable Iterated Greedy crew scheduling approach based on GRA, GRAVIG), GRAVIG裁剪了變迭代貪婪算法(Variable Iterated Greedy, VIG)求解乘務(wù)調(diào)度問(wèn)題,其中嵌入了GRA班次評(píng)價(jià)方法作為調(diào)度過(guò)程中班次評(píng)價(jià)的求解器,較大地提升了VIG的搜索能力,此外,還精心設(shè)計(jì)了一種基于偏向概率的破壞階段,它能夠使得“好的”班次可以保留在方案中,同時(shí)又不丟失隨機(jī)性。實(shí)驗(yàn)測(cè)試結(jié)果表明該方法是有效的。提出了逼近理想解排序(TOPSIS)班次評(píng)價(jià)方法。同時(shí)設(shè)計(jì)了變鄰域搜索乘務(wù)調(diào)度方法(Variable Neighbourhood Search crew scheduling approach, VNS), VNS裁剪了變鄰域搜索算法求解乘務(wù)調(diào)度問(wèn)題,其中,設(shè)計(jì)了兩種帶概率的復(fù)合鄰域結(jié)構(gòu),極大地增大了搜索空間的多樣性。在VNS中嵌入了TOPSIS方法以作為調(diào)度過(guò)程中班次評(píng)價(jià)的求解器,較大地提升了VNS的搜索能力,在VNS中還嵌入了模擬退火算法(Simulated Annealing, SA)以進(jìn)行有效的局部探索,最后實(shí)驗(yàn)測(cè)試結(jié)果表明方法的有效性。提出了兩種多目標(biāo)乘務(wù)輪班方法,即模擬退火乘務(wù)輪班方法(Multi-Objective SA crew rostering approach, MOSA)和變鄰域搜索乘務(wù)輪班方法(multi-objective Variable Neighbourhood Search crew rostering approach, VNS),它們使用了兩種評(píng)價(jià)接受函數(shù)來(lái)更好地處理用戶(hù)偏好。在MOSA中,首先設(shè)計(jì)了一個(gè)啟發(fā)式來(lái)構(gòu)建初始解,接著設(shè)計(jì)了一個(gè)基于SA的可行性修復(fù)算法來(lái)使該解可行,最后,設(shè)計(jì)了一個(gè)基于SA的非支配解生成算法來(lái)獲得非支配解。其中,設(shè)計(jì)了增量評(píng)價(jià)策略,鄰域切割技術(shù)和偏向精英解重啟策略以分別提升計(jì)算速度和搜索能力；在VNS中設(shè)計(jì)了兩種復(fù)合鄰域結(jié)構(gòu),每一個(gè)分別對(duì)應(yīng)一個(gè)目標(biāo),它們?cè)赩NS中依次執(zhí)行,在每個(gè)鄰域結(jié)構(gòu)中以SA作為局部搜索的求解器,此外,還專(zhuān)門(mén)設(shè)計(jì)了一種解的改進(jìn)接受準(zhǔn)則以提升VNS的搜索能力。最后實(shí)驗(yàn)結(jié)果說(shuō)明了這些方法的有效性。
[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.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：U492.22;TP18
，

本文編號(hào)：2110372