  In this paper, we study a facility location problem within a competitive
market context, where customer demand is predicted by a random utility choice
model. Unlike prior research, which primarily focuses on simple constraints
such as a cardinality constraint on the number of selected locations, we
introduce routing constraints that necessitate the selection of locations in a
manner that guarantees the existence of a tour visiting all chosen locations
while adhering to a specified tour length upper bound. Such routing constraints
find crucial applications in various real-world scenarios. The problem at hand
features a non-linear objective function, resulting from the utilization of
random utilities, together with complex routing constraints, making it
computationally challenging. To tackle this problem, we explore three types of
valid cuts, namely, outer-approximation and submodular cuts to handle the
nonlinear objective function, as well as sub-tour elimination cuts to address
the complex routing constraints. These lead to the development of two exact
solution methods: a nested cutting plane and nested branch-and-cut algorithms,
where these valid cuts are iteratively added to a master problem through two
nested loops. We also prove that our nested cutting plane method always
converges to optimality after a finite number of iterations. Furthermore, we
develop a local search-based metaheuristic tailored for solving large-scale
instances and show its pros and cons compared to exact methods. Extensive
experiments are conducted on problem instances of varying sizes, demonstrating
that our approach excels in terms of solution quality and computation time when
compared to other baseline approaches.
