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

Tractor Routing Problem in Auto-Carrier

林志鴻(Chih-Hung Lin) ； 陳春益(Chuen-Yih Chen) ； 曹以明(I-Ming Chao)

《運輸計劃季刊》 31卷1期 (2002/03) Pp. 171-206

https://doi.org/10.6402/TPJ.200203.0171

摘要

國內每年新車約銷售四十幾萬輛，如何將新車由集保場（或製造廠）直接配送到各經銷商交車中心或銷售據點為一重要的課題。本研究僅針對負責拖運新車之專業汽車運送業加以探討，經初步了解，汽車運送業者多以拖車及專用板架進行新車之配送作業，統拖車之路線規劃而言，除需考量途程因素外，尚需考量裝載、回頭車利用、以及相互支援等因素，故此拖車路線規劃問題較一般車輛途程問題(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.

並列關鍵字

Auto-carrier ； Tractor routing problem ； Asymmetric multiple depot vehicles routing problem

參考文獻

Agbegha, G.Ballou, R.Mathur, K.(1998).Optimizing Auto-carrier Loading.Transportation Science.32(2)

Bodin, L. D.Golden, B. L.Assad, A. A.Ball, M. O.(1983).Routing and scheduling of vehicles and crews: the state of the art.Computers and Operations Research.10(2)

Fischetti, M.Toth, P.Vigo, D.(1994).A Branch and Bound Algorithm for the Capacity Vehicle Routing Problem on Directed Graphs.Operations Research.42

Gillett, B. E.Johnson, J. G.(1976).Multi-terminal Vehicle-dispatch Algorithm.Omega.4(6)

Gillett, B. E.Miller, L. R.(1974).A heuristic algorithm for the vehicle dispatch problem.Operations Research.22(2)