Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Транспортная задача Коммивояжера
 
#1
04.06.2015 16:37:33
Доброго времени суток! Нужно решить транспортную задачу Коммивояжера для 70 адресов. Поиск решения не подходит, так как в нем ограничение для 200 изменяемых ячеек (а у меня 70*70). Можете помочь в написании макроса, так как программирование я не изучала?
 
 
 
#2
04.06.2015 16:45:59
посмотрите здесь: http://www.excelworld.ru/forum/3-12090-1
но, думаю, 70 - это слишком много.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#3
04.06.2015 16:58:33
Планировала сделать так как на первом листе, только для большого размера. Не могу придумать как просчитать дополнительные переменные, вводить вручную глупо долго. Может можно вообще другим методом решить?
 
 
 
#4
04.06.2015 17:03:13
Задача коммивояжера решается разными способами (ссылку на пример решения уже дали):
Полным перебором можно решить для 12-13 городов
Динамическим программированием 20-22 города.
Методом ветвей и границ - зависит от исходных данных, алгоритм не простой (я так его не осилил)
Графическим (геометрическим) методом можно получить приблеженное к оптимальному решение, количество городов практически не ограничено, можно решить и для нескольких сотен городов, но есть определенные требования к исходной информации.

Можно применять различные эвристики, алгоритмы муравьиных колоний, генетические алгоритмы и т.п.
Или самый простой - "Жадный алгоритм".

Без примера исходных данных трудно что-то конкретное предложить
 
 
 
#5
04.06.2015 17:03:16
Уже читала эту тему, там нету решения для 70 адресов. К тому же там просчитывается расстояние по воздуху, а в моем варианте, там уже дана матрица расстояний с гугл API
 
 
 
#6
04.06.2015 17:12:02
Если покажите пример исходных данных, то можно придумать усредненное решение: по координатам построить приближенное решение "по воздуху", а затем локальным перебором коротких участков найти более оптимальное решение по матрице расстояний
 
 
 
#7
04.06.2015 17:15:31
Пример в сообщении выше
 
 
 
#8
04.06.2015 19:39:35
Странная у Вас матрица смежности, в ней не числа а текст, записаны через точку, а также есть пробел и встречаются буквы.
Можете составить матрицу с нормальными числами?
 
 
 
#9
04.06.2015 19:45:34
Извините, данные полученны с помощью программы, забыла их отформатировать. Вот готовые:
 
 
 
#10
04.06.2015 19:47:51
Я так почитала, что вроде нужно решать методом динамического программирования, только вот код сделать не могу
 
 
 
#11
04.06.2015 20:06:23
Динамическим программированием вроде бы можно сделать для большой размерности, или я ошибаюсь?
 
 
 
#12
04.06.2015 20:27:01
я бы решил поиском решения разделив на 25 подзадач

Excel 2013 в помощь отметить точки на карте, для выбора пулов точек
 
 
 
#13
04.06.2015 20:30:59
Расскажите подробнее как это сделать
 
 
 
#14
04.06.2015 20:56:10
Для 20 городов "Поиск решения" нашел оптимальный маршрут.
Для 71 города, можно найти решение лучше "жадного" алгоритма, но не факт, что это оптимальный маршрут
Изменено: MCH - 05.06.2015 09:22:14
 
 
 
#15
07.06.2015 19:17:17
lihtaryk, решение не подошло или задача больше не актуальна?
 
 
 
#16
08.06.2015 13:07:27
Думаю, что подойдет. Пробую еще одним методом решить)

Спасибо огромное!
 
 
 
#17
08.06.2015 14:02:40
Каким методом решена задача через поиск решения?
 
 
 
#18
08.06.2015 14:25:13
Цитата
lihtaryk написал: Каким методом решена задача через поиск решения?
Поиском решения :)
Я специально сохранил в файле скрин настроек "Поиска решения"

Кроме того, в файле есть макрос, который способен решить задачу для 20 городов методом динамического программирования (гарантировано будет найден оптимальный вариант).
А также есть формулы, для определения расстояния "жадным" алгоритмом
 
 
 
#19
09.06.2015 11:19:16
Извините, можете посмотреть мой файл. При выполнении макроса выбивает ошибку
 
 
 
#20
09.06.2015 12:13:29
Ошибка в значениях на главной диагонале матрицы смежности, там не должно быть текста. Все значения "-" замните на 0
 
 
 
#21
09.06.2015 12:58:31
Спасибо большое! Все работает!
 
 
 
#22
09.06.2015 14:52:19
Вопрос не по теме [МОДЕРАТОР]
 
 
 
#23
25.02.2019 13:35:02
Цитата
MCH написал:
Для 71 города, можно найти решение лучше "жадного" алгоритма, но не факт, что это оптимальный маршрут
Прорешал матрицу из 71 города своими методами решения задачи коммивояжера, получилось, для текущей задачи из 71 города - 120,29 (не обязательно, что это глобальный оптимум)
решение получилось на 7,5% лучше жадного алгоритма и на 1,4% лучше, чем решил "Поиск решения" генетическим алгоритмом
 
 
 
#24
26.02.2019 09:16:37
MCH,Доброго времени суток! Современные системы мониторинга успешно решают эти задачи с подтягиваний расстояний по дорогам в своих интерфейсах. Даже есть специальные библиотеки в Pythone и JS. Дорогая альтернатива Вашим несомненно крутым разработкам!
 
 
 
Страницы: 1
Читают тему
Loading...