臺灣博碩士論文加值系統

隨著國人對生活品質的要求提升，以及網際網路快速發展下，電子商務的崛起，使得國人對宅配服務之需求正快速增加。為滿足顧客多元及高品質的需求，各宅配業者所提供之服務更趨向快速化及多元化，然為達此目標亦隨之帶來宅配業者之配送成本的向上攀升。因此在競爭激烈的宅配服務業中，如何有效降低成本並同時提供顧客完善的服務已是宅配業者決勝關鍵。在相關宅配服務規劃中，屬於長期規劃的運輸網路站所區位設置尤其影響宅配業者成本甚鉅。
本研究將針對宅配業者在給定軸輻式網路架構下，追求包含設施構建固定成本及運輸變動成本之總成本的最小化，以給予宅配業者各站所開設及區位間隸屬關係之建議。本研究包含三種設施：宅配站、次轉運中心及主轉運中心，以及供給與需求發生之服務區，其中服務區須隸屬於唯一宅配站，宅配站須隸屬於唯一之主轉運中心或次轉運中心，而次轉運中心須隸屬於唯一主運轉中心。為改善傳統求解混合整數規劃問題之方法，本研究利用Benders decomposition將混合整數規劃模式分解成一個純整數規劃模式及一個線性規劃模式進行求解，為加速最佳解收斂速度加入提升Lower bound之方法，測試結果顯示測試結果顯示於主問題成本遠大於次問題成本時，Benders decomposition能夠有效降低求解時間。

People in Taiwan are aspiring better quality life much than ever. Internet and e-commerce further give profound impact on provisioning of logistics service. In this regard, all the logistics firms are providing not only quick delivery but also providing multiple-temperature services. Thus, how to simultaneously reduce their delivery cost as well as offer high-end service to their customers has becoming one of the critical issues under this competitive market. Among issues that most enterprises face, strategic transportation network planning is usually considered as an important factor which greatly influences operational cost.

A structure of hub-and-spoke network is assumed in this study. The network consists of three major facilities: home delivery station, secondary hub, and primary hub. In particular, each service zone should be assigned to a single home delivery station; each home delivery station should be subordinate to either a secondary hub or primary hub, and each secondary hub in turn is subordinated by a primary hub. We first proposed a mixed integer programming formulation to model the problem. In order to improve poor efficiency resulting from solving a monolithic mixed integer programming model, we use Benders decomposition method to separate mixed integer programming model into two submodels: (1) an integer programming model and (2) a linear programming model. Moreover, in order to enhance the speed of convergence to an optimal solution, lower bound techniques are also introduced in the integer programming model. Computational results seem to show that Benders decomposition method took less solution time in contrast to traditional branch an bound based solver.

書名頁 i
論文口試委員審定書 ii
授權書 iii
中文摘要 iv
英文摘要 v
誌 謝 vi
表目錄 x
圖目錄 xi
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的及問題描述 2
第二章 文獻探討 5
2.1 傳統區位問題與傳統軸輻式網路區位問題 5
2.2 軸輻式網路區位問題 7
2.2.1 USApHMP (Uncapacitated Single Allocation p-Hub Median Problem) 8
2.2.2 USAHLP (Uncapacitated Single Allocation Hub Location Problem) 9
2.2.3 UMApHMP (Uncapacitated Multiple Allocation p-Hub Median Problem) 10
2.2.4 UMAHLP (Uncapacitated Multiple Allocation Hub Location Problem) 11
2.2.5 CSAHLP (Capacaitated Single Allocation Hub Location Problem) 12
2.2.6 CMAHLP (Capacitated Multiple Allocation Hub Allocation Problem) 12
2.3 最佳化求解法 12
2.3.1 Branch and Bound Method 12
2.3.2 Benders decomposition method 13
第三章 模式建構 15
3.1 模式建構說明 15
3.2 不考慮所有現行網路既有設施位址情況下數學模式之建構 16
3.2.1 不考慮所有現行網路既有設施位址情況下之混合整數規劃模式(模式1) 19
3.3 已知現行網路既有設施位址固定之情況下 23
3.3.1 已知所有現行網路既有設施位址情況下之混合整數規劃模式(模式2) 24
第四章 最佳化演算法 25
4.1 限制服務區隸屬於最近K個宅配站之改良模式 25
4.2 Benders Decomposition 演算法概念 27
4.3 演算法 30
第五章 實驗結果與分析 31
5.1 測試環境 31
5.2 測試例題說明 31
5.2.1 測試題組1 32
5.2.2 測試題組2 32
5.2.3 測試題組3 33
5.2.4 測試題組4 33
5.3 測試結果與分析 34
5.3.1測試題組1之結果與分析 34
5.3.2 測試題組2之結果與分析 35
5.3.3 測試題組3之結果與分析 36
5.3.4 測試題組4之結果與分析 37
第六章 結論與建議 38
6.1 結論 38
6.2 後續研究與建議 39
參考文獻 40
附錄 42

