помогите, может быть кто сталкивался:
есть большой склад (1000000 адресов)
на каждом адресе может лежать несколько разных серий лек. препаратов
есть накладная, которую надо собрать, состоит из строк: серия, количество
задача: как построить оптамильный (самый короткий) маршрут сборщика, при котором вся накладная будет собрана
Здравствуйте, aaalex, Вы писали:
A>помогите, может быть кто сталкивался: A>есть большой склад (1000000 адресов) A>на каждом адресе может лежать несколько разных серий лек. препаратов A>есть накладная, которую надо собрать, состоит из строк: серия, количество A>задача: как построить оптамильный (самый короткий) маршрут сборщика, при котором вся накладная будет собрана
короткий в каком смысле? растояния заданы? какие свойства у растояний, адресов?
решается как коммивояжер, сначало составляешь задачу коммивояжера по накладной
к тому же если нельзя собрать за один проход, то уже задача VRP
Здравствуйте, ilnar, Вы писали:
I>короткий в каком смысле? растояния заданы? какие свойства у растояний, адресов? I>решается как коммивояжер, сначало составляешь задачу коммивояжера по накладной I>к тому же если нельзя собрать за один проход, то уже задача VRP
топология склада не прямолинейна, несколько рядов стелажей, ну типа такого:
| | | |
| | | |
| | | |
| | | |
каждую "палочку" мыслим непрерывным стеллажом, около 7 метров
каждый стеллаж можно обойти вокруг
расстояния м/у адресами заданы
насколько я помню, в задаче коммивояжера надо обойти ВСЕ вершины графа
здесь же в каждой вершине(адресе) могут быть разные серии по нескольку штук
задача в том, чтобы НАСОБИРАТЬ НУЖНЫЕ КОЛИЧЕСТВА, пройдя наименьший путь из заданной наперед вершины.
Первое упрощение, на мой взгляд, в том чтобы выбрать подграф из тех вершин, в которых лежат нужные серии, их окажется штук 100 например
потом можно было бы решить что-то вроде "задачи о рюкзаке", но только в "векторной" постановке, если такая есть.
А потом для всех решений "задачи о рюкзаке" решить задачу коммивояжера и выбрать самое лучшее решение (наиболее короткий путь)
Здравствуйте, aaalex, Вы писали:
A>Здравствуйте, ilnar, Вы писали:
I>>короткий в каком смысле? растояния заданы? какие свойства у растояний, адресов? I>>решается как коммивояжер, сначало составляешь задачу коммивояжера по накладной I>>к тому же если нельзя собрать за один проход, то уже задача VRP
A>топология склада не прямолинейна, несколько рядов стелажей, ну типа такого: A>| | | | A>| | | | A>| | | | A>| | | | A>каждую "палочку" мыслим непрерывным стеллажом, около 7 метров A>каждый стеллаж можно обойти вокруг A>расстояния м/у адресами заданы
A>насколько я помню, в задаче коммивояжера надо обойти ВСЕ вершины графа
в графовой постановке — да, есть матричная постановка, нужно построить цикл наименьшей стоимости, задана матрица стоимостей
A>здесь же в каждой вершине(адресе) могут быть разные серии по нескольку штук
серии по одному адресу объединяются в один пункт, и соответственно объем пункта
A>задача в том, чтобы НАСОБИРАТЬ НУЖНЫЕ КОЛИЧЕСТВА, пройдя наименьший путь из заданной наперед вершины.
а почему ее задавать? все равно у кассы начинаешь, там и заканчиваешь, не так?
если надо фиксировать начальный и конечный пункты — просто вводится фиктивный пункт, от которого в начальный и конечные пункты нулевая стоимость, во все остальные — бесконечные
A>Первое упрощение, на мой взгляд, в том чтобы выбрать подграф из тех вершин, в которых лежат нужные серии, их окажется штук 100 например
так и есть, подграф строится по накладной
A>потом можно было бы решить что-то вроде "задачи о рюкзаке", но только в "векторной" постановке, если такая есть.
а зачем задача о рюкзаке? если считаешь что нельзя за один обход все взять, то получается задача VRP
A>А потом для всех решений "задачи о рюкзаке" решить задачу коммивояжера и выбрать самое лучшее решение (наиболее короткий путь)
ваш вариант можно рассмотреть как путь к упрощению задачи — эвристический алгоритм, не гарантирует точности, однако упрощает жизнь
точный метод для коммивояжера (алгоритм Литла) решает, например у меня, до 65 пунктов в хороших случаях за час
хотя если длину мерить в метрах, то сравнительно малый разбег может помощь побыстрее решать
для VRP год назад получал такие результаты — решал точно до 25 пунктов при 3-х подмаршрутах, 20 при 4-х, хотя с тех пор примененный метод улучшился — тогда решал 45 пунктов при 1 маршруте (все равно что задача коммивояжера)
повторно отмечу — это просто мои тестовые результаты при точном решении, результаты сильно отличаются в зависимости от входных данных, при специальных данных решается даже 1000 пунктов за пару минут
Здравствуйте, ilnar, Вы писали:
I>в графовой постановке — да, есть матричная постановка, нужно построить цикл наименьшей стоимости, задана матрица стоимостей I>серии по одному адресу объединяются в один пункт, и соответственно объем пункта
мне не сомсем ясно! есть вектор количеств серий (x1,x2,x3,...), которые надо насобирать
и есть в каждой вершине вектор наличия (v11,v12,v13,...), (v21,v22,v23,...), ...
надо найти такой маршрут, чтобы ( Сумма(vi1) по i ) <= x1, ( Сумма(vi2) по i ) <= x2, ...
при этом его длина должна быть минимальной
что значит "объем пункта"?
I>а почему ее задавать? все равно у кассы начинаешь, там и заканчиваешь, не так? I>если надо фиксировать начальный и конечный пункты — просто вводится фиктивный пункт, от которого в начальный и конечные пункты нулевая стоимость, во все остальные — бесконечные
ну, касса и будет заданной вершиной
I>а зачем задача о рюкзаке? если считаешь что нельзя за один обход все взять, то получается задача VRP
здесь поподробнее, я не пойму, что значит "за один обход" и что такое VRP, то же не знаю
I>точный метод для коммивояжера (алгоритм Литла) решает, например у меня, до 65 пунктов в хороших случаях за час I>хотя если длину мерить в метрах, то сравнительно малый разбег может помощь побыстрее решать I>для VRP год назад получал такие результаты — решал точно до 25 пунктов при 3-х подмаршрутах, 20 при 4-х, хотя с тех пор примененный метод улучшился — тогда решал 45 пунктов при 1 маршруте (все равно что задача коммивояжера) I>повторно отмечу — это просто мои тестовые результаты при точном решении, результаты сильно отличаются в зависимости от входных данных, при специальных данных решается даже 1000 пунктов за пару минут
что-то это меня пугает считать должно во время проведения накладной, чтобы оператор осбо не ходил покурить
секунд за 10 хотя бы
Здравствуйте, aaalex, Вы писали:
A>Здравствуйте, ilnar, Вы писали:
I>>в графовой постановке — да, есть матричная постановка, нужно построить цикл наименьшей стоимости, задана матрица стоимостей I>>серии по одному адресу объединяются в один пункт, и соответственно объем пункта A>мне не сомсем ясно! есть вектор количеств серий (x1,x2,x3,...), которые надо насобирать A>и есть в каждой вершине вектор наличия (v11,v12,v13,...), (v21,v22,v23,...), ... A>надо найти такой маршрут, чтобы ( Сумма(vi1) по i ) <= x1, ( Сумма(vi2) по i ) <= x2, ... A>при этом его длина должна быть минимальной A>что значит "объем пункта"?
теперь я не понял. один товар есть в нескольких вершинах?
выделяешь адреса, в которых нужно взять хотя бы одну серию
а объем для адреса — это количество забираемого из адреса (если есть разные серии, суммируем)
I>>а почему ее задавать? все равно у кассы начинаешь, там и заканчиваешь, не так? I>>если надо фиксировать начальный и конечный пункты — просто вводится фиктивный пункт, от которого в начальный и конечные пункты нулевая стоимость, во все остальные — бесконечные A>ну, касса и будет заданной вершиной
тогда не заморачивайся, решение — цикличный маршрут обхода, в качестве одного из пунктов берешь кассу
I>>а зачем задача о рюкзаке? если считаешь что нельзя за один обход все взять, то получается задача VRP A>здесь поподробнее, я не пойму, что значит "за один обход" и что такое VRP, то же не знаю
есть у тебя корзина, в него размещается определенный объем, набрал, вернулся в кассу, отправился добирать. если объем в пункте меньше вместимости корзины — забираешь за один раз все, устраивание "салата", когда в нескольких походах есть одно изделие, не оптимально
VRP — усложнение задачи коммивояжера, когда все пункты обходить надо не за один циклический маршрут, а в несколько. вводится так называемая база, который присутствует в каждом цикле. суммарный объем цикла ограничивается сверху "вместимостью" (или количеством пунктов, или открытыми на данный момент пунктами — VRP с временными окнами, когда можно войти в пункт и выйти из пункта)
I>>точный метод для коммивояжера (алгоритм Литла) решает, например у меня, до 65 пунктов в хороших случаях за час I>>хотя если длину мерить в метрах, то сравнительно малый разбег может помощь побыстрее решать I>>для VRP год назад получал такие результаты — решал точно до 25 пунктов при 3-х подмаршрутах, 20 при 4-х, хотя с тех пор примененный метод улучшился — тогда решал 45 пунктов при 1 маршруте (все равно что задача коммивояжера) I>>повторно отмечу — это просто мои тестовые результаты при точном решении, результаты сильно отличаются в зависимости от входных данных, при специальных данных решается даже 1000 пунктов за пару минут A>что-то это меня пугает считать должно во время проведения накладной, чтобы оператор осбо не ходил покурить A>секунд за 10 хотя бы
тогда сразу хватаемся за эвристические методы! иначе никак, это экспоненциальные задачи
для коммивояжера методов эвристических куча — жадный алгоритм (greedy), 2-opt, 2,5-opt, 3-opt, ....
VRP — алгоритм Кларка-Райта, ...
I>теперь я не понял. один товар есть в нескольких вершинах?
да, а одной вершине может быть несколько товаров I>выделяешь адреса, в которых нужно взять хотя бы одну серию
я могу выделить вершину, в которой МОЖНО взять хотя бы одну серию, а надо или нет — это как раз и стоит определить I>а объем для адреса — это количество забираемого из адреса (если есть разные серии, суммируем)
не ясно, зачем суммировать количества разных серий?
I>есть у тебя корзина, в него размещается определенный объем, набрал, вернулся в кассу, отправился добирать. если объем в пункте меньше вместимости корзины — забираешь за один раз все, устраивание "салата", когда в нескольких походах есть одно изделие, не оптимально I>VRP — усложнение задачи коммивояжера, когда все пункты обходить надо не за один циклический маршрут, а в несколько. вводится так называемая база, который присутствует в каждом цикле. суммарный объем цикла ограничивается сверху "вместимостью" (или количеством пунктов, или открытыми на данный момент пунктами — VRP с временными окнами, когда можно войти в пункт и выйти из пункта)
понял, пока считаем, что корзина не ограничена (как правило, одна накладная = один ящик среднего размера)
хотя я о такой постановке еще не задумывался, возможно, может возникнуть и такой случай, что за один раз не утащиить
I>тогда сразу хватаемся за эвристические методы! иначе никак, это экспоненциальные задачи I>для коммивояжера методов эвристических куча — жадный алгоритм (greedy), 2-opt, 2,5-opt, 3-opt, .... I>VRP — алгоритм Кларка-Райта, ...
спасибо, попробуем
Здравствуйте, aaalex, Вы писали:
A>Здравствуйте, ilnar, Вы писали:
I>>теперь я не понял. один товар есть в нескольких вершинах? A>да, а одной вершине может быть несколько товаров
значит один товар в есть в нескольких адресах, ммм, как бы выбрать нужный??? подумать нада — как вариант динамическая задача коммивояжера, если зашел в один пункт, другой пропадет
I>>выделяешь адреса, в которых нужно взять хотя бы одну серию A>я могу выделить вершину, в которой МОЖНО взять хотя бы одну серию, а надо или нет — это как раз и стоит определить
выбери для начала тот адрес, в котором достаточно и в котором меньше всего
или минимизировать сначало кол-во пунктов, с которых можно набрать всю накладную
все равно где-то надо от оптимальности уйти, слишком сложную задачу иначе получишь
I>>а объем для адреса — это количество забираемого из адреса (если есть разные серии, суммируем) A>не ясно, зачем суммировать количества разных серий?
надо если придется в несколько раз набирать
все же сначала составь модель: что и как сводится к задачи коммивояжера, адреса, серии, накладная...
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, aaalex, Вы писали:
A>>ну, не строгая модель выглядит так A>>
I>в 2) слово крайтчайшее не надо I>сейчас более понятно, позже попробую подумать над решением
Здравствуйте, aaalex, Вы писали:
A>Здравствуйте, ilnar, Вы писали:
I>>Здравствуйте, aaalex, Вы писали:
A>>>ну, не строгая модель выглядит так A>>>
I>>в 2) слово крайтчайшее не надо I>>сейчас более понятно, позже попробую подумать над решением
A>спасибо, жду
на чем текст писал? ворд или тех? если второе, пришли кусок?
Здравствуйте, aaalex, Вы писали:
A>Здравствуйте, ilnar, Вы писали: I>>на чем текст писал? ворд или тех? если второе, пришли кусок? A>в ворде, вот на всякий случай, тут Документ ворд
обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой"
говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании
сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, ....
т.е. максимально упрощать задачу эвристическими идеями
Re[14]: оптимальный маршрут по складу
От:
Аноним
Дата:
19.01.06 09:16
Оценка:
Здравствуйте, ilnar, Вы писали:
I>обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой" I>говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании I>сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, .... I>т.е. максимально упрощать задачу эвристическими идеями
интересено, довольно прикольный подход!
а где бы познакомиться с этими идеями поближе?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, ilnar, Вы писали:
I>>обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой" I>>говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании I>>сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, .... I>>т.е. максимально упрощать задачу эвристическими идеями А>интересено, довольно прикольный подход! А>а где бы познакомиться с этими идеями поближе?
ну, есть варианты:
1. поступить к нам учится
2. попробую найти тетрадку и неспешно отсканирую — результат врачебный почерк
3. как в 2, олько главные идеи выпишу
4. у руководителя найдутся что-то с этими идеями, бумажки, электронка
эти идеи — разработка нашей кафедры для каких-то производств еще в советское время, внедренное
I>>обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой" I>>говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании I>>сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, .... I>>т.е. максимально упрощать задачу эвристическими идеями А>интересено, довольно прикольный подход! А>а где бы познакомиться с этими идеями поближе?
действительно интересно
Здравствуйте, ilnar, Вы писали:
I>ну, есть варианты: I>1. поступить к нам учится
для начала: куда конкретно? I>2. попробую найти тетрадку и неспешно отсканирую — результат врачебный почерк I>3. как в 2, олько главные идеи выпишу
буду признателен, если смогу разобрать I>4. у руководителя найдутся что-то с этими идеями, бумажки, электронка I>эти идеи — разработка нашей кафедры для каких-то производств еще в советское время, внедренное
а вот это самое оно! буду ОЧЕНЬ признателен
Здравствуйте, aaalex, Вы писали:
A>Здравствуйте, ilnar, Вы писали:
I>>ну, есть варианты: I>>1. поступить к нам учится A> для начала: куда конкретно?
КГУ, ВМК, экономическая кибернетика