考量區域涵蓋限制之運輸計劃選擇問題

Abstract

運輸規劃(Transportation Programming)對一個國家基礎建設的發展，扮演重要的角色。基於有限的預算，在眾多可能的計劃之中，進行挑選並分配經費便成了一個極具挑戰性的決策問題。實務上，計劃之間的相關性(Inter-dependency)使得運輸規劃問題更形複雜。例如，某些計劃共同執行所產生的利益(或成本)會與個別執行該等計劃所產生的利益(或成本)總合不同。此外，有些計劃本質上並不相容、是不能同時選擇。例如，同一計劃不同程度的規模、或不同形式的版本，是不能同時選擇的；又例如，使用同一資源(如同一塊土地)的多個計劃也不能同時選擇。尤其更重要的是，在現今民主與多元的社會，預算分配的公平性以及區域發展的平衡性備受關注。因此，為考量社會的公平性與政治運作上的可行性，本研究提出一個以集合涵蓋問題(Set Covering Problem, SCP)為基礎的整數規劃(Integer Programming)模式，以確保在運輸規劃過程中，每一個區域皆可不被忽略。本研究藉由拉式鬆弛法(Lagrangian Relaxation)，將此具有預算及計劃相容性限制的集合涵蓋(SCP)模型，轉化為一個線性規劃(Linear Programming)問題。本研究之主要任務為即在設計一個求解演算法，可有效地調整拉氏乘數與找出可行解，藉以在可接受之運算時間內求出高品質的解。最後，本研究將以能反映實務情況之數值測試，驗證所發展模型與求解演算法的適用性。

Transportation Programming (TP) plays an important role in the development of the infrastructure of a country. Given the limited budget, it is a challenging decision to select the projects to be funded and implemented from the numerous options. The problem is complicated by the fact that some of the potential projects are inter-dependent. The benefit (and/or the cost) of the joint project combining multiple projects can be different from the sum of the benefits (and/or the costs) if the associated projects are implemented separately. Besides, some projects cannot be selected at the same time as they are incompatible or exclusive to each other by nature. The typical examples are the projects utilizing the same resource, such as a piece of land. In particular, much more attention nowadays is paid to the fairness of budget allocation and the balance of regional development as the society becomes more democratic and diversified. Thus, in order to address the issue of social justice and political feasibility, a new inter programming (IP) model based on the set covering problem (SCP) has been proposed to ensure that the regional balance issue is addressed. This SCP-based model, with the constraints taking into account of budget limitation and project compatibility, is transformed into a linear programming (LP) model by Lagrangian Relaxation (LR). The key theme of this study is then to design the solution algorithm that can efficiently adjust the LP multipliers and find the feasible solutions so as to achieve a high-quality solution within an acceptable computation time. Finally, the numerical experiment that can reflect the practical situations is performed to validate the applicability of the developed model and solution algorithm.