Mardi 26 novembre 2019, 14h, en salle P310
Abstract :
Variants of the Travelling Salesman Problems (TSP) which do not require to visit all customers have been studied extensively (e.g., the Orienteering Problem and the Stochastic TSP). In this presentation we give a characterisation of these variants in terms of the decision power attributed to the tour planner, show that only the two extreme cases - no power, complete power - have been studied in detail, and propose an intermediate problem motivated by a real-life case: crowdsourcing of last-mile delivery. Given the complexity of the problem, which requires the solution of an exponential number of NP-complete sub-problems (!!!) we propose heuristic approaches, some of which use machine learning techniques.