一般性車輛途程問題之探討

Algorithms for General Routing Problems

陳功欽(Kung-Chin Chen)

指導教授 ： 徐旭昇

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

摘要

本文旨在討論一般性車輛途程規劃問題(general routing problems,
GRP)。所謂一般性車輛途程問題為尋求一以花費最小成本旅行網圖中之任
務節點、有向任務網枝及無向任務網枝至少一次回到原出發點之途程。就
本人所知過去相關研究僅研究混合節點與無向網枝之情況，本文加入了有
向網枝之考量，使得問題更為完備。本文首先說明GRP問題可轉換成DTSP
問題。另就GRP近似演算法部份，本文採用三個方向，(一) 利用上述GRP
與DTSP之轉換關係結合Karp(1979)的patching演算法之GRP演算法；(二)
將任務節點、有向及無向任務網枝連接而成一連結網圖，再加以修正而得
GRP途程。(三) 應用類似 stacker crane problems 、郊區郵差問題與
TSP問題之演算法概念，提出四個近似演算法，並對其中LARGEARCS(II),
SMALLARCS及仿Christofides演算法相互之間互補之關係，提出結合此三
演算法之聯合策略，並說明其最壞情況界限為3/2~2之間。在實務應用方
面，本文提出兩個實務應用例子做為參考：不定顧客包裹快遞及迅收服務
與自動焊接途程。最後，對於研究方法中所提出演算法則進行實驗分析，
剖析各演算法之優劣，評估各演算法之平均績效，以驗證演算法之良窳。

關鍵字

一般性車輛途程問題 ； 有向旅行推銷員問題 ； 郊區郵差問題 ； 近似演算法 ； 最壞情況分析

並列摘要

Several heuristics for one-vehicle general routing problems(
GRPs) are introduced. An GRP is to find a tour passing a
designated set of nodes, undirected arcs, and directed arcs at
least once in a mixed network with minimum cost. In the past,
researchers worked on GRPs in either combining nodes and
undirected arcs or combining nodes and directed arcs. In this
research, we study the general case. At first, we point out
that an GRP can be polynomially reduced to a directed traveling
salesman problem(DTSP). This shows that the GRP is NP-complete
since the TSP, the rural postman problem(RPP), and the stacker
crane problem(SCP) are subproblems of the GRP. Three heuristics
are proposed for solving the GRP. The first heuristic solves an
GRP by transforming it into an DTSP and then solves the
transformed DTSP by the patching algorithm proposed by Karp
(1979). The second heuristic solves an GRP by firstly shrinking
every designated arc into a node. The transformed problem is
also an DTSP but its problem size is half smaller than that
obtained from the first heuristic. Patching algorithm is then
applied to this DTSP and some modifications are done in order to
obtain a good solution. The third heuristic finds a feasible
solution with the ideas similar to Frederickson's Largearcs and
Smallarcs algorithms solving SCPs and Christofides' algorithm
solving TSPs. This composite algorithm provides a worst case
bound between 3/2 and 2, depending on the ratio of the cost of
undirected arcs over that of directed arcs in a network.
Experiments are also conducted so as to test the performance of
the three heuristics. The experiments are designed according to
the following two bases: (1) the ratio between the cost of the
total designated arcs and the cost of an optimum route (2) the
ratio between the number of directed arcs and of undirected
arcs. The size of the tested problems are chosen so that an
optimal tour of an GRP can be found in acceptable running time
under our facilities.

並列關鍵字

General routing problems ； Directed traveling salesman problems ； Rural postman problems ； NP-completeness ； Approximation algorithms ； Worst case analysis