оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 08:15
Оценка:
помогите, может быть кто сталкивался:
есть большой склад (1000000 адресов)
на каждом адресе может лежать несколько разных серий лек. препаратов
есть накладная, которую надо собрать, состоит из строк: серия, количество
задача: как построить оптамильный (самый короткий) маршрут сборщика, при котором вся накладная будет собрана
Re: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 18.01.06 08:21
Оценка:
Здравствуйте, aaalex, Вы писали:

A>помогите, может быть кто сталкивался:

A>есть большой склад (1000000 адресов)
A>на каждом адресе может лежать несколько разных серий лек. препаратов
A>есть накладная, которую надо собрать, состоит из строк: серия, количество
A>задача: как построить оптамильный (самый короткий) маршрут сборщика, при котором вся накладная будет собрана

короткий в каком смысле? растояния заданы? какие свойства у растояний, адресов?
решается как коммивояжер, сначало составляешь задачу коммивояжера по накладной
к тому же если нельзя собрать за один проход, то уже задача VRP
Re[2]: оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 08:46
Оценка:
Здравствуйте, ilnar, Вы писали:

I>короткий в каком смысле? растояния заданы? какие свойства у растояний, адресов?

I>решается как коммивояжер, сначало составляешь задачу коммивояжера по накладной
I>к тому же если нельзя собрать за один проход, то уже задача VRP

топология склада не прямолинейна, несколько рядов стелажей, ну типа такого:
| | | |
| | | |
| | | |
| | | |
каждую "палочку" мыслим непрерывным стеллажом, около 7 метров
каждый стеллаж можно обойти вокруг
расстояния м/у адресами заданы

насколько я помню, в задаче коммивояжера надо обойти ВСЕ вершины графа
здесь же в каждой вершине(адресе) могут быть разные серии по нескольку штук
задача в том, чтобы НАСОБИРАТЬ НУЖНЫЕ КОЛИЧЕСТВА, пройдя наименьший путь из заданной наперед вершины.
Первое упрощение, на мой взгляд, в том чтобы выбрать подграф из тех вершин, в которых лежат нужные серии, их окажется штук 100 например
потом можно было бы решить что-то вроде "задачи о рюкзаке", но только в "векторной" постановке, если такая есть.
А потом для всех решений "задачи о рюкзаке" решить задачу коммивояжера и выбрать самое лучшее решение (наиболее короткий путь)
Re[3]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 18.01.06 09:09
Оценка:
Здравствуйте, 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 пунктов за пару минут
Re[4]: оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 09:24
Оценка:
Здравствуйте, 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 хотя бы
Re[5]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 18.01.06 09:49
Оценка:
Здравствуйте, 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 — алгоритм Кларка-Райта, ...
Re[6]: оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 11:24
Оценка:
Здравствуйте, ilnar, Вы писали:


I>теперь я не понял. один товар есть в нескольких вершинах?

да, а одной вершине может быть несколько товаров
I>выделяешь адреса, в которых нужно взять хотя бы одну серию
я могу выделить вершину, в которой МОЖНО взять хотя бы одну серию, а надо или нет — это как раз и стоит определить
I>а объем для адреса — это количество забираемого из адреса (если есть разные серии, суммируем)
не ясно, зачем суммировать количества разных серий?

I>есть у тебя корзина, в него размещается определенный объем, набрал, вернулся в кассу, отправился добирать. если объем в пункте меньше вместимости корзины — забираешь за один раз все, устраивание "салата", когда в нескольких походах есть одно изделие, не оптимально

I>VRP — усложнение задачи коммивояжера, когда все пункты обходить надо не за один циклический маршрут, а в несколько. вводится так называемая база, который присутствует в каждом цикле. суммарный объем цикла ограничивается сверху "вместимостью" (или количеством пунктов, или открытыми на данный момент пунктами — VRP с временными окнами, когда можно войти в пункт и выйти из пункта)
понял, пока считаем, что корзина не ограничена (как правило, одна накладная = один ящик среднего размера)
хотя я о такой постановке еще не задумывался, возможно, может возникнуть и такой случай, что за один раз не утащиить

I>тогда сразу хватаемся за эвристические методы! иначе никак, это экспоненциальные задачи

I>для коммивояжера методов эвристических куча — жадный алгоритм (greedy), 2-opt, 2,5-opt, 3-opt, ....
I>VRP — алгоритм Кларка-Райта, ...
спасибо, попробуем
Re[7]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 18.01.06 11:39
Оценка:
Здравствуйте, aaalex, Вы писали:

A>Здравствуйте, ilnar, Вы писали:



I>>теперь я не понял. один товар есть в нескольких вершинах?

A>да, а одной вершине может быть несколько товаров
значит один товар в есть в нескольких адресах, ммм, как бы выбрать нужный??? подумать нада — как вариант динамическая задача коммивояжера, если зашел в один пункт, другой пропадет

I>>выделяешь адреса, в которых нужно взять хотя бы одну серию

A>я могу выделить вершину, в которой МОЖНО взять хотя бы одну серию, а надо или нет — это как раз и стоит определить
выбери для начала тот адрес, в котором достаточно и в котором меньше всего
или минимизировать сначало кол-во пунктов, с которых можно набрать всю накладную
все равно где-то надо от оптимальности уйти, слишком сложную задачу иначе получишь

