Solving the Regular Language-Constrained Team Orienteering Problem with Time Windows for Route Planning Applications
Nikolaos Vathis, Grammati E. Pantziou, Charalampos G. Konstantopoulos, Damianos Gavalas · 2024
We introduce the Regular Language-Constrained Team Orienteering Problem with Time Windows (RLC-TOPTW) as a generalization of the Team Orienteering Problem with Time Windows (TOPTW). The problem is pertinent to application domains which entail categorization of graph/network nodes and constraints associated with the categories of the nodes in the solution path. RLC-TOPTW captures any type of constraints as long as they can be described by regular expressions, and its solution provides a feasible path that satisfies the constraints. As RLC-TOPTW is NP-hard we present two efficient heuristic approaches: The first heuristic is based on the solution approach for solving the Regular Language-Constrained Orienteering Problem with Time Windows (RLC-OPTW) given in[1] while the second is a genetic algorithm approach. The proposed algorithms have been assessed using publicly available datasets.