求解器太慢

我仍在使用OptaPlanner來優化與VehicleRoutingExample類似的鏈接計劃問題。我的計劃實體有一個計劃變量，這是另一個計劃實體。得分是HardSoftScores，這是用IncrementalScore計算的。求解器太慢

目前我遇到的問題是求解器所需的時間仍然太長以至於找不到可接受的解決方案。

我想優化一個固定數量的工人的問題，他們必須用多個時間窗口處理固定數量的訂單。

訂單是我的鏈式實體，工人被用作鏈條的錨點。我正在計算聽衆訂單的開始和結束時間點。另一位聽衆正在保存每個實體中每個鏈的錨點（因爲它需要很多時間才能通過可能超過1000個實體的鏈......）

我的目標是解決有關3000個實體的問題目前求解器需要2個多小時才能獲得可接受的解決方案。對於400個實體的較小問題，它需要近5分鐘，這也太長了。 10分鐘爲更大的問題10分鐘會沒事的，小的1分鐘。

我已經與benchmarker找到最好的解算器的配置工作...

是否有人看到了一些可能性，使我更快地求解？

P.S .:是一個使用多線程的機會？還是optaplanner已經使用它？

來源

2014-11-14 Jon As

這將是很好看你到目前爲止所嘗試過的。即使是一小段代碼，也可以幫助讀取長文本。 –

發佈一些代碼並解釋什麼是* VehicleRoutingExample *。我們是程序員，而不是巫師。 – ortis

很抱歉，這是一個關於vrp（vehicle-routing-problem）變體的特定optaplanner問題， –

看看附近的選項在6.2.0.CR2（和CR1也是）。

enter image description here

這只是部分記錄尚未...而不是對所有類型的移動還（只是改變和交換動作）......要有耐心。但是一旦你達到2K實體或更多，它就會更好。沒有它，這比該曲線的最糟糕的人更糟糕：

enter image description here

這裏是我的本地基準之一的快速和骯髒的複製和粘貼：

<#list [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 5000] as linearDistributionSizeMaximum> 
    <solverBenchmark> 
    <name>LA Nearby LinDist max${linearDistributionSizeMaximum}</name> 
    <solver> 
     <constructionHeuristic> 
      <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType> 
     </constructionHeuristic> 
     <localSearch> 
      <unionMoveSelector> 
       <changeMoveSelector> 
        <entitySelector id="entitySelector1"/> 
        <valueSelector> 
         <nearbySelection> 
          <originEntitySelector mimicSelectorRef="entitySelector1"/> 
          <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass> 
          <linearDistributionSizeMaximum>${linearDistributionSizeMaximum}</linearDistributionSizeMaximum> 
         </nearbySelection> 
        </valueSelector> 
       </changeMoveSelector> 
       <swapMoveSelector> 
        <entitySelector id="entitySelector2"/> 
        <secondaryEntitySelector> 
         <nearbySelection> 
          <originEntitySelector mimicSelectorRef="entitySelector2"/> 
          <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass> 
          <linearDistributionSizeMaximum>${linearDistributionSizeMaximum}</linearDistributionSizeMaximum> 
         </nearbySelection> 
        </secondaryEntitySelector> 
       </swapMoveSelector> 
      </unionMoveSelector> 
      <acceptor> 
       <lateAcceptanceSize>200</lateAcceptanceSize> 
      </acceptor> 
      <forager> 
       <acceptedCountLimit>1</acceptedCountLimit> 
      </forager> 
     </localSearch> 
    </solver> 
    </solverBenchmark> 
</#list> 
<#list [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 5000] as parabolicDistributionSizeMaximum> 
    <solverBenchmark> 
    <name>LA Nearby ParDist max${parabolicDistributionSizeMaximum}</name> 
    <solver> 
     <constructionHeuristic> 
      <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType> 
     </constructionHeuristic> 
     <localSearch> 
      <unionMoveSelector> 
       <changeMoveSelector> 
        <entitySelector id="entitySelector1"/> 
        <valueSelector> 
         <nearbySelection> 
          <originEntitySelector mimicSelectorRef="entitySelector1"/> 
          <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass> 
          <parabolicDistributionSizeMaximum>${parabolicDistributionSizeMaximum}</parabolicDistributionSizeMaximum> 
         </nearbySelection> 
        </valueSelector> 
       </changeMoveSelector> 
       <swapMoveSelector> 
        <entitySelector id="entitySelector2"/> 
        <secondaryEntitySelector> 
         <nearbySelection> 
          <originEntitySelector mimicSelectorRef="entitySelector2"/> 
          <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass> 
          <parabolicDistributionSizeMaximum>${parabolicDistributionSizeMaximum}</parabolicDistributionSizeMaximum> 
         </nearbySelection> 
        </secondaryEntitySelector> 
       </swapMoveSelector> 
      </unionMoveSelector> 
      <acceptor> 
       <lateAcceptanceSize>200</lateAcceptanceSize> 
      </acceptor> 
      <forager> 
       <acceptedCountLimit>1</acceptedCountLimit> 
      </forager> 
     </localSearch> 
    </solver> 
    </solverBenchmark> 
</#list>

來源

2014-11-14 14:22:15

回答

相關問題