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

Abstract

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

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