Table of contents

Computational Complexity of Air Travel Planning

Air Travel Planning

Outline

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

Prices

Fare Components

Fare Components 2

Priceable Units

PU: Adv Purchase

PU Sat Night

PU Dependencies

Partitions

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

One-step

Multi-step

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

Multiplication

Unary Multiplication

Binary Multiplication

Outline: Availability

Seat Availability

Availability Dynamics

O & D Availability

Availability Queries

Further Info

Exercise

Author: Carl de Marcken, ITA Software

Homepage: http://www.itasoftware.com/

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