A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding

We consider a monthly crew scheduling problem with preferential bidding in the airline industry. We propose a new methodology based on a graph coloring model and a tabu search algorithm for determining if the problem contains at least one feasible solution. We then show how to combine the proposed approach with a heuristic sequential scheduling method that uses column generation and branch-and-bound techniques.     

Solving a robust airline crew pairing problem with column generation

In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey.     

基于SMT的机组排班问题优化求解

机组排班是航空公司运营计划非常重要的一个环节,合理的机组排班可以为航空公司省下一大笔机组成本支出,从而增加航空公司的收益.由于机组排班过程涉及大量的复杂约束,属于NP难问题,因此优化求解困难.本文提出了一种基于可满足性模理论(Satisfiability Modulo Theories,SMT)的航空公司机组排班问题的优化求解方法,将机组排班过程中的各种约束转化为一阶逻辑公式,设立求解目标为最小化成本和最大化机组利用率,将问题转化为求在给定逻辑公式可满足情况下的最优解,并利用SMT求解器Z3进行求解.实验表明,本文的算法能有效的求解一定规模航班计划的机组排班问题,给航空公司带来一定的收益.     

An adaptive amoeba algorithm for constrained shortest paths

The constrained shortest path problem (CSP) is one of the basic network optimization problems, which plays an important part in real applications. In this paper, an adaptive amoeba algorithm is combined with the Lagrangian relaxation algorithm to solve the CSP problem. The proposed method is divided into two steps: (1) the adaptive amoeba algorithm is modified to solve the shortest path problem (SPP) in a directed network; (2) the modified adaptive amoeba algorithm is combined with the Lagrangian relaxation method to solve the CSP problem. In addition, the evolving processes of the adaptive amoeba model have been detailed in the paper. Two examples are used to illustrate the efficiency of the proposed method. The results show that the proposed method can deal with the CSP problem effectively.     

Models and Algorithms for Integration of Vehicle and Crew Scheduling

This paper deals with models, relaxations, and algorithms for an integrated approach to vehicle and crew scheduling for an urban mass transit system with a single depot. We discuss potential benefits of integration and provide an overview of the literature which considers mainly partial integration. Our approach is new in the sense that we can tackle integrated vehicle and crew scheduling problems of practical size.We propose new mathematical formulations for integrated vehicle and crew scheduling problems and we discuss corresponding Lagrangian relaxations and Lagrangian heuristics. To solve the Lagrangian relaxations, we use column generation applied to set partitioning type of models. The paper is concluded with a computational study using real life data, which shows the applicability of the proposed techniques to practical problems. Furthermore, we also address the effectiveness of integration in different situations.     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

An iterative approach to robust and integrated aircraft routing and crew scheduling

In airline scheduling a variety of planning and operational decision problems have to be solved. We consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights in a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved later. Also, when minimal cost solutions are used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day. We generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We solve the two original problems iteratively. Starting from a minimal cost solution, we produce a series of solutions which are increasingly robust. Using data from domestic airline schedules we evaluate the benefits of the approach as well as the trade-off between cost and robustness. We extend our approach considering the aircraft routing problem together with two crew pairing problems, one for technical crew and one for flight attendants.     

Row and column generation technique for a multistage cutting stock problem

The multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.Scope and purposeWe investigate a broad class of large-scale linear programming models and suggest a new and efficient way to solve them. The proposed method belongs to a category of decomposition techniques generalizing the famous column generation method. An iteration of the revised simplex algorithm may “enrich” the LP matrix either by generating a new column, as a purely column generation method does, or by generating a combination of a new row and a pair of new columns. The method is a row and column generation technique that we propose and investigate. Applications modeled by a multistage CSP occur in the industries that use a multistage cutting process: paper, leather, film, steel, etc., or a nested packing/loading process: transportation. The unknown variables in the multistage cutting stock problem are intermediate sizes (rows) and cutting patterns (columns). According to the algorithm both are to be generated dynamically. The proposed algorithm brings tremendous benefits in terms of the quality of solutions and computational performance.     

Exact computational solution of Modularity Density Maximization by effective column generation

Modularity Density Maximization (MDM) is associated with clustering problems in networks. MDM is an alternative to the resolution limit issue of the Modularity Maximization problem. Several reports in the literature have described mathematical programming models for MDM which solve instances of at most 40 nodes. In this context, this paper presents six new column generation methods that find exact solutions for the MDM problem. These methods use exact and auxiliary heuristic problems and an initial variable generator. Our methods show clear improvements over current results. Comparisons between our proposed methods and state-of-the-art algorithms are also carried out. Our results show that (i) two of our methods surpass the exact state-of-the-art algorithms in terms of time, and (ii) our methods provide optimal values for larger instances than current approaches can tackle.     

