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

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