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 Problemwith Service Time and Mandatory & Incompatible Nodes (TOP-ST-MIN). This problem generalises two real-world healthcareapplications: (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 deterministicversion of the problem. To provide a meaningful analysis, new benchmark instance sets were generated in order to highlightthe impact of the new features on the TOP. A comprehensive quantitative study demonstrated the effectiveness and competitivenessof 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 wasdeveloped to handle stochasticity, while four Branch & Regret approaches were designed to manage dynamic aspects such ascustomer 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 comparedconsidering the deterministic version of the TOP-ST-MIN while a fairness over time is investigated considering the dynamicity of theproblem as for the Branch & Regret approaches