單一車輛貨物運輸途程之探討

An Approximation Algorithm for Stacker-Crane Problems

陳振稻(Jan-Daw Chen)

指導教授 ： 徐旭昇

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

摘要

本文探討一製造系統工作站之間物料搬運之車輛途程問題，藉著將問題化
成Stacker-crane Problem (SCP) 的方式，對 SCP作進一步研究。SCP 是
指以最小成本為目標，走過混合網圖之全部有向網枝至少一次的網路問題
。SCP 為一NP-complete 問題， Frederickson 等人曾提出一聯合兩個演
算法之策略，使得最壞情況界限(worst case bound)達到1.8，並說明SCP
與旅行推銷員問題(TSP)等義之關係。本研究提出SCP與有向旅行推銷員問
題 (DTSP)等義的觀點。對於Frederickson等人所提之演算法，本研究認
為可再作改善，使其表現更佳。本研究亦提出一包括兩個副演算法的演算
法則，並證實當網圖之全部有向網枝所構成的子網圖是有向連結網圖時，
此演算法可求得最佳解。如果子網圖不為有向連結網圖，本文亦以聯合兩
個副演算法之策略，以期降低與最佳解之誤差。最後本研究並作實驗分析
，評估此策略的平均績效，以驗證演算法則之優劣。

關鍵字

車輛途程 ； 貨櫃吊車問題 ； 旅行推銷員問題

並列摘要

The purpose of the research is to solve a single-material
transportation network problem in which the number of
deliveries from one station to another is specified. The
problem can be converted to a vehicle routing problem called
Stacker-crane problem (SCP). In the Sacker-crane problem, a
vehicle is asked to traverse every directed arc in original
point at the minimum cost. Frederickson et al.[1978]showed that
the Stacker-crane problem and the traveling salesman problem
(TSP) are equivalent.They also presented an algorithm which is
based on the notions of bipartite matching and minimum cost
spanning trees, and the TSP heuristic developed by
Christofides[1965].In this paper, we point out the equivalent
relationship between the Stacker-crane problem and the directed
traveling salesman problem (DTSP). We also present a heuristic
which can be viewed as a partly modified version of
Frederickson'' algorithm. Our heuristic contains one main
heuristic and two sub-heuristics. We show that, after the main
heuristic, if the resulting route is a closed path then it is
an optimum route. The two sub-heuristics are developed based on
complementarity, so that a bad case for one sub-heuristic can
be saved by the other. An experimental study reveals that our
heuristic works well on problems of small size.

並列關鍵字

Vehicle Routing Problems ； Stacker-crane problems