最大覆蓋選址問題(Maximal Covering Location Problem, MCLP)在許多領域裡都扮演著非常重要的角色。例如配置緊急設施位址、設置無線網路路由器位址、工廠(倉儲)的選址等。在這個問題中,在給定的服務距離內,配置n個設施,使得能覆蓋或服務最多的需求數。在設置上述之設施時,通常需要考慮到該設施能夠服務到最多的需求點,且需求點到該設施的距離或時間最短。 過往用來解決MCLP的方法可分為:(1)啟發式方法、(2)精確方法。然而,近年來最常被用到的萬用啟發式方法是當中能以較快速度求得臨近最佳解的方法,但萬用啟發式演算法法有很多種,因此,本研究嘗試拿未曾用在解MCLP上的重覆性局部搜尋法(ILS)搭配貪婪增加法(Greedy methods)而成的新方法與過往的方法進行比較,經實驗證實,ILS演算法亦能有效的解決MCLP的問題,改善的幅度也可達到0.166%。
Given a set of client sites and a set of server sites, the maximum covering location problem (MCLP) seeks to find a fixed number of server sites in order to cover the maximum number of client sites. A client site is said to be covered if it is within a user-specified service distance from any selected server sites. The MCLP is important for its wide applicability. Typical applications include ambulance location selection, public facilities location selection, police station location selection, data abstraction, cluster analysis, list selection, and so on. Traditional approaches for solving MCLP are (1) Heuristics methods and (2) Exact methods. But exact methods compute exact solutions but perform disappointingly for large problems. Therefore, we proposed the ILS algorithm combined with the greedy adding algorithm to solve the MCLP. Experiments show that such an approach achieves good performance on solving the MCLP.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。