Отгрузка пакетов (объединение пакетов) с помощью OR-Tools CP Solver в Python (многозадачный) - PullRequest
Новая
       77

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

0 голосов
/ 11 октября 2019

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

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

У Mini_Packages есть некоторые важныеатрибуты в источнике данных (фиксированное назначение, вес, допустимый диапазон дат доставки).

Моя основная целочисленная переменная 0-1 выглядит следующим образом: 

x[mini_package_source_number, destination, optimal_shipment_date, package_number]

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

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

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

Потенциальный код: 

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

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

Решение для потенциального решения: 

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

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

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

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

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

2. Добавление

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

3. Конфликт продуктов:

Очки 2-3 перенесены в:
https://or.stackexchange.com/questions/2786/shipments-consolidation-with-or-tools-cp-solver-in-python-multi-knapsack

1 Ответ

0 голосов
/ 11 октября 2019

Создайте boolvar для каждой пары [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)

Та же логика для дат.

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

...