Эвристика строительства на VRP - медленная работа на больших наборах данных

Question

У меня есть большая проблема с VRP с более чем 10000 остановками. Разработка эвристики строительства занимает много времени, независимо от того, какие опции используются, включая фильтры и другие трюки.

Алгоритмы перемещения и свопа обычно работают хорошо, как только они начинаются, но для решения фазы строительства требуется 30 минут.

Любые предложения по вариантам, которые могут обеспечить лучший результат? Я чувствую, что Optaplanner слишком строг на этапе строительства, когда более простой вариант может быть лучшим балансом.

Config, которая, кажется, работает лучше всего выглядит следующим образом:

<constructionHeuristic> 
    <queuedEntityPlacer> 
     <entitySelector id="placerEntitySelector"> 
      <cacheType>PHASE</cacheType> 
      <selectionOrder>SORTED</selectionOrder> 
      <sorterManner>DECREASING_DIFFICULTY</sorterManner> 
     </entitySelector> 
     <changeMoveSelector> 
      <entitySelector mimicSelectorRef="placerEntitySelector" /> 
      <filterClass>org.optaplanner.examples.vehiclerouting.domain.solver.CustomerSelectionFilter</filterClass> 
     </changeMoveSelector> 
    </queuedEntityPlacer> 
</constructionHeuristic> 

Приветствия, ник

Answer 1

Пару идеи вот что я по не ВРП случаев (которые будут работать, в какой-то степени) :

• selectedCountLimit (Я бы не стал меньше 1) действительно является стандартным способом ускорить эвристику строительства. Качество результата для скорости.
• CH FIRST_FEASIBLE_FIT - это еще один способ. Он похож на selectedCountLimit 1. Разница в том, что он выбирает больше значений, пока он еще не нашел значения, которое не нарушит каких-либо жестких ограничений.

Реальное решение, потому что вы получили 10k + VRP мест:

• Соседнего выбор внутри строительной эвристики (я полагаю, вы уже используете Соседний Выбор внутри локального поиска (если нет, то вы должны быть)). Я еще не делал никаких экспериментов с этим - он находится в моем списке non-customer-priority todo. Я считаю, что в optaplanner-core требуется несколько улучшений, но ничего хорошего. Задачи в 6.2: 1) CH требуют окончания селекторов, а ближайший выбор всегда никогда не заканчивается (потому что он использует вероятности). Комбинация selectionOrder RANDOM и selectionLimit 1000, возможно, справится с этим. Или еще лучше, мы должны поддерживать оригинальный выбор в ближайшем порядке (который заканчивался бы и не использовал бы вероятности). Обратите внимание, что selectionLimit сам по себе не достаточен, потому что «ближайший» порядок списка сущностей отличается от сущности к сущности. 2) Некоторые близкие случайные распределения не позволяют выбирать каждый элемент. Должны быть выбраны только инициализированные элементы (нарушаются другие принципы мудрой цепочки). Не уверен, что происходит сейчас. Необходимо проверить.

• Строительный эвристический «Ближайший сосед». Еще нет встроенного в optaplanner 6.2. В то время как (true) соединяют 2 местоположения, которые наиболее близки друг к другу. Могло бы временно нарушить принципы цепочки ... Это инверсия Fit First. Вместо установки одного хозяйствующего субъекта по одному (взять объект и найти его значение), значения подходят один за другим (взять значение и найти свою сущность.

НТН