應用門檻接受法於求解容量限制節線途程問題及家庭廢棄物清運規劃之研究

A Threshold Accepting Algorithm for the Capacitated Arc Routing Problem and Application of Hosehold Waste Collection

孟欐潓(Li-Hui Meng)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

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

摘要

有容量限制的節線途程問題(Capacitated Arc Routing Problem, CARP)屬於節線途程問題(Arc Routing Problem, ARP)，自提出後就常被應用在許多問題，如信件寄送、街道清掃規劃、校車路線與家庭廢棄物清運規劃。其問題定義為給定一個無方向之網路，網路中的節線有一路徑成本與需求量，當節線為有非負需求量稱之為需求節線。而服務車輛有容量限制，且為單一車種多台車。每台車從場站出發滿足車容量後再回至場站，每條需求節線僅被一台車輛服務，但可被經過數次。決定一最短的總旅行成本路徑，使得每條需求節線皆被服務。由於CARP為一NP-hard問題，本研究應用啟發式演算法中參數設定少、執行容易、求解時間快速與效果顯著的門檻接受法(Threshold Accepting, TA)求解之。本研究所發展之門檻接受法利用不同移步組合、動態搜尋與控制懲罰函數來調整搜尋的廣度與深度。測試部分使用三組CARP標竿測試例題，並設定相關參數進行測試。測試發現，參數的影響對於TA較不敏感，故選擇一組考量CPU時間與Gap績效較佳之參數組合。總結，本研究之門檻接受法可找到69%測試例題文獻最佳解，其中在小型例題可全部找到文獻最佳解，且求解時間優於其它演算法，表示TA應用於求解CARP上確實具有可行性。
　在實務應用方面，考慮實際道路有方向之限制，將家庭廢棄物清運規劃成有方向性有容量限制的節線途程問題(Directed Capacitated Arc Routing Problem, DCARP)，並建構以DCARP為基礎之數學模式。實證分析以中壢市一收運責任區之家庭廢棄物清運為例，利用GoogleMap電子地圖並以Borland C++ 6.0繪製中壢市清運路線。本研究提出三種改善方案，僅以縮短路線總距離為目標，並未考慮到實際收運時之收運時間限制、各路線在不同時間車流量與紅綠燈狀況等。由於簡化收運狀況，且僅以縮短路線為目標，分析結果發現，目前討論之收運責任區，若不考慮各種收運限制，僅以收運行駛距離最小化為目標，經由更動現行規劃之收運路線運規劃，可縮短收運路線距離。未來研究中可將中壢市作整體考量規劃，並且將各種收運限制納入考量，以更能有效反映實務狀況。

關鍵字

容量限制 ； 節線途程問題 ； 門檻接受法 ； 家庭廢棄物 ； 逆物流

並列摘要

The capacitated arc routing problem (CARP) is a special routing problem which has a variety of practical applications, such as urban waste collection, snow plowing, sweeping, gritting, etc. The CARP is defined on an undirected graph with a set of edges. Each edge has a routing cost and a demand. The edges with positive demand make up the subset of the required edges. A set of identical vehicles with capacity is available. Each required edge has to be served exactly by one vehicle. Each route must start and end at the same depot and the total demand served by a route cannot exceed vehicle capacity. The objective of CARP is to find a set of vehicle routes to minimize the total traveling cost.
Due to the CARP is a NP-hard problem, it is difficult to solve optimally within a reasonable computational time by exact solution approaches. Therefore, this research intends to present a threshold accepting (TA) meta-heuristic to solve the CARP. TA is tested on three groups of benchmark instances from the literature. Its performance is compared with other algorithms from the literature. The computational results show that TA is effective to solve the CARP and its performance is highly competitive. TA reaches 65 best known solutions in 81 instances.
In the practical application, we apply TA to solve the household refuse collection problem in Chung-Li city. The household refuse collection problem is formulated as a directed capacitated arc routing problem (DCARP). The road network is built by using GoogleMap and Borland C++ 6.0 and data were collected from Chung-Li city cleaning squad. The results show that the distance of waste collection can be reduced by arranging and planning the new routes under simplified situation. In the future research, we can consider the Chun-Li city for whole waste collection planning and take the real traffic situation into account.

並列關鍵字

Capacity Constrain ； Arc Routing Problem (ARP) ； Threshold Accepting (TA) ； Household Refuse Collection ； Reverse Logistics

參考文獻

9. 卓裕仁與朱佑旌(2008)，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計劃季刊，37(4)，405-430。

18. 張寶豐(2003)，「以複合啟發式演算法求解時窗限制車輛途程問題」，私立中原大學工業工程學系碩士學位論文。

19. 陳百傑(2002)，「以啟發式演算法求解時窗限制車輛途程問題」，私立中原大學工業工程學系碩士學位論文。

31. 韓復華、楊智凱、卓裕仁(1997)，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季刊，26(2)，253-280。

24. 黃仁杼(2004)，「都垃圾轉運政策研擬及設置可行性研究－以桃園縣為例」，私立元智大學機械工程學系碩士論文。