時間相依暨服務時窗限制下旅行推銷員問題研究

A Study on Time Dependent Traveling Salesman Problem with Time Windows

求解車輛排程問題，一般皆假設各路段旅運成本為一固定佳，但一般交通條件皆具有明顯尖、離峰特性，故如何克服此實務上的交通狀況，為本研究之主要動機。是此，本文以旅行推銷員問題為例，探討在尖峰及離峰交通條件及顧客服務時窗限制下，以動態規劃法為基礎發展最佳解演算法，透過隨機範例的測試，暸解該類型問題於不同網圖(Network Graph)結構下，固定型(Fixed)與時依型(Time Dependent)兩類旅運時間計算方式應用時之最終排程計畫、總旅運距離、總旅運時間等輸出結果的差異。研究繕果顯示(1)動態規劃法應適用於時依性網路問題的求解，然未來應改善各運算階段內狀態之篩檢效率，以強化此演算法在大型問題上之適用性(2)路段的切割與路段內時間是否跨區的設定將對未來車隊規模的規劃產生實質性的影響(3)於對稱性網圍問題分析中發現，套用固定式與時區式旅行速率兩類成本計算方式，其運算結果顯示隨服務範圍大小的調整，兩者在總旅運距離及總旅運時間的差異變化趨勢十分接近(4)於非對稱性網圖問題分析中發現，隨服務範圍逐漸的擴大，套用兩類成本計算方式，其運算結果在總旅運時間上之差距愈趨明顯(5)數值分析結果顯示，無論在對稱性或非對稱性網圖問題中，套用兩類成本計算方式，其旅運距離的差距與服務範圍似無一定之闢係。

In general, the traveling salesman problem (TSP) assumes constant link travel speed both in peak and non-peak traffic hours. The assumption may generate significant and uncontrollable bias. The article is therefore to propose an exact-solution method for the traveling salesman pl叫lem with two-segment time dependent traffic conditions and time windows. We define the problem as the time dependent traveling salesman problem with time windows (TDTSPTW). The TDTSPTW is a generalization ofTSP, of which the time window of each customer must be satisfied and travel cost between O/D (or cities, traffic zones) is measured by travel distance and/or travel time. Based on the dynamic programming algorithm, a solving procedure for TDTSPTW is proposed and test results with randomly generated small-size problems are also reported in this paper. Under the objeàive o} minímizirtg total travel distance, the result shows that the proposed time dependent traveling speed method be insignificantly different from the conventional constant appeed ones for a symmetrical network with varying service area. However, the proposèd method is significantly superior tothe conventional ones for an unsymmetrical network with varying service areas under the objective of minimizing total travel time. The result shows that the varying patterns of the difference of the necessary total traveling distance and time, between constant and time dependent traveling speed assumptions, is very similar in the symmetric network test problems. The difference, on the other hand, is increasing with the enlarging serving area in the asymmetric network test problem.