有方向性節線排程問題解法之研究

Abstract

在交通運輸領域以及物流上，對有關車輛排程問題的探討一直是相當受人 重視的。一個好的車輛排程系統，不僅可以使得該單位的營運成本大幅降 低，更可增進整體的服務水準，因此在近幾年來有許多研究人員投入了相 當多的人力、物力，希望能發展出一個實務上有效的方法。 有關車輛排程的問題基本上可分成兩大類：一是節點排程問題，另一則是 節線排程問題，而本研究主要是針對 DCARP 問題及 DCARPTW 問題的解法 做一完整的探討。首先本研究提出一個新的轉換方法，成功的將節線排程 問題轉換為節點排程問題，在與舊有轉換方法比較轉換後網路的節點數後 ，發現本研究的結果優於 Pearn , Assad & Golden（1987）所提，且此 轉換方法亦可應用於一般化節線排程問題中。接著本研究則分別發展求解 DCARP 及 DCARPTW 問題的下限值、可行解的方法，並已證得在 DCARP 問 題中，利用拉氏鬆弛法求得的下限值與最佳解的比值將在 2 倍之內。 Vehicle routing problems are attracting lots of research interests in the areas of transportation and logistics. A good vehicle routing system not only can greatly decrease operation cost but can improve the level of service. This research fucuses on the development of algorithms for DCARP and DCARPTW. We accomplished three major works in this research. The first is to develop an algorithm transforming arc routing problems into node routing problems. This transforming method beats othermethods found in the liturature. The secondly is to develop two lower bound finding algorithms (NDALB and LRLB) for both DCARP and DCARPTW. We show that the ratio of lower bound obtained by LRLB, which is a Lagrangian relaxation algorithm and the optimal solution is less than 2 in DCARP.