CVRPTW с Precedences amd транспортного средства отказа в OptaPlanner - PullRequest
Новая
       27

CVRPTW с Precedences amd транспортного средства отказа в OptaPlanner

0 голосов
/ 27 августа 2018

У меня есть проблема, и мне действительно трудно справиться с ней. Я хочу использовать OptaPlanner для решения CVRPTW с прецедентами и отказами транспортных средств. До сих пор я делал стандартный пример и решал его в графическом интерфейсе, а затем сохранял результаты. Затем я изменил XML-файл в Python, чтобы вручную удалить автомобиль и освободить клиентов. Я знаю, что правильный способ - это создать ProblemFact, но я понятия не имею, как это сделать. Я видел некоторые ответы, но мне нужно больше помощи или пример того, как это делается.

Во-вторых, как я могу смоделировать приоритеты. Таким образом, клиент «А» должен прийти раньше клиента «Б». (Единственный пример относится к другой проблеме, которая называется Планирование заданий проекта)

Большое спасибо!

1 Ответ

0 голосов
/ 28 августа 2018

Вопрос А очень прост.

Вопрос Б не так.

Что касается A, вам нужно находиться в положении, в котором вы можете получить доступ к графу объектов (например, после десериализации решения). Затем вы получаете первого клиента этого транспортного средства, устанавливая его previousStandstill на null: 

 Customer nextCustomer = vehicle.getNextCustomer();
 if (nextCustomer != null){
     scoreDirector.beforeVariableChanged(nextCustomer, "previousStandstill");
     nextCustomer.setPreviousStandstill(null);
     scoreDirector.afterVariableChanged(nextCustomer, "previousStandstill");
     scoreDirector.triggerVariableListeners();
 }

Я считаю, что Вопрос B заслуживает большего внимания. Стандартный способ сделать это состоит в том, чтобы реализовать OrderListener, который запускает previousStandstill клиента, слушатель обновляет всех клиентов в цепи транспортного средства всякий раз, когда previousStandstill изменяется для любого клиента: 

@CustomShadowVariable(variableListenerClass = OrderListener.class,
        sources = {@PlanningVariableReference(variableName = "previousStandstill")})
public Integer getPositionInVehicleChain() {
    return position;
}

, а затем в методе OrderListener afterVariableChanged получить что-то вроде этого: 

while (nextCustomer != null) {
        if (position == nextTe.getPositionInVehicleChain()) break;
        scoreDirector.beforeVariableChanged(nextCustomer, "position");
        nextCustomer.setPositionInStapelabschnitt(pos);
        scoreDirector.afterVariableChanged(nextCustomer, "position");
        pos++;
        nextCustomer = nextCustomer.getNextCustomer();  
    }

Затем вы реализуете isBeforeCustomer(Customer otherCustomer) в вашем Customer классе, где вы сравниваете два position s.

Однако это, безусловно, не самый элегантный метод, поскольку его временная сложность равна O(n), где n - общее количество планирующих объектов. хороший способ сделать это состоит в том, чтобы реализовать так называемую структуру данных обслуживания заказов для клиентов по транспортному средству. Эта структура данных поддерживает операции

  1. Вставка (x, y): вставка нового клиента в существующую цепочку
  2. Удалить (x): это удаление клиента из существующей цепочки, см. Вопрос А.
  3. Порядок (x, y): определите, предшествует ли x порядку y в цепочке - это то, что вам нужно.

Состояние современных алгоритмов (см., Например, «Бендер М.А., Коул Р., Демейн Э.Д., Фарах-Колтон М., Зито Дж. (2002) Два упрощенных алгоритма для поддержания порядка в списке». В: Мёринг R., Raman R. (eds) Алгоритмы - ESA 2002. ESA 2002. Конспект лекций в области компьютерных наук, том 2461. Springer, Berlin, Heidelberg ") поддерживает O(1) амортизированное время вставки / удаления и O(1) запрос в худшем случае время, намного лучше, чем система, предложенная выше (но гораздо больше работы). Посмотрите на транзитивность утилит , если вы заинтересованы в реализации. Мне было бы очень интересно, если бы такая структура данных была включена в виде теневых переменных из коробки в optaplanner - вопрос о том, находится ли один объект перед другим в цепочке, является повсеместным.

...