Benders decomposition has been applied significantly to tackle large-scale optimization problems with complicating variables, which, when temporarily fixed, ...

Operations research specialists at the OCP Group, the Mohammed VI Polytechnic University, and the Polytechnique Montreal operationalized a system optimizing ...

Perturbations are universal in supply chains, and their appearance is getting more frequent in the past few years. These perturbations affect industries and ...

This paper presents a multiobjective, mixed-integer linear programming (MILP) model that integrates production scheduling, inventory management, and vessel a...

The parameter configuration problem consists of finding a parameter configuration that provides the most effective performance by a given algorithm. This pap...

Crew pairing problems (CPP) are regularly solved by airlines to produce crew schedules. The goal of CPPs is to find a set of pairings (sequence of flights a...

The primal simplex algorithm is still one of the most used algorithms by the operations research community. It moves from basis to adjacent one until optimal...

The personalized crew rostering problem (CRP) consists of assigning pairings (sequences of flights, deadheads, connections, and rests, forming one or several...

The monthly crew pairing problem (CPP) consists of determining a least-cost set of feasible crew pairings (sequences of flights starting and ending at a crew...

The crew pairing problem is generally modelled as a set partitioning problem where the flights have to be partitioned in pairings. A pairing is a sequence of...

Overbooking is a common practice in the air cargo industry because booked and actual demands often differ greatly. As a consequence, in case of excessive ove...

In large commercial airlines, the monthly schedule (roster) of the crew members is usually determined by solving two problems sequentially, namely, the crew ...

We present a case study of using machine learning classification algorithms to initialize a large scale commercial operations research solver (GENCOL) in the...

We consider a personalized employee scheduling problem with characteristics present in retail stores consisting of multiple departments. In the setting under...

The airline crew scheduling problem involves determining schedules for airline crew members such that all the scheduled flights over a planning horizon (usua...

The primal adjacency-based algorithm and the multi-directional dynamic programming algorithm are two exact methods that have recently been developed to effic...

In this paper, we address a personalized multi-department multi-day shift scheduling problem with a multi-skill heterogeneous workforce where employees can b...

The shortest path problem with resource constraints (SPPRC) is often used as a subproblem within a column generation approach for routing and scheduling prob...

The shortest path problem with resource constraints finds the least cost path between two nodes in a network while respecting constraints on resource consump...

The airline crew scheduling problem, because of its size and complexity, is usually solved in two phases: the crew pairing problem and the crew assignment pr...

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we fo...

Airline crew scheduling is typically performed in two steps : crew pairing followed by crew assignment. The crew pairing problem (CPP) finds a set of pairing...

In this paper, we introduce a general framework for vector space decompositions that decompose the set partitioning problem into a reduced problem, defined...

To solve integer linear programs, primal algorithms follow an augmenting sequence of integer solutions leading to an optimal solution. In this work, we focu...

The integral simplex using decomposition (ISUD) algorithm <font size=2>[Zaghrouti, A., Soumis, F., Elhallaoui, I.: Integral simplex using decomposition for t...

Given a flight schedule and a set of aircraft of different types, the airline fleet assignment problem (FAP) consists of assigning an aircraft type to each f...

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight...

Starting from the improved primal simplex (IPS) decomposition, introduced by Elhallaoui et al. (2011) to tackle degeneracy in general linear programs, we int...

In this paper, we tackle the aircraft conflict resolution problem under uncertainties. We consider errors due to the wind effect, the imprecision on the airc...

In this article, we tackle the conflict resolution problem using a new variant of the minimum weight maximum clique model. The problem consists in identifyi...

Various disturbances such as adverse weather conditions may result in delayed or canceled flights and affect the optimized schedules planned for airline crew...

We propose a primal algorithm for the Set Partitioning Problem based on the Integral Simplex Using Decomposition of Zaghrouti et al. (2014). We present the a...

The airline crew scheduling problem involves assigning a group of crew members to scheduled flights over a planning horizon (usually a month) while respectin...

In this article, we develop the two-dimensional positive edge criterion for the dual simplex. This work extends a similar pricing rule implemented by Towhidi...

Cake-cutting is a metaphor for problems where a principal agent has to fairly allocate resources. Such problems cover various areas of operations research ...

Since its introduction in 1969, the set partitioning problem has received much attention, and the structure of its feasible domain has been studied in detail...

Including employee preferences in a shift-scheduling scheme raises the question of how to aggregate employee satisfactions in a sensible manner. To do so, we...

The airline crew scheduling problem has received extensive attention, particularly in the last sixty years. This problem is frequently divided into crew pair...

In this paper, we introduce a new measure of social fairness based on unfairness feelings of the players involved in an allocation problem, e.g., cake-cuttin...

Air traffic in Europe is predicted to increase considerably over the next decades. In this context, we present a study of the interactions between the costs...

The improved primal simplex (IPS) was recently developed by Elhalaloui et al. to take advantage of degeneracy when solving linear programs with the primal si...

Shift scheduling when the demand for employees is stochastic is usually done in two steps. Since employees need to know their shifts before the demand is kno...

In this article, we propose a general framework for an algorithm derived from the primal simplex that guarantees a strict improvement in the objective after ...

This paper presents the first direct implementation of the positive edge criterion using COIN-OR's CLP, where it has been combined with the Devex pivot rule....

In this paper, we suggest a new approach called the <i>return function</i> to deal with the determination of Bayesian-Nash equilibria in games of incomplet...

Since the 1970's, several authors have studied the structure of the set partitioning polytope and proposed adaptations of the simplex algorithm that find an ...

Aircraft maintenance planning is of critical importance to the safe and efficient operations of an airline. It is common to solve the aircraft routing and ma...

In many situations, such as art auctions, privatization of public assets and allocation of television airwaves to wireless carriers, the value of the objec...

Le secteur économique du transport aérien de passagers est soumis à de fortes contraintes dues aux nouveaux acteurs dans le domaine qui tendent les prix vers...

Stochastic programming can yield significant savings over deterministic approaches. For example, the stochastic approach for the shift scheduling problem sol...

The <i>positive edge</i> is a new pricing rule for the primal simplex: it identifies, with a probability error less than or equal to 2^-30 in sing...

The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and re...

Traditionally, the airline crew scheduling problem has been decomposed into a crew pairing and a crew assignment problem that are solved sequentially. The f...

In several companies such as large retail stores, the employees perform different activities (e.g., cashier or clerk in a specific department) to respond to ...

A crew pairing is a sequence of flights, connections and rests that start and end at a crew base and is assigned to a single crew. The crew pairing problem c...

Given a set of scheduled flights that must be operated by the same aircraft type, the aircraft routing problem (ARP) consists of building anonymous aircraft ...

The <i>improved primal simplex</i> (IPS) method has been proposed by Elhallaoui et al. (2008). We rewrite the theory of IPS for a cold start with an initial ...

The Improved Primal Simplex algorithm IPS [8] is a dynamic constraint reduction method particularly effective on degenerate linear programs. It is able to ac...

Most Fleet Assignment Problem (FAP) formulations use a leg-based estimation of revenue loss to derive the passenger revenue component of their objective fu...

We present a model that rapidly finds an approximation of the expected passenger flow on an airline network, given forecast data concerning 1) the distribut...

Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithm for solving linear programs. It is very efficient wh...

In the integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew pairings must be constructed...

Given buses of different types arriving at a depot during the evening, the bus parking problem consists of assigning these buses to parking slots in such a w...

This paper considers large shift scheduling problems with different shift start times and lengths, fractionable breaks and work stretch duration restrictions...

In this article we consider the problem of assigning parking slots to buses of different types so that the required buses can be dispatched easily in the mo...

In a transit authority bus depot, buses of different types arrive in the evening to be parked in the depot for the night, and then dispatched in the morning...

We consider a widespread solution method that consists of a column generation approach embedded in a branch-and-bound scheme to solve the multiple depot veh...

Given the sets of flights and aircraft of an airline carrier, the fleet assignment problem consists of assigning the most profitable aircraft type to each f...

Given the flight schedule of an airline, the fleet assignment problem consists of determining the aircraft type to assign to each flight leg in order to max...

Column generation has become a powerful tool in solving large scale integer programs. It is well known that most of the often reported compatibility issues ...

This paper considers a shift scheduling problem that includes different forms of flexibility in terms of shift starting times, break lengths and break plac...

This paper introduces the first exact approach for constructing aircrew member personalized monthly work schedules when a preferential bidding system (PBS) ...

The fractional aircraft market is the fastest growing segment of the business aircraft industry. A fractional aircraft operation is complex - essentially an...

We describe an approach that computes an optimal primal basic solution given an optimal vector of dual multipliers. It consists in restricting the dual prob...

This article presents a formulation for the job shop problem based on the Dantzig- Wolfe decomposition with a subproblem for each machine. Each subproblem i...

We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, va...

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on r...

The integrated aircraft routing and crew scheduling problem consists in determining a minimum-cost set of aircraft routes and crew pairings such that each fl...

Column generation is often used to solve problems involving set partitioning constraints, such as vehicle routing and crew scheduling problems. When these co...

This paper presents a new branching strategy that is applied on the cost of a subproblem during the solution of a large-scale linear program by a column gene...

This paper considers the locomotive assignment problem encountered during the planning of the operations of a freight railroad, which consists of providing s...

This paper introduces a new integrated model for the combined day-off and shift scheduling problem (the tour scheduling problem). This model generalizes the...

This paper introduces a new kind of operational crew scheduling problem which consists in simultaneously modifying, as necessary, the existing flight depart...

Although airlines plan aircraft routes and crew schedules in advance, perturbations occur everyday. As a result, flight schedules may become infeasible and ...

This paper describes and solves the operational pilot scheduling problem for one day of operations. The problem consists in simultaneously modifying, as nec...

Assigning locomotives and cars to a set of scheduled trains is a complex but important problem for passenger railways. This task is normally carried out in ...

Le problème de plus court chemin avec contraintes de ressources consiste à trouver un chemin d'un point origine à un point destination de coût minimum et re...

Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and crew scheduling problem consists of determining a...

This paper presents a survey on the <i>Vehicle Routing Problem with Pickup and Delivery</i> in which a heterogeneous vehicle fleet based at multiple termina...

This paper presents a survey of the research on the Vehicle Routing Problem with Time Windows (VRPTW), an extension of the Capacitated Vehicle Routing Probl...

Le problème de plus court chemin avec contraintes de ressources consiste à trouver un chemin d'un point origine à un point destination de coût minimum et re...

The problem of assigning locomotives and cars to trains is a complex task for most railways. In this paper, we propose a multi-commodity network flow based ...

The problem of assigning locomotives to trains consists of selecting the types and number of engines that minimize the fixed and operational locomotive cost...

An important aspect of railway planning concerns the distribution of locomotives and cars in the network and their assignment to the scheduled trains. In th...

This paper considers the placement of components onto printed circuit boards (PCB's) using surface mount technology. Multiple automatic placement machines, ...

Cet article décrit un problème d'horaires mensuels personnalisés pour les membres d'équipage (pilotes et officiers) en transport aérien. Ce problème consist...

One of the many problems faced by rail transportation companies is to optimize the utilization of the available stock of locomotives and cars. In this paper...

The locomotive assignment problem is to provide at minimum cost sufficient motive power to pull all the trains of a time tabled schedule. Optimization metho...

This article describes a method for solving the crew rostering problem in air transportation. This problem consists of constructing personalized schedules ...

This paper describes the Preferential Bidding Problem solved in the airline industry to construct personalized monthly schedules for pilots and officers. T...

We propose a common solution approach for different crew scheduling problems arising at the planning and operational levels in the airline industry. Specifi...

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the Vehicle Routing Problem with Time Windows (VRPTW). ...

The need for an integrating framework for vehicle routing and crew scheduling problems has been apparent for some time. While several attempts have been ma...

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing pr...

This paper classifies research contributions on decomposition approach for solving mathematical programming problems. More than 60 papers are presented with...

We consider a weekly locomotive scheduling problem encountered at Swedish State Railways. The objective is to find cyclic locomotive schedules, which minim...

The purpose of this paper is to develop optimal tool partitioning policies and strip sequencing strategies for a class of flexible manufacturing problems. ...

This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. This problem consists of modifyin...

This paper formulates the problem of maximal closure on a graph with resource constraints as an integer programming problem with binary variables, and propo...

Cet article présente une étude comparative des algorithmes de flot maximum pour la résolution du problème de fermeture maximale sur un graphe. Plusieurs ap...

We study the problem of finding a shortest collision-free path for a point car-like robot maneuvering around polygonal obstacles in a room bounded by a poly...

We study the problem of minimizing the peak load in single-command cycle shared storage policies. The peak load is the maximum of the daily material handlin...

The multi-depot vehicle scheduling problem with time windows consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task i...

The problem of assigning locomotives to train-segments is very important for railway companies, in view of the high cost of operating locomotives. The prob...

This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time window...

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 compo...

Nous nous penchons sur la modélisation et le traitement de problèmes d'entreposage du type partagé. Nous supposons que l'entrepôt est à charge unitaire et q...

In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipat...

We present a recent optimization approach that can be applied equally to aircraft routing, crew pairing generation and bidding/rostering problems arising in...

The purpose of this paper is to develop optimal tool partitioning policies and strip sequencing strategies for a class of flexible manufacturing problems su...

There are several routing and scheduling problems faced by airline companies, notably, aircraft scheduling, pairing generation and crew bidding and rosterin...

This survey paper describes the significant advances made in time constrained vehicle routing and crew scheduling problems. In terms of solution methodolog...

This paper describes strip sequencing models for large scale traveling salesman problems arising in flexible manufacturing operations in two or three discre...

In this paper we analyze the efficiency of a given robot movement schedule for the case of a flowshop robotic production cell with <i>m</i> different machin...

This paper propose a column generation method for optimally solving the rostering problem. Various strategies for accelerating the column generation process...

The purpose of this paper is to formulate and solve an optimization problem arising in the operations of a numerical control machine such as a punch press. ...

In operations planning in an open pit mine an economic blocks model is generally used which attempts to determine which blocks will be extracted during each...

We consider the problem of finding a shortest path for a car-like robot maneuvering in a convex cell. This robot, capable of forward and backward motion, is...

We study the problem of finding a shortest path for a car-like mobile robot with a minimal turning radius constraint. This vehicle can move either forward o...

One important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time-changing information even in ...

We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation ...

The NP-hard problem addressed in this paper is well known in the scheduling literature as <i>R</i>|<i>C</i>_{<font size=-1>max</font>}. We introduce...

The problem of finding a minimal length trajectory (MLT) for a mobile robot has changed in the last five years, as vehicle kinematics have come to be taken ...

In this paper, optimal strip strategies are developed for a variety of two-dimensional and three-dimensional sequencing problems arising in flexible manufac...

We present a new two-commodity flow formulation for the traveling salesman problem. Each commodity corresponds to a resource that is either distributed or p...

In this paper, the expected distance between two uniformly distributed random points in a rectangle or in a rectangular parallelepiped is computed under thr...

The Airline Crew Scheduling Problem can be defined as the problem of finding a set of feasible rotations so that the total cost is minimum and all the fligh...

In many cities around the world, public transportation services are requested to provide adapted transportation for handicapped persons and people with rest...

We consider a generalization of PERT where task durations are variable and the cost of each task is a convex function of its duration. Moreover, each preced...

The development of truck dispatching systems has during recent years taken two directions. One has been systems using mathematical optimization and powerfu...

In this paper we develop a stochastic, dynamic network equilibrium model of airline passenger transportation. The model explicitly incorporates the behavior...

CREW-OPT is a new software module in the HASTUS family of scheduling software. CREW-OPT produces optimal or near-optimal crew schedules for small problems (...

Le problème classique de dimensionnement d'un réseau de télécommunications se formule en général comme suit: étant donné un réseau, une matrice de trafic et...

The problem we consider is that of preparing a minimum cost transportation plan by simultaneously solving the following two sub-problems: first the assignm...

This paper presents a model for the optimization of productivity in a steel plant comprised of four arc furnaces and three continuous casting machines and su...

The two-dimensional cutting-stock problem consists of laying out a specified list of rectangular pieces on rectangular sheets, in such a way as to minimize t...

The vehicle routing problem (VRP) involves the design of a set of minimum cost routes for a fleet of vehicles which services exactly once a set of customers...

Schedule compression is a major concern in project management. We propose an extension of the classical crashing model to include the managerial practice of...

We consider projects represented by a PERT network, with convex cost-of-time functions on individual activities, and we show the existence of an efficient m...

The multiple vehicle many-to-many routing problem is presented in the context of a dial-a-ride system. It is solved by mini-clustering first and optimal ro...

We present an algorithm that solves the problem of finding the vehicle schedule which minimizes total inconveniences for travel along a fixed path, where se...

Le problème classique d'optimisation de la capacité des réseaux de télécommunications s'énonce comme suit: pour un réseau dont la structure, la demande et l...

Several single-commodity, two-commodity and multi-commodity flow formulations have recently been introduced for the travelling salesman problem. The purpose...

We present a dual algorithm to minimize a separable convex function under ratio constraints between variables. This minimization problem occurs when the dep...

The problem is to elaborate a minimum cost transportation plan by simultaneously solving the following two sub-problems: the assignment of available units at...

We present an algorithm that solve the problem of finding the best vehicle time schedule (minimizing total inconveniences) for a fixed path, knowing that vis...

We propose a measure of the reliability of a telecommunication network based on the expected value of the lost call traffic due to failures in the network. ...

The urban transit crew scheduling problem arises in mass transit corporations who have to create minimal cost bus driver schedule respecting both the collect...

This paper presents mathematical formulations for some vehicle routing and scheduling problems with time window constraints and the optimal solution approach...

This paper considers a vehicle routing problem with full loads and time limit constraints. This problem can be formulated as an asymmetrical travelling sale...

The single-vehicle dial-a-ride problem with time window constraints for both pick-up and delivery locations, and precedence and capacity constraints, is solv...

This paper presents some preliminary results from an ongoing study of the impact of various operating scenarios on the construction and quality of reoutes in...

In this article, we examine the use of Lagrangian relaxation to obtain a lower bound on the minimum fleet size for the m-TSP with time window constraints on ...

Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost and a time interval within which the tr...

Bus fleet route planning is often carried out in the following two sequential stages:<br> 1) Based on the demand, determine the trips to be carried out.<br>...

Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost and a time interval within which the tr...

Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost and a time interval within which the tr...

Le problème considère un ensemble de parcours ayant chacun un lieu de début, un lieu de fin, une durée, un coût et un intervalle de temps pendant lequel ils ...

Le service de transport des handicapés vise à procurer un transport à toute personne handicapée incapable d'utiliser le service de transport urbain régulier....