Problem: In this programming assignment, you are tasked with the computation of the capacity of a simplified model of the National Airspace System (NAS). More specifically, we would like to compute the largest number of individuals that can travel between two large cities (in our case between Source: Los Angeles (LAX) and Destination: New York City (JFK)), in a 24 hour time period, using commercially available flights. Our 24 hour period will start at 6:00AM on one day and and end at 5:59 AM on the following day. Please use the data set that will be provided to you. The dataset is based on the flight schedule data published by the three largest airlines, American Airlines (AA), Delta Airlines (DL) and United Airlines (UA). Aside from these LAX and JFK, two our simplified model of NAS consists of the following airports (codes) as well - San Francisco (SFO), Phoenix (PHX), Seattle (SEA), Denver (DEN), Atlanta (ATL), Chicago (ORD), Boston (BOS) and Washington DC (IAD).
• A passenger travel starts at LAX and ends at NYC.
• For multi-hop itineraries, the arrival time of a flight at an intermediate airport must be earlier than the departing time of the next flight from that airport.
Datasets: We will be uploading a sample timetable which includes flight information for all three airlines. The first column is the source airport, the second column is the destination airport, the third column indicates the departure time, the fourth column indicates the arrival time and the final column indicates the capacity of that flight. The filename is “flights.txt”.
1
Hint: To accomplish this task, you might be thinking in similar lines with the process of “constructing a directed graph with all the cities represented as nodes and directed edges from a node A to B if there is a flight travelling from city A to city B”. However, such a graph only captures the spatial information (flights between cities) and not the temporal information (time of the flights). Thus, such an approach is incomplete and is not going to capture the entire picture. The graph you create should capture the temporal aspect of the task as well, in order to accurately capture the capacity of the NAS. For further simplification, you can round the flight times (departure and arrival) to the nearest hour.
2