1.G.G. Cornurjols, G.L. Nemhauser and L.A. Wolsey, 1990. The uncapacitated facility location problem. In Discrete Location Theory, R.L. Francis and P. Mirchandani (eds.). Wiley Interscience, NewYork.
2.S.H. Owen and M.S. Daskin, “Strategic facility location,” European Journal of Operational Research 111 (1998) 423-447.
3.M.E. O’kelly and J.M. Harvey, “The hub network design problem: a review and synthesis,” Journal of Transport Geography 2 (1994) 31-40.
4.J.F. Campbell, “A survey of hub location,” Studies in Locational Analysis 6 (1994) 31-49.
5.S.L. Shaw, “Hub structures of major US passengers airlines,” Journal of Transport Geography 1 (1993) 47-58.
6.L. Chestler, “Overnight air express: spatial pattern, competition and the future in small package delivery services,” Transportation Quarterly 39 (1985) 59-71.
7.W. Wei, “Network design issues in terabit optical internet,” Communications Engineer 1 (2003) 38-41.
8.M.G. Yoon, Y.H. Beak and D.W. Tcha, “Optimal design of a distributed fiber transport network with hubbing technology,” European Journal of Operational Research 104 (1998) 510-520.
9.R. Bolllapragada, J. Camm, U.S. Rao and J. Wu, “A two-phase greedy algorithm to locate and allocate hubs for fixed-wireless broadband access,” Operations Research Letters 33 (2005) 134-142.
10.M.E. O’Kelly, “The location of interacting hub facilities,” Transportation Science 20 (1986) 92-106.
11.M.E. O’Kelly, “A quadratic integer program for the location of interacting hub facilities,” European Journal of Operational Research 32 (1987) 393-404.
12.S. Abdinnour and M.A. Venkataramanan, “Solution approaches to hub location problems,” Annals of Operations Research 78 (1998) 31-50.
13.A.T. Ernst and M. Krishnamoorthy, “Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem,” European Journal of Operational Research 104 (1998) 100-112.
14.J.F. Campell, “Integer programming formulations of discrete hub location problems,” European Journal of Operational Research 72 (1994) 387-405.
15.A. Marin, L. Canovas and M. Landete, “New formulations for the uncapacitated multiple allocation hub location problem,” European Journal of Operational Research 172 (2006) 274-292.
16.L. Canovas, S. Garcia and A. Marin, “Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique,” European Journal of Operational Research 2006 May.
17.T. Aykin, “Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problems,” European Journal of Operational Research 79 (1994) 501-523.
18.A.T. Ernst and M. Krishnamoorthy, “Solution algorithms for the capacitated single allocation hub location problem,” Annals of Operations Research 86 (1999) 141-159.
19.Marin, “Formulating and solving splitting capacitated multiple allocation hub location problem,” Computers and Operations Research 32 (2005) 3093-3109.
20.G.M. Roodman and L.B. Schwarz, “Extensions of the multi-period facility phase-out model: new procedures and applications to a phase-in/phase-out problem,” AIIE Transactions 9 (1977) 103-107.
21.S.H. Chung, Y.S. Myung and D.W. Tcha, “Optimal design of a distributed network with a two-level hierarchical structure,” European Journal of Operational Research 62 (1992) 105-115.

22.Brad, J.F. ,L. Huang, M. Dror, and P. Jaillet, “A branch and cutalgorithem for the VRP with satellite facilities”, IIE Transaction, 30(1998),821-834.

23.J.F. Benders, “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik 4 (1962) 238-252.