Benders Decomposition於具容量限制之軸輻網路區位問題研究

A Study on a Capacitated Hub-Location Problem with the Application of Benders Decomposition Method

薛博文(Po-Wen Hsueh)

指導教授 ： 申生元

元智大學/資訊學院/資訊管理學系/碩士(2007年)

https://doi.org/10.6838/YZU.2007.00189

摘要

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

關鍵字

軸輻式網路 ； Benders decomposition method ； 混合整數規劃

並列摘要

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.

並列關鍵字

Hub and spoke network ； Benders decomposition method ； mixed integer programming.

參考文獻

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.

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.

5. S.L. Shaw, “Hub structures of major US passengers airlines,” Journal of Transport Geography 1 (1993) 47-58.

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.