Guy Desaulniers
RetourPublications
Cahiers du GERAD
Branch-and-Price
Integer (linear) programs are a standard way of formalizing a vast array of optimization problems in industry, services, management, science, and technology....
référence BibTeX
Bus scheduling in public transit consists in determining a set of bus schedules to cover a set of timetabled trips at minimum cost. This planning process has...
référence BibTeX
This study addresses large-scale personnel scheduling problems in the service industry by combining mathematical programming with data mining techniques to...
référence BibTeX
Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision...
référence BibTeX
The multi-depot scheduling problem (MDVSP) is one of the most studied problem in public transport service planning. It consists of assigning buses to each ti...
référence BibTeX
Personnel scheduling consists in determining employee work schedules (sequences of work shifts and days off) to cover the demands of multiple jobs over a pl...
référence BibTeXMachine-learning-based arc selection for constrained shortest path problems in column generation
Column generation is an iterative method used to solve a variety of optimization problems. It decomposes the problem into two parts: a master problem, and on...
référence BibTeX
In this paper, we introduce a new variant of the vehicle routing problem with time windows (VRPTW) that arises in parcel delivery by postal services. In addi...
référence BibTeXParallel stimulation of disruptions for personnel scheduling in a flexible working environment
Personnel scheduling aims to determine least-cost personnel schedules to meet the demand for employees in each period of a planning horizon. In this article,...
référence BibTeXDeep-learning-based partial pricing in a branch-and-price algorithm for personalized crew rostering
The personalized crew rostering problem (CRP) consists of assigning pairings (sequences of flights, deadheads, connections, and rests, forming one or several...
référence BibTeXAn improved integral column generation algorithm using machine learning for aircrew pairing
The crew pairing problem (CPP) is solved in the first step of the crew scheduling process. It consists of creating a set of pairings (sequence of flights, co...
référence BibTeX
We consider logistic collaborations where multiple carriers collaborate by consolidating demands, combining delivery routes, and serving new customers. Logis...
référence BibTeX
Given a set of predefined duties and groups of drivers, the duty assignment problem with group-based driver preferences (DAPGDP) aims at building rosters tha...
référence BibTeX
We study a new variant of the well-studied Vehicle Routing Problem with Time Windows (VRPTW), called the fragility-constrained VRPTW, which assumes that ...
référence BibTeXA branch-price-and-cut algorithm for the two-echelon vehicle routing problem with time windows
In this paper, we propose an exact branch-price-and-cut (BPC) algorithm for the two-echelon vehicle routing problem with time windows. This problem arises i...
référence BibTeX
We study a new variant of the vehicle routing problem, which arises in hospital-wide scheduling of physical therapists. Multiple service locations exist for...
référence BibTeX
Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the ...
référence BibTeX
Column generation (CG) is widely used for solving large-scale optimization problems. This article presents a new approach based on a machine learning (ML) t...
référence BibTeX
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...
référence BibTeX
Column generation algorithms for solving vehicle routing problems often rely on a relaxed pricing subproblem where routes may be non-elementary and which is ...
référence BibTeX
The integral column generation algorithm (ICG) was recently introduced to solve set partitioning problems involving a very large number of variables. This pr...
référence BibTeX
Personnel scheduling consists of determining least-cost work schedules to cover the demand of multiple jobs expressed in number of employees per job and peri...
référence BibTeXVariable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models
Variable fixing by reduced costs is a popular technique for accelerating the solution process of mixed-integer linear programs. For vehicle routing problems ...
référence BibTeX
Significant progress has been made in the field of computer vision, due to the development of supervised machine learning algorithms, which efficiently extra...
référence BibTeX
In large commercial airlines, the monthly schedule (roster) of the crew members is usually determined by solving two problems sequentially, namely, the crew ...
référence BibTeX
In the Inventory Routing Problem customer demand is satisfied from inventory which is replenished with capacitated vehicles. The objective is to minimize tot...
référence BibTeX
Given a set of duties to be operated over a cyclic one-week horizon and groups of drivers with similar characteristics, the cyclic bus driver rostering probl...
référence BibTeX
We consider a personalized employee scheduling problem with characteristics present in retail stores consisting of multiple departments. In the setting under...
référence BibTeXA PCA-based approximation scheme for combinatorial optimization with uncertain and correlated data
This paper addresses combinatorial optimization problems under uncertain and correlated data where the mean-covariance information of the random data is assu...
référence BibTeX
The Time Window Assignment Vehicle Routing Problem (TWAVRP) is the problem of assigning time windows for delivery before demand volume becomes known. This i...
référence BibTeX
Les problèmes de gestion de personnel visent à déterminer les horaires de travail les moins coûteux pour couvrir la demande d'une ou plusieurs tâches à chaqu...
référence BibTeXA two-stage solution approach for personalized multi-department multi-day shift scheduling
In this paper, we address a personalized multi-department multi-day shift scheduling problem with a multi-skill heterogeneous workforce where employees can b...
référence BibTeX
Vehicle routing problems (VRPs) are among the most studied problems in operations research. Nowadays, the leading exact algorithms for solving many classes o...
référence BibTeX
Maintenance of power generators is essential for reliable and efficient electricity production. Because generators under maintenance are typically inactive, ...
référence BibTeX
This paper focuses on the traveling salesman problem with time windows (TSPTW) that arises in postal services and parcel deliveries and has features differin...
référence BibTeX
Employee scheduling is an important activity in the service industry as it has a significant impact on costs, sales, and profitability. While a large amount ...
référence BibTeX
In this paper we consider a version of the capacitated vehicle routing problem (CVRP) where travel times are assumed to be uncertain and statistically corre...
référence BibTeX
The multiple depot vehicle scheduling problem (MDVSP) has been widely studied in the context of public transit systems. It consists of building vehicle sched...
référence BibTeX
In global liner shipping networks a large share of transported cargo is transshipped at least once between container vessels, and the total transportation ti...
référence BibTeX
Maintenance activities help prevent costly generator breakdowns but because generators under maintenance are typically unavailable, the impact of maintenance...
référence BibTeXIntegral column generation
The integral simplex using decomposition (ISUD) algorithm was recently developed to solve efficiently set partitioning problems containing a number of variab...
référence BibTeX
The bid construction problem (BCP) for combinatorial total truckload transportation service procurement auctions consists of determining one or several bids ...
référence BibTeX
Personnel scheduling consists of determining least-cost employee work schedules to cover the demand of one or several jobs in each period of a time horizon. ...
référence BibTeX
La méthode de branch-cut-and-price est la plus performante pour une grande panoplie de problèmes de tournées de véhicules (PTV). Pour plusieurs d'entre eux...
référence BibTeX
In this paper, we propose an integer programming model for obtaining lower bounds for the curriculum-based course timetabling problem, in which weekly assign...
référence BibTeX
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...
référence BibTeX
La création d’horaires de personnel aériens est généralement effectuée en deux étapes : la création de rotations d’équipage, suivie par la création d’horaire...
référence BibTeXA Branch-Price-and-Cut algorithm for a production-routing problem with short-lifespan products
We study a rich production-routing problem with time windows arising at a catering services company. The production part consists of assembling the meals to ...
référence BibTeX
The vehicle routing problem with time windows (VRPTW) consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited...
référence BibTeX
Inventory routing problems aim at minimizing the cost of the total distance traveled over a time horizon discretized in periods, while guaranteeing that th...
référence BibTeX
This paper introduces the pickup and delivery problem with time windows and handling operations. In this problem, the loading compartment of a vehicle is mod...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
Cet article traite la prise en compte d'incertitudes lors de la résolution de conflits. Plus particulièrement, nous considérons les incertitudes dues aux err...
référence BibTeX
Nous présentons un modèle déterministe pour le problème de détection et de résolution de conflits entre aéronefs. Les aspects liés à la dynamique des avions,...
référence BibTeX
This paper introduces a new primal algorithm for solving a linear program LP. In this algorithm, a pricing problem, namely a linear fractional program, is ...
référence BibTeX
Dans cet article, nous étudions des stratégies pour résoudre le problème de partitionnement d'ensemble (PPE), en particulier les gains en efficacité qui pe...
référence BibTeX
This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loade...
référence BibTeX
Effective route planning for battery electric commercial vehicle (ECV) fleets has to take into account their limited autonomy and the possibility of visiting...
référence BibTeX
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...
référence BibTeX
In this article, we solve the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading. LIFO loading minimizes handling while unloa...
référence BibTeX
We present a matheuristic, an integer programming based heuristic, for the liner shipping network design problem. This problem consists of finding a set of...
référence BibTeX
The inventory-routing problem (IRP) integrates two well-studied problems, namely, inventory management and vehicle routing. Given a set of customers to servi...
référence BibTeX
The <b>VRPTW-ST</b> introduced by Errico et al. (2013) in the form of a chance-constrained model mainly differs from other vehicle routing problems with st...
référence BibTeX
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...
référence BibTeX
This paper proposes a state-of-the-art branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands (VRPSD). We adapt the model of ...
référence BibTeX
In this paper we present a comparative study of several strategies that can be applied to achieve the so-called elementary lower bound in vehicle routing p...
référence BibTeX
Onshore oil fields may contain hundreds of wells that use sophisticated and complex equipments. These equipments need maintenance regularly to keep the...
référence BibTeX
In this paper we consider the vehicle routing problem with hard time windows and stochastic service times (VRPTW-ST); in this variant of the classic VRPTW ...
référence BibTeX
This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and last-in-first-out (LIFO) loading constr...
référence BibTeX
This paper studies a districting problem which arises in the context of financial product pricing. The challenge lies in partitioning a set of small geogra...
référence BibTeX
We consider the multicommodity network flow formulation of the Multiple Depot Vehicle Scheduling Problem (MDVSP) and investigate several strategies within a ...
référence BibTeX
In this paper we introduce the discrete time window assignment vehicle routing problem. This problem consists of assigning a single time window from a ...
référence BibTeX
The airline fleet assignment problem (FAP) consists of assigning an aircraft type to each flight leg of a flight schedule in order to maximize the airline ...
référence BibTeX
Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solvi...
référence BibTeXBranch-Price-and-Cut for Creating an Annual Delivery Program of Multi-Product Liquefied Natural Gas
In this paper a new branch-price-and-cut method for a maritime inventory routing problem for one of the world's largest producers of liquefied natural gas (L...
référence BibTeX
In an onshore oil field, the productivity of oil wells decreases when they require maintenance. To restore full productivity at a well, it must be visi...
référence BibTeX
The min-max <i>k</i>-vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle in order to find a set of b...
référence BibTeX
We present a branch-price-and-cut method to solve a maritime pickup and delivery problem with time windows and split loads. The fleet of ships is heterogen...
référence BibTeX
In the service industry, the employees perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The ...
référence BibTeX
Le problème d'affectation d'activités et de tâches consiste à affecter des activités interruptibles et des tâches non interruptibles à des quarts de travai...
référence BibTeX
La plupart des compagnies distribuant de l’huile de chauffage résolvent des problèmes de tournées de véhicules presque quotidiennement. Ces problèmes peuven...
référence BibTeXIntegrated Airline Crew Scheduling: A Bi-Dynamic Constraint Aggregation Method using Neighborhoods
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...
référence BibTeX
The multi-activity assignment problem consists of assigning interruptible activities to given work shifts so as to match as much as possible for each activit...
référence BibTeX
The vehicle routing problem with time windows VRPTW consists of finding least-cost vehicle routes to service given customers exactly once each while satisfyi...
référence BibTeX
Traditionally, the airline crew scheduling problem has been decomposed into a crew pairing and a crew assignment problem that are solved sequentially. The f...
référence BibTeX
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 ...
référence BibTeX
In this paper, we propose a generic model based on linear programming that allows building an optimal production plan for a work shift in an open-pit mine. T...
référence BibTeXEnhanced Branch-and-Price-and-Cut for Vehicle Routing with Split Deliveries and Time Windows
In this paper, we study the split delivery vehicle routing problem with time windows SDVRPTW that is a variant of the well-known vehicle routing problem with...
référence BibTeX
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...
référence BibTeX
As of April 2007, the European Union has new regulations concerning driver working hours. These rules force the placement of breaks and rests into the vehicl...
référence BibTeX
This paper presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be de...
référence BibTeX
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 ...
référence BibTeX
In the <i>Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows</i>, the set of customers is the union of <i>delivery customers</i> and...
référence BibTeX
The Dutch railway network experiences about three large disruptions per day on average. In this paper, we present an algorithm to reschedule the crews when s...
référence BibTeX
This work presents an exact branch-cut-and-price algorithm for the vehicle routing problem with time windows (VRPTW) where the well-known clique inequalities...
référence BibTeX
We consider a maritime inventory routing problem in the liquefied natural gas (LNG) business. Here, an actor is responsible for the routing of the fleet of s...
référence BibTeX
This paper addresses the split delivery vehicle routing problem with time windows (SDVRPTW) that consists of determining least-cost vehicle routes to service...
référence BibTeX
The bidline scheduling problem with equity arises in several North American airlines. It consists of determining anonymous monthly schedules, called bidlines...
référence BibTeXPath Reduced Costs for Eliminating Arcs
In many branch-and-price algorithms, the column generation pricing problem consists of computing feasible paths in a network. In this paper, we show how, in...
référence BibTeX
Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible v...
référence BibTeX
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...
référence BibTeX
An edge coloring of a graph <img src="/cgi-bin/mimetex.cgi?G = (V,E)"> is a function <img src="/cgi-bin/mimetex.cgi?c:E \rightarrow N"> that assigns a co...
référence BibTeX
Given a set of timetabled tasks, the multi-depot vehicle scheduling problem is a wellknown problem that consists of determining least-cost schedules for veh...
référence BibTeX
The vehicle routing problem with time windows consists of delivering goods at minimum cost to a set of customers using an unlimited number of capacitated ve...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
We consider vehicle routing and crew scheduling problems that involve a lexico- graphic bi-level objective function (for instance, minimizing first the numb...
référence BibTeX
This paper introduces the first exact approach for constructing aircrew member personalized monthly work schedules when a preferential bidding system (PBS) ...
référence BibTeX
In most vehicle routing and crew scheduling applications solved by column generation, the subproblem corresponds to a shortest path problem with resource con...
référence BibTeX
Column generation is often used to solve problems involving set partitioning constraints, such as vehicle routing and crew scheduling problems. When these co...
référence BibTeXPublic Transit
This paper reviews state-of-the-art models and approaches for solving a wide variety of public transit problems encountered at the strategic, tactical, and...
référence BibTeX
This paper presents an exact solution approach for the problem of the simultaneous dispatching and conflict-free routing of automated guided vehicles. The ...
référence BibTeX
This paper considers the locomotive assignment problem encountered during the planning of the operations of a freight railroad, which consists of providing s...
référence BibTeX
We consider a new variant of constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part...
référence BibTeX
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 ...
référence BibTeXThe VRP with Pickup and Delivery
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...
référence BibTeXThe VRP with Time Windows
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...
référence BibTeX
This paper presents an exact approach for solving the simultaneous vehicle and crew scheduling problem in urban mass transit systems. We consider the single...
référence BibTeX
This paper focuses on accelerating strategies used in conjunction with column generation to solve Vehicle Routing and Crew Scheduling problems. We describ...
référence BibTeX
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...
référence BibTeX
This paper considers the shortest path problem with waiting costs (SPWC) as an extension of the shortest path problem with time windows. The problem consis...
référence BibTeX
This paper addresses the problem of generating valid crew pairings in the context of a regional air carrier. The classical column generation solution appro...
référence BibTeX
We propose a common solution approach for different crew scheduling problems arising at the planning and operational levels in the airline industry. Specifi...
référence BibTeXA Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeXCrew 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 compo...
référence BibTeX
In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipat...
référence BibTeX
We consider the problem of finding a shortest path for a car-like robot (approximated by a point) maneuvering around obstacles. This robot is capable of for...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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 ...
référence BibTeX