A Class of Cross-Layer Optimization Algorithms for Performance and Complexity Trade-Offs in Wireless Networks

In this paper, we solve the problem of a joint optimal design of congestion control and wireless MAC-layer scheduling using a column generation approach with imperfect scheduling. We point out that the general subgradient algorithm has difficulty in recovering the time-share variables and experiences slower convergence. We first propose a two-timescale algorithm that can recover the optimal time-share values. Most existing algorithms have a component, called global scheduling, which is usually NP-hard. We apply imperfect scheduling and prove that if the imperfect scheduling achieves an approximation ratio rho, then our algorithm produces a suboptimum of the overall problem with the same approximation ratio. By combining the idea of column generation and the two-timescale algorithm, we derive a family of algorithms that allows us to reduce the number of times the global scheduling is needed.     

A novel column generation strategy for large scale airline crew pairing problems

A crew pairing is a sequence of flight legs beginning and ending at the same crew domicile. Crew pairing planning is the primary cost-determining phase in airline crew scheduling. Optimizing crew pairings of an airline timetable is an extremely important process which helps to minimize operational crew costs and to maximize crew utilization.There are various restrictions imposed by regulations or company policies that must be considered and satisfied in crew pairing generation process. Keeping these restrictions and regulations in mind, the main goal of the optimization is the generation of low cost sets of valid crew pairings which cover all flights in airline's timetable.For this research study, already existing works related to crew pairing optimization are examined and a new column generation strategy, a pricing network design and a pairing elimination heuristic are developed as a contribution to the previous studies. In the proposed strategy, the main problem is modeled and solved as a set-covering problem and the pricing sub problem is modeled as a shortest-path problem which is efficiently solved over a duty-flight overnight connection graph by the combined usage of heuristic and exact algorithms. The proposed strategy has been tested with real world data obtained from Turkish Airlines and it is seen that it is capable of generating very competitive solutions compared to current practices in Turkish Airlines. It is also observed that there are various advantages of proposed solution approach such as sensitivity to penalty coefficients, generating less deadheads, very close solution times with a single threaded software and light weight hardware.     

侦察卫星探测资源调度研究

侦察卫星探测资源调度是一类基于约束满足的优化问题。对卫星探测资源和探测任务的特点进行分析,在此基础上构建卫星探测资源调度的目标函数和约束条件,利用约束满足问题的建模思想对该调度问题进行建模。针对约束满足模型规模大、求解复杂的情况,结合卫星探测资源调度问题的特征,提出一种基于启发式禁忌搜索算法的模型求解方法,并通过仿真算例进行说明与分析。该调度模型和算法充分考虑了星载资源与对应任务的特点,尽量回避假设与简化条件的提出,具有较好的适用性,将为侦察与预警卫星网络任务规划与资源调度的研究奠定基础。     

Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation

We consider vehicle routing and crew scheduling problems that involve a lexicographic bi-level objective function (for instance, minimizing first the number of vehicles and second the operational costs) and can be solved by column generation where the subproblem is a resource constrained shortest path problem. Such problems are often modeled using a single-level objective function with a large fixed cost (weight) for ensuring the minimization of the primary objective. In this paper, we study the impact on the solution time of the fixed cost value. First, we present computational results which show that the solution time increases as the fixed cost value gets larger. Then, we develop an exact dynamic fixed cost procedure compatible with column generation that starts with a relatively small fixed cost value and increases it iteratively until optimality is reached. To prove optimality, a shortest path problem with resource constraints needs to be solved. Through a series of computational experiments on two types of problems, we show that this procedure can reduce solution times by up to 50% when compared to an approach relying on one very large fixed cost value.     

Crew pairing optimization based on hybrid approaches

The crew pairing problem (CPP) deals with generating crew pairings due to law and restrictions and selecting a set of crew pairings with minimal cost that covers all the flight legs. In this study, we present three different algorithms to solve CPP. The knowledge based random algorithm (KBRA) and the hybrid algorithm (HA) both combine heuristics and exact methods. While KBRA generates a reduced solution space by using the knowledge received from the past, HA starts to generate a reduced search space including high quality legal pairings by using some mechanisms in components of genetic algorithm (GA). Zero-one integer programming model of the set covering problem (SCP) which is an NP-hard problem is then used to select the minimal cost pairings among solutions in the reduced search space. Column generation (CG) which is the most commonly used technique in the CPP literature is used as the third solution technique. While the master problem is formulated as SCP, legal pairings are generated in the pricing problem by solving a shortest path problem on a structured network. In addition, the performance of CG integrated by KBRA (CG_KBRA) and HA (CG_HA) is investigated on randomly generated test problems. Computational results show that HA and CG_HA can be considered as effective and efficient solution algorithms for solving CPP in terms of the computational cost and solution quality.     

