An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem

The Multiple Depot Crew Scheduling Problem (MD-CSP) appears in public transit systems (e.g., airline, bus and railway industry) and consists of determining the optimal duties for a set of crews (or vehicles) split among several depots in order to cover a set of timetabled trips satisfying a number of constraints. We consider the case in which every crew must return to the starting depot and limits are imposed on both the elapsed time and the working time of any duty. The MD-CSP is an extension of both the Multiple Depot Vehicle Scheduling Problem (MD-VSP) and the single depot Crew Scheduling Problem (CSP). The MD-CSP is formulated as a set partitioning problem with side constraints (SP), where each column corresponds to a feasible duty. In this paper we extend to the MD-CSP the exact method used by Bianco, Mingozzi and Ricciardelli (1994) for MD-VSP and that used by Mingozzi et al. (1999) for the CSP. We also introduce a new bounding procedure based on Lagrangian relaxation and column generation which can deal with the MD-CSP constraints. The computational results for both random and real-world test problems from the literature show that the new exact procedure outperforms, on the test problems used, other exact methods proposed in the literature for the MD-VSP and the CSP.     

Best Practice Simulated Annealing for the Airline Crew Scheduling Problem

We report about a study of a simulated annealing algorithm for the airline crew pairing problem based on a run-cutting formulation. Computational results are reported for some real-world short- to medium-haul test problems with up to 4600 flights per month. Furthermore we find that run time can be saved and solution quality can be improved by using a problem specific initial solution, by relaxing constraints as far as possible, by combining simulated annealing with a problem specific local improvement heuristic and by multiple independent runs.     

The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies

In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits.     

Airline Crew Scheduling: State-of-the-Art

The airline industry is faced with some of the largest scheduling problems of any industry. The crew scheduling problem involves the optimal allocation of crews to flights. Over the last two decades the magnitude and complexity of crew scheduling problems have grown enormously and airlines are relying more on automated mathematical procedures as a practical necessity. In this paper we survey different approaches studied and discuss the state-of-the-art in solution methodology for the airline crew scheduling problem. We conclude with a discussion about promising areas for further work to make it possible to get very good solutions for the crew scheduling problem.     

航空公司机组排班计划研究

以中国国际航空公司北京-成都航班为例,提出一种航空公司制定机组排班计划的新方法。首先以机组异地停留时间最短为目标,应用匈牙利算法生成“机组航班串”;然后,应用人员排班方法求得保证机组每周连休两日的条件下完成“机组航班串”飞行任务的最少机组数;最后,对这些机组制定具体的排班计划。应用该方法制定的机组排班计划使得航空公司在保证机组每周连休两日的条件下能够以最少的机组完成航班飞行任务,且机组在异地的停留时间最短。     

Parallel Integer Optimization for Crew Scheduling

Performance aspects of a Lagrangian relaxation based heuristic for solving large 0-1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew scheduling problems. We present a scalable parallelization of the original algorithm used in production at Carmen Systems AB, Göteborg, Sweden, based on distributing the variables. A lazy variant of this approach which decouples communication and computation is even useful on networks of workstations. Furthermore, we develop a new sequential active set strategy which requires less work and is better adapted to the memory hierarchy properties of modern RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.     

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1｜rj,pj=bj-ajuj,Cmax≤｜∑uj和1｜rj,prec,pj=bj-ajuj C max≤｜∑uj并给出求其最优资源分配的多项式算法.     

Crew pairing at Air France

In the airline industry, crew schedules consist of a number of pairings. These are round trips originating and terminating at the same crew home base composed of legal work days, called duties, separated by rest periods. The purpose of the airline crew pairing problem is to generate a set of minimal cost crew pairings covering all flight legs. The set of pairings must satisfy all the rules in the work convention and all the appropriate air traffic regulations. The resulting constraints can affect duty construction, may restrict each pairing, or be imposed on the overall crew schedule.The pairing problem is formulated as an integer, nonlinear multi-commodity network flow problem with additional resource variables. Nonlinearities occur in the objective function as well as in a large subset of constraints. A branch-and-bound algorithm based on an extension of the Dantzig-Wolfe decomposition principle is used to solve this model. The master problem becomes a Set Partitioning type model, as in the classical formulation, while pairings are generated using resource constrained shortest path subproblems. This primal approach implicitly considers all feasible pairings and also provides the optimality gap value on a feasible solution. A nice feature of this decomposition process is that it isolates all nonlinear aspects of the proposed multi-commodity model in the subproblems which are solved by means of a specialized dynamic programming algorithm.We present the application and implementation of this approach at Air France. It is one of the first implementations of an optimal approach for a large airline carrier. We have chosen a subproblem network representation where the duties rather than the legs are on the arcs. This ensures feasibility relative to duty restrictions by definition. As opposed to Lavoie, Minoux and Odier (1988), the nonlinear cost function is modeled without approximations. The computational experiments were conducted using actual Air France medium haul data. Even if the branch-and-bound trees were not fully explored in all cases, the gaps certify that the computed solutions are within a fraction of one percentage point of the optimality. Our results illustrate that our approach produced substantial improvements over solutions derived by the expert system in use at Air France. Their magnitude led to the eventual implementation of the approach.     

置换流水车间调度问题的中心引力优化算法求解

目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。     

An Algorithm for the Allocation Problem

This paper* sets out a procedure for solving allocation problems, on different lines from procedures based on linear programming.     

A Method for Solving Crew Scheduling Problems