I>>а объем для адреса — это количество забираемого из адреса (если есть разные серии, суммируем)

A>не ясно, зачем суммировать количества разных серий?
надо если придется в несколько раз набирать

все же сначала составь модель: что и как сводится к задачи коммивояжера, адреса, серии, накладная...
Re[8]: оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 12:37
Оценка:
ну, не строгая модель выглядит так
Re[9]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 18.01.06 12:42
Оценка:
Здравствуйте, aaalex, Вы писали:

A>ну, не строгая модель выглядит так

A>

в 2) слово крайтчайшее не надо
сейчас более понятно, позже попробую подумать над решением
Re[10]: оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 14:40
Оценка:
Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, aaalex, Вы писали:


A>>ну, не строгая модель выглядит так

A>>

I>в 2) слово крайтчайшее не надо

I>сейчас более понятно, позже попробую подумать над решением

спасибо, жду
Re[11]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 18.01.06 14:43
Оценка:
Здравствуйте, aaalex, Вы писали:

A>Здравствуйте, ilnar, Вы писали:


I>>Здравствуйте, aaalex, Вы писали:


A>>>ну, не строгая модель выглядит так

A>>>

I>>в 2) слово крайтчайшее не надо

I>>сейчас более понятно, позже попробую подумать над решением

A>спасибо, жду

на чем текст писал? ворд или тех? если второе, пришли кусок?
Re[12]: оптимальный маршрут по складу
От: aaalex  
Дата: 18.01.06 14:55
Оценка:
Здравствуйте, ilnar, Вы писали:
I>на чем текст писал? ворд или тех? если второе, пришли кусок?
в ворде, вот на всякий случай, тут Документ ворд
Re[12]: оптимальный маршрут по складу
От: Аноним  
Дата: 19.01.06 09:01
Оценка:
up
Re[13]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 19.01.06 09:12
Оценка:
Здравствуйте, aaalex, Вы писали:

A>Здравствуйте, ilnar, Вы писали:

I>>на чем текст писал? ворд или тех? если второе, пришли кусок?
A>в ворде, вот на всякий случай, тут Документ ворд

обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой"
говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании
сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, ....
т.е. максимально упрощать задачу эвристическими идеями
Re[14]: оптимальный маршрут по складу
От: Аноним  
Дата: 19.01.06 09:16
Оценка:
Здравствуйте, ilnar, Вы писали:

I>обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой"

I>говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании
I>сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, ....
I>т.е. максимально упрощать задачу эвристическими идеями
интересено, довольно прикольный подход!
а где бы познакомиться с этими идеями поближе?
Re[15]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 19.01.06 09:21
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, ilnar, Вы писали:


I>>обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой"

I>>говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании
I>>сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, ....
I>>т.е. максимально упрощать задачу эвристическими идеями
А>интересено, довольно прикольный подход!
А>а где бы познакомиться с этими идеями поближе?

ну, есть варианты:
1. поступить к нам учится
2. попробую найти тетрадку и неспешно отсканирую — результат врачебный почерк
3. как в 2, олько главные идеи выпишу
4. у руководителя найдутся что-то с этими идеями, бумажки, электронка
эти идеи — разработка нашей кафедры для каких-то производств еще в советское время, внедренное
Re[15]: оптимальный маршрут по складу
От: aaalex  
Дата: 19.01.06 09:22
Оценка:
I>>обсудил я с руководителем, который читает курс "управление гиперпроизводственной системой"
I>>говорит что задача стоит не только в составлении маршрута, но и в "правильном" складировании
I>>сейчас смутно вспоминаю этот курс со времен студенчества, но там есть определенные идеи насчет распределения товара по стеллажу в зависимости от частоты использования конкретных товаров, ....
I>>т.е. максимально упрощать задачу эвристическими идеями
А>интересено, довольно прикольный подход!
А>а где бы познакомиться с этими идеями поближе?
действительно интересно
Re[16]: оптимальный маршрут по складу
От: aaalex  
Дата: 19.01.06 09:49
Оценка:
Здравствуйте, ilnar, Вы писали:

I>ну, есть варианты:

I>1. поступить к нам учится
для начала: куда конкретно?
I>2. попробую найти тетрадку и неспешно отсканирую — результат врачебный почерк
I>3. как в 2, олько главные идеи выпишу
буду признателен, если смогу разобрать
I>4. у руководителя найдутся что-то с этими идеями, бумажки, электронка
I>эти идеи — разработка нашей кафедры для каких-то производств еще в советское время, внедренное
а вот это самое оно! буду ОЧЕНЬ признателен
Re[17]: оптимальный маршрут по складу
От: ilnar Россия  
Дата: 19.01.06 10:03
Оценка:
Здравствуйте, aaalex, Вы писали:

A>Здравствуйте, ilnar, Вы писали:


I>>ну, есть варианты:

I>>1. поступить к нам учится
A> для начала: куда конкретно?
КГУ, ВМК, экономическая кибернетика
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.