The Hampered Traveling Salesman Problem with Neighbourhoods

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.

Keywords: Routing, Travelling salesman, Networks, Conic programming and interior point methods

GT12.GELOCA1 Invited Session
November 10, 2023  9:30 AM
CC1: Audience

C. Domínguez Sánchez, R. Gázquez, J. M. Morales, S. Pineda

F. Temprano Garcia, D. Ponce López, J. Puerto Albandoz

G. González Domínguez, J. Puerto Albandoz, V. Blanco Izquierdo

B. Cobeña, I. Contreras, L. I. Martínez Merino, A. M. Rodríguez Chía