基于逐次确定换班机会集的乘务调度列生成方法

发布时间：2018-04-10 20:48

本文选题：乘务调度 + 换班机会　；参考：《计算机集成制造系统》2017年01期

【摘要】：传统列生成方法在求解乘务调度问题时,由于搜索二叉树的节点数呈指数级增长使其难以解决大规模问题。为避免搜索整个树节点,提出一种逐次缩小问题规模的迭代优化方法。针对乘务调度问题提出带有换班机会选择的最小费用网络流模型。利用Dantzig-Wolfe分解原理,将该模型转化为带有换班机会选择的集覆盖模型,并采取列生成方法求解其线性松弛解,以得到原问题的下界。在求解整数解时,利用线性松弛解信息,逐次确定不被使用的换班机会集,将问题转化为一系列规模逐次缩小的乘务调度问题。对城市公交中的多组乘务调度实例进行计算,将结果与问题下界和常用遗传算法的结果进行比较,表明大多数实例都能在合理的时间内取得最优解或近优解。
[Abstract]:In the traditional column generation method, it is difficult to solve the large-scale problem because the number of nodes in the binary tree is increasing exponentially.In order to avoid searching the whole tree node, an iterative optimization method is proposed to reduce the scale of the problem one by one.A minimum cost network flow model with shift opportunity selection is proposed for the crew scheduling problem.By using the Dantzig-Wolfe decomposition principle, the model is transformed into a set covering model with shift opportunity selection, and the linear relaxation solution is solved by column generation method, and the lower bound of the original problem is obtained.In order to solve the integer solution, the information of linear relaxation solution is used to determine the unused commutation opportunity set step by step, and the problem is transformed into a series of reduced scale crew scheduling problems.In this paper, the author computes several groups of bus crew scheduling examples, and compares the results with the lower bound of the problem and the results of common genetic algorithms. The results show that most of the examples can obtain the optimal solution or near optimal solution in a reasonable time.
【作者单位】：湖北文理学院数学与计算机学院;
【基金】：国家自然科学基金资助项目(71501064) 湖北省自然科学基金计划青年基金资助项目(2014CFB640)~~
【分类号】：U492.22

【相似文献】