  We consider an online version of a longest path problem in an undirected and
planar graph that is motivated by a location and routing problem occurring in
the board game "Turn & Taxis". Path extensions have to be selected based on
only partial knowledge on the order in which nodes become available in later
iterations. Besides board games, online path extension problems have
applications in disaster relief management when infrastructure has to be
rebuilt after natural disasters. For example, flooding may affect large parts
of a road network, and parts of the network may become available only
iteratively and decisions may have to be made without the possibility of
planning ahead.
  We suggest and analyse selection criteria that identify promising nodes
(locations) for path extensions. We introduce the concept of tentacles of paths
as an indicator for the future extendability. Different initialization and
extension heuristics are suggested on compared to an ideal solution that is
obtained by an integer linear programming formulation assuming complete
knowledge, i.e., assuming that the complete sequence in which nodes become
available is known beforehand. All algorithms are tested and evaluated on the
original "Turn & Taxis" graph, and on an extended version of the "Turn & Taxis"
graph, with different parameter settings. The numerical results confirm that
the number of tentacles is a useful criterion when selecting path extensions,
leading to near-optimal paths at relatively low computational costs.

Optimization and Control;Discrete Mathematics