TOP-ST-MIN: a new variant of the Team Orienteering Problem

  • place:

    Gebäude 05.20, Raum 4A-21

  • sws:

    23. Februar 2023

  • Referent:

    Prof. Roberto Aringhieri, Università di Torino (Italy)

  • Zeit:


TOP-ST-MIN: a new variant of the Team Orienteering Problem

During the Italian lock-down, between an online exam and a [ zoom | webex | teams | bbb | meet ] call, we started to study a problem arising in the everyday management of the Covid pandemic, that is the daily swab test collection problem (DSTCP). The idea stems from the paper in which the Digital Contact Tracing was suggested as containment measure against the Covid pandemic.

Almost at the same time, we were working on the Ambulance Routing Problem (ARP). The ARP consists in finding the best ambulance tours to transport the patients in relief operations after a disaster.

Both the DSTCP and the ARP can be modeled as a variant of the classical Team Orienteering Problem (TOP) that we called TOP with Service Time and Mandatory and Incompatible Nodes (TOP-STMIN).

In this talk, we briefly introduce the DSTCP and the ARP to highlight the three characteristics (service times, mandatory and incompatible nodes) that jointly determine the new variant of the TOP. Then we describe our ongoing work on the TOP-ST-MIN (formulations, algorithms, preliminary results). After discussing the so called price of fairness, we report some numerical results obtained considering three alternative and general approaches to model the fairness in the case of the ARP. Concluding remarks closes the talk.