  Park-and-ride facilities are car parks where users can transfer to public
transportation. Commuters can use P&R facilities or choose to travel by car to
their destinations, and individual choice behavior is assumed to follow a logit
model. The P&R facility location problem identifies locations for a fixed
number of P&R facilities from among potential locations such that the number of
users of the P&R facilities is maximized. This problem has previously been
formalized under a multinomial logit demand function. However, as it imposes
the strong condition of the independence of irrelevant alternatives, the MNL
model is unable to represent the real-world P&R facility location problem
exactly. Respecting the nested structure of individual choice behavior, we
generalize the MNL model to a nested logit model and develop two computational
methods -- neighborhood search and randomized rounding -- to solve large-scale
P&R facility location problems under the NL demand function. The neighborhood
search method first finds one feasible solution and then improves the feasible
solution to the next one along an edge of the polyhedron whose vertices are the
feasible solutions. The neighborhood search method is randomized to create an
adaptive randomized rounding procedure. Computational experiments verified that
the computational methods were able to solve the nonlinear optimization problem
under the NL demand function on 1,000 medium-scale instances to exact
optimality rapidly. Specifically, the methods were verified to solve the MNL
model to exact optimality 10,000 times faster than the mixed integer linear
programming formulation described in the literature. We performed additional
computational experiments to assess the performance of our computational
methods on a variety of large-scale instances. Our computational analysis also
elucidates the difference between the MNL and NL models.
