考慮設施容量與因時段而異之使用者偏好的設施選址問題

Abstract

設施位置問題長年以來都是被廣泛討論的問題，在傳統的設施位置問題中，決策者決定設施的位置，並指派使用者到指定的設施以最大化決策者的利潤，但是當設施需直接面對消費者時，消費者對於不同的設施會有自己的偏好，此時決策者無法強迫消費者去指定的設施，只能被動地由使用者選擇他們所偏好的設施，此外，設施的容量往往是有限的，消費者在選擇設施時也只能選擇尚未額滿的設施。因此在考慮設施位置時必須考慮到設施容量與使用者偏好，其中使用者的偏好又可能會因時間而異，在多個時段之中，使用者對同個設施也會有不同的偏好程度，且他們也不會在每一個時段都前往設施，因此考慮到因時段而異的使用者偏好可以更加符合使用者實際的狀況，也能增加設施使用上的效率。 在本研究中，我們研究一個決策者如何根據已知的消費者偏好，在有限的經費內去選擇設施的位置及規模，以最大化其服務的顧客數量。我們考慮了若干顧客與若干可以建造設施的候選地點，其中每個設施都有若干種規模可以選擇，在每個時段之中，使用者對於不同的設施有著不同的偏好。當決策者決定要建造的設施位置以及規模之後，使用者則會根據其偏好，在尚有空位的設施之中選擇要去的設施。我們提出了一個新的模型將這個二階段整數規劃問題轉成單一階段整數規劃問題，並藉由前人的啟發設計了 GSAMFE 跟 GSAMFETE 兩個啟發性演算法，在演算法中我們將問題轉成最大流問題，設計了一個以貪婪法為底的演算法，並結合了前人提出的方法估算最大流，以加速的計算。透過實驗，我們發現新的模型可以在短時間內解出大規模的問題，在運算時間上有極大的進步，而兩個演算法在各種情況也都可在可接受的時間範圍內得到近似最佳解的結果。

Facility location problems have been widely discussed for decades. In typical facility location problems, the decision maker decides where to build the facilities and then assigns customers to those facilities. However, when facilities provide service to the customers, customers tend to have heterogeneous preference for those facilities. In this case, customers’ behavior cannot be imposed by the decision maker, and they will choose the most preferred facility among the built ones. Besides, facilities usually have limited supply, so customers also cannot choose facilities that are full. Moreover, even for the same facility, customers’ preference are heterogeneous in different time period, and they will not go to facilities in every time period. Therefore, considering time-dependent user preference. In our research, we consider a multi-period capacitated facility location problem with user preference. The problem aims to maximize total served customers within budget constraint. The decision maker decides locations and scales to build facilities and customers then choose facilities according to their preference. We reformulate the bi-level problem into a single-level mixed integer problem. Through previous research, we designed two greedy-based heuristic algorithms (GSAMFE and GASMFETE) using maximum flow, flow estimation and incremental maximum flow. In numerical study, we find out that our new reformulation has significant improvement in computation time and can solve large scale problem in short time. The algorithm can also provide near-optimal solutions in reasonable time.