求解随机机会约束规划的混合智能算法及应用

为更有效地求解随机机会约束规划问题,提出一种基于克隆选择算法(CSA)、随机模拟技术及神经网络的混合智能算法。采用随机模拟技术产生随机变量样本矩阵训练反向传播(BP)网络以逼近不确定函数,之后在CSA中利用神经网络检验个体的可行性、计算适应度,从而得到优化问题的最优解。为保证算法搜索的快速性和有效性,CSA采用双克隆和双变异策略。仿真结果表明,与已有算法相比,混合智能算法在500代时已取得比较满意的结果,且其精度在单目标优化问题中提高了2.2%,在多目标优化问题中提高了65%;将该算法应用于求解水库优化调度的难题上,结果也表明所建立的模型及算法的可行性和有效性。     

A near-exact method for solving the log-truck scheduling problem

We propose a solution method for the log‐truck scheduling problem, which is a generalisation of the pick‐up and delivery problem with time windows. Our approach is based on column generation and pseudo branch and price. Each column in the proposed mathematical model represents one feasible route for one truck. We start by designing a priori an initial set of routes. Then, the subproblem, which is a constrained shortest path problem, is solved by applying a k‐shortest path algorithm. Numerical results from a case study are presented.     

A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes

In this paper, we consider the scheduling problem on a single batch processing machine with non-identical job sizes; in which the machine has a limited capacity and can process a group of jobs simultaneously as a batch. The processing time of a batch is the longest processing time of all jobs in the batch. The objective is to minimize the makespan. We formulate the problem using Dantzig–Wolfe decomposition as a set partitioning problem. Based on the set partitioning formulation, we present a tight lower bound using column generation method. A heuristic algorithm is also developed to generate the basic solution in the column generation method. A branch and price algorithm which combines the column generation technique with branch and bound method is then presented to obtain the optimal solution of the problem. The efficiency of the proposed branch and price algorithm is ultimately compared to the branch and bound algorithm from the literature, based on the generated sample problems.     

Efficient trip generation with a rule modeling system for crew scheduling problems

Trip generation is the most time consuming phase in the solution process of crew scheduling problems faced by large transportation companies such as airlines and railways. A large number of trips must be constructed while satisfying a complex set of regulations. In this paper, we present an efficient trip generation method that utilizes originally a rule modeling system in order to reduce the corresponding search space. Special pruning rules are defined using a high-level rule language, which also supports the modeling of the business regulations required in the scheduling process. In addition, the legality checking mechanism involved has been tuned to perform efficiently in order to cope with the vast amount of the legality checks required by the trip generator. The algorithms are tested as a module for a crew scheduling application satisfying the tight response time requirements of a production system. We present experimental results based on problems provided by a major European airline that validate the usefulness and applicability of our work.     

An integrated scenario-based approach for robust aircraft routing,crew pairing and re-timing

For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (e.g. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision-making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture many dependencies between the various stages, most notably between those of aircraft routing and crew pairing, and how these dependencies affect the propagation of delays through the flight network. In Dunbar et al. (2012) [9] we introduced a new algorithm to accurately calculate and minimize the cost of propagated delay, in a framework that integrates aircraft routing and crew pairing. In this paper we extend the approach of Dunbar et al. (2012) [9] by proposing two new algorithms that achieve further improvements in delay propagation reduction via the incorporation of stochastic delay information. We additionally propose a heuristic, used in conjunction with these two approaches, capable of re-timing an incumbent aircraft and crew schedule to further minimize the cost of delay propagation. These algorithms provide promising results when applied to a real-world airline network and motivate our final integrated aircraft routing, crew pairing and re-timing approach which provides a substantially significant reduction in delay propagation.     

Integrated airline scheduling

Airline scheduling is composed of fleet assignment, aircraft maintenance routing, and crew scheduling optimization subproblems. It is believed that the full optimization problem is computationally intractable, and hence the constituent subproblems are optimized sequentially so that the output of one is the input of the next. The sequential approach, however, provides an overall suboptimal solution and can also fail to satisfy the maintenance constraints of an otherwise feasible full problem. In this paper several integrated models for the optimization of airline scheduling are presented for the first time, and solved by applying an enhanced Benders decomposition method combined with accelerated column generation. Solutions of several realistic data sets are computed using the integrated models, which are compared with solutions of the best known approaches from the literature. As a result, the integrated approach significantly reduces airline costs. Finally, a comparison of alternative formulations has shown that keeping the crew scheduling problem alone in the Benders subproblem is much more efficient than keeping the aircraft routing problem.