gifts2017

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

Опубликовал 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
10
.ert 272,50Kb 10 Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

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

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

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