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

Tractor Routing Problem in Auto-Carrier

10.6402/TPJ.200203.0171

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

汽車運送業 ； 拖車途程問題 ； 不對稱性多場站車輛途程問題 ； Auto-carrier ； Tractor routing problem ； Asymmetric multiple depot vehicles routing problem

運輸計劃季刊

31卷1期（2002 / 03 / 30）

171 - 206

繁體中文

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

1. Agbegha, G.Ballou, R.Mathur, K.(1998).Optimizing Auto-carrier Loading.Transportation Science,32(2)
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)
3. Fischetti, M.Toth, P.Vigo, D.(1994).A Branch and Bound Algorithm for the Capacity Vehicle Routing Problem on Directed Graphs.Operations Research,42
4. Gillett, B. E.Johnson, J. G.(1976).Multi-terminal Vehicle-dispatch Algorithm.Omega,4(6)
5. Gillett, B. E.Miller, L. R.(1974).A heuristic algorithm for the vehicle dispatch problem.Operations Research,22(2)
6. Golden, B. L.Magnanti, T. L.Nguyen, H. T.(1977).Implementing Vehicle Routing Algorithms.Networks,7
7. Laporte, G.Gendreau, M.Potvin, J. Y.Semet, F.(2000).Classical and Modern Heuristic for the Vehicle Routing Problem.International Transactions in Operations Research,7
8. Laporte, G.Mercure, H.Nobert, Y.(1986).An Exact Algorithm for Asymmetrical Capacitated Vehicle Routing Problem.Networks,16
9. Laporte, G.Nobert, Y.Taillefer, S.(1986).Solving a Family of Multi-depot Vehicle Routing and Location-routing Problems.Transportation Science,22
10. Paessens, H.(1988).The Savings Algorithm for the Vehicle Routing Problem.European Journal of Operational Research,34
11. Pape, U.(1988).Vehicle Routing: Methods and Studies.North-Holland Inc..
12. Raft, O. M.(1982).A Modular Algorithm for an Extended Vehicle Scheduling Problem.European Journal of Operational Research,11
13. Reeves, C. R.(1993).Modern Heuristic Techniques for Combinatorial Problems.John Wiley and Sons, Inc..
14. Renaud, J.Laporte, G.Boctor, F. F.(1996).A tabu search heuristic for the multi-depot vehicle routing problem.Computers and Operations Research,23(3)
15. Tillman, F. A.(1969).The Multiple Terminal Delivery Problem with Probabilistic Demands.Transportation Science,3
16. Tillman, F. A.Cain, T. M.(1972).An Upperbound Algorithm for the Single and Multiple Terminal Delivery Problem.Management Science,18(11)
17. Vigo, D.(1996).A Heuristic Algorithm for the Asymmetric Capacitated Vehicle Routing Problem.European Journal of Operational Research,89
18. Wren, A.Holliday, A.(1972).Computer scheduling of vehicles from one or more depots to a number of delivery points.Operational Research Quarterly,23(1)
19. 曹以明 Chao, I-MingGolden, B. L.Wasil, E.(1993).A New Heuristic for the Multi-depot Vehicle Routing Problem That Improves Upon Best-known Solution.American Journal of Mathematical and Management Sciences,13
20. 陳春益 Chen, Chuen-Yih余秀梅李振源(1993)。82年電子計算機於土木水利工程應用論文集。
21. 黃木才(1996)。貨櫃運輸公司車輛途程問題之研究－模糊多目標遺傳演算法之應用。國立交通大學交通運輸研究所。

1. 陳春益、林志鴻(2002)。新車裝載問題之研究。運輸計劃，31(4)，765-793。
2. 陳春益、林志鴻(2003)。汽車運送業新車配送路線規劃問題之研究。運輸計劃，32(1)，75-101。