汽車運送業拖車途程問題之研究

Tractor Routing Problem in Auto-carrier

國內每年新車約銷售四十幾萬輛，如何將新車由集保場（或製造廠）直接配送到各經銷商交車中心或銷售據點為一重要的課題。本研究僅針對負責拖運新車之專業汽車運送業加以探討，經初步了解，汽車運送業者多以拖車及專用板架進行新車之配送作業，就拖車之路線規劃而言，除需考量途程因素外，尚需考量裝載、回頭車利用、以及相互支援等因素，故此拖車路線規劃問題較一般車輛途程問題（vehicles routing problem, VRP）複雜；就實務作業而言，主要依車次規劃、新車裝載、以及拖車途程等三階段進行拖車之路線規劃，而本研究旨在就拖車途程階段之拖車途程問題（tractor routing problem, TRP）加以探討。經實地調查，此拖車途程問題是不對稱性多場站車輛途程問題（asymmetric multiple depot vehicles routing problem, AMDVRP）之變化，是NP-hard問題之一種，本文為其開發一啟發法進行求解，並依問題之特性設計測試題目進行求解測試，且配以禁忌搜尋法（tabu search ）進行改善；經測試題之求解結果顯示，此啟發法應能有效求解此拖車途程問題。 More than 400,000 new automobiles are sold in Taiwan every year. Efficiently distributing new automobiles from manufacturing centers to dealers is an important problem faced by managers. The paper addresses the tractor routing problem (TRP) in auto-carriers’ delivery of new automobiles to minimize the total operation cost. In fact, the TRP is a variant of the asymmetric multiple depot vehicles routing problem (AMDVRP) which belongs to a variant of NP-hard. In this study, we develop a new heuristic construction algorithm to solve the TRP followed by a tabu search to improve the solution. The computational results have shown that the heuristic can efficiently solve the TRP.

More than 400,000 new automobiles are sold in Taiwan every year. Efficiently distributing new automobiles from manufacturing centers to dealers is an important problem faced by managers. The paper addresses the tractor routing problem (TRP) in auto-carriers’ delivery of new automobiles to minimize the total operation cost. In fact, the TRP is a variant of the asymmetric multiple depot vehicles routing problem (AMDVRP) which belongs to a variant of NP-hard. In this study, we develop a new heuristic construction algorithm to solve the TRP followed by a tabu search to improve the solution. The computational results have shown that the heuristic can efficiently solve the TRP.