訂單型之旅行家問題

Abstract

在現今的商業行為模式下，許多服務內容都是以訂單做為計算單位，而以業主的角度來說，更關心的可能是訂單的交付時間，不是傳統的個別工作完成時間。因此，本論文考慮一個特殊型態的旅行家問題，捨棄傳統問題的目標式，而改由訂單交付時間為主要考量。在問題中，每個必須拜訪的節點隸屬於某一訂單，而每筆訂單的完成時間定義為此訂單所有節點都被拜訪完的時間點，其目的是要找出一組拜訪順序，使得所有訂單的加權平均完成時間最小。針對這個問題，我們提出了一個0/1線性數學式，並設計一個複雜度為O(n22n)的動態規劃產生最佳解。此外，為了能夠在可接受的時間內產生合理的近似解，我們設計了禁忌搜尋法、迭代區域搜尋法以及基因演算法等近似演算法。為驗證本論文所提之相關演算法，我們設計一系列實驗。實驗結果顯示，迭代區域搜尋法在節點數較多之時的效能表現優於其他兩者。

This thesis considers the traveling salesman problem incorporating order delivery. There is a set of nodes to be visited and each node belongs to a specific group. The completion time of a group is the moment when all nodes belonging to it have been visited. The problem is to determine a visitation sequence of the nodes such that the weighted sum of completion times over all groups is minimized. We present a binary linear programming model to formulate the studied problem and then develop an O(n22n) dynamic programming algorithm for determining optimal solutions. To produce approximate solutions within an acceptable time, we design a tabu search algorithm, an iterated local search algorithm and a genetic algorithm. Computational experiments are conducted to study the performance of the proposed model and algorithms. Numerical statistics suggest that the binary linear program can reach optimal solutions faster than the existing model, and the iterated local search algorithm outperforms other approaches when the number of nodes increases.