需求具內生性的市場設址共同決策問題

Abstract

大規模設址規劃中，經常會同時涉及到一些區域級別的潛在成本，這些潛在成本可能會以多種形式存在，例如各區政府對於特定產業可能會各自有不同程度的限制，甚或可能是不同類型的補助，這類型的區域級別要素可以被認知為成本般的存在。以充電站的建設為例，如美國各州對於其規定與補助各不相同，有些州別認定充電站為單純的電力轉賣，要求業者須要持有指定執照才能夠建設，而有些州別則要求業者必須要是電力公司的身分才能夠建設。 在本研究中，我們研究一個供應商在市場設址的雙層級問題中如何共同規畫市場以及設址的選擇才能使其利益最大化，他需要考慮的主要因素為建設各站址的效益以及選擇市場的成本，我們將效益當作一個凹函數，使我們的模型具有邊際效益遞減的效果，最後考慮各站點的建造成本，我們得到一個不可分割的非線性整數規劃問題。 藉由前人的研究，我們可以證明此問題的為NP-hard問題，並提出DSAA 演算法來處理此問題。我們藉由前人的研究啟發而設計出此 DSAA 演算法，並且證明在特定情況下此演算法所提出的解答與最佳解之間存在有效能保證。最後我們透過數值分析驗證了兩種演算法的表現、穩定性、計算時間。

A joint market selection and facility location problem is a problem that can be observed regularly yet unsolved. For a large-scale facility planning problem, one must not ignore costs for choosing specific market. Market costs can take form of but not limited to regional government regulation, which will increase or decrease the amount of budget needed for entering a specific market. For example, the construction of electronic automobile charging station is considered as resale in State of Washington and thus construction of charging station requires permit from government, whereas Oregon considers charging station to be utility and allow company to the construction freely. In this study, we investigate the problem of a profit maximizing retailer in selecting a set of markets and facilities within these markets to build from a given set of locations. We assume that the retailer needs to consider the benefit of each single facility. The benefit will then be input into a nondecreasing concave function to capture the diminishing marginal benefit property. By considering the overall benefit, total cost of building facilities, and market selection cost, the retailer decides where to build facilities to maximize her profit. The problem is formulated as a nonseparable nonlinear integer program. The problem is proven to be NP-hard. Since the most common approach to deal with NP-had problems is to develop heuristic algorithms, we propose an algorithm to solve this joint market selection and facility location problem. The algorithm, which is based on relaxing the integer constraints, is called the Duo-sorting-approximation algorithm (DSAA). We show that DSAA has different worst-case performance guarantees for certain special cases of our general problem. We then study the average performance of the algorithms in various scenarios through numerical experiments.