基于智能优化的乘务调度与轮班问题研究

发布时间：2018-07-09 19:08

  本文选题：公共交通 + 乘务调度　； 参考：《华中科技大学》2016年博士论文

【摘要】：随着我国城市化和机动化进程迅猛发展,道路拥堵等问题日益严重,城市交通面临严峻挑战,优先发展公共交通势在必行,如何建设和管理现代化的公共交通系统已成为我国经济社会发展中亟待解决的重大理论和现实问题。在公共交通规划与运营中,乘务调度与轮班问题是关键问题,决定了乘务员的工作方案,有效方案可以提高公共交通运营效率,降低运营成本,保障乘务员真正享受国家劳动法赋予的权益。它包含两个顺序执行的子问题：乘务调度问题和乘务轮班问题,其中前者是后者的基础,它们是NP难问题,其复杂性主要在于大规模、多目标、特别是有一系列复杂多样的劳动法规约束。因此,研制高效的求解算法具有十分重要的现实意义和理论意义。目前,智能优化方法是主要求解方法类别之一,但是问题的高度复杂性使得对该类算法的研究仍有很大发展空间,其中,深刻理解问题的领域知识并将其融入算法设计中是算法设计的关键和难点,需要深入研究。此外,乘务调度问题中的班次评价是一个复杂多属性决策问题,是很多乘务调度方法的基础,然而现有的多属性决策班次评价方法研究很少。针对以上问题,本文首先从不同角度研制了四种乘务调度方法,其中,研制了两种多属性决策班次评价方法,随后研制了两种多目标乘务轮班方法,具体如下：提出了一种自适应演化乘务调度方法,它定义了一个新的染色体表示方法,具有直观、短小,允许表达非可行乘务方案的特点,其初始长度是专门设计为最优班次总数的下界,有助于保证和分析解的质量,设计了带增补和删除策略的交叉和变异操作,使得染色体长度能够在算法迭代过程中自适应地增大或减小,实验表明算法的计算速度快、求解质量高。提出了灰关联分析(Grey Relational Analysis, GRA)班次评价方法。为了确定GRA班次评价方法中的最优参数,进一步提出了一种基于GRA的演化乘务调度算法(Evolutionary crew scheduling algorithm based on GRA, EGRA),最优调度方案会随着这些参数相应得到。EGRA是一种专门设计的嵌入快速局部搜索的混合遗传算法,其中的局部搜索是精致设计的,用以提升算法的集中性,实验测试说明了EGRA的优越性。提出了基于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),它们使用了两种评价接受函数来更好地处理用户偏好。在MOSA中,首先设计了一个启发式来构建初始解,接着设计了一个基于SA的可行性修复算法来使该解可行,最后,设计了一个基于SA的非支配解生成算法来获得非支配解。其中,设计了增量评价策略,邻域切割技术和偏向精英解重启策略以分别提升计算速度和搜索能力；在VNS中设计了两种复合邻域结构,每一个分别对应一个目标,它们在VNS中依次执行,在每个邻域结构中以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