Подскажите алгоритм.

Дано:
склад с пронумерованными ячейками, в которых лежат различные товары.
один товар может лежать в нескольких местах.
задано, сколько нужно собрать на поддон товара A(1) N(1) штук, товара А (2) N(2) штук, ... товара А (m) N(m) штук

Надо:
рассчитать из каких ячеек брать и порядок обхода, чтобы длина пути была минимальна.

Если бы ячейки были фиксированными, то это алгоритм коммивояжера. Но тут можно варьировать, из каких ячеек брать.

TaffyОдин раз просчитать расстояние между ячейками (всеми), занести в табличку. (Эта-то инфа относится к структуре склада и по идее не должна меняться значимо часто).
Затем берем все ячейки в которых находится наш товар. Строим ВСЕ возможные цепочки обхода ячеек.

10 товаров, каждый может быть на одном из 10 мест - вполне реальные количества. Сколько будет вариантов наборов ячеек? 10 в степени 10 = 10000000000
Прямым перебором нереально.

Taffy
Примерно так, но на практике заставить кладовщиков ходить по маршрутам очень тяжелая задача


Пусть ходят как хотят, главное, чтобы брали из тех ячеек, из которых сказано.
Если программа не будет предлагатся идиотские маршруты, то проблем не возникнет.

просчитать всегда легче чем организовать кого-либо

Проба сил№
У меня мелкие количество собираются в "ближнем" месте, большие в "дальнем". Так же можно добавить наиболее часто встречающиеся товары и положить их поближе... Более просто для понимания и действенно. Кладовщик получает маршрутный лист с перечнем ячеек из которых должен забрать, ячейки имеют сортировку по наиболее оптимальному маршруту (как у Taffy), но идти ли по нему на усмотрение...


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

[quot Taffy]
просчитать всегда легче чем организовать кого-либо
[/qout]

пока что в этом случае наоборот

LSVА нужно ли ЭТО ????????????

Нужно. Слово WMS ничего не говорит? Просьба не писать ерунду.

andbary
Когда я сталкивался с данной проблемой мы использовали понятие "идеальный маршрут".

Очень интересно. Можно попробнее?

Для обсуждения целесообразности WMS систем прошу создать отдельный топик.
Тут обсуждается организация марштрутов сборки и ничего больше.
Вроде бы исходная задача сформулирована достаточно четко.

casmithИнтересно, что именно Вы хотите получить?
Алгоритм расчета "в лоб" именно минимальной длины обхода Вам уже подсказали.

...

Т.е в любом случае получаем граф, в узлах которого лежат товары. Считаем длины путей графа и выбираем наименьший.
Как по другому?

Какой алгоритм? Прямой перебор? Все просто как у Шарикова: взять и посчитать? Это не алгоритм, у него запредельная выч. сложность.

Товар не штучный. Склад ответственного хранения. Сбор коробок с поддономест на поддон. Возможно, мне надо было написать не ячейки, а поддоны в первом сообщении, тогда было бы яснее.
Длинные стеллажи с поддонами выставлены во много рядов, не в один.