bdd2

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

Опубликовал 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) 55 15.10.14 01:14 Сейчас в теме
На мой взгляд самое сложное в данной задаче легально получить матрицу расстояний между точками, а лучше время проезда с учетом пробок. Если брать по прямой, то толку от такой оптимизации крайне мало
FFelix; monkbest; +2 Ответить 2
2. Анатолий Шведов (ShtomBY) 15.10.14 01:30 Сейчас в теме
с учетом пробок? это было бы интереснее)
3. Сергей (ildarovich) 4786 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) 4786 15.10.14 09:48 Сейчас в теме
(4) monkbest, никаких огромных мощностей не нужно: http://habrahabr.ru/post/211388/ там у них получилось от 60 до 250 ms на на Core i7 3.4 Ghz.
7. cdr (phsin) 111 15.10.14 10:14 Сейчас в теме
(1) MadHead, город можно сравнить с сильно связным графом
если вы ставите вопрос о том, что с реальными расстояниями будет точнее, то я с вами соглашусь.
в статье Vehicle routing with real road distances проводится сравнение вычислений с матрицей расстояний "по прямой" и "реальными" расстояниями, выигрыш составляет 5%

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

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