時窗限制動態車輛路線問題之線上型路線建立啟發式解法

由於過去對於具有線上求解需要的時窗限制動態車輛路線問題（Dynamic Vehicle Routing Problem with Time Windows，DVRPTW），僅有少數研究成果出現，因此，本研究的目的即是對此需求變動的動態問題提出明確的意義與求解演算法，並藉以分析此一問題之特性，進而促進理論研究與實務應用的結合。此一問題之特性在於顧客的需求隨著時間逐一出現，且當需求出現時，調度人員僅知道現有的顧客需求資訊，未來的需求則一無所悉，並須立即選擇適當車輛加以服務。為達成此一線上求解的需要，本文採取路線建立式（route construction）及啟發式（heuristic）方法，配合線上型演算法（on-line algorithm）的觀念設計求解演算法，並利用動態等候串列（Dynamic Queuing List, DQL）代表需求已出現但尚未服務的顧客。各演算法以實例分析法加以驗證，線上型問題則係修改自Solomon[1983]的標準問題集（benchmarks）。經由詳細的比較分析結果，顯示本文提出的線上求解架構適合用於求解DVRPTW，應有助於對此問題特性之了解及後續研究之發展。

關鍵字

動態車輛路線問題；時窗限制；線上型演算法；啟發式解法；路線建立式方法

並列摘要

The dynamic vehicle routing problem with time windows (DVRPTW) that has on-line demands still has not received many attentions before in the literature. Therefore, the purpose of this study is to clarity the meanings of this dynamic problem and design its solution algorithms. This problem differs from the traditional static or off-line problem in the dynamical arrival of requests and the execution of the partial tour during the run time. To achieve this on-line requirement in computing, the study develops some route construction heuristics based on the concepts of ＂on-line algorithms＂ Moreover, the requests that have been arrived but not be serviced yet are represented by a dynamic queuing list (DQL). All the proposed heuristic algorithms are evaluated in the empirical studies. The on-line test problems are modified from the problems used in Solomon [1983]. According to the computational results, the proposed solution framework is adequate in solving the DVRPTW. Furthermore, these analyses provide many insights of the DVRPTW and enhance the development of future studies.