Applications of Combinatorial Optimization

Vangelis Th. Paschos

• Publisher: Wiley-ISTE
• Year: 2014
• Print ISBN: 9781848216587
• eBook ISBN: 9781119015246
• Edition: 2
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts:
- On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity;
- Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming;
- Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.

Chapter 1

Airline Crew Pairing Optimization

1.1. Introduction

In the airline industry, optimizing and automating the building of crew pairings is a major financial and organizational issue. The problem consists of covering all the company’s flights, programmed in a given time window, with teams made up of cockpit personnel (pilots, copilots) and of cabin personnel (stewardesses, stewards) at a minimum cost. With a frequency of several days (in the order of a week), each crew leaves from the base to which it is assigned, carries out a certain number of flights, and comes back to the base. This sequence of flights with a return to the base is called a rotation, or pairing. Drawing up the pairings of an airline company is highly constrained by international, national and internal work regulations, and by the limited availability of resources. These constraints make the problem particularly hard to solve. Besides the gains in terms of organization, security and calculation time, the use of optimization programs and models for this problem allows big companies to make substantial financial gains. It is not unusual for a reduction of 1% in the total cost of the rosters to result in savings of several tens of millions of dollars for big companies [DES 97], which is one reason for the abundant fundamental and applied research on this subject. The general crew pairing problem with resource constraints problem (CPP-RC) can be formulated as a minimum cost multicommodity flow problem with additional variables and resource constraints. Even though in most applications the cost of a rotation is non-linear [DES 97, LAV 88], in this chapter we will restrict ourselves to the case where the cost function is a linear approximation. The ways of constructing a network of feasible pairings, and calculating the cost of the rosters, along with the associated mathematical program, are presented in section 1.2. Section 1.3 gives an overview of classical solution techniques, with a focus on the column generation method, whose associated subproblem is studied in section 1.4. Section 1.5 concludes the chapter.

1.2. Definition of the problem

The set of flights to be covered by the crews is denoted by

= {1,…, n}. The flight program and the associated timetables are established more or less exactly for the considered period, in the order of a month or a week depending on the size of the company. The term flight associated with each element i ∈

is abusive in some cases, insofar as i may in reality represent a sequence of aggregated and indivisible flights, that is a series of flights that can only be covered by the same crew. Also, the task to be covered by a crew is often not only a flight, but rather a flight service that may start before and end after the actual flight, to account for the time needed for preparing the plane and for accompanying passengers, for example. However, we will maintain this flight terminology, to help readability. For each flight i ∈

we know:

i) the departure time

;

ii) the arrival time

;

iii) the departure airport

;

iv) the destination airport

.

A rotation must start and end at one of the company’s bases. The set

of bases is generally made up of large interconnection platforms called hubs. The CPP often has resource constraints on the pairings. In order to take the pairing validity constraints into account, a classical modeling associates a subnetwork, constructed in the following way, with each crew.

1.2.1. Constructing subnetwo...

Table of contents

• Cover
• Table of Contents
• Title Page
• Copyright
• Preface
• Chapter 1: Airline Crew Pairing Optimization
• Chapter 2: The Task Allocation Problem
• Chapter 3: A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems
• Chapter 4: Production Planning
• Chapter 5: Operations Research and Goods Transportation
• Chapter 6: Optimization Models for Transportation Systems Planning
• Chapter 7: A Model for the Design of a Minimum-cost Telecommunications Network
• Chapter 8: Parallel Combinatorial Optimization
• Chapter 9: Network Design Problems: Fundamental Methods
• Chapter 10: Network Design Problems: Models and Applications
• Chapter 11: Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints
• General Bibliography
• List of Authors
• Index