Алгоритм подбора заказов со складов

Question

Я объясню мою проблему на примере. Допустим, у нас есть:

• An Заказ в определенном магазине на пять продуктов, назовем эти продукты A, B, C, D, & E , с их количествами В Заказ A (19), B (25), C (6), D (33) , E (40) .

• Один Грузовик , который может соответствовать разному количеству каждого продукта: A (30), B (40), C (25), D (50), E (30).

Ex : при транспортировке A & B вместе, я загрузил грузовик с A (19), так что это две трети того, что может выдержать мой грузовик, так что остается одна треть для B , что означает, что я могу перевозить только 1/3 от B Максимальная вместимость грузовика составляет (40/3 ≈ 13).

• Набор из Складов , который содержит различные количества каждого продукта.

Я создал электронную таблицу Excel, которая содержит более полезную информацию о таких складах, как ( Количество , Расстояние друг от друга , Расстояние от магазина ).

Я хочу доставить этот заказ в магазин с наименьшим количеством поездок и пройденным расстоянием.

Есть ли алгоритм для такого рода проблем, или что-то близкое, что я могу изменить?

РЕДАКТИРОВАТЬ: Обновлены ссылки.

Answer 1

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

Моя точка зрения такова, что проще закодировать вашу проблему с помощью таких инструментов. Если вам не хватает производительности / точности - вы можете разработать индивидуальное решение на основе ваших предварительных результатов.

Для CSP я бы предложил Minizin c, который имеет приличную документацию и примеры.

Вы можете начать исследование MIP с GLPK . Он не очень мощный, но он определенно способен справиться с некоторыми игрушечными примерами.