Click here to start

Table of contents

Computational Complexity of Air Travel Planning

Air Travel Planning


North American flights

The Flight Network

San Francisco to Boston: 2,000 paths

San Francisco to Boston: 10,000 paths

Growth rate of # of paths

Outline: Prices


Fare Components

Fare Components 2

Priceable Units

PU: Adv Purchase

PU Sat Night

PU Dependencies


Fare Portfolio

Fare Rules

Sample Fare Rules

Summary: The Search Problem

Example with numbers

Why this mess ? Variable pricing

Outline: Complexity

Some Complexity Results

Single fare, fixed route is NP-hard

Fixed flights, variable fares is NP-hard

Full search is EXPSPACE-hard



EXPSPACE details

Full search is unsolvable

How to multiply with fares

Complexity Review

Outline: Demos

TM Simulations

R-to-L Increment

LAX-NCE graphics

Pose Query

Incrementer Results

Bit rotation


Unary Multiplication

Binary Multiplication

Outline: Availability

Seat Availability

Availability Dynamics

O & D Availability

Availability Queries

Further Info


Author: Carl de Marcken, ITA Software


Further information:
These are a set of annotated slides ITA Software has prepared on the computational complexity of air travel planning. The PDF version may be more readable.

Download presentation in PDF format