gifts2017

Конструктор логиста

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

Формирование маршрутов доставки на основе генетического алгоритма (решения задачи коммивояжера) для 1С Предприятия 7.7

 

Формирвоание маршрутов можно свести к решению задачи коммивояжера с дополнительными ограничениями. Давайте поставим задачу.

Дано:

  • Некоторое количество торговых точек (ТТ), обычно 50-500
  • Вес товара, который необходимо доставить в каждую ТТ
  • Некоторое количество машин с ограниченными вместимостью 1500 кг и ограниченными человеческими ресурсами - не более 15 магазинов в день

    Необходимо:

    Найти оптимальный маршрут с минимальным количеством машин и минимальнцым расстоянием доставки (пробегом)

     

    Существует несколько способов решения этой задачи

    1. Традиционный - деление по районам
    2. Перебор - для 100 точек потребуется 100! итераций, а это ОЧЕНЬ много
    3. Жадный алгоритм - вседа выбираем ближайшую точку, к сожалению, алгоритм дает иногда самый не оптимальный вариант
    4. Генетический алгоритм
    5. Алгоритм муравьиной колонии
  • Краткое описание алгоритма

    Описание структуры данных:

    Популяция состоит из Генов - возможные решения. Каждый Ген имеет стоимость, стоимость состоит из расстояния, пройденного машиной и весом, который эта машина перевозит.

    1. Формируем начальную популяцию. Можно формировать случайно, по районам или по жадному алгоритму
    2. Запускаем цикл (чем больше итераций тем лучше).
    3. Генерируем потомков только у лучших генов
    4. Сортируем по возрастанию стоимости
    5. "Элита" остается, остальные "умирают"

Сходимость решения во многом зависит от начальной выборки и параметров алгоритма. Значения параметры получены экспериментальным путем, возможно для кого-то существуют более оптимальные...

Добавлено разделение ТТ по районам и расстояния между районами. 

 

P.S. Огромная благодарность рябятам создавшим и развивающим проект 1С++!!! Так держать! Вы молодцы!

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

Наименование Файл Версия Размер Кол. Скачив.
map.rar
.rar 682,37Kb
11.01.13
74
.rar 682,37Kb 74 Скачать
Конструктор логиста с районами
.rar 901,35Kb
14.01.13
37
.rar 901,35Kb 37 Скачать

См. также

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

Комментарии

1. popal (popal_al@mail.ru) 12.01.13 23:09
мне кажется это из проклуба за 200... год и разработчик не вы
нашел... просьба несчитать это рекламой проклуба
http://1c.proclub.ru/modules/mydownloads/personal.php?cid=5&lid=8162
разработчик veritas его сайт http://map.samtel.ru

да уж... просто хотел сказать - ссылаемся на автора
2. cdr (phsin) 13.01.13 10:43
Спасибо что помните! Вы знаете очень приятно! :)
Я разработчик, просто на proclub опубликовал под другим псевдонимом veritas в далеком 2008 году...
К своему удивлению не обнаружил на infostart'е
В последнее время заметил интерес к теме генетических алгоритмов (http://forum.infostart.ru/forum24/topic77246/) и поэтому решил опубликовать здесь.
Надеюсь кому-то будет интересно.
3. Владимир Земцов (vladzem) 14.01.13 09:30
А с 2008 года обработка както менялась? Если да просьба прислать ее на адрес prog@sirobogatov.ru В настоящий момент занят проблемой оптимальной доставки.
4. cdr (phsin) 14.01.13 11:47
Добавлено "районирование" - разделение торговых точек по районам и составление маршрутов с учетом доставки по районам, чтобы исключить из маршрута точки которые находятся географически близко, но добраться до них сложно (например разделены рекой). Постараюсь найти последний релиз...
5. Владимир Земцов (vladzem) 14.01.13 12:16
6. Доржи Балбаров (Angeros) 22.01.13 07:33
Ну вот в разработке представлено целых 2 файла, конструктор и мап, а что из них что?! Как-то не так пост оформлен, приводиться преамбула. Есть список вариантов решения проблемы, но на этом все...
Для построения логистики по городу нужно как минимум иметь дорожный граф где указаны точки с координатами, расстояния между точками и т.д. как это получается в вашей разработке?
7. cdr (phsin) 24.01.13 12:33
Angeros, спасибо за вопрос.

Нам нужны координаты точки доставки, исходим из предположения что кварталы прямоугольные, поэтому расстояние между точками = модулю разности координат (да, сразу надо отметить, что расстояние считается неправильно, но поскольку сравниваются одинаковые величины, то мне кажется что на решение это особо не отражается)
Поскольку невозможно рассчитать точное расстояние между N=500 точками доставки (если учитывать что граф ориентированный, то получится (N-1)! значений для вычислений)

В решении с районами добавляем к расстоянию между точками расстояние между районами, которое уже берем из графа (Справочника) Расстояния между районами.
Справочник "Расстояние между районами" заполняем из экселевской таблицы (пример таблицы в EXTFORMS) или вносим "вручную"

предлагается 2 файла - решения задачи
Скачать "map.rar" - решение без районов...
Скачать "Конструктор логиста с районами" - решение с районами...
8. Роман Зиновьев (Широкий) 25.11.14 11:12
Сыпется куча ошибок при запуске.
Если и удается сформировать расчет - выдает несколько маршрутов. Описания нет
Беда какая то
9. cdr (phsin) 25.11.14 13:32
Обработка давнишняя, поддерживать ее, наверно, не имеет смысла,
сейчас ее можно использовать пожалуй как упрощенную демонстрацию генетического алгоритма
на текущий момент есть более эффективные решения например http://infostart.ru/public/307383/
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа