На самом деле на реальном складе необходимо рассчитывать не минимальную длину пути при сборе заказа, а манимальные трудозатраты при сборе заказа. Организация склада, когда один товар может находиться в нескольких местах, порочна сама по себе.
К тому же обычно:
1) порядок обхода склада задается самой топологией - расположением стеллажей. Существует АВС классификация ячеек и пр. и пр.
2) необходимо учитывать вес товара, чтобы тяжелое не положить поверх легкого - раздавит.
3) в общем случае необходимо учитывать количество товара, помещающееся на один поддон...
4) и т.д. и т.п.

Собственно, маршрут обхода практически задается на этапе размещения.

Заставить ходить по маршруту кладовщиков - если маршрутный лист вменяемый, то будут ходить без проблем!

Идея "идеального маршрута" исходя из опыта видится мне оптимальной по критерию выгода/затраты.

Давным-давно существуют роботизированные склады. :)
Мечта любого программиста складских систем - избавиться от персонала. :)

andbary casmithОрганизация склада, когда один товар может находиться в нескольких местах, порочна сама по себе.

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

Возможно, применил неточное слово. :) Речь шла именно об отборе товара, а не приемке. Вопрос о "товарным кэше" как месте для отбора мелких партий - достаточно спорный вопрос. :)
andbary
2. Топология склада постоянно меняется (поставили новый стелаж и все), лучше использовать дополнительные цифровые поля для сортировки.
Это на каком складе постоянно меняется топология, можно узнать? И "постоянно" - это с какой частотой? :) andbary
4. Если маршрутный лист вменяемый... и если вменяемый то для кого... и если за такие деньги наняли вменяемый персонал... и тд и тп Вменяемый - это такой, который содержит такой маршрут отбора, какой выбрал бы квалифицированный отборщик. Ну или близкий к такому маршрут. :)

Исходя из всего метод экспертного назначения маршрутов (или "идеальный маршрут", как его здесь еще назвали) при соблюдении правильной стратегии размещения является наименее трудоемким и наиболее простым, в дополнение и наиболее управляемым. :)

andbary LSVЕсли вышеперечисленного не учесть, то грош-цена такой системе . Она будет неточной, а по сему ненужной .
А теперь оцените, целесообразно ли строить такую систему ? ? ?
beginner20004Слово WMS ничего не говорит?Говорит ! Говорит !
Однако не уверен, что такой орешек Вам по зубам. Возможно я ошибаюсь...
Если... если учесть всю эту фигню для большинства складов то система увеличит расходы по хранению на 10-20%

Я видел несколько систем... они как раз страдают от учета лишнего и не учета присущего конкретному бизнесу деталей...Лично я не видел WMS систему, которая в общем случае может сократить расходы. Вопреки распространенным мнениям и утверждениям, она практически всегда увеличивает прямые расходы на хранение. Парадокс. Но за это увеличение дает дополнительные преимущества. :)

Интересно, что именно Вы хотите получить?
Алгоритм расчета "в лоб" именно минимальной длины обхода Вам уже подсказали. Правда, количество осмысленных вариантов маршрута на реальных складах немного меньше, чем N в сепени K, топология ограничивает, нельзя, к примеру, подойти от одного стеллажа к другому напрямую. Так же предложили осмысленные варианты маршрутов (или их отрезков) составлять экспертно.
Т.е в любом случае получаем граф, в узлах которого лежат товары. Считаем длины путей графа и выбираем наименьший.
Как по другому?

Читаем только то, что хотим увидеть? Или решаем абстрактную учебную задачу?

1. Марштуты отбора на складе ограничены топологией. Могут задаваться экспертно. (Администратор определяет, в какой последовательности имеет смысл обходить каналы хранения). Или у вас склад - это цирковая арена с расставленными по кругу ячейками хранения?
2. Кратчайший путь имеет смысл искать только среди определенных экспертом-администраторам маршрутов (иначе перебор N^M вариантов)
3. Опыт (мой) показывает, что маршрут в зоне отбора штучного товара всего ОДИН (так происходит по причине многих факторов). Более того, мое мнение, если маршрутов несколько, то значит что-то неправильно в топологии склада или размещении товара.

beginner20004Товар не штучный. Склад ответственного хранения. Сбор коробок с поддономест на поддон. Возможно, мне надо было написать не ячейки, а поддоны в первом сообщении, тогда было бы яснее.
Длинные стеллажи с поддонами выставлены во много рядов, не в один.Да какая разница?! :) С т.з. системы отгружаемая коробка - это штука (или юнит, или миним. единица хранения], так ведь?
Чувствуется, что Вы в самом начале длинного и тернистого пути.

Неужели организованы проходы между ВСЕМИ поддонами, с которых собирают на транспортный паллет и переход из ряда в ряд свободен? И пикеры-отборщики не мешают друг-другу, если идут навстречу друг-другу при отборе? И они не мешают удалению пустых поддонов и установке полных из зоны долговременного хранения? :)

[quot LSVГораздо проще оптимизировать его организационную составляющую.
Дать кладовщику план склада с отмеченными точками подбора и грамотным листом подбора. Он сам найдёт оптимальный путь исходя из огромного числа вышеописанных пунктов...[/quot]Много минусов, например, высокая квалификация (читай стоимость) грамотного отборщика. Система, которая НЕ ЗНАЕТ, в какой последовательности отбирать заказ - это не складская система. Максимум - учетная. :)
Насчет "проще оптимизировать организационную составляющую" - на складе эта составляющая как раз сложнее всего поддается оптимизации! :)

