一般化卡車拖車路線問題

Abstract

摘 要 卡車與拖車路線問題(Truck and Trailer Routing Problem, TTRP)是傳統車輛路線問題(Vehicle Routing Problem, VRP)的一種衍生型態，藉由卡車或整車(卡車附掛拖車)之路線服務具有不同可及性的顧客。本研究依TTRP問題特性，從合理化構建成本與擴充限制條件兩方面著手，使其成為「一般化卡車拖車路線問題」(Generalized TTRP, GTTRP)，更能符合實際應用的需求。GTTRP考慮的物流配送較VRP與TTRP更具實用彈性，但另一方面問題的複雜性也更高。 本研究使用「限制規劃」(Constraint Programming, CP)與「包容性深廣度搜尋法」(Generic Intensification and Diversification Search, GIDS)，發展適合GTTRP的求解工具。CP應用於起始解構建部分。GIDS巨集啟發式方法則搭配門檻接受法(Threshold Accepting, TA)與大洪水法(Great Deluge Algorithm, GDA)兩種搜尋法，以及兩極跳躍法(Flip Flop, FF)構建多組演算模組進行路線改善測試。本研究依據Chao的TTRP題庫，建立一組18題的GTTRP測試題庫，並以C++語言撰寫程式在AMD PC上執行測試。結果發現，本研究所設計求解GTTRP之模組皆有不錯之解題績效。本研究亦以GTTRP之模式求解TTRP問題，亦發現有5題結果較Chao佳，整體平均誤差為4.18%，平均執行時間為15.08秒，比Chao 60747.57秒快了4000倍以上，此亦印證本研究GTTRP求解方法的效果。

ABSTRACT The Truck and Trailer Routing Problem (TTRP) is a variant of traditional Vehicle Routing Problem (VRP). The problem considers the use of trucks as well as the combination of truck-and-trailers to service customers. TTRP is relative new in literature, e.g., Gerdessen (1996) and Chao (2002). This research extends the TTRP to include more generalized considerations, and defines the generalized Truck and Trailer Problem (GTTRP). As contrast to TTRP, which ignores the costs associated with the decoupling / coupling of the truck and the trailer as well as that of additional parking lots to park the trailers, our proposed GTTRP includes such costs in general. We applied Constraint Programming (CP) and the meta-heuristic method of Generalized Intensification and Diversification Search (GIDS) to develop heuristic solution algorithms to solve GTTRP. The initial solution of GTTRP is generated by CP. The GIDS integrates the use of Threshold Accept (TA) and Great Deluge Algorithm (GDA) and Flip Flop (FF) to improve the incumbent solution. For numerical-analysis purposes, we developed a bank of 18 test problems of GTTRP based on Chao’s test problems of TTRP. We wrote computer programs in C++ and implemented our models on an AMD personal computer. Results found that our proposed models can provide useful tools for GTTRP applications.