Сейчас разрабатываем CRМ, который связан с логистикой.
Следовательно тут всплывают задачи комбинаторной оптимизации, в частности вариации задачи коммивояжера. Также в проекте присутствуют оптимизации еффективного заполнения складов как по используемому пространству в заданный момент времени (задача о рюкзаке), так и планирования расписания заполнения складов по времени.
Однако сейчас стоит такая проблема, никто из разработчиков в тонкостях не разрибается в решении оптимизационных задач, а нужна высокая эффективность для проекта!
Может быть кто-то знает есть ли какие-то готовые компоненты для решения подобных задач? Либо можно аутсорсить такой компонент, где были бы реализованы только математические алгоритмы и предоставлен интерфейс для взаимодействия с ними?
Никто не имеет подобного опыта?
Здравствуйте, Sidus, Вы писали:
S>Сейчас разрабатываем CRМ, который связан с логистикой. S>Следовательно тут всплывают задачи комбинаторной оптимизации, в частности вариации задачи коммивояжера. Также в проекте присутствуют оптимизации еффективного заполнения складов как по используемому пространству в заданный момент времени (задача о рюкзаке), так и планирования расписания заполнения складов по времени.
S>Однако сейчас стоит такая проблема, никто из разработчиков в тонкостях не разрибается в решении оптимизационных задач, а нужна высокая эффективность для проекта!
S>Может быть кто-то знает есть ли какие-то готовые компоненты для решения подобных задач? Либо можно аутсорсить такой компонент, где были бы реализованы только математические алгоритмы и предоставлен интерфейс для взаимодействия с ними? S>Никто не имеет подобного опыта?
S>Может быть кто-то знает есть ли какие-то готовые компоненты для решения подобных задач? Либо можно аутсорсить такой компонент, где были бы реализованы только математические алгоритмы и предоставлен интерфейс для взаимодействия с ними?
Здравствуйте, Sidus, Вы писали:
S>Вот порылся в сетях нашел компонент, который в принципе решает подобные задачи. S>http://www.divosoft.com/Products/Eol/Combinatory/Overview.aspx?lang=RU
S>Компонент специфический насколько я понял — только мат-алгоритмы, при этом у них можно купить и готовое решение для конкретной задачи. S>Может кто знаком с ним?
Работать не приходилось. Но вроде как там есть Getting Started лицензия — попробуй посмотреть.
ЗЫ
Немного настораживает раздел "Тестирование", а вернее отсутствие каких-либо результатов тестирования
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, Sidus, Вы писали:
S>>Вот порылся в сетях нашел компонент, который в принципе решает подобные задачи. S>>http://www.divosoft.com/Products/Eol/Combinatory/Overview.aspx?lang=RU
S>>Компонент специфический насколько я понял — только мат-алгоритмы, при этом у них можно купить и готовое решение для конкретной задачи. S>>Может кто знаком с ним?
B>Работать не приходилось. Но вроде как там есть Getting Started лицензия — попробуй посмотреть.
B>ЗЫ B>Немного настораживает раздел "Тестирование", а вернее отсутствие каких-либо результатов тестирования
хорошо бы такой раздел дать, раз написали что реализованы самые лучшие алгоритмы )))
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, Bell, Вы писали:
B>>Здравствуйте, Sidus, Вы писали:
S>>>Вот порылся в сетях нашел компонент, который в принципе решает подобные задачи. S>>>http://www.divosoft.com/Products/Eol/Combinatory/Overview.aspx?lang=RU
S>>>Компонент специфический насколько я понял — только мат-алгоритмы, при этом у них можно купить и готовое решение для конкретной задачи. S>>>Может кто знаком с ним?
B>>Работать не приходилось. Но вроде как там есть Getting Started лицензия — попробуй посмотреть.
B>>ЗЫ B>>Немного настораживает раздел "Тестирование", а вернее отсутствие каких-либо результатов тестирования
I>хорошо бы такой раздел дать, раз написали что реализованы самые лучшие алгоритмы )))
Написал им.
Ответили такой раздел будет, просто компонент только недавно зарелизили я так понял.
Здравствуйте, Sidus, Вы писали:
I>>хорошо бы такой раздел дать, раз написали что реализованы самые лучшие алгоритмы )))
S>Написал им. S>Ответили такой раздел будет, просто компонент только недавно зарелизили я так понял.
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, Sidus, Вы писали:
I>>>хорошо бы такой раздел дать, раз написали что реализованы самые лучшие алгоритмы )))
S>>Написал им. S>>Ответили такой раздел будет, просто компонент только недавно зарелизили я так понял.
B>А выслать не могут?
Выслали — сижу раздупляю
Правда бесплатно только фреймворк, а для того, довести до решения конкретной задачи нужно писать свои адаптирующие классы либо заказать у них эти классы.
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, Sidus, Вы писали:
S>>Написал им. S>>Ответили такой раздел будет, просто компонент только недавно зарелизили я так понял.
B>Да, посмотри еще здесь B>Там хоть результаты тестов есть
Глянул бегло — это медот ветвей и границ у них реализован? Насколько я понимаю он далеко не самый быстрый.
Надо разобраться подетальнее. Кто юзал его уже?
Здравствуйте, Sidus, Вы писали:
B>>Да, посмотри еще здесь B>>Там хоть результаты тестов есть S>Глянул бегло — это медот ветвей и границ у них реализован? Насколько я понимаю он далеко не самый быстрый.
Это беда всех точных методов S>Надо разобраться подетальнее. Кто юзал его уже?
Нет, не приходилось.
В свое время пробовали для решения VRP использовать ILOG Dispatcher, но пришлось отказаться — медленно, и далеко не всегда удается сделать именно то, что нужно — уж больно много специфики в реальных задачах...
Так что пришлось разработать свой солвер.
Насчет результатов тестов, которые тебе выслали: можешь мне выслать? Если это позволительно конечно. В частности интересует VRP и TSP
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, Sidus, Вы писали:
B>>>Да, посмотри еще здесь B>>>Там хоть результаты тестов есть S>>Глянул бегло — это медот ветвей и границ у них реализован? Насколько я понимаю он далеко не самый быстрый. B>Это беда всех точных методов
Да уж..согласен.
S>>Надо разобраться подетальнее. Кто юзал его уже? B>Нет, не приходилось. B>В свое время пробовали для решения VRP использовать ILOG Dispatcher, но пришлось отказаться — медленно, и далеко не всегда удается сделать именно то, что нужно — уж больно много специфики в реальных задачах... B>Так что пришлось разработать свой солвер.
Столько времени терять на изучение мне не позволительно. Я в оптимизации не спец, да и уверен, что таких спецов не так уж и много, поэтому мне выгоднее что-то готовое и работающее.
B>Насчет результатов тестов, которые тебе выслали: можешь мне выслать? Если это позволительно конечно. В частности интересует VRP и TSP
Выслали они сам фреймворк, а тесты уже на сайте есть тут.
Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?
Здравствуйте, Sidus, Вы писали:
S>Столько времени терять на изучение мне не позволительно. Я в оптимизации не спец, да и уверен, что таких спецов не так уж и много, поэтому мне выгоднее что-то готовое и работающее.
ИМХО это проще сказать, чем найти Уж слишком много специфики.
S>Выслали они сам фреймворк, а тесты уже на сайте есть тут. S>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?
Это не результаты тестов — это набор ни о чем не говорящих графиков.
Есть общепризнанные тестовые задачи, которые используются для оценки качества алгоритмов.
Например для VRP: http://web.cba.neu.edu/~msolomon/
Для TSP: http://www.tsp.gatech.edu/data/index.html
Для задач упаковки тоже наверняка есть что-то подобное.
ЗЫ
Можешь предоставить данные для своей TSP? Мне интересно попробовать свой солвер.
Здравствуйте, ilnar, Вы писали:
B>>ЗЫ B>>Можешь предоставить данные для своей TSP? Мне интересно попробовать свой солвер.
I>а что, решают TSP? I>хочу тоже свой солвер опробывать на ваших данных. у меня точный алгоритм, вдруг эти данные для нее будут кстати.
Эээ... к кому вопрос?
Любите книгу — источник знаний (с) М.Горький
Re[10]: Решение задач комбинаторной оптимизации
От:
Аноним
Дата:
23.08.07 18:52
Оценка:
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, Sidus, Вы писали:
S>>Столько времени терять на изучение мне не позволительно. Я в оптимизации не спец, да и уверен, что таких спецов не так уж и много, поэтому мне выгоднее что-то готовое и работающее. B>ИМХО это проще сказать, чем найти Уж слишком много специфики.
S>>Выслали они сам фреймворк, а тесты уже на сайте есть тут. S>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов? B>Это не результаты тестов — это набор ни о чем не говорящих графиков. B>Есть общепризнанные тестовые задачи, которые используются для оценки качества алгоритмов. B>Например для VRP: http://web.cba.neu.edu/~msolomon/ B>Для TSP: http://www.tsp.gatech.edu/data/index.html B>Для задач упаковки тоже наверняка есть что-то подобное.
B>ЗЫ B>Можешь предоставить данные для своей TSP? Мне интересно попробовать свой солвер.
Народ а не подскажите vrptw -шечки по 50-70 пунктов, где можно достать?
Я разработал метод для их точного решения (в т.ч. CVRP), сейчас пока програмлю, но предварительные результаты впечатляют, быстрая нижняя граница — ~97%, это без дополнительных модификаций
А>Народ а не подскажите vrptw -шечки по 50-70 пунктов, где можно достать? А>Я разработал метод для их точного решения (в т.ч. CVRP), сейчас пока програмлю, но предварительные результаты впечатляют, быстрая нижняя граница — ~97%, это без дополнительных модификаций
не заню даже. а ты cvrp уже пробовал? и большие тоже? какие результаты по времени?
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, ilnar, Вы писали:
B>>>ЗЫ B>>>Можешь предоставить данные для своей TSP? Мне интересно попробовать свой солвер.
I>>а что, решают TSP? I>>хочу тоже свой солвер опробывать на ваших данных. у меня точный алгоритм, вдруг эти данные для нее будут кстати.
B>Эээ... к кому вопрос?
в основном топикстартеру. Можете и вы, интересны задачи из практики (можно [a]tsp, cvrp)
Здравствуйте, Аноним, Вы писали:
А>Народ а не подскажите vrptw -шечки по 50-70 пунктов, где можно достать?
По ссылке, которую я привел, лежат как раз VRPTW. Там же есть результаты решений.
Вообще там сотки, но результаты есть для первых 25, 50, 75.
Имей ввиду способ вычисление расстояний/времен: для оптимальных результатов использовалась такая схема: вычислить евклидово расстояние, отбросить все знаки со второго после запятой, т.е. 10,19 -> 10,1.
Источник вот эта книжица: здесь
К сожалениею не все придерживались такой схемы, поэтому на результаты нужно смотреть осторожно. Еще плохо то, что не приводятся полученные туры...
А>Я разработал метод для их точного решения (в т.ч. CVRP), сейчас пока програмлю, но предварительные результаты впечатляют, быстрая нижняя граница — ~97%, это без дополнительных модификаций
Ну доделывай и выкладывай новые оптимальные решения
...
S>Выслали они сам фреймворк, а тесты уже на сайте есть тут. S>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?
мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального
