Transcriptic: Flight Routing

readme.mdown

Flight Routing

• Difficulty: Medium
• Expected time: 2 hours

Description

An airline wants to serve its passengers as efficiently as possible. This airline's network is defined as the set of cities (A, B, C, ..., AA, AB, ...) it serves. Each city has a coordinate in 2D euclidian space (x, y) that defines its location. At any given time, the airline has a set of tickets that are active; that is, need to be flown. A ticket is a tuple of cities (A, B) giving the passenger's starting and ending cities. The airline needs to turn each ticket into an itinerary, which is an ordered list of flights to be made to deliver the passenger from point A to point B. The choice of legs to serve depends on the overall demands of the network. The airline is tracking two distinct key metrics: total distance flown and number of legs flown. The total distance flown should be minimized in order to save fuel, which is very expensive. However, the number of legs flown should also be kept down since aircraft maintenance, and eventual retirement, is partly based on "cycles," or takeoffs and landings. Therefore, given:

1. a map of cities -> (x, y) coordinates, and,
2. a list of tickets (city pairs to be transited)

determine:

1. the list of cities to connect directly (legs to offer),
2. the itinerary to fly for each ticket,
3. the total expected mileage to fly, and,
4. the total expected number of takeoffs needed to clear the tickets given.

assuming:

1. $1.00 per unit distance flown
2. $0.20 per takeoff/landing cycle

Minimize dollars spent to fulfill all tickets.

This is an optimization problem, so your goal isn't just to return any solution, but the most efficient one you can find. You're welcome to cite (and build off of) recent literature in constructing your solution. A theoretical explanation of the challenges inherent in this problem along with your concrete solution is a major bonus.

Solution Guidelines

You can use C, C++, Java, Python, Perl, Ruby, PHP, Javascript, Clojure, or Scala in your solution. Please provide a script such that your solution is invokable using:

`./flightrouting cities.csv tickets.csv`

For example, if using Java, you might provide a file flightrouting that contains:

`java -cp flightrouting.jar flightrouting.Main`

Scripting languages such as Python and Ruby should be fine as-is.

Your solution should run a standalone application without requiring any external resources (i.e., remote servers). Your solution should take no longer than 60 seconds to run.

Your solution results should be written to STDOUT.

cities.csv

city_id  x  y
a        2  2
b        1  8
c        4  9
d        5  4
e        6  7
f        7  9
g        7  2
h        9  4
i        9  7
j        11 10
k        11 2
l        13 5

tickets.csv

from_city_id  to_city_id
f             i
b             j
d             h
a             j
b             j
f             i
a             f
b             j
a             i
b             k
b             j
h             j
e             k
g             f
c             a
k             b
j             b
l             c
j             a
f             b
d             j
i             j
j             i
e             b
j             b
b             j
j             a
b             c
a             b
k             a
k             f
k             b
a             h
h             f
j             c
l             e
l             c
d             j
c             b
j             c
j             l
j             a
b             k
b             f
a             i
a             i
i             j
j             b
b             f
f             l
f             k
a             i
a             g
g             e
g             d
d             e
k             e
e             j
e             b
f             e
i             j
i             k
i             g
a             b
g             f
f             d
a             f
a             j
a             e
a             i
a             j
b             j
b             g
g             f
g             h
g             b
j             e
d             j
g             i
k             a
b             c