On the online path extension problem – Location and routing problems in board games
share
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.
READ FULL TEXT