Наведите порядок в Jsprit с помощью HardActivityConstraint

В сценарии повторного решения ранее решенной проблемы (конечно, с некоторыми новыми данными), как правило, невозможно переназначить самое первое назначение транспортного средства после того, как оно было дано. Драйвер уже в пути, и любое новое решение должно учитывать следующее:

  • работа должна оставаться его (не может быть назначена на другой автомобиль)
  • деятельность, которая была назначена ему как самая первая, должна оставаться таковой в будущих решениях

Для простоты я использую сценарий с одним транспортным средством и пытаюсь применить только вторую пулю (т.е. гарантировать, что определенное действие будет первым в решении).

Вот как я определил ограничение:

new HardActivityConstraint()
{
    @Override
    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct,
                                       double prevActDepTime)
    {
        String locationId = newAct.getLocation().getId();

        //  we want to make sure that any solution will have "C1" as its first activity
        boolean activityShouldBeFirst = locationId.equals("C1");

        boolean attemptingToInsertFirst = (prevAct instanceof Start);

        if (activityShouldBeFirst && !attemptingToInsertFirst)
            return ConstraintsStatus.NOT_FULFILLED_BREAK;

        if (!activityShouldBeFirst && attemptingToInsertFirst)
            return ConstraintsStatus.NOT_FULFILLED;

        return ConstraintsStatus.FULFILLED;
    }
}

Вот как я строю алгоритм:

VehicleRoutingAlgorithmBuilder vraBuilder;
vraBuilder = new VehicleRoutingAlgorithmBuilder(vrpProblem, "schrimpf.xml"); 
vraBuilder.addCoreConstraints();
vraBuilder.addDefaultCostCalculators();

StateManager stateManager = new StateManager(vrpProblem);
ConstraintManager constraintManager = new ConstraintManager(vrpProblem, stateManager);
constraintManager.addConstraint(new HardActivityConstraint() { ... }, Priority.HIGH);
vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);

VehicleRoutingAlgorithm algorithm = vraBuilder.build();

Результаты не очень хорошие. Я получаю решения только с одной назначенной работой (той, которая требует активности). При отладке ясно, что итерации вставки заданий учитывают множество жизнеспособных вариантов, которые, по-видимому, полностью решают проблему, но в конечном итоге лучшее решение, возвращаемое алгоритмом, не включает другие задания.

ОБНОВЛЕНИЕ: еще более удивительно то, что когда я использую ограничение в сценариях с более чем 5 транспортными средствами, оно работает нормально (худшие результаты - с 1 транспортным средством).

При необходимости я с удовольствием приложу дополнительную информацию.

Спасибо Зак


java jsprit
person Zach-M    schedule 06.03.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, вы можете использовать начальные маршруты, чтобы гарантировать, что определенные задания должны быть назначены конкретным транспортным средствам с самого начала (см. пример).

Во-вторых, чтобы гарантировать, что никакое действие не будет вставлено между start и вашим начальным заданием (местоположением) (например, «C1» в вашем примере), вам необходимо запретить его так, как вы определили свой HardActConstraint, просто измените его так, чтобы newAct никогда не мог быть между prevAct = Start и nextAct = act (C1).

В-третьих, что касается вашего обновления, просто имейте в виду, что суть алгоритма состоит в том, чтобы разрушить часть решения (удалить несколько заданий) и заново воссоздать решение (вставить неназначенные задания). В настоящее время алгоритм schrimpf разрушает количество заданий относительно общего числа заданий, то есть noJobs = 0,5 * totalNoJobs для случайного разрушения и 0,3 * totalNoJobs для радиального разрушения. Если ваша проблема очень небольшая, то доли удаляемых вакансий может быть недостаточно. Это изменится в следующем выпуске, где вы можете использовать алгоритм из коробки, который определяет абсолютный минимум заданий, которые необходимо удалить. А пока измените общие ресурсы в своем algorithmConfig.xml.

person Stefan Schröder    schedule 10.03.2015
comment
Спасибо за быстрый и подробный ответ, Стефан. Однако и поправьте меня, если я ошибаюсь, похоже, что способ работы addInitialVehicleRoute () ограничен для отгрузок - если я добавляю часть доставки отгрузки в initialVehicleRoute, я также должен включить часть доставки, которая бросает вызов цели, позволяющей алгоритму определить лучший способ включить часть доставки в будущий маршрут - person Zach-M; 10.03.2015
comment
Кроме того, что касается вашего второго пункта, предлагая изменить ограничение, чтобы newAct никогда не проходил между Start и C1 - то, что я сделал, было на самом деле более общим, не позволяя newAct не-C1 появляться после Start (независимо от nextAct). По логике, оба этих вкуса должны дать один и тот же результат, за исключением того, что более общая форма должна привести нас к нему быстрее. Почему вы предлагаете ослабить ограничение? - person Zach-M; 10.03.2015
comment
Вы правы, способ, которым вы реализовали ограничение, умнее того, что я предлагал. - person Stefan Schröder; 11.03.2015