問題描述

我們小組選擇的問題是TOPTW問題，即the Team Orienteering Problem with Time Windows，中文名稱可以譯為“帶有時間窗的團(tuán)隊定向越野問題”，不過在查找及復(fù)現(xiàn)論文的過程中，我們認(rèn)為這本質(zhì)就是一個“帶有時間窗的車輛路徑問題”，即VRPTW。

問題描述如下：地圖上存在許多的顧客點，每個顧客點處于可被服務(wù)狀態(tài)的時間是有限的，即存在顧客點可被服務(wù)的開始時間OpenTime與結(jié)束時間CloseTime，服務(wù)每個顧客都需要持續(xù)一定的時間ServiceTime，如果一個顧客點被成功服務(wù)了，則可以獲得一定的收益profit，并且每個顧客最多只能被服務(wù)一次；地圖上同時存在一個倉庫Depot，倉庫派出一定數(shù)量的服務(wù)車，車子從倉庫出發(fā)，途徑各個顧客點服務(wù)顧客獲得收益，倉庫也存在開啟時間和關(guān)閉時間，因此所有的車子需要在開啟時間出發(fā)，在關(guān)閉時間之前回到倉庫；此問題的目標(biāo)是，給定一定數(shù)量的車子，如何規(guī)劃每輛車子的服務(wù)路徑，使得所獲得的總收益最大。

偏數(shù)學(xué)描述：給定無向圖，表示地圖上的個點，代表每兩個點之間的邊，從點到點之間的時間等于兩個點之間的距離，號點代表倉庫，倉庫的時間窗是，其余點代表顧客，每個顧客點有一個收益，服務(wù)時間，和一個時間窗，如果車子的服務(wù)時間在顧客的時間窗之內(nèi)則服務(wù)成功，如果車子在顧客時間窗未開始之前到達(dá)則需要等待，服務(wù)成功可獲得收益，TOPTW的目標(biāo)是在車輛有限的情況下通過規(guī)劃路徑獲得最大的收益。

算法描述

概括

The structure of the three-component heuristic

Solution representation

給定可使用的車子數(shù)量，該論文使用個有序列表對該問題的解進(jìn)行表示，其中一個列表代表沒有被任何一輛車子服務(wù)過的顧客點，其余個列表代表輛車的顧客點訪問順序（路徑），每條路徑的表頭和表尾都是0，代表倉庫，其余數(shù)字代表顧客點，按從左往右的順序在地圖上依次訪問。

Example of a solution representation

public class route {
    public ArrayList<Integer> tour;
    public int profit;
    private int apr;
    private boolean used;
    public long time;
   }

上述是代碼中route的部分，route即每輛車的路徑，ArrayList存儲車輛路徑，profit代表此路徑的利潤，apr代表路徑的權(quán)重，這在精確算法部分會用到，used代表此路徑是否在精確算法的最終結(jié)果中被使用，time代表此路徑花費的時間。

 public boolean check(Instance inst) {
        long start = inst.openTime(0);
        long end = inst.closeTime(0);
        int cur = 0;
        int next;
        for (int i = 0; i < tour.size(); i++) {
            next = tour.get(i);
            long ss = start + inst.dist(cur, next);
            if (ss < inst.openTime(next))
                start = inst.openTime(next) + inst.serviceTime(next);
            else if (ss >= inst.openTime(next) && ss <= inst.closeTime(next))
                start = ss + inst.serviceTime(next);
            else {
                return false;
            }
            cur = next;
        }
        if (start + inst.dist(cur, 0) > end){
            return false;
        }
        return true;
    }

此部分用來檢測該路徑是否可行。而Solution則是以route為元素的數(shù)組。同時帶有收益，每個顧客點的平均收益，總時間，可能獲得的最大收益這些屬性。

public class Solution {
    public int profit;
    public route[] Sol;
    private double ave_pro;
    private long sumTime;
    public int maxPro;
}

The Neighborhood Operator

本論文使用了八個鄰域算子，分別是，，，，，，，，接下來重點描述一下算子。

