Submodularity and local search approaches for maximum capture problems under generalized extreme value models
We study the maximum capture problem in facility location under random utility models, i.e., the problem of seeking to locate new facilities in a competitive market such that the captured user demand is maximized, assuming that each customer chooses among all available facilities according to a rand...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2022
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/6239 https://ink.library.smu.edu.sg/context/sis_research/article/7242/viewcontent/Facilities_Locations__1_.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-7242 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-72422022-09-27T03:51:14Z Submodularity and local search approaches for maximum capture problems under generalized extreme value models DAM, Tien Thanh TA, Thuy Anh MAI, Tien We study the maximum capture problem in facility location under random utility models, i.e., the problem of seeking to locate new facilities in a competitive market such that the captured user demand is maximized, assuming that each customer chooses among all available facilities according to a random utility maximization model. We employ the generalized extreme value (GEV) family of discrete choice models and show that the objective function in this context is monotonic and submodular. This finding implies that a simple greedy heuristic can always guarantee a (1−1/e) approximation solution. We further develop a new algorithm combining a greedy heuristic, a gradient-based local search, and an exchanging procedure to efficiently solve the problem. We conduct experiments using instances of different sizes and under different discrete choice models, and we show that our approach significantly outperforms prior approaches in terms of both returned objective value and CPU time. Our algorithm and theoretical findings can be applied to the maximum capture problems under various random utility models in the literature, including the popular multinomial logit, nested logit, cross nested logit, and mixed logit models. 2022-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/6239 info:doi/10.1016/j.ejor.2021.09.006 https://ink.library.smu.edu.sg/context/sis_research/article/7242/viewcontent/Facilities_Locations__1_.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Facilities planning and design Maximum capture Random utility maximization Generalized extreme value Greedy heuristic Operations Research, Systems Engineering and Industrial Engineering Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Facilities planning and design Maximum capture Random utility maximization Generalized extreme value Greedy heuristic Operations Research, Systems Engineering and Industrial Engineering Theory and Algorithms |
spellingShingle |
Facilities planning and design Maximum capture Random utility maximization Generalized extreme value Greedy heuristic Operations Research, Systems Engineering and Industrial Engineering Theory and Algorithms DAM, Tien Thanh TA, Thuy Anh MAI, Tien Submodularity and local search approaches for maximum capture problems under generalized extreme value models |
description |
We study the maximum capture problem in facility location under random utility models, i.e., the problem of seeking to locate new facilities in a competitive market such that the captured user demand is maximized, assuming that each customer chooses among all available facilities according to a random utility maximization model. We employ the generalized extreme value (GEV) family of discrete choice models and show that the objective function in this context is monotonic and submodular. This finding implies that a simple greedy heuristic can always guarantee a (1−1/e) approximation solution. We further develop a new algorithm combining a greedy heuristic, a gradient-based local search, and an exchanging procedure to efficiently solve the problem. We conduct experiments using instances of different sizes and under different discrete choice models, and we show that our approach significantly outperforms prior approaches in terms of both returned objective value and CPU time. Our algorithm and theoretical findings can be applied to the maximum capture problems under various random utility models in the literature, including the popular multinomial logit, nested logit, cross nested logit, and mixed logit models. |
format |
text |
author |
DAM, Tien Thanh TA, Thuy Anh MAI, Tien |
author_facet |
DAM, Tien Thanh TA, Thuy Anh MAI, Tien |
author_sort |
DAM, Tien Thanh |
title |
Submodularity and local search approaches for maximum capture problems under generalized extreme value models |
title_short |
Submodularity and local search approaches for maximum capture problems under generalized extreme value models |
title_full |
Submodularity and local search approaches for maximum capture problems under generalized extreme value models |
title_fullStr |
Submodularity and local search approaches for maximum capture problems under generalized extreme value models |
title_full_unstemmed |
Submodularity and local search approaches for maximum capture problems under generalized extreme value models |
title_sort |
submodularity and local search approaches for maximum capture problems under generalized extreme value models |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2022 |
url |
https://ink.library.smu.edu.sg/sis_research/6239 https://ink.library.smu.edu.sg/context/sis_research/article/7242/viewcontent/Facilities_Locations__1_.pdf |
_version_ |
1770575898438795264 |