需求具內生性的服務設施位置問題

A Service Facility Location Model with Endogenous Consumer Demands

廖偉宏(Wei-Hung Liao)

指導教授 ： 孔令傑

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201601596

摘要

在顧客透過設施據點取得服務或商品的商業模式下，設施據點數量與位置影響消費者需求是一個很正常的現象，消費者周遭的設施據點越多；代表消費者能夠越便利的取得服務或商品，同時有意願使用服務或產品的顧客數量也會增加。有趣的是，設置一處設施據點不只會影響需求，還會影響其他設施據點對需求的影響，以YouBike為例，在捷運發達的台北，很多使用者利用YouBike作為從捷運站點到實際目的地之間的短程交通工具，因此若在捷運站點與工作區、學校、居住地之間皆設置站點，將會帶來額外的網路效益。
在本研究中，我們研究一個供應商該選擇哪些位置設置站點才能夠使其利益最大化，他需要考慮到的主要因素有兩個，分別為單獨效益以及網路效益，我們將這兩個效益當作一個凹函數的參數使我們的模型具有邊際效益遞減的效果，最後考慮各站點的建造成本，我們得到一個不可分的非線性整數規劃問題。
之後我們證明背包問題為此問題的子問題得到此問題為弱NP-困難問題，並提出ARSA、NGA兩個演算法。我們由著名的背包問題演算法中獲得靈感，設計出ARSA演算法，並證明在特定情況下所提出的解與最佳解相距在一定比例內。NGA演算法則是簡單的貪婪演算法。最後我們透過數值分析驗證了兩種演算法的表現、穩定性、計算時間。

關鍵字

設施位置 ； 網路效應 ； 內生需求 ； 近似演算法

並列摘要

For those facilities that serve end consumers directly, it is natural that consumer demands are affected by the number and locations of facilities. Vehicle sharing system provide a good illustration, as more users join the system when there are more rental sites. Interestingly, opening a facility not only affects customer demands directly but also changes how other facilities affect consumer demands. For example, for a typical bike sharing system, users often travel from the subway stations to their offices, schools, and home. When there are rental sites at both sides, an additional network effect emerges.
In this study, we investigate the problem of a profit maximizing retailer in selecting a set of facilities to build from a given set of locations. We assume that the retailer needs to consider two major types of effects: (1) the stand-alone benefit of a single facility and (2) the network benefit between two facilities. The sum of these two benefits will then be input into a nondecreasing concave function to capture the diminishing marginal benefit property. By considering the overall benefit and total cost of building facilities, the retailer decides where to build facilities to maximize her profit. The problem is then formulated as a nonseparable nonlinear integer program.
We first prove that the problem is weakly NP-hard. As one of the most common method to approach NP-hard problems is to develop heuristic algorithms, we propose two algorithms. The first one, which is based on relaxing the integer constraints, is called the approximation-relaxation-sorting algorithm (ARSA). The second one, which is called the naive greedy algorithm (NGA), is a straightforward greedy algorithm. We show that ARSA has different worst-case performance guarantees for some special cases of our general problem. We then study the average performance of the two algorithms in various scenarios through numerical experiments.

並列關鍵字

Facility location ； network effect ； endogenous consumer demands ； approximation algorithm

參考文獻

Aboolian, R., O. Berman, D. Krass. 2007. Competitive facility location model with concave demand. European Journal of Operational Research 181(2) 598-619.

Arya, V., N. Garg, R. Khandekar, A. Meyerson, K. Munagala, V. Pandit. 2004. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing 33(3) 544-562.

Berman, O., D. Krass. 1998. Flow intercepting spatial interaction model: a new approach to optimal location of competitive facilities. Location Science 6(1-4) 41-65.

Caprara, A., H. Kellerer, U. Pferschy, D. Pisinger. 2000. Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research 123(2) 333-345.

Feige, U., V.S. Mirrokni, J. Vondrk. 2011. Maximizing non-monotone submodular functions. SIAM Journal on Computing 40(4) 1133-1153.