The method discussed provides an allocation of jobs to men in a transportation system. Each man is assigned a prespecified shift, associated with a base station, and returned to his base station at the end of his shift. The total number of men required is minimized, subject to a minimum time between jobs, a suitable lunch break, and the performance of all the jobs, employing the decomposition principle of linear programming.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

多目标指派问题在潜艇兵力配置中的应用

运用模糊数学的思想，首先将各目标下的属性值矩阵转化为模糊关系矩阵，再将模糊关系合成矩阵与解决传统指派问题的匈牙利法相结合，提出一种求解多目标指派问题的综合方法：模糊匈牙利法，并结合优化潜艇兵力配置问题进行了应用分析。     

一种改进的多模式项目反应性调度问题

既有的项目反应性调度问题只关注了基准调度方案的稳定性,而忽略了项目调度目标的最优实现。本文提出了一种两阶段多模式资源受限项目反应性调度问题。第一阶段,在新的项目执行环境下,对项目进行完全重调度,得到新的最优调度目标值。第二阶段,以新的最优调度目标值为约束,以最大化调度稳定性为目标,求得新的最优调度方案。针对问题特点,基于IBM ILOG优化编程语言OPL和CPLEX V12.8.0,设计出该问题的求解程序。最后,基于标准算例,对本文提出的反应性调度方法、既有的反应性调度方法、完全重调度方法进行了充分的比较测试,结果表明本文提出的反应性调度方法在缩短项目工期、保护基准方案的稳定性方面具有明显优势。     

An Improved Formulation for the Job-Shop Scheduling Problem

This paper presents an extension of an earlier integer programming model developed by other authors to formulate a general n-job, m-machine job-shop problem. The new formulation involves substantially fewer functional constraints at the expense of an increase in the number of upper bound variables. This reduction of functional constraints, together with the imposition of upper and lower bounds on the objective value, significantly reduces the computation time for solving the integer model for the job-shop scheduling problem.     

An Algorithm for Solving a Resource Allocation Problem

The paper discusses the solution of a resource allocation problem and a new method for solving a special case of the problem. An algorithm for solving the general problem is presented, and computational experience comparing it with existing methods is given.     

An Improved Solution Procedure for the Scheduling Problem

Given a set of n jobs to be processed on a single machine, the problem is to find an optimal job sequence that hierarchically minimizes a bi-criterion objective function. The primary criterion is the maximum value of a general non-decreasing penalty function of job completion time, while the secondary criterion is total job flow time. An extension of Emmons's result is presented on the basis of which an improved solution procedue is developed to reduce the computational effort to find the optimal solution.     

An Integer Programming Approach to the Vehicle Scheduling Problem

This paper describes an integer programming formulation of the vehicle scheduling problem and illustrates how such a formulation can be extended to incorporate restrictions on work load, coverage and service that occur in real world vehicle scheduling problems. The integer programme is solved using the Revised Simplex method, additional constraints being introduced to retain integrality during convergence. The feasible region of this integer programme is initially restricted so that only routes constructed through sets of radially contiguous locations are considered. The effect of relaxing these over-constraints is explored. The method is demonstrated on fifteen problems ranging in size from 21 to 100 locations and the results generally show an improvement on previously published results. This is particularly true of the larger problems. This method compares favourably with other methods in computational efficiency.     

An Integrated Plant Design and Scheduling Problem in the Food Industry

An integrated plant design and scheduling problem in the food industry is discussed, and a solution is proposed. This involves the use of two models. The first model is an integer programming model that deals with long-term decisions. The second model deals with decisions that have to be made instantly.     

Modeling and solving a Crew Assignment Problem in air transportation

A typical problem arising in airline crew management consists in optimally assigning the required crew members to each flight segment of a given time period, while complying with a variety of work regulations and collective agreements. This problem called the Crew Assignment Problem (CAP) is currently decomposed into two independent sub-problems which are modeled and solved sequentially: (a) the well-known Crew Pairing Problem followed by (b) the Working Schedules Construction Problem. In the first sub-problem, a set of legal minimum-cost pairings is constructed, covering all the planned flight segments. In the second sub-problem, pairings, rest periods, training periods, annual leaves, etc. are combined to form working schedules which are then assigned to crew members.In this paper, we present a new approach to the Crew Assignment Problem arising in the context of airline companies operating short and medium haul flights. Contrary to most previously published work on the subject, our approach is not based on the concept of crew-pairings, though it is capable of handling many of the constraints present in crew-pairing-based models. Moreover, contrary to crew-pairing-based approaches, one of its distinctive features is that it formulates and solves the two sub-problems (a) and (b) simultaneously for the technical crew members (pilots and officers) with specific constraints. We show how this problem can be formulated as a large scale integer linear program with a general structure combining different types of constraints and not exclusively partitioning or covering constraints as usually suggested in previous papers. We introduce then, a formulation enhancement phase where we replace a large number of binary exclusion constraints by stronger and less numerous ones: the clique constraints. Using data provided by the Tunisian airline company TunisAir, we demonstrate that thanks to this new formulation, the Crew Assignment Problem can be solved by currently available integer linear programming technology. Finally, we propose an efficient heuristic method based on a rounding strategy embedded in a partial tree search procedure.The implementation of these methods (both exact and heuristic ones) provides good solutions in reasonable computation times using CPLEX 6.0.2: guaranteed exact solutions are obtained for 60% of the test instances and solutions within 5% of the lower bound for the others.