Задача коммивояжера методом ветвей и границ в 1С

04.07.12

Разработка - Математика и алгоритмы

Пример для тестирования решения задачи коммивояжера методом ветвей и границ.

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

Наименование Файл Версия Размер
ЗадачаКоммивояджера
.epf 13,72Kb
58
.epf 13,72Kb 58 Скачать

Пример реализации алгоритма задачи коммивояджера методом ветвей и границ.

На закладке "Матрица расстояний" необходимо задать размерность, т.е. количество узлов маршрута и нажать кнопку "Создать структуру", в заполненной таблице необходимо заполнить прямые и обратные расстояния между пунктами, после чего нажать на кнопку "Решить", после расчета в строке сообщений будет выведен оптимальный маршрут (последовательность узлов).
Второй вариант - это несколько доработать справочник "Регионы" стандартной конфигурации "УТ", добавить 2 регвизита "Широта" и "Долгота", в которых заполнены географические координаты населенных пуктов. Я заполнял пользуясь shape-файлами, брал например здесь http://gis-lab.info/projects/osm-export.html , можно пользуясь сервисами API карт yandex или google. Тогда на закладке "Пункты" нужно заполнить список регионами, между которыми выполнять поиск, нажать кнопку "Создать матрицу" (таблица "Матрица расстояний" будет заполнена исходя из расстояний между координатами регионов на сфере), после этого нажать на кнопку "Решить", при этом на закладке "Пункты" будет отображено графическое представление пунктов и кратчайшего маршрута между ними.

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1756    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4426    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7465    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8843    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7808    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Angeros 05.07.12 08:48 Сейчас в теме
Списибо, давно искал, самому было лень вспоминать :)
2. Angeros 05.07.12 08:53 Сейчас в теме
А что со скрин шотами? какойто новомодный дэзайн?
3. MarcoPolo3 50 05.07.12 11:25 Сейчас в теме
(2) Angeros, а что не так со скриншотами?
4. automatizator 169 11.07.12 02:44 Сейчас в теме
Осталось объединить например с infostart.ru/public/142306 и написать обработку для оптимизации развоза товара для УТ, или планирования маршрута торгпредов!

Кому не слабо?
5. putin-vv 11.07.12 09:53 Сейчас в теме
(4) automatizator, дело за малым - сколько заказчик готов за это заплатить
6. catena 110 16.07.12 11:40 Сейчас в теме
(4)Вряд ли получится. Для того, чтобы вышел толк, надо к длине пути добавлять еще вес загруженности и альтернативные маршруты - иначе в любом более менее большом городе это планирование маршрутов накроется медным тазом.
7. philya 77 07.05.13 10:20 Сейчас в теме
Проверить работоспособность не удалось. На трех точках с матрицей

0 1 1
1 0 1
1 1 0

пишет "все плохо. идите вон"

{ВнешняяОбработка.ЗадачаКоммивояджера.МодульОбъекта(128)}: Операции сравнения на больше-меньше допустимы только для значений совпадающих примитивных типов (Булево, Число, Строка, Дата)
Если НовыйУзел.Оценка < ДеревоРешений.Оценка Тогда
8. Aleksey81 1177 27.01.14 15:32 Сейчас в теме
Пишет все плохо!!!
{ВнешняяОбработка.ЗадачаКоммивояджера.МодульОбъекта(128)}: Операции сравнения на больше-меньше допустимы только для значений совпадающих примитивных типов (Булево, Число, Строка, Дата)
Если НовыйУзел.Оценка < ДеревоРешений.Оценка Тогда
Явная ошибка в алгоритме!!!
Оставьте свое сообщение