Optimization Problems

You have started a new travel website that finds the cheapest direct or multi-leg flight between any given origin and destination. You do this by first asking your customer to enter information about his/her desired departure date, time, and the origin, as well as his/her desired arrival date, time, and the destination. You will then get information on all flights departing from the origin whose departure times are within your customer’s specifications (leg 1). For each of those flights, you will get information on all flights that will depart after at least an hour from the first flight’s arrival time from the same airport (leg 2). You will repeat this until a flight’s destination is the same as your customer’s destination or its arrival date and time is not within your customer’s acceptable arrival date and time. This will give you a table like the following:

AirportABCDEDESTOrigin140200150–900A-100-170–B–200180400-C—-250-D—-160300E—–210

The entries in the above table represent the total cost of using that route.
Specifically, it includes any disutility that your customer may experience from the layover period in any airport other than the origin and destination.
If a cell is filled with “-“, it means that it is not possible to go from the airport identified by the cell’s row label, to the airport identified by the cell’s column label.
For example, there is no flight between airports A and C that fits your customer’s specification.

Here are a few other examples:

• There is a flight from origin to airport A, and it costs 140.
• There is a flight from airport A that goes to airport B and it costs 100. There is also a flight from airport A that goes to airport D and it costs 170.
• There is a flight from airport D that goes to airport E and costs 160. There is also a flight from airport D that goes to Destination (DEST) and costs 300