C. Valverde, J. Puerto Albandoz
This talk deals with routing design problems in a continuous space with neighbours and barriers. Each one of these two elements, neighbours and barriers, makes the problems harder than their standard counterparts. Therefore, mixing both together results in a new challenging problem that, as far as we know, has not been addressed before but that has applications for inspection and surveillance activities and the delivery industry assuming uniformly distributed demand in some regions.
We provide exact mathematical programming formulations for both problems assuming polygonal barriers and neighbours that are second-order cone (SOC) representable. These hypotheses give rise to mixed integer SOC formulations that we preprocess and strengthen with valid inequalities. The paper also reports computational experiments showing that our exact method can solve instances with 75 neighbourhoods and a range between 125-145 barriers.
Palabras clave: Routing, Travelling salesman, Networks, Conic programming and interior point methods
Programado
GT12.GELOCA1 Sesión Invitada
10 de noviembre de 2023 09:30
CC1: Auditorio