使用K-means分群法與Prim's最小生成樹法發展揀貨單合併與指派之最佳化策略-以攝像鏡頭模組為例

Developing an Optimization Strategy for Picking-list Consolidation and Assignment by Using K-means Clustering and the Prim's Minimum Spanning Tree Algorithm – A Case Study of the Compact Camera Module

洪肇蔚(Chao-Wei Hung)

指導教授 ： 江梓安

國立臺北商業大學/管理學院/企業管理系（所）/碩士(2021年)

摘要

由於5G、自駕車以及智慧城市、智能家居的興起，使得攝像鏡頭模組產品在智慧型手機、車載攝像鏡頭和安防監控等市場需求量暴增。為了因應時代科技趨勢下所帶動攝像鏡頭模組之需求，本研究以攝像鏡頭模組作為研究對象進行探討。此外，攝像鏡頭模組屬於高度客製化的訂單，會因為不同客戶需求導致每筆揀貨單截然不同，加大揀貨人員揀貨的困難度。且當揀貨人員連續被指派到差異甚大的揀貨單，更會使得揀貨人員在倉儲的移動距離增加、揀貨時間拉長。
為了有效解決上述因接單式生產，導致揀貨單差異大的問題，本研究的主要目的將致力於發展解決之方法論。該解決方法論是一個兩階段的揀貨單處理模式，分別為最佳揀貨單合併策略以及最佳揀貨單分派順序策略。首先，第一階段利用K-means分群演算法，將擁有相似零組件的揀貨單合併到同一群集中，找出最佳的揀貨單合併策略。第二階段，我們透過Prim's最小生成樹演算法，找出揀貨的最短路徑，作為本研究之最終揀貨單分派順序策略。最後，我們基於個案研討以及揀貨路徑的模擬分析，驗證了本研究方法論之可行性，並發展出一套最終改善流程框架。
研究結果顯示，當遵循本研究所提出之最終改善揀貨流程，揀貨人員只須進入倉儲一次，且相比現行策略下的總行徑距離，整整縮短了702.8公尺，大幅縮短了揀貨人員在倉儲中移動之距離，也提升了整體的揀貨效率，更為H公司解決了所面臨揀貨效率不高的問題。

關鍵字

攝像鏡頭模組 ； 揀貨單指派 ； K-means分群法 ； 圖論 ； 最小生成樹法

並列摘要

Technological advances such as 5th generation wireless systems, self-driving cars, smart city, and smart home applications have greatly increased the demand for compact camera modules in smartphones, car cameras, and security monitoring systems. Thus, this study investigated compact camera modules to cope with their increased demand. Because orders for compact camera modules are highly customized, the order picking-list from one customer can vary greatly from that from another customer, substantially increasing the difficulty faced by order pickers. Moreover, when assigned orders that vary greatly, order pickers may have to travel long distances and spend more time than usual in warehouses to complete the orders.
This study proposes a method to effectively resolve the problems of build-to-order production involving greatly varying order picking-lists. This method divides order picking into two stages, namely the optimization of picking-list consolidation and the optimization of picking-list assignment. In the first stage, k-means clustering is performed to allocate picking-lists that contain the similar product parts into the same cluster, thereby generating an optimal picking-list consolidation strategy. In the second stage, the Prim's minimum spanning tree algorithm is applied to identify the shortest route for order picking, which is adopted as the basis for picking-list assignment. Through case studies and simulations, we verified the feasibility of the proposed method and refined it to its final form.
According to the research results, the proposed method enabled order pickers to enter warehouses only once, and it substantially reduced order pickers’ travel distance by 702.8 m. Thus, order picking has become more efficient overall, solving Company H’s long-standing problem of low order picking efficiency.

並列關鍵字

Compact Camera Module ； Picking-list Assignment ； K-means Clustering ； Graph Theory ； Minimum Spanning Tree

參考文獻

中文文獻

毛正、游凡 (2020)。多攝升級和車載市場爆發，光學業務駛入快車道—聯創電子。新時代證券研究所。

王平陽 (2020)。技術創新+多領域需求擴展，光學行業景氣度全面提升。產業研究報告：電子。東吳證券研究所。

陳彩華譯(石田保輝、宮崎修一著) (2017)。演算法圖鑑：26種演算法+7種資料結構，人工智慧、數據分析、邏輯思考的原理和應用全圖解。臉譜出版。

庄林楠 (2020)。電子行業：光學鏡頭研究—持續創新。中國頭豹研究院。