iscrafmМаршрут в этой последовательности только одна из составляющих и не всегда главная. Оптимизируют размещение, а не маршрут обхода при каждой отгрузке, т.е. думать нужно немного ранее. При отгрузке долго размышлять просто некогда зачастую. Задача конечно интересная, но не нужная. Достаточно печатать задания на подбор и выдавать их бригадам.Без всякого сомнения размещение влияет на маршрут. Тем не менее, оптимизация именно отбора, и как часть этого процесса - обхода, имеет место быть! Как он сам отметил, у человека есть задача - оптимизировать обход при отборе! Вот и помогите с алгоритмом, если можете. Никто ничего кроме выбора из экспертных маршрутов до сих пор не предложил.

Была задача.
Отбор с помошью высотной техники с высотных же стеллажей 9 ярусов. Необходимо формировать маршрут обхода в 3Д, чтобы штабелер не гонять вверх-вниз без толку. :)

iscrafm casmithКак он сам отметил, у человека есть задача - оптимизировать обход при отборе! Вот и помогите с алгоритмом, если можете.

casmithБыла задача.
Отбор с помошью высотной техники с высотных же стеллажей 9 ярусов. Необходимо формировать маршрут обхода в 3Д, чтобы штабелер не гонять вверх-вниз без толку. :)
И как, используется?Насколько мне известно - давным-давно НЕТ. Система не пошла в пром. эксплуатацию.

beginner20004>Я имел в виду разницу между розничной сборкой маленьких упаковок и оптовой сборкой, когда отгружаются поддоны и короба.
Тем не менее разница практически только в действиях человека. А с т.з. системы какая разница?
beginner20004
Что значит проходы между всеми, не понятно. Привожу схему склада. Черные прямоугольники - это стеллажи поддонов.
Разойтись грузчики смогут, если встретятся. Удалению поддонов и установке не мешают.
> Маршрут всегда 1 (один) и количество маршрутов по складу ограничено!!!
Что значит маршрут один? Что-то типа конвейера имеете в виду? Случай не тот.

Картинку не вижу, нет ее.
Если бы поддоны стояли отдельно и особняком, и к каждому был бы свободный доступ человеку с рохлой, то задача наикратчайшего пути была бы в переборе n^m вариантов. А если есть структура (граф топологии), например, зашел в один ряд, пока не пройдешь его, переходить в другой не имеет смысла, то количество вариантов резко сокращается. Не так ли? А осмысленных вариантов вообще раз, два и обчелся! Об этом Вам и пытаются сказать. И эти осмысленные варианты обхода по всем ячейкам легче построить человеку, а компьютеру просто выбирать из этих вариантов соответствующий текущему требованию.
Хотя на мой взгляд и из моего опыта и это излишне сложно.
beginner20004
> iscrafm
> Так помог же :)
Чем это, интересно?
Грузчик не должен, думать, за него это должна делать программа и давать ему указания куда пойти и что взять.Истину глаголите! :) Но я вообще сторонник подхода, когда программа просто говорит КУДА пойти и СКОЛЬКО взять.

beginner20004 casmith[quot beginner20004]>Разные схемы работы могут быть. То ли розничные пополняемые ячейки, которые по кругу обходятся непрерывным потоком, как конвейер, то ли забирать прямо с мест хранения.
Вот и я о том же, разница только в действиях человека. А для системы в чем разница?
beginner20004
Стоят рядами. Доступ есть к каждому. Двое смогут разминутся. Вообще немного человек одновременно собирают, поэтому можно пренебречь тем, что они не разойдутся.
Пусть я буду считать весь ряд одной вершиной графа. Все равно их будет 30 - слишком много для прямого перебора:-(
Прикрепляю картинку еще раз. перечислите пожалуйста это малое множество для данной схемы. на мой взгляд, там можно ходить практически как угодно.
На мой взгляд маршрут один - змейка - от начала вверх, направо, вниз направо и т.д. Неудобство, что проходов нечетное кол-во, к конечной точке придется возвращаться "в холостую". Да Вы попробуйте сами поставте точки и посмотрите длину пути. :) Отсортировать каналы с товарами в "змеиную" последовательность не сложно. И на первый взгляд путь короче не найти. :)
beginner20004
[quot casmith]
Истину глаголите! :) Но я вообще сторонник подхода, когда программа просто говорит КУДА пойти и СКОЛЬКО взять.
Я тоже. Не собираюсь ему схему марштрута чертить. Просто список мест и товара в порядке очереди. :) А я немного о другом...

beginner20004Человеку надо взять 5 коробок из 3-го места в первом ряду и 8 из 5 во втором и он должен обходить все змейкой? Это же полная ерунда получаетсяТяжело с Вами...
У Вас есть 2 места отбора: (ряд1место3) и (ряд2место5).
КАК Вы сможете заставить его пройти всю змейку? Вам нужно просто дать сортированный список мест - то-есть маршрут. :)
Итого, в маршруте будет:
1) (ряд1место3) взять 5 кор.
2) (ряд2место5) взять 8 кор.

ВСЕ.