Competitive Facility Location under Cross-Nested Logit Customer Choice Model: Hardness and Exact Approaches
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911979618172928 |
|---|---|
| author | Le, Ba Luat Mai, Tien Ta, Thuy Anh Ha, Minh Hoang Vu, Duc Minh |
| author_facet | Le, Ba Luat Mai, Tien Ta, Thuy Anh Ha, Minh Hoang Vu, Duc Minh |
| contents | We study the competitive facility location problem, where a firm aims to establish new facilities in a market already occupied by competitors. In this problem, customer behavior is crucial for making optimal location decisions. We explore a general class of customer choice models, known as the cross-nested logit (CNL) model, which is recognized for its flexibility and generality in predicting people's choice behavior. To explore the problem, we first demonstrate that it is NP-hard, even when there is only one customer class. We further show that this hardness result is tight, as the facility location problem under any simpler choice models (such as the logit or nested logit) is polynomial-time solvable when there is one customer class. To tackle the resulting facility location problem, we demonstrate that the objective function under a general cross-nested structure is not concave. Interestingly, we show that by a change of variables, the objective function can be converted to a convex program (i.e., a maximization problem with a concave objective and convex constraints), enabling it to be solved to optimality via an outer-approximation algorithm. Extensive experiments show the efficiency of our approach and provide analyses on the benefits of using the cross-nested model in the facility location context. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_02925 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Competitive Facility Location under Cross-Nested Logit Customer Choice Model: Hardness and Exact Approaches Le, Ba Luat Mai, Tien Ta, Thuy Anh Ha, Minh Hoang Vu, Duc Minh Optimization and Control We study the competitive facility location problem, where a firm aims to establish new facilities in a market already occupied by competitors. In this problem, customer behavior is crucial for making optimal location decisions. We explore a general class of customer choice models, known as the cross-nested logit (CNL) model, which is recognized for its flexibility and generality in predicting people's choice behavior. To explore the problem, we first demonstrate that it is NP-hard, even when there is only one customer class. We further show that this hardness result is tight, as the facility location problem under any simpler choice models (such as the logit or nested logit) is polynomial-time solvable when there is one customer class. To tackle the resulting facility location problem, we demonstrate that the objective function under a general cross-nested structure is not concave. Interestingly, we show that by a change of variables, the objective function can be converted to a convex program (i.e., a maximization problem with a concave objective and convex constraints), enabling it to be solved to optimality via an outer-approximation algorithm. Extensive experiments show the efficiency of our approach and provide analyses on the benefits of using the cross-nested model in the facility location context. |
| title | Competitive Facility Location under Cross-Nested Logit Customer Choice Model: Hardness and Exact Approaches |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2408.02925 |