A Monte Carlo Tree Search for the Optimisation of Flight Connections

In 2017, Kiwi.com proposed the Travelling Salesman Problem 2.0. Despite some similarities with the classic Travelling Salesman Problem (TSP), the problem is more complex. It can be characterised as an asymmetric, time-constrained and generalised TSP. Moreover, infeasibility further complicates the challenge, as no flights may be available between certain airports on specific days. Exact methods often fail in solving these <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{N} \mathcal{P}$</tex> -Hard problems. Therefore, alternative approaches, such as heuristics, are typically favoured. A Monte Carlo Tree Search (MCTS) is implemented to tackle Kiwi's problem, an algorithm traditionally used in board games but adapted here for air travel optimisation. The MCTS has been chosen for its proven effectiveness in handling complex and high-dimensional search spaces.