考慮顧客偏好與內生產能決策之設施位置問題

A Facility Location Problem with Customer Preference and Endogenous Capacity Decision

江柏宣(Po-Hsuan Chiang)

指導教授 ： 孔令傑

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

https://doi.org/10.6342/NTU201703025

摘要

以往在考慮位置設施問題時，常常會假設使用者能夠被任意指派到任何一個設施。這樣的假設在討論提供服務的設施時就不太適用，一旦設施需要直接面對顧客而不是面對生產線上的下游時，消費者對於每個設施可能會有屬於自己的偏好，這些偏好可能來自於設施的位置、大小、提供的服務品質等等。決策者並不能強迫顧客去特定的設施，只能被動提供設施，由顧客來選擇。
在本研究中，我們研究一個決策者要如何根據已知的消費者偏好，去選擇設施的位置以及規模，使其利益最大化。我們考慮的情境有兩個階層，首先決策者決定設施的建造計畫後，接著消費者根據自己的偏好決定要去的設施。
針對這個兩階層的情境，我們設計出一個單階層的整數規劃模型。由於最大覆蓋問題是我們的問題的一個特例，我們便藉由一些經典的最大覆蓋問題演算法中得到靈感，再將消費者如何選擇設施的過程轉化為網路最大流問題，進而設計出一個以貪婪法為基礎的演算法，並且證明在特定情況下所提出的解與最佳解相距在一定比例內。我們同時提出另一個版本的演算法，將網路最大流問題以簡單的方式得到估計值，以大幅縮短求解時間。最後，我們透過數值分析驗證了我們的演算法的表現與求解時間。

關鍵字

設施位置問題 ； 服務設施位置問題 ； 近似演算法 ； 最大覆蓋問題 ； 網路最大流問題

並列摘要

When we talk about facility location problems, we often assume that a user can be assigned to any facility by the decision maker. This assumption does not hold for service facilities. When facilities are providing service to customers rather than, say, other entities in a supply chain, customers often have their own preferences influenced by the location, capacity, service level, etc, of the facilities. The decision maker cannot enforce customer to go to a certain facility. Instead, he can only decide the locations and scales of built facilities. Customers will choose where to go by themselves.
In this study, we formulate our facility location problem as a single-layer integer program and find that the maximum cover problem is a special case of our problem. Inspired by some famous algorithms for the maximum cover problem, we design a greedy algorithm by transforming customers’ decision into a maximum flow problem. We show that the algorithm has worst-case performance guarantees in some special cases.
By using a simple method to estimate the value of maximum flow, we propose a modified algorithm, which may perform worse than the first one but runs much faster than it. Finally, we study the average performance and computation time of the modified algorithm in various scenarios through numerical experiments

並列關鍵字

Facility location problem ； Service facility location problem ； Approximation algorithm ； Maximum coverage problem ； Maximum flow problem

參考文獻

Liao, W.H. 2016. A service facility location model with endogenous consumer demands. Master’s thesis, National Taiwan University.

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

Ahuja, Ravindra K., James B. Orlin, Clifford Stein, Robert E. Tarjan. 1994. Improved algorithms for bipartite network flow. SIAM Journal on Computing 23(5) 906–933.

Camacho-Vallejo, J., A. Cordero-Franco, R.G. Gonzlez-Ramrez. 2014. Solving the bilevel facility location problem under preferences by a stackelberg-evolutionary algorithm. Mathematical Problems in Engineering 2014.

Goldberg, Andrew V., Robert E. Tarjan. 1988. A new approach to the maximum-flow problem. Journal of the ACM 35(4) 921–940.