首先隨機(jī)地從每條路徑中移除一些顧客節(jié)點，如果原路徑中沒有任何節(jié)點則不進(jìn)行移除操作，之后從路徑，即未被服務(wù)的顧客節(jié)點中選擇頭節(jié)點，將其插入路徑中第一個可以插入的位置，即插入之后路徑是一個可行路徑。如果所有的位置都無法插入，則將該節(jié)點置于的末尾，繼續(xù)選擇下一個頭節(jié)點進(jìn)行上述操作，直至中的每一個節(jié)點都無法再插入任何位置。此時的Solution則被定義成一個complete Solution，即在不改變路徑中顧客順序的情況下，中的所有顧客點都無法被插入到路徑中。

這個算子的設(shè)計點之一在于，如何從路徑中移除顧客點更有效率。論文采用的設(shè)計是計算出當(dāng)前解中每個顧客結(jié)點給予的平均收益值，如果某個顧客點的收益大于平均收益，則以較小的概率移除，否則以較大的概率移除，這樣子可以讓留下來的顧客節(jié)點大部分具有更大的收益。

其余算子由于課堂上都進(jìn)行過詳細(xì)的講述，這里不再重點展開，簡單來說，其余六個算子中，，，，，在受訪問顧客點不變的情況下，通過改變顧客點的訪問順序，降低路徑所需的總時間，以期可以插入更多的未服務(wù)顧客節(jié)點；而，可以從中選擇節(jié)點放置在路徑中或者與路徑的某個節(jié)點互換，以期增大路徑的收益。

介紹基礎(chǔ)算子之后，本論文通過一個Post-Processing的操作對后七個常用算子進(jìn)行了聚合，即循環(huán)使用 ，，，，，，對某個solution進(jìn)行處理，直至此solution無法得到有效的改進(jìn)。

Illustration of operators in the post-processing procedure

Local Search & Simulated Annealing

Local Search和Simulated Annealing是I3CH算法中的前兩個的部分，它們也都是被廣泛使用的算法，在I3CH中，使用它們的目的是為了得到一個較好的解以及在探索過程中收集所有可行的，以便在精確算法中對它們進(jìn)行組合。

Local Search

LS算法較為基礎(chǔ)，在本論文中，對于一個Solution ，我們通過算子生成它的個鄰域解，如果鄰域解沒有超過的，則使用最后一次探索過程中的解代替，反之，用鄰域中最優(yōu)的解替代；用記錄迭代過程中得到的最優(yōu)解，如果一次迭代過程后優(yōu)于，則用更新；不斷重復(fù)上述過程，直至連續(xù)沒有得到優(yōu)化的迭代次數(shù)超出了設(shè)定值，至此，論文通過LS對解進(jìn)行了優(yōu)化，并得到了許多用于組合的可行路徑。在實現(xiàn)過程中，考慮到單獨一個算子實際探索鄰域的范圍可能較小，我們將Post-Processing操作也用在了鄰域的探索中。

Simulated Annealing

SA是通過對物理中的退火現(xiàn)象進(jìn)行觀察而得來的，其本質(zhì)是在一定概率下接受一個相對不那么好的鄰域解，借此跳出局部最優(yōu)。本論文的SA需要用到的參數(shù)有初始溫度，降溫系數(shù)，退火溫度，以及最大無優(yōu)化次數(shù)；對于某個Solution ，記為SA過程中得到的最優(yōu)解，對于應(yīng)用算子得到解，如果的收益優(yōu)于，則使用更新繼續(xù)進(jìn)行退火的過程，如果的收益比還要低，則以的概率接受，即使用更新繼續(xù)進(jìn)行退火；為了與LS相適應(yīng)，論文將LS中的作為一次迭代過程中退火的次數(shù)，每一次退火之后都使用對退火溫度進(jìn)行更新，降低接受較差解的概率；不斷重復(fù)上述過程，直至連續(xù)沒有得到優(yōu)化的迭代次數(shù)超出了設(shè)定值；至此，論文通過SA對解進(jìn)行了另一種方式的優(yōu)化，同時生成了許多可行的路徑。

