Time table of all LIRMM seminars

Prenons un graphe non orienté. Il peut représenter les routes d’une ville, la couverture d’un territoire par des capteurs, ou même les relations entre des individus. Si nous voulons installer des caméras à des intersections pour surveiller toutes les routes, il existe une solution simple, en mettre à chaque intersection. Si nous voulons éviter d’utiliser deux capteurs côtes-à-côtes pour surveiller un territoire, il existe une solution simple, choisir les capteurs un par un en oubliant tous les voisins. Si nous voulons un ensemble d’individus qui ne se connaissent pas, qui sont en relation avec tous les autres, mais que nous ne pouvons choisir que par grappes, existe-t-il toujours une solution simple ? D’un point de vue théorique, ce problème est celui de l’Indépendant Dominant avec des Obligations. Nous verrons que déterminer l’existence d’une solution devient particulièrement difficile, en particulier que ce problème est NP-complet même dans un chemin. Pour saisir la place des obligations dans ce saut de complexité, nous nous pencherons également sur son impact dans des problèmes de tournées.

Workload equity is an emerging topic in the routing literature. Typically, efficient solutions usually lack equity, thus, the challenge is to propose models and algorithms capable of finding solutions with an equitable workload distribution between drivers with a low impact on the routing cost. In the current literature, most papers naturally manage equity within a bi-objective model. In this work, we rather use the classic min cost objective as the single objective and manage equity on the drivers route costs with equity constraints. We use a test-bed routing problem motivated by the non-emergency transportation of patients integrating our equity constraints. We show that the straightforward set partitioning formulation can not be solved efficiently by a standard branch-and-price approach and propose three original solution methods, two branch-and-price algorithms and a heuristic. The proposed branch-and-price algorithms are based on new models to manage the equity constraints. In the first model, the variables (columns) are indexed by a route and a driver. In the second model, equity constraints are expressed on nodes instead of drivers. The heuristic is based on a dichotomic search. Algorithms are evaluated on real world based instances with up to 50 customers. Computational experiments highlight pros and cons of each algorithm and show that equitable solutions can be found with low impact on the routing cost.