TY - JOUR
T1 - A branch-and-bound algorithm for the maximum capture problem with random utilities
AU - Freire, Alexandre S.
AU - Moreno, Eduardo
AU - Yushimito, Wilfredo F.
N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2016/7/1
Y1 - 2016/7/1
N2 - The maximum capture problem with random utilities seeks to locate new facilities in a competitive market such that the captured demand of users is maximized, assuming that each individual chooses among all available facilities according to the well-know a random utility model namely the multinomial logit. The problem is complex mostly due to its integer nonlinear objective function. Currently, the most efficient approaches deal with this complexity by either using a nonlinear programing solver or reformulating the problem into a Mixed-Integer Linear Programing (MILP) model. In this paper, we show how the best MILP reformulation available in the literature can be strengthened by using tighter coefficients in some inequalities. We also introduce a new branch-and-bound algorithm based on a greedy approach for solving a relaxation of the original problem. Extensive computational experiments are presented, benchmarking the proposed approach with other linear and non-linear relaxations of the problem. The computational experiments show that our proposed algorithm is competitive with all other methods as there is no method which outperforms the others in all instances. We also show a large-scale real instance of the problem, which comes from an application in park-and-ride facility location, where our proposed branch-and-bound algorithm was the most effective method for solving this type of problem.
AB - The maximum capture problem with random utilities seeks to locate new facilities in a competitive market such that the captured demand of users is maximized, assuming that each individual chooses among all available facilities according to the well-know a random utility model namely the multinomial logit. The problem is complex mostly due to its integer nonlinear objective function. Currently, the most efficient approaches deal with this complexity by either using a nonlinear programing solver or reformulating the problem into a Mixed-Integer Linear Programing (MILP) model. In this paper, we show how the best MILP reformulation available in the literature can be strengthened by using tighter coefficients in some inequalities. We also introduce a new branch-and-bound algorithm based on a greedy approach for solving a relaxation of the original problem. Extensive computational experiments are presented, benchmarking the proposed approach with other linear and non-linear relaxations of the problem. The computational experiments show that our proposed algorithm is competitive with all other methods as there is no method which outperforms the others in all instances. We also show a large-scale real instance of the problem, which comes from an application in park-and-ride facility location, where our proposed branch-and-bound algorithm was the most effective method for solving this type of problem.
KW - Branch and bound
KW - Facility location
KW - Maximum capture
KW - Random utility model
UR - http://www.scopus.com/inward/record.url?scp=84960365012&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2015.12.026
DO - 10.1016/j.ejor.2015.12.026
M3 - Article
AN - SCOPUS:84960365012
SN - 0377-2217
VL - 252
SP - 204
EP - 212
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -