以競爭性區位模式求解替代能源補充站設置問題

Abstract

石油產品的消耗導致了地球暖化與嚴重空氣污染，促使各先進國家致力發展、推廣替代能源車輛。能源的缺乏使傳統燃油費用上升，民眾因而在選擇代步車輛時，將替代能源車輛列入考量，但卻會因為其燃油的可及性，而影響了替代能源車輛的普及。隨著替代能源車輛數目逐年增加，然而重新建置替代能源車輛能源補充站的成本鉅大，如何經濟且有效率的設置替代能源補充設施，是本研究重視的課題。 本研究的假設是在一特定區域市場中，已存有競爭對手所設立之替代能源補充站設施，我方也欲在此區域設置替代能源補充站設施。本研究之研究模式是由競爭型流量截取設置模式發展而來，已知需求會透過網路空間經濟地移動到設施接受服務。基於都會區替代能源車輛能源補充站的密度較高，本研究模式中設不考慮部分替代能源車輛補充能源模式之續航力限制假設，透過理想的設施設址，爭取截取(Capturing)到之車流量最大化。針對此問題，本研究除了提出一整數規劃模式(Integer Programming)外，基於求解運算負荷的考量，本研究利用最大涵蓋問題模式(Maximum Coverage Problem)的概念來設計一近似的整數規劃模式，以降低本問題的求解複雜度。透過資料的事先處理，可將原本競爭模式三個索引降低為兩個索引，在求解中、大型問題時能大幅降低解題所需時間。 有關數值驗證部分，本研究以七點小型路網、二十五點中型路網來進行數值測試，並考量路網內不同位置之既存競爭者，以及不同數目之新設施，以研究中新競爭者與既存競爭者設施數量相對多寡的關係。既存替代能源補充設施之位置以及需求流量以亂數產生，數值測試的結果顯示，透過最大涵蓋模式來進似之求解結果優於文獻中貪婪法(Greedy Heuristics)的求解品質，而求解時間則遠小於最佳解的整數規劃模式。本研究的成果，應該可以做為未來廣設替代能源補充站規劃及決策上之參考依據。

The consumption of petroleum products is one of the factors causing global warming and serious air pollution. Therefore, many developed countries have devoted great effort to promoting alternative fuel vehicles (AFVs). In addition, due to the nature resource scarcity, the price of traditional fuel is getting higher and higher, some people view the AFV as a good option. However, poor accessibility to refueling stations is one of the major barriers to the adaption of AFVs. However, the cost of establishing the infrastructure to promote the use of AFVs is very high. Thus, the objective of this study is to economically and efficiently determine the location of the AFV refueling facilities. Given a specific market, it is assumed there are some alternative fuel stations set up by an existing competitor, and the new provider plan to set up its own facilities This study is based on competitive flow-capturing location allocation problem (FCLAP) and assume that the drivers/the demand can detour through networks to obtain the service. In the model formulation, we do not take the driving range of AFVs into account, as the density of the facilities in the urban area is relatively high. In order to find the ideal facility locations to maximize the captured traffic flow, we propose an integer programming (IP) model. In addition, with an aim to alleviate the computational load, we make use of the well-known maximum coverage problem to design another IP model to reduce the complexity when solving the problem. By some data pre-processing, we can reduce the indexes of the binary decision variables from three to two, and thus significantly cut the program run time when dealing with the medium or large scale problems. In the numerical experiment, the proposed models and the solution algorithm were tested with a small-sized example network and a middle-sized example network with 7 nodes and 25 nodes respectively. The effects of the number of new facilities in the network and the different facility locations of the existing competitor were examined. In these test problems, we simulate the locations of the existing facilities and the demand flow by random number generators. It is found the solution approach based on the maximum coverage model achieve a better solution quality when compared with the greedy heuristic algorithm in the literature. The test results show the developed model and solution approach can be used for allocating alternative-fuel stations.