My next trip is an adventure to the Middle East, prompted by a fare drop by Turkish Airlines. San Francisco to Istanbul via Turkish is a new route and fares were quite good relative to historical data (along with other critera), prompting a nifty algorithm to send me an email. Seeing $680 round-trip, I naturally bought the ticket.
Primarily three modifications of my previous algorithm allow for novelty:
- Searching round trip fares when they are cheaper than one way; that is, introducing a round-trip fare when a route of one ways has a complementary OD pair (e.g. SFO -> HRG -> [intermediate cities] -> HRG -> SFO has a complementary/reversed OD pair)
- Leveraging intermediate city fares, omitting the remainder of an itinerary (e.g. buying a ticket from Egypt to Hungary, but getting off at a layover in Turkey
- Airport proximity: allowing different airport codes per city hop (e.g. flying into Cyprus’ ECN, out of LCA, which is 45km away)
It turns out, including the above does not significantly increase the search space, which is a nice way to say, a linear penalty is miniscule if we’re already at O(n!), where n is the number of airport codes. Consequently, with naive brute force enumeration, I find runtime to be sub-20 seconds via Pypy.
The full route is as follows:
- San Francisco (SFO) -> Istanbul (IST) -> Hurghada (HRG) $680 — get off at IST
- Istanbul (IST) -> Cyprus (ECN) $108
- Cyprus (LCA) -> Tel Aviv (TLV) $76
- Tel Aviv (TLV) -> Amman (AMM) — unknown: bus fare
- Amman (AMM) -> Cairo (CAI) $184
- Cairo (CAI) -> Hurghada (HRG) $103
- Hurghada (HRG) -> San Francisco (SFO) — return flight
Total: $1150 (plus bus fare from Jerusalem to Amman).
I also had a few goals/constraints, which all were satisified:
- No propeller aircraft — in this case, all A320s
- Direct flights only
- Reasonable departure times — i.e. no waking up early or arriving after 8pm
Definitely lots of opportunity for improvement computation/algorithm-wise — perhaps another trip will yield some insight.