Игрушки для логиста

Опубликовал cdr (phsin) в раздел Обмен - Обмен с другими системами

Задача (Vehile Routing problem - VRP) была сформулирована более 40 лет назад и сейчас является одной из наиболее трудных и интересных комбинаторных задач. Она заключается в построении оптимальных маршрутов, чтобы удовлетворить условия поставки для некоторого количества покупателей.

Задачу можно сформулировать следующим образом: используя ограниченное количество машин, доставить товары покупателям. Учитывая, ограничения:

  • вместимость каждой машины
  • время доставки товара покупателю
  • количество точек доставки
  • время работы водителя

Оптимизировать пробег машин для экономии времени и топлива.

Предлагаем вашему вниманию программу Optaplanner для оптимизации маршрутов доставки.

OptaPlanner - это модуль планирования, написанный на Java™. Модуль совмещает набор эврестических и метаэвристических алгоритмов с эффективной оценкой результатов.

OptaPlanner - open source software, распространяется под лицензией Apache Software License.

Выгрузка для 1С Предприятия 7.7

Предлагаем воспользоваться обработкой для выгрузки точек доставки из 1С Предприятие 7.7 Комплексная в формате СVRP и CVRPTW

  • CVRP - Capaсity Vehile Routing Problem - Задача оптимизации маршрутов с ограниченной вместимостью
  • CVRPTW - Capaсity Vehile Routing Problem with Time Windows - Задача оптимизации маршрутов с ограниченной вместимостью и временем доставки

Координаты точек доставки предлагается определять по адресу доставки с помощью Yandex maps api

Алгоритм работы:

  1. В 1С Предприятии 7.7 запустить обработку Конструктор логиста
  2. Заполнить отгрузки за один день
  3. Установить координаты для всех точек доставки
  4. Установить последнюю версию Optaplanner
  5. Запустить ..\optaplanner-distribution-6.0.1.Final\examples\runExamples.bat
  6. Пункт Vehile Routing
  7. Import - для CVRP, Open - для CVRPTW

Дополнительная информация

Скачать файлы

Наименование Файл Версия Размер
КонструкторЛогистаВыгрузкаOptaplanner.ert
.ert 272,50Kb
14.10.14
11
.ert 272,50Kb 11 Скачать

См. также

Комментарии
1. Михаил Горбов (MadHead) 55 15.10.14 01:14 Сейчас в теме
На мой взгляд самое сложное в данной задаче легально получить матрицу расстояний между точками, а лучше время проезда с учетом пробок. Если брать по прямой, то толку от такой оптимизации крайне мало
FFelix; monkbest; +2 Ответить 2
2. Анатолий Шведов (ShtomBY) 15.10.14 01:30 Сейчас в теме
с учетом пробок? это было бы интереснее)
3. Сергей (ildarovich) 4892 15.10.14 09:08 Сейчас в теме
Ссылки интересные приведены
4. Антон Антонов (monkbest) 26 15.10.14 09:20 Сейчас в теме
(1) MadHead, собственно да. Мало того, что нужно раздобыть полный граф карты города. Всем ветвям графа нужно как-то проставить вес. Следующая проблема, что граф рельного города настолько большой, что вычисления оптимального маршрута - задача для мощного сервака, а не десктопа.
И тут получается вывод, что нужен сервис типа Яндекса, в котором есть средние скорости по каждому отрезку пути, есть все карты и есть огромные вычислительные мощности
5. Наталья Резникова (natarezn) 15.10.14 09:33 Сейчас в теме
100 процентов не коммуникативно ?
6. Сергей (ildarovich) 4892 15.10.14 09:48 Сейчас в теме
(4) monkbest, никаких огромных мощностей не нужно: http://habrahabr.ru/post/211388/ там у них получилось от 60 до 250 ms на на Core i7 3.4 Ghz.
7. cdr (phsin) 112 15.10.14 10:14 Сейчас в теме
(1) MadHead, город можно сравнить с сильно связным графом
если вы ставите вопрос о том, что с реальными расстояниями будет точнее, то я с вами соглашусь.
в статье Vehicle routing with real road distances проводится сравнение вычислений с матрицей расстояний "по прямой" и "реальными" расстояниями, выигрыш составляет 5%

Если же сравнивать алгоритмы кластеризации (или деление по районам, как все обычно делают) с оптимизацией с расстояниями "по прямой", то думаю что выигрыш будет больше - порядка 20-30% , хотя с такими исследованиями пока не сталкивался.
8. cdr (phsin) 112 15.10.14 10:26 Сейчас в теме
Geoffrey De Smet предлагает воспользоваться Java библиотекой GraphHopper, основанной на OpenStreetMap, Загрузка всей сети дорог Северной Америки занимает около 6GB.
9. cdr (phsin) 112 15.10.14 10:29 Сейчас в теме
(4) monkbest, вы можете опробовать Optaplanner на своём компьютере, думаю, вы будете приятно удивлены
10. olga pt (pt_olga) 58 22.10.14 19:20 Сейчас в теме
без наложения на карту и построения маршрута по конкретным географическим условиям и дорогам задача большого смысла не имеет, но разве что в будущем для летающих машин))
11. Сергей (ildarovich) 4892 22.10.14 20:06 Сейчас в теме
(10) pt_olga, будущее уже совсем рядомнаступило - DHL запускает беспилотную доставку в Германии(Ссылка)

А вот еще на ту же тему: Создателя Copter Express оштрафовали за доставку пиццы дронами. В последнем случае дело происходило в Сыктывкаре.
Прикрепленные файлы:
12. Иванов Дмитрий (mdmdvd) 50 30.10.14 15:02 Сейчас в теме
Можно попробовать сервис от Гугл Матрица Расстояний называется
13. cdr (phsin) 112 30.10.14 15:35 Сейчас в теме
(12) mdmdvd, спасибо за интересную ссылку.
14. Сергей (ildarovich) 4892 30.10.14 20:43 Сейчас в теме
(12) mdmdvd, но там только 25 точек (входов и выходов суммарно) или 100 связей ограничение. То есть получится только 10 точек реально считать. Да и с лицензией как то мутно. С чего бы Гугл задарма такой сервис десктопным приложениям раздавало? Это для сайтов, как и у Яндекса, чтобы рекламу доставлять.