The Team Orienteering Problem with Service Times and Mandatory & Incompatible Nodes

The thesis investigates a new variant of the Team Orienteering Problem (TOP), namely the Team Orienteering Problem with Service Time and Mandatory & Incompatible Nodes (TOP-ST-MIN). This problem generalises two real-world healthcare applications: (i) the daily swab test collection and (ii) the ambulance routing in post-disaster management. The TOP-ST-MIN is NP-hard and even determining a feasible solution has been shown to be NP-complete. Two mathematical formulations and corresponding exact and heuristic algorithms were developed to solve the deterministic version of the problem. To provide a meaningful analysis, new benchmark instance sets were generated in order to highlight the impact of the new features on the TOP. A comprehensive quantitative study demonstrated the effectiveness and competitiveness of the proposed models and algorithms also compared with the TOP state-of-the-art approaches. The thesis further explored stochastic travel and service times as well as dynamic aspects. An exact Integer L-shaped method was developed to handle stochasticity, while four Branch & Regret approaches were designed to manage dynamic aspects such as customer arrivals or disappearance, road closures and other environmental changes. Finally, the study has been extended including the concept of fairness. Different fairness approaches have been studied and compared considering the deterministic version of the TOP-ST-MIN while a fairness over time is investigated considering the dynamicity of the problem as for the Branch & Regret approaches