تقرير
Submodularity and Local Search Approaches for Maximum Capture Problems under Generalized Extreme Value Models
| العنوان: | Submodularity and Local Search Approaches for Maximum Capture Problems under Generalized Extreme Value Models |
|---|---|
| المؤلفون: | Dam, Tien Thanh, Ta, Thuy Anh, Mai, Tien |
| المصدر: | European Journal of Operational Research - 300(2022) 953-965 |
| سنة النشر: | 2021 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control |
| الوصف: | 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 greed heuristic can always guarantee an (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 difference 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 the mixed logit models. |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1016/j.ejor.2021.09.006 |
| URL الوصول: | http://arxiv.org/abs/2102.05754 |
| رقم الأكسشن: | edsarx.2102.05754 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!