Route Recombination

RR算法是一種精確算法，理論上說，如果可以找出所有可行的車輛路徑，對其進(jìn)行組合，則一定可以找到TOPTW的最優(yōu)解，但實際操作中過于復(fù)雜，因此不太實用，但其思想仍然可以借鑒。本論文即是通過兩個有效的算法，對所有可行的車輛路徑的范圍進(jìn)行縮小，只對算法實施過程中生成的車輛路徑進(jìn)行組合，以期得到更好的解。同時，為了說明這一操作的有效性，論文提出了兩個定理：
第一：對于一個求解TOPTW的算法，對其在求解過程中得到的所有可行車輛路徑進(jìn)行符合條件的組合，得到的“最優(yōu)組合解”不比原算法得出的最優(yōu)解更差。

第二：對于兩個不同的求解TOPTW的算法，對它們在求解過程中得到的所有可行車輛路徑進(jìn)行符合條件的組合，得到的“最優(yōu)組合解”不比它們?nèi)魏我粋€得到的最優(yōu)解更差。
根據(jù)這兩個定理，我們可以得出，如果待組合的路徑包含上述兩個算法過程中所有生成的可行路徑，則I3CH算法得出的最優(yōu)解，一定可以通過組合得出來。

盡管通過兩個算法實施過程中得出的可行路徑數(shù)量相對于所有的可行數(shù)量大大降低了，但依然是個較大的數(shù)字，我們只能存儲有限數(shù)量的可行路徑，所以論文采用了一定的策略進(jìn)行優(yōu)化。首先，給每一條路徑都增加一個權(quán)重，即為上文提到的，我們使用優(yōu)先隊列對探索出的可行路徑進(jìn)行存儲，記為，權(quán)重小的路徑“優(yōu)先級”較高，路徑剛進(jìn)入時，權(quán)重設(shè)為0，RR算法對中的路徑進(jìn)行組合時，最終結(jié)果中，被選中的路徑的增加100，其余未被選中的路徑的減少1，即代表一條可行路徑的“優(yōu)秀程度”,越優(yōu)秀的路徑，被選中的可能性更大，其權(quán)重也更高；存在一個容量上限，當(dāng)優(yōu)先隊列中存儲的路徑數(shù)量已經(jīng)達(dá)到時，將優(yōu)先級高即權(quán)重最小的路徑從隊列中移除，再添加新的路徑。通過上述策略，可以在有限容量的情況下，對路徑進(jìn)行遴選以保留優(yōu)秀的路徑。

對于之內(nèi)的路徑的組合，采用了精確算法即整數(shù)規(guī)劃的算法，論文是通過調(diào)用cplex對整數(shù)規(guī)劃問題進(jìn)行求解，建模如下：代表路徑的集合，，，代表顧客在路徑中被訪問了，否則，第條路徑的收益由表示。定義決策變量表示路徑在最終組合里被選中，否則，目標(biāo)函數(shù)和約束條件如下：




其中式表達(dá)了目標(biāo)函數(shù)即備選路徑的總收益最大化，式表明每個顧客最多只能出現(xiàn)在一條路徑中，式表明選擇的路徑數(shù)量不能超過車的數(shù)量。通過對以上整數(shù)規(guī)劃問題的求解，我們可以得出當(dāng)前中可以產(chǎn)生的最優(yōu)的組合。

Construction

一個優(yōu)秀的啟發(fā)式算法有四個組主要的部分，Solution representation，Construction ， Solution neighborhood，Escaping local optima，其中Solution representation上文已經(jīng)提到，Solution neighborhood則由那八個算子進(jìn)行生成，Escaping local optima可以通過SA算法中對于較差解的接受準(zhǔn)則來實現(xiàn)，因此接下來簡要分析初始解的構(gòu)造部分。

