Отгрузка пакетов (объединение пакетов) с помощью OR-Tools CP Solver на Python (мульти-рюкзак)

Реализую решение для консолидации пакетов (на основе решения задачи медсестры) с OR-Tools CP Solver.

Есть фабрика, которая производит небольшие упаковки, которые необходимо доставить клиентам по почте. Было бы оптимальным объединить некоторые mini_Packages в более крупные пакеты (например, если мы соблюдаем ограничение по общему весу, мы можем объединить 3 легких mini_Packages в один пакет и оплатить транспортные расходы один раз, а не три раза).

Мини-пакеты имеют некоторые важные атрибуты в источнике данных (фиксированный пункт назначения, вес, допустимый диапазон дат доставки).

Моя основная целочисленная переменная 0-1 выглядит так:

x[mini_package_source_number, destination, optimal_shipment_date, package_number]

Это == 1, если mini_package должен отправиться в определенное место назначения в определенный день, объединенный с определенным Package_number.

Мне удалось собрать большую часть модели, кроме:

1. Основная проблема
Как наложить ограничение, гарантирующее, что, когда решателем назначается оптимальный номер посылки, он не может использоваться ни с каким другим местом назначения или shipment_date? (это физически один консолидированный пакет, отправляемый в определенное место)

Возможный код:

for package_number in range(Packages):
  model.Add(sum(x[mini_package_source_number, destination, optimal_shipment_date, package_number] for ...) <= 1)

было бы неправильно, поскольку назначенный Package_number может существовать много раз, объединяя несколько mini_Packages. Он может существовать несколько раз, но всегда должен быть привязан к одному и тому же месту назначения и дате.

Возможное решение:

x[1, Place67, 2019-01-01, 8] = 1
x[2, Place124, 2019-01-04, 119] = 1
x[3, Place124, 2019-01-04, 119] = 1

пока все в порядке, mini_Packages 2 и 3 были объединены в пакет 119 с тем же местом назначения (и датой).

x[4, Place55, 2019-01-05, 119] = 1

было бы неправильно, потому что mini_Package 4 также был объединен в пакет 119, который ранее был решен решателем для перехода в другое место назначения (и в другую дату).

Как это можно было закодировать? Я был бы очень признателен за любое предложение решения.

2. Дополнение

Чувство @Stradivari (ответ ниже) является точным. Весьма вероятно, что я использую лишние переменные.

3. Проблема с конфликтующими продуктами

Пункты 2–3 перемещены в:
https://or.stackexchange.com/questions/2786/shipments-consolidation-with-or-tools-cp-solver-in-python-multi-knapsack.


python scheduling knapsack-problem or-tools cp
person Tomasz Kot    schedule 11.10.2019    source источник
comment
Это размещено здесь: groups.google.com / forum / #! topic / or-tools-Обсуждение / TkaPJT-i168   -  person Stradivari    schedule 11.10.2019
comment
Можете ли вы оставить здесь только исходный вопрос и переместить вопросы моделирования на или.stackexchange.com?   -  person Stradivari    schedule 12.10.2019
comment
Ok. Пункты 2–3 перемещены в: or.stackexchange.com/questions/2786/   -  person Tomasz Kot    schedule 12.10.2019

Ответы (1)


arrow_upward
0
arrow_downward

Создайте логическую переменную для каждой пары [pkg, destination].

for package_number in range(Packages):
    for destination in destinations:
        model.AddBoolOr(v for k, v in x.items() if k[1] == destination and k[3] == package_number).OnlyEnforceIf(pkg_dest[package_number, destination])
        model.AddBoolAnd(v.Not() for k, v in x.items() if k[1] == destination and k[3] == package_number).OnlyEnforceIf(pkg_dest[package_number, destination].Not())
    model.Add(sum(pkg_dest[package_number, destination] for destination in destinations) == 1)

Та же логика для свиданий.

Кстати, я чувствую, что вы можете создать много бесполезных переменных с этой формулировкой, можете ли вы действительно выбрать место назначения и / или дату мини-пакета? Или только его пакет, а затем для каждого пакета его место назначения и дату?

person Stradivari    schedule 11.10.2019
comment
2. Ваше ощущение верное. Очень вероятно, что я использую лишние переменные (первый проект ранца). Я добавил пункт 2 в вышеупомянутом сообщении, описывая его и спрашивая о потенциальных идеях по упрощению. - person Tomasz Kot; 12.10.2019
comment
3. Чтобы дать кому-либо полную идею, в посте выше я добавил дополнительную задачу (пункт 3), которая важна (и может повлиять на оптимальные направления решения). - person Tomasz Kot; 12.10.2019