gifts2017

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

Опубликовал Алексей Иванов (MarcoPolo3) в раздел Программирование - Практика программирования

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

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

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

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

См. также

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

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

0 1 1
1 0 1
1 1 0

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

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