參、資料結構

ㄧ、<Time>

long time：以分鐘為單位
long year = 2009：預設為2009年
long month = 1：預設為1月
long day = 1：預設為1日
long hr = 0：預設為0時
long min = 0：預設為0分

2009/01/01 00:00時間的基底，因此當time = 0時，時間為2009/01/01 00:00，而當time = 123時，時間為2009/01/01 02:03。支援兩種形式的建構，分別為給總分鐘數或給年月日時分，建構時會自動轉換（總分鐘數<->形式格式）。由於閏年機制只考慮4年，沒有考慮100年和400年，因此<Time>只支援2009年~2099年。

二、<Position>

double x = 0.0：x值或緯度值
double y = 0.0：y值或緯度值
String name = ""：地點名稱或地址

<Position>支援平面座標與經緯度座標，因此計算距離時，也支援平面距離和大圓距離。

三、<Event>

String title：行程標題
Position position：行程位置
Time starTime：行程起始時間
Time endTime：行程終止時間
Time serviceTime：行程服務時間
int type = 0：行程型態，0 : None, 1 : Start event, 2 : End event, 3 : New event, 4 : Old event.
String description：行程描述

<Event>支援由早到晚的排序。

肆、TSPTW演算法

一、有時間窗的旅行推銷員問題 (Traveling Salesman Problem with Time Windows, TSPTW)

TSPTW

TSPTW為TSP的變型，TSPTW有加入時間窗 (time windows)的限制。所以TSPTW想要找到一個排程，在不違反時間窗限制前提下，其排程總距離為最短距離。

時間窗規範此行程地點的抵達時間，但不規範離開時間。例如：有個行程的時間窗為 (2022/01/18 09:00, 2022/01/18 11:00)，則代表我必早上9點~11點抵達此行程，不可以8點到（早到），也不能12到（晚到），但可以12點離開此行程。

二、VIG_VNS algorithm for TSPTW

VIG_VNS algorithm for TSPTW

VIG_VNS演算法是混合Variable Iterated Greedy Algorithm (VIG)和Variable Neighborhood Search (VNS)，VIG為主架構，V代表摧毀 (destruction)數量是會變動的，I代表會迭代 (iteration)多次，G代表使用貪婪演算法 (greedy algorithm)執行全域搜尋 (global search)，即為DestructConstruct()。VNS可以看成區域搜尋 (local search)，把全域搜尋的解再用區域搜尋去優化現行解，即為VNS_1_Opt()。最後使用Superiority of Feasible Solutions (SF)去比較哪一個排程比較好。

三、Variable Iterated Greedy Algorithm (VIG)

Variable Iterated Greedy Algorithm (VIG)

VIG中的DestructConstruct(π, n)有兩個階段，分別為摧毀 (destruction)與建構 (construction)，π為行程的排列，n為摧毀的數量。

摧毀階段 (destruction)：首先先從π中隨機選出n個元素，並將π拆成兩個部分。上圖n = 3，橘色為被選中的元素，會拆成沒選中的部分和有選中的部分。
建構階段 (construction)：迭代1時，將選中部分的元素1插入所有可能位置，並比較所有可能的排列，選擇最好的排列當成下一次迭代的排列；迭代2時，將選中部分的元素2插入所有可能位置，再從中選擇最好的排列，直到所有被摧毀的元素都插回排列中為止。上圖1有7個可以插入的位置，因此會產生7條新排列，再從中選出最好的排列當下一次迭代的排列。

四、Variable Neighborhood Search (VNS)

Variable Neighborhood Search (VNS)

VNS和VIG很像，一樣都有摧毀和建構的階段，只不過是一個一個慢慢摧毀與建構，更像是區域搜尋 (local search)。VNS_1_Opt()同時使用backward_1_Opt()和forward_1_Opt()，backward和forward相似，只不過摧毀與建構方向是相反的，最後再從三個排列（原始、backward、forward）中取最好的。以下為backward_1_Opt()解說

摧毀階段 (destruction)：從最後一個元素到最前面的元素，一個一個璀毀，如上圖先從最後一個元素(3)開始摧毀。
建構階段 (construction)：將被摧毀的元素，插入到前面所有可以插入的位置中，從這些新排列中選出最好的排列當作下一次迭代的排列，直到摧毀到第一個元素為止。如上圖3前面有4個可以插入的位置，並從這4條中選出最好的排列，當作下一次迭代的排列。

五、Superiority of Feasible Solutions (SF)

Superiority of Feasible Solutions (SF)

使用SF原則去比較兩個排列的優劣，以下情境可以說πa優於πb：

πa和πb都是合理的 (feasible)且πa的fitness值比πb小
πa是合理的且πb是不合理的 (infeasible)
πa和πb都是不合理的且πa違反時間窗的數目比πb少
πa和πb都是不合理的且πa和πb違反時間窗的數目相同且πa的fitness值比πb小

六、Fitness function : Adaptive Penalty Approach

Fitness function : Adaptive Penalty Approach

Fitness = Cost + Penalty，Cost = Traveling time + Service time，Penalty的部分是會隨著迭代次數而有所變化的。NFT 被定義為距可行區域的閾值距離，從而鼓勵在可行區域內和可行區域的 NFT 鄰域內進行搜索，但不鼓勵超過該閾值。常數建議值為NFT0 = 0.001, lambda = 0.04, alpha = 2。

參考文獻

Karabulut, K., & Tasgetiren, M.F. (2014). A variable iterated greedy algorithm for the traveling salesman problem with time windows. Inf. Sci., 279, 383-395.

宗平方 TsungSquare

搜尋此網誌

排程力 Schedule Z 2：演算法介紹｜VIG_VNS for TSPTW