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

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

Без примера исходных данных трудно что-то конкретное предложить
 
Уже читала эту тему, там нету решения для 70 адресов. К тому же там просчитывается расстояние по воздуху, а в моем варианте, там уже дана матрица расстояний с гугл API
 
Если покажите пример исходных данных, то можно придумать усредненное решение: по координатам построить приближенное решение "по воздуху", а затем локальным перебором коротких участков найти более оптимальное решение по матрице расстояний
 
Пример в сообщении выше
 
Странная у Вас матрица смежности, в ней не числа а текст, записаны через точку, а также есть пробел и встречаются буквы.
Можете составить матрицу с нормальными числами?
 
Извините, данные полученны с помощью программы, забыла их отформатировать. Вот готовые:
 
Я так почитала, что вроде нужно решать методом динамического программирования, только вот код сделать не могу
 
Динамическим программированием вроде бы можно сделать для большой размерности, или я ошибаюсь?
 
я бы решил поиском решения разделив на 25 подзадач

Excel 2013 в помощь отметить точки на карте, для выбора пулов точек
 
Расскажите подробнее как это сделать
 
Для 20 городов "Поиск решения" нашел оптимальный маршрут.
Для 71 города, можно найти решение лучше "жадного" алгоритма, но не факт, что это оптимальный маршрут
Изменено: MCH - 05.06.2015 09:22:14
 
lihtaryk, решение не подошло или задача больше не актуальна?
 
Думаю, что подойдет. Пробую еще одним методом решить)

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

Кроме того, в файле есть макрос, который способен решить задачу для 20 городов методом динамического программирования (гарантировано будет найден оптимальный вариант).
А также есть формулы, для определения расстояния "жадным" алгоритмом
 
Извините, можете посмотреть мой файл. При выполнении макроса выбивает ошибку
 
Ошибка в значениях на главной диагонале матрицы смежности, там не должно быть текста. Все значения "-" замните на 0
 
Спасибо большое! Все работает!
 
Вопрос не по теме [МОДЕРАТОР]
 
Цитата
MCH написал:
Для 71 города, можно найти решение лучше "жадного" алгоритма, но не факт, что это оптимальный маршрут
Прорешал матрицу из 71 города своими методами решения задачи коммивояжера, получилось, для текущей задачи из 71 города - 120,29 (не обязательно, что это глобальный оптимум)
решение получилось на 7,5% лучше жадного алгоритма и на 1,4% лучше, чем решил "Поиск решения" генетическим алгоритмом
 
MCH,Доброго времени суток! Современные системы мониторинга успешно решают эти задачи с подтягиваний расстояний по дорогам в своих интерфейсах. Даже есть специальные библиотеки в Pythone и JS. Дорогая альтернатива Вашим несомненно крутым разработкам!
Страницы: 1
Наверх