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

Публикация № 168946

Разработка - Практика программирования

Формирование маршрутов доставки на основе генетического алгоритма (решения задачи коммивояжера) для 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
76
.rar 682,37Kb 76 Скачать
Конструктор логиста с районами

.rar 901,35Kb
39
.rar 901,35Kb 39 Скачать

Специальные предложения

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

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

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

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

См. также

Печать чеков для ККМ АТОЛ и ШТРИХ на основании текстового файла, где содержится описание товаров, цен, НДС (все требования 54-ФЗ, поддержка изменений от 01/07/19). Для 1С (7.7 и 8 УФ, обычных форм) есть готовые обработки Промо

ККМ Фискальный регистратор Кассовые операции Оптовая торговля Розничная торговля Кассовые операции Оптовая торговля Розничная торговля v7.7 v8 v8::УФ 1cv8.cf 1cv7.md Россия Абонемент ($m)

Это программа печати чеков, которая читает обычный текстовый файл, где перечислено, что надо распечатать на ФР - описание содержимого чека. Такой механизм позволяет использовать комплект для WEB сайтов, для не типовых или сильно измененных 1с7 или 1с8. Для любых программ которые умеют работать с текстовыми файлами (будь то CLIPPER,FOXPRO,JAVA, WSH, VBS итд). Внутри комплекта лежат готовые внешние печатные формы для печати из документов Реализация товаров и услуг 1с8 УТ10, БП2, БП2Базовая, БП2Корп, УТ11, БП3, БП3Базовая, БП3Корп, Для 1с:ТиС 7.7 Реализация ТМЦ, Бух4.5, Бух1.3 и Печать из ПКО Подключать ФР к 1С не надо! Не надо открывать смену. Подходит для любой конфигурации, для любого документа. Более 300 внедрений на ккм Штрих-Мини-ФР-К, Штрих ОнЛайн Атол 11Ф, 55Ф, 30. Возможна пробитие оплаты наличным или VISA  (Электронные деньги). Поддерживает передачу в ОФД имени кассира, телефон или email покупателя. Для каждого чека можно поменять ОСН (ЕНВД, Доходы-расходы итд). Возможна печать чека с выровненными колонками, Наименование,Количество Цена, Сумма, в этом случае фискализация будет одной строкой с общей суммой. Можно пробить не фискальный чек. (чек будет, но в налоговую не уйдет). Добавлена расшифровка длинных наименований, что актуально для Штрих (программа сама переносит длинные наименования на след строку). Есть внесение и выплата денег. 29.06.17 добавлено пробитие 2 видов оплат в одном чеке.

10 стартмани

11.04.2017    75167    222    ah7777777    575    

Отправка SMS в 1С:Предприятие 7.7 "Торговля + Склад", 1С:Предприятие 8 "УТ 10.3", "УТ 11", "БП 3.0" по справочнику контрагенты 22 копейки за СМС

SMS рассылки Управление взаимоотношениями с клиентами (СRM) Управление взаимоотношениями с клиентами (СRM) v8 v77::ОУ УТ10 1С7:ТиС БП3.0 УТ11 УУ Абонемент ($m)

Очень часто в торговых организациях проводятся рассылки своим покупателям об акциях, скидках, новых поступлениях и т.д. Для этих целей мы создали комплекс внешних обработок, которые помогут осуществить рассылку. Для отправки используем сервис sms.ru, который является дешевым: 22 копеек за 1 SMS, если количество отправленных SMS перевалило через сумму 5 т.р. то цена снижается до 7 копеек за SMS. Плюс, этот вариант давно обкатан на наших клиентах.

1 стартмани

01.04.2013    47369    341    Diversus    29