在論文中，算法的開始需要構(gòu)造初始解，首先，將算子作用于一個所有的都為空，而包含了所有顧客點的Solution A，因為都為空，所以無法從中移除任何顧客點，而直接從中選取顧客點向中插入，直至得到一個complete solution A，之后對其進(jìn)行Post-Processing操作，得到一個改進(jìn)后的A；對上述過程重復(fù)次，從中選擇最優(yōu)的solution作為初始解，進(jìn)行接下來的操作。同樣地，在初始解構(gòu)造過程中，將探索得到的可行加入到中去，以便于第一次組合。

算法框架

有了上述的部分，我們可以對I3CH的總體算法框架進(jìn)行描述。
首先，設(shè)定最大迭代次數(shù)，構(gòu)造初始解，以及路徑集合；之后，對于中的進(jìn)行組合，得到解 ，對應(yīng)用LS算法，得到解，對應(yīng)用SA算法，得到解 ，令解復(fù)制中總收益最大的解，用更新；不斷重復(fù)上述過程直至迭代次數(shù)超過，如果某次迭代過后得到的解中的已經(jīng)覆蓋了所有的顧客點，則跳出循環(huán)。

總結(jié)

以上便是對該論文提出的I3CH算法的簡要描述，在復(fù)現(xiàn)過程中，我們基本上原封不動地遵從論文的設(shè)定進(jìn)行復(fù)現(xiàn)，只有幾個小的地方與原論文有所差異，基本不夠成影響。在對該算法的學(xué)習(xí)過程中，我們認(rèn)為該算法是一種樸實且有效的算法，其思想并不復(fù)雜。算法應(yīng)用了幾種十分常用的算子，其中對于算子根據(jù)問題做出了一定的優(yōu)化；采用了兩種常用的啟發(fā)式算法，LS和SA，對初始解進(jìn)行優(yōu)化，其創(chuàng)新之處在于合理地運用了Set Packing的方法，通過只對算子操作過程中出現(xiàn)的可行進(jìn)行收集，同時通過優(yōu)化策略保留優(yōu)秀，大大降低了Set Packing的實施范圍，提高了解的求解效率以及質(zhì)量。此算法同時具有很好的拓展性，譬如可以設(shè)計出更多的算子收集可行，擴(kuò)大可能收集到的的范圍，提出更多的遴選策略保留優(yōu)秀，以達(dá)到進(jìn)一步改進(jìn)解的質(zhì)量的目的。

結(jié)果比較

雖然此算法分析起來較為簡單，但由于具體實現(xiàn)起來涉及到各種細(xì)節(jié)，比如算子的進(jìn)一步優(yōu)化，算法框架的具體形式，參數(shù)的選擇，因此最后的結(jié)果與論文的結(jié)果仍有一定的差距

1.在對算子的復(fù)現(xiàn)過程中，由于這些算例問題規(guī)模較小，因此對于，，，，，，這些改變顧客點訪問順序的結(jié)果使用了一定程度上遍歷窮舉的方式進(jìn)行實現(xiàn)，但在具體的實現(xiàn)上，譬如四條路徑之間的如何更大程度的窮舉出來，出現(xiàn)了問題，其他的算子在實現(xiàn)過程中，也有些許的問題，因此在算子對解進(jìn)行優(yōu)化時，很可能難以得出一個接近論文最優(yōu)解的解，而無論是LS還是SA的操作，甚至是RR算法對進(jìn)行組合，最根本的就是這些算子，因此整體解的質(zhì)量弱于論文的解；同時，對算子進(jìn)行的優(yōu)化較少，這也是一個不足之處。

2.參數(shù)調(diào)整，由于我們實現(xiàn)出的代碼與論文的代碼存在許多細(xì)節(jié)差異，因此我們無法直接按照論文里的最優(yōu)參數(shù)進(jìn)行使用，需要嘗試出一個較好的參數(shù)，并且有些地方我們更改了參數(shù)的使用方式，譬如算子部分，我們沒有使用論文中的，“p_l”這兩個不同的概率對不同收益值的顧客點進(jìn)行移除，而只使用了，因此也可能影響到解的質(zhì)量，參數(shù)方面依然有很大的調(diào)整空間。

由此看出，此次復(fù)現(xiàn)的代碼仍有較大的改進(jìn)空間。