OptaPlanner-TSPTW最小化總時間

Question

我使用OptaPlanner來解決什麼是有效的旅行推銷員問題與時間Windows（TSPTW）。我有一個基於OptaPlanner提供的VRPTW示例的初始解決方案。

現在我試圖解決我的要求，從標準TSPTW偏離，它們是：

1. 我試圖儘量減少花費，而不是移動的總距離總時間。正因爲如此，空閒時間對我不利。
2. 除了標準時間訪問訪問之外，我還必須支持不遲於（NLT）訪問（即X時間後不訪問）和不早於（NET）訪問（即不訪問在X時間之前）。

我目前的解決方案總是將第一次訪問的到達時間設置爲該訪問的開始時間。這對我的要求有以下問題：

1. 這可能會引入不必要的空閒時間，如果訪問是在某個時間晚些時候到達其時間窗口時可以避免的，則可以避免不必要的空閒時間。
2. NLT的行爲有問題。如果我定義的開始時間設置爲Long.MIN_VALUE（表示它是無限的，而不使用空值），那麼這就是NLT訪問到達的時間（與＃1相同的問題）。我嘗試通過將開始時間設置爲NLT時間來解決這個問題。這導致正好趕上NLT訪問，但超出了隨後訪問的時間窗口。

我該如何解決這個/這些問題？我懷疑解決方案將涉及ArrivalTimeUpdatingVariableListener，但我不知道該解決方案應該是什麼樣子。

如果相關，我已經粘貼了下面的當前評分規則。有一點要注意的是，「距離」實際上是旅行時間。另外，出於域名原因，我鼓勵NLT和NET到達時間接近截止時間（NLT的結束時間，NET的開始時間）。

import org.optaplanner.core.api.score.buildin.hardsoftlong.HardSoftLongScoreHolder; 

global HardSoftLongScoreHolder scoreHolder; 

// Hard Constraints 
rule "ArrivalAfterWindowEnd" 
    when 
    Visit(arrivalTime > maxStartTime, $arrivalTime : arrivalTime, $maxStartTime : maxStartTime) 
    then 
    scoreHolder.addHardConstraintMatch(kcontext, $maxStartTime - $arrivalTime); 
end 

// Soft Constraints 
rule "MinimizeDistanceToPreviousEvent" 
    when 
    Visit(previousRouteEvent != null, $distanceFromPreviousRouteEvent : distanceFromPreviousRouteEvent) 
    then 
    scoreHolder.addSoftConstraintMatch(kcontext, -$distanceFromPreviousRouteEvent); 
end 

rule "MinimizeDistanceFromLastEventToHome" 
    when 
    $visit : Visit(previousRouteEvent != null) 
    not Visit(previousRouteEvent == $visit) 
    $home : Home() 
    then 
    scoreHolder.addSoftConstraintMatch(kcontext, -$visit.getDistanceTo($home)); 
end 

rule "MinimizeIdle" 
    when 
    Visit(scheduleType != ScheduleType.NLT, arrivalTime < minStartTime, $minStartTime : minStartTime, $arrivalTime : arrivalTime) 
    then 
    scoreHolder.addSoftConstraintMatch(kcontext, $arrivalTime - $minStartTime); 
end 

rule "PreferLatestNLT" 
    when 
    Visit(scheduleType == ScheduleType.NLT, arrivalTime < maxStartTime, $maxStartTime : maxStartTime, $arrivalTime : arrivalTime) 
    then 
    scoreHolder.addSoftConstraintMatch(kcontext, $arrivalTime - $maxStartTime); 
end 

rule "PreferEarliestNET" 
    when 
    Visit(scheduleType == ScheduleType.NET, arrivalTime > minStartTime, $minStartTime : minStartTime, $arrivalTime : arrivalTime) 
    then 
    scoreHolder.addSoftConstraintMatch(kcontext, $minStartTime - $arrivalTime); 
end 

Answer 1

我能夠通過修改ArrivalTimeUpdatingVariableListener的updateArrivalTime方法來解決我的問題，以便向後和（嘗試）移動先前到達時間。另外，我引入了一個getPreferredStartTime（）方法來儘可能遲的支持默認的NLT事件。最後，爲了代碼清潔，我將ArrivalTimeUpdatingVariableListener中的updateArrivalTime方法移入了Visit類。

下面是從訪問類的相關代碼：

public long getPreferredStartTime() 
{ 
    switch(scheduleType) 
    { 
     case NLT: 
      return getMaxStartTime(); 
     default: 
      return getMinStartTime(); 
    } 
} 

public Long getStartTime() 
{ 
    Long arrivalTime = getArrivalTime(); 
    if (arrivalTime == null) 
    { 
     return null; 
    } 

    switch(scheduleType) 
    { 
     case NLT: 
      return arrivalTime; 
     default: 
      return Math.max(arrivalTime, getMinStartTime()); 
    } 
} 

public Long getEndTime() 
{ 
    Long startTime = getStartTime(); 
    if (startTime == null) 
    { 
     return null; 
    } 
    return startTime + duration; 
} 

public void updateArrivalTime(ScoreDirector scoreDirector) 
{ 
    if(previousRouteEvent instanceof Visit) 
    { 
     updateArrivalTime(scoreDirector, (Visit)previousRouteEvent); 
     return; 
    } 

    long arrivalTime = getPreferredStartTime(); 
    if(Utilities.equal(this.arrivalTime, arrivalTime)) 
    { 
     return; 
    } 

    setArrivalTime(scoreDirector, arrivalTime); 
} 

private void updateArrivalTime(ScoreDirector scoreDirector, Visit previousVisit) 
{ 
    long departureTime = previousVisit.getEndTime(); 
    long arrivalTime = departureTime + getDistanceFromPreviousRouteEvent(); 

    if(Utilities.equal(this.arrivalTime, arrivalTime)) 
    { 
     return; 
    } 

    if(arrivalTime > maxStartTime) 
    { 
     if(previousVisit.shiftTimeLeft(scoreDirector, arrivalTime - maxStartTime)) 
     { 
      return; 
     } 
    } 
    else if(arrivalTime < minStartTime) 
    { 
     if(previousVisit.shiftTimeRight(scoreDirector, minStartTime - arrivalTime)) 
     { 
      return; 
     } 
    } 

    setArrivalTime(scoreDirector, arrivalTime); 
} 

/** 
* Set the arrival time and propagate the change to any following entities. 
*/ 
private void setArrivalTime(ScoreDirector scoreDirector, long arrivalTime) 
{ 
    scoreDirector.beforeVariableChanged(this, "arrivalTime"); 
    this.arrivalTime = arrivalTime; 
    scoreDirector.afterVariableChanged(this, "arrivalTime"); 

    Visit nextEntity = getNextVisit(); 
    if(nextEntity != null) 
    { 
     nextEntity.updateArrivalTime(scoreDirector, this); 
    } 
} 

/** 
* Attempt to shift the arrival time backward by the specified amount. 
* @param requested The amount of time that should be subtracted from the arrival time. 
* @return Returns true if the arrival time was changed. 
*/ 
private boolean shiftTimeLeft(ScoreDirector scoreDirector, long requested) 
{ 
    long available = arrivalTime - minStartTime; 
    if(available <= 0) 
    { 
     return false; 
    } 

    requested = Math.min(requested, available); 
    if(previousRouteEvent instanceof Visit) 
    { 
     //Arrival time is inflexible as this is not the first event. Forward to previous event. 
     return ((Visit)previousRouteEvent).shiftTimeLeft(scoreDirector, requested); 
    } 

    setArrivalTime(scoreDirector, arrivalTime - requested); 
    return true; 
} 

/** 
* Attempt to shift the arrival time forward by the specified amount. 
* @param requested The amount of time that should be added to the arrival time. 
* @return Returns true if the arrival time was changed. 
*/ 
private boolean shiftTimeRight(ScoreDirector scoreDirector, long requested) 
{ 
    long available = maxStartTime - arrivalTime; 
    if(available <= 0) 
    { 
     return false; 
    } 

    requested = Math.min(requested, available); 
    if(previousRouteEvent instanceof Visit) 
    { 
     //Arrival time is inflexible as this is not the first event. Forward to previous event. 
     //Note, we could start later anyways but that won't decrease idle time, which is the purpose of shifting right 
     return ((Visit)previousRouteEvent).shiftTimeRight(scoreDirector, requested); 
    } 

    setArrivalTime(scoreDirector, arrivalTime + requested); 
    return false; 
} 

Answer 2

若要查看使用實際道路倍，而不是道路距離的一個例子：在這些例子中的應用程序，開放式車輛路徑，點擊按鈕導入，加載文件roaddistance/capacitated/belgium-road-time-n50-k10.vrp。那些時間是calculated with GraphHopper。

要查看使用時間窗口的示例，請打開車輛路徑並快速打開名爲cvrptw（tw代表時間窗口）的數據集。如果你看看CVRPTW的學術規範（從文檔第三章IIRC鏈接），你會發現它已經有一個嚴格的約束「不要在時間窗關閉後到達」 - 所以你會看到一個分數規則drl。至於到達太早（並因此失去空閒時間）：複製粘貼硬約束，使其變軟，使其使用readyTime而不是dueTime，並且反轉它的比較和懲罰計算。我實際上最初是這樣實施的（因爲這是合乎邏輯的），但是因爲我遵循學術規範（與學術成果相比較），我必須將其刪除。