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

Опубликовал 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) 111 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) 111 14.01.13 11:47 Сейчас в теме
Добавлено "районирование" - разделение торговых точек по районам и составление маршрутов с учетом доставки по районам, чтобы исключить из маршрута точки которые находятся географически близко, но добраться до них сложно (например разделены рекой). Постараюсь найти последний релиз...
5. Владимир Земцов (vladzem) 14.01.13 12:16 Сейчас в теме
6. Доржи Балбаров (Angeros) 22.01.13 07:33 Сейчас в теме
Ну вот в разработке представлено целых 2 файла, конструктор и мап, а что из них что?! Как-то не так пост оформлен, приводиться преамбула. Есть список вариантов решения проблемы, но на этом все...
Для построения логистики по городу нужно как минимум иметь дорожный граф где указаны точки с координатами, расстояния между точками и т.д. как это получается в вашей разработке?
7. cdr (phsin) 111 24.01.13 12:33 Сейчас в теме
Angeros, спасибо за вопрос.

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

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

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