基因演算法於具容量限制之軸輻網路區位問題研究

A Study on a Capacitated Hub-Location Problem with the Application of Genetic Algorithm

陳義翔(Yi-Hsiang Chen)

指導教授 ： 申生元

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

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

摘要

近年來，電子商務蓬勃發展，各種特色商品與在地化商品搭上虛擬行銷通路販售，經由網際網路的蓬勃發展帶動了以上一連串的經濟活動，也促使忙碌的現代人改變實體購物之消費習慣，連帶提升了宅配業之業務量。而為了滿足顧客多樣化且高品質之需求，宅配業者也必須提供更優質且迅速便捷之服務，如此一來，勢必增加業者於成本上的開銷。如何以較低之服務成本去滿足顧客之需求是業者決勝之關鍵。
本研究將針對宅配業者在給定軸輻式網路架構下，以設施構建之固定成本及運輸變動成本之總成本的最小化為希冀，以給予宅配業者各站所開設及區位間隸屬關係之建議。本研究包含宅配站、次轉運中心及主轉運中心等三種轉運站所，還有實際發生供給與需求之服務區；其中，服務區須隸屬於服務水準規範下一個且唯一之宅配站，宅配站須隸屬於唯一之主轉運中心或次轉運中心，而次轉運中心須隸屬於唯一之主運轉中心。本研究為了改善傳統最佳化演算法對於大規模問題之求解瓶頸，發展一基因演算法進行求解，期望可以在大幅縮短時間的情況下，求得一近似最佳解，以便在有效時間內提供經營決策者進行決策評估。研究結果顯示於較大之問題規模下，基因演算法可在相對節省資源的情況下求出合適解。

關鍵字

軸輻式網路 ； 基因演算法 ； 混合整數規劃

並列摘要

In recent years, e-commerce has received enormous attention due to its importance in e-marketing channel as well as in other economic activities. This phenomenon not only changes our shopping habit from physical to online but also brings revenues for courier services. However, in order to fulfill customer’s various needs, courier service provider should offer much speedy delivery yet minimize their costs. Therefore, customer satisfaction and minimized cost are parallel issues for practitioners. In this study, we treat hub and spoke delivery network as our research framework. We aim at minimizing the transportation cost and the fixed cost among various nodes (i.e. station and hubs), their mater-slave relationships are: (1) Service zone belongs to the only home delivery station under the specific service level (supply and demand). (2) Home delivery station belongs to the only primary hub or secondary hub. (3) Secondary hub belongs to the only primary hub. Finally, time-saving based genetic algorithm was developed to improve traditional optimization algorithms. This would help practitioners making their decision in a short period of time.

並列關鍵字

Hub and spoke network ； Genetic Algorithm ； Mixed integer programming

參考文獻

[1] A. Marín, “Formulating and solving splitting capacitated multiple allocation hub location problem,” Computers and Operations Research 32 (2005), pp. 3093-3109.

[2] A. Marín, L. Cánovas, M. Landete, “New formulations for the uncapacitated multiple allocation hub location problem,” European Journal of Operational Research 172 (2006), pp. 274–292.

[3] 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), pp. 100-112.

[4] A.T. Ernst and M. Krishnamoorthy, “Solution algorithms for the capacitated single allocation hub location problem,” Annals of Operations Research 86 (1999), pp. 141-159.

[5] C.B. Cunha and M.R. Silva, “A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil,” European Journal of Operational Research 179 (2007), pp. 747–758.