Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Задача коммивояжера - Страница 2 - Мир MS Excel

Старая форма входа
  • Страница 2 из 3
  • «
  • 1
  • 2
  • 3
  • »
Модератор форума: _Boroda_, Manyasha, SLAVICK, китин  
Мир MS Excel » Вопросы и решения » Готовые решения » Задача коммивояжера (Excel)
Задача коммивояжера
AK Дата: Вторник, 06.03.2018, 01:16 | Сообщение № 21
Группа: Пользователи
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 0% ±

Excel 2016
MCH,
Спасибо огромное! Вы очень помогли.
Подскажите, пожалуйста, какой метод используется в данном файле?
Он решил задачу лучше стандартного "Поиска решения".
 
Ответить
СообщениеMCH,
Спасибо огромное! Вы очень помогли.
Подскажите, пожалуйста, какой метод используется в данном файле?
Он решил задачу лучше стандартного "Поиска решения".

Автор - AK
Дата добавления - 06.03.2018 в 01:16
MCH Дата: Вторник, 06.03.2018, 07:54 | Сообщение № 22
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Подскажите, пожалуйста, какой метод используется в данном файле?

Метод описан в первом сообщении данной темы под пунктом 1. (Графическим способом)
В качестве последующей оптимизации и улучшения найденного решения используется динамическое программирование (вынесено в отдельную dll)

Он решил задачу лучше стандартного "Поиска решения".

Через "Поиск решения" трудно составить линейную модель для решения задачи коммивояжера, если применять генетический метод решения, то не гарантировано будет найдено оптимальное решение, может быть найден локальный оптимум
 
Ответить
Сообщение
Подскажите, пожалуйста, какой метод используется в данном файле?

Метод описан в первом сообщении данной темы под пунктом 1. (Графическим способом)
В качестве последующей оптимизации и улучшения найденного решения используется динамическое программирование (вынесено в отдельную dll)

Он решил задачу лучше стандартного "Поиска решения".

Через "Поиск решения" трудно составить линейную модель для решения задачи коммивояжера, если применять генетический метод решения, то не гарантировано будет найдено оптимальное решение, может быть найден локальный оптимум

Автор - MCH
Дата добавления - 06.03.2018 в 07:54
AK Дата: Вторник, 06.03.2018, 14:41 | Сообщение № 23
Группа: Пользователи
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 0% ±

Excel 2016
MCH, спасибо за разъяснение! :)
Мне было интересно какой результат даст расчет методом ветвей и графов, вы не сталкивались с реализацией в Excel задачи коммивояжера этим методом?
 
Ответить
СообщениеMCH, спасибо за разъяснение! :)
Мне было интересно какой результат даст расчет методом ветвей и графов, вы не сталкивались с реализацией в Excel задачи коммивояжера этим методом?

Автор - AK
Дата добавления - 06.03.2018 в 14:41
MCH Дата: Вторник, 06.03.2018, 14:58 | Сообщение № 24
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

в 18 сообщении я выкладывал ссылку на решение задачи коммивояжера методом ветвей и границ (МВиГ)
Но на текущий момент алгоритм нуждается в оптимизации и, скорее всего, 48 городов для указанной реализации будет непосильной задачей.
 
Ответить
Сообщениев 18 сообщении я выкладывал ссылку на решение задачи коммивояжера методом ветвей и границ (МВиГ)
Но на текущий момент алгоритм нуждается в оптимизации и, скорее всего, 48 городов для указанной реализации будет непосильной задачей.

Автор - MCH
Дата добавления - 06.03.2018 в 14:58
DarK_RenO Дата: Среда, 20.06.2018, 00:43 | Сообщение № 25
Группа: Пользователи
Ранг: Участник
Сообщений: 66
Репутация: 0 ±
Замечаний: 60% ±

Excel 2007
Подскажите пожалуйста а как проложить оптимально маршрут с незамкнутым кругом? прямой линии. Можно к доставкам внутри города привязать?
К сообщению приложен файл: 3105513.rar(68.1 Kb)
 
Ответить
СообщениеПодскажите пожалуйста а как проложить оптимально маршрут с незамкнутым кругом? прямой линии. Можно к доставкам внутри города привязать?

Автор - DarK_RenO
Дата добавления - 20.06.2018 в 00:43
MCH Дата: Четверг, 21.06.2018, 15:18 | Сообщение № 26
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Для того, чтобы из замкнутого круга сделать незамкнутый, можно изменить описание графа.
Путь из конечной точки в первую занулить во все остальные сделать условной бесконечностью (большим числом)
В примере реализован вариант когда нужно попасть из первой точки во вторую, пройдя все остальные
Код решения не менял, изменил только составленный граф.

PS: файлы для решения с помощью DLL и EXE есть по ссылке из 18го сообщения
К сообщению приложен файл: TSP_VBADLLEXE_1.xlsm(69.7 Kb)
 
Ответить
СообщениеДля того, чтобы из замкнутого круга сделать незамкнутый, можно изменить описание графа.
Путь из конечной точки в первую занулить во все остальные сделать условной бесконечностью (большим числом)
В примере реализован вариант когда нужно попасть из первой точки во вторую, пройдя все остальные
Код решения не менял, изменил только составленный граф.

PS: файлы для решения с помощью DLL и EXE есть по ссылке из 18го сообщения

Автор - MCH
Дата добавления - 21.06.2018 в 15:18
Eger Дата: Понедельник, 23.07.2018, 22:37 | Сообщение № 27
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

Excel 2016
Если я все правильно понял, то данное решение подходит для "летающего" коммивояжера живущего на "плоской" планете.
Т.Е. путь строится прямыми линиями а не по дорогам (которые всегда извилисты и не могут рассчитываться геометрически).
А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.

А существует ли решение, работающее в реальных условиях? по дорогам на круглой планете?
Приблизительное расстояние между точками А и Б можно рассчитать по формуле:
=ACOS(SIN(РАДИАНЫ(<ШиротаА>))*SIN(РАДИАНЫ(<ШиротаБ>))+COS(РАДИАНЫ(<ШиротаА>))*COS(РАДИАНЫ(<ШиротаБ>))*COS(РАДИАНЫ(<ДолготаА>)-РАДИАНЫ(<ДолготаА>)))*6371
Где широта и долгота точек А и Б задана в градусах, а 6371 км. - это средний радиус нашей планеты.
Результат - расстояние между точками в километрах.

Если говорить про коммивояжера, который перемещается по дорогам, (прикрепил образец входящих данных)
есть ли у Вас алгоритм, который сможет обработать матрицу "расстояний по дорогам"?

То есть там где геометрия не работает,
Где расстояние между двумя точками "туда" и "обратно" может различаться (одностороннее движение, запреты маневров...)
Где между двумя рядом стоящими точками (на разных берегах реки), расстояние по дороге может составлять десятки километров...
Такое возможно? И каким способом? С каким максимальным количеством точек?
К сообщению приложен файл: TSP_VBADLLEXE_.xlsm(73.7 Kb)


Сообщение отредактировал Eger - Вторник, 24.07.2018, 01:06
 
Ответить
СообщениеЕсли я все правильно понял, то данное решение подходит для "летающего" коммивояжера живущего на "плоской" планете.
Т.Е. путь строится прямыми линиями а не по дорогам (которые всегда извилисты и не могут рассчитываться геометрически).
А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.

А существует ли решение, работающее в реальных условиях? по дорогам на круглой планете?
Приблизительное расстояние между точками А и Б можно рассчитать по формуле:
=ACOS(SIN(РАДИАНЫ(<ШиротаА>))*SIN(РАДИАНЫ(<ШиротаБ>))+COS(РАДИАНЫ(<ШиротаА>))*COS(РАДИАНЫ(<ШиротаБ>))*COS(РАДИАНЫ(<ДолготаА>)-РАДИАНЫ(<ДолготаА>)))*6371
Где широта и долгота точек А и Б задана в градусах, а 6371 км. - это средний радиус нашей планеты.
Результат - расстояние между точками в километрах.

Если говорить про коммивояжера, который перемещается по дорогам, (прикрепил образец входящих данных)
есть ли у Вас алгоритм, который сможет обработать матрицу "расстояний по дорогам"?

То есть там где геометрия не работает,
Где расстояние между двумя точками "туда" и "обратно" может различаться (одностороннее движение, запреты маневров...)
Где между двумя рядом стоящими точками (на разных берегах реки), расстояние по дороге может составлять десятки километров...
Такое возможно? И каким способом? С каким максимальным количеством точек?

Автор - Eger
Дата добавления - 23.07.2018 в 22:37
SLAVICK Дата: Вторник, 24.07.2018, 09:41 | Сообщение № 28
Группа: Модераторы
Ранг: Старожил
Сообщений: 2290
Репутация: 758 ±
Замечаний: 0% ±

2019
А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.

Прочтите тему сначала внимательно, и смотрите вложения. Тут есть решения как геометрически, так и по справочнику расстояний.
Например в моем посте №16 - подредактированный код Михаила из 14-го поста.
Там как раз сделано по матрице расстояний (кстати в Вашем вложении этот же файл)- подставьте реальные расстояния в матрицу смежности - получите реальные цифры
Добавлено:
График нужен только для наглядности - и строится как раз линейно по координатам.


Иногда все проще чем кажется с первого взгляда.
 
Ответить
Сообщение
А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.

Прочтите тему сначала внимательно, и смотрите вложения. Тут есть решения как геометрически, так и по справочнику расстояний.
Например в моем посте №16 - подредактированный код Михаила из 14-го поста.
Там как раз сделано по матрице расстояний (кстати в Вашем вложении этот же файл)- подставьте реальные расстояния в матрицу смежности - получите реальные цифры
Добавлено:
График нужен только для наглядности - и строится как раз линейно по координатам.

Автор - SLAVICK
Дата добавления - 24.07.2018 в 09:41
MCH Дата: Среда, 06.02.2019, 10:24 | Сообщение № 29
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Реализовал алгоритм решения задачи коммивояжера для задач больше чем 20-25 городов
Отказался от графического метода.
В основе алгоритма, построение нескольких разных маршрутов и их оптимизация, с выбором лучшего решения
К реализации подтолкнула данная статья: https://habr.com/ru/post/335016/
В качестве оптимизации используется 2-opt оптимизация и 3-opt оптимизация (с моей их интерпретацией), плюс дополнительные методы.
Алгоритм реализованный на чистом VBA для задачи не более 100 городов отрабатывает за секунды, находит или оптимальный маршрут или очень близкий к нему
для 200 городов - время исчисляется минутами
500 - 1000 городов - существенно дольше.
Также перенес код в Freebasic, что дало ускорение в разы (пока еще не задействовал потоки, это еще ускорит расчет).
Указанный метод можно применять как для замкнутого, так и не замкнутого маршрута.
Т.к. не используется графический способ, то можно вместо координат подставлять матрицу расстояний между городами, задача должна быть симметричной.

Примеры задач и их решения во вложении, можно менять настройки от минимальных (решение находится очень быстро, но как правило не оптимальное), до более сложных.
К сообщению приложен файл: tsp225.xlsm(69.2 Kb) · eil.xlsm(88.6 Kb)
 
Ответить
СообщениеРеализовал алгоритм решения задачи коммивояжера для задач больше чем 20-25 городов
Отказался от графического метода.
В основе алгоритма, построение нескольких разных маршрутов и их оптимизация, с выбором лучшего решения
К реализации подтолкнула данная статья: https://habr.com/ru/post/335016/
В качестве оптимизации используется 2-opt оптимизация и 3-opt оптимизация (с моей их интерпретацией), плюс дополнительные методы.
Алгоритм реализованный на чистом VBA для задачи не более 100 городов отрабатывает за секунды, находит или оптимальный маршрут или очень близкий к нему
для 200 городов - время исчисляется минутами
500 - 1000 городов - существенно дольше.
Также перенес код в Freebasic, что дало ускорение в разы (пока еще не задействовал потоки, это еще ускорит расчет).
Указанный метод можно применять как для замкнутого, так и не замкнутого маршрута.
Т.к. не используется графический способ, то можно вместо координат подставлять матрицу расстояний между городами, задача должна быть симметричной.

Примеры задач и их решения во вложении, можно менять настройки от минимальных (решение находится очень быстро, но как правило не оптимальное), до более сложных.

Автор - MCH
Дата добавления - 06.02.2019 в 10:24
MCH Дата: Среда, 06.02.2019, 10:25 | Сообщение № 30
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Exe файл к предыдущему посту и исходник на Freebasic во вложении
код легко переносится в VBA
К сообщению приложен файл: mchTSPexe.rar(44.8 Kb)
 
Ответить
СообщениеExe файл к предыдущему посту и исходник на Freebasic во вложении
код легко переносится в VBA

Автор - MCH
Дата добавления - 06.02.2019 в 10:25
MCH Дата: Среда, 06.02.2019, 12:08 | Сообщение № 31
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Прорешал 50 различных задач TSP от 50 до 1000+ городов: https://yadi.sk/d/aQkKPfZrAh69yA
Источник данных: TSPLIB

Больше половины решений имеют оптимальный маршрут
В сложных задачах (500 и более городов) решение отличается от оптимального не более чем на 1-2%

UPD: 58 маршрутов, более 40 из них имеют оптимальные решения
https://yadi.sk/d/t388388W9sfb7g
 
Ответить
СообщениеПрорешал 50 различных задач TSP от 50 до 1000+ городов: https://yadi.sk/d/aQkKPfZrAh69yA
Источник данных: TSPLIB

Больше половины решений имеют оптимальный маршрут
В сложных задачах (500 и более городов) решение отличается от оптимального не более чем на 1-2%

UPD: 58 маршрутов, более 40 из них имеют оптимальные решения
https://yadi.sk/d/t388388W9sfb7g

Автор - MCH
Дата добавления - 06.02.2019 в 12:08
MCH Дата: Понедельник, 25.02.2019, 14:33 | Сообщение № 32
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Сделал решение для асимметричной задачи коммивояжера: https://u.to/oe-EFA
Результаты выдает приемлемые.
На VBA считает не очень быстро, можно применять для задач до 100 городов
 
Ответить
СообщениеСделал решение для асимметричной задачи коммивояжера: https://u.to/oe-EFA
Результаты выдает приемлемые.
На VBA считает не очень быстро, можно применять для задач до 100 городов

Автор - MCH
Дата добавления - 25.02.2019 в 14:33
dadade Дата: Понедельник, 07.10.2019, 19:11 | Сообщение № 33
Группа: Пользователи
Ранг: Новичок
Сообщений: 11
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
С обеда изучаю ваши фалы и пытаюсь сделать свое но никак не получается ввиду того что у меня двоичный массив примерно на 500x500 значении.
У каждой точки координаты, и нужно вычислить расстояние между точками вот на этом застрял. Задача найти самые близкие точки.
Файл с коммивояжерами не подходит, так как не показывает расстояние между точками.
Помогите пжл решить данную задачу.
Заранее спасибо!
К сообщению приложен файл: Book1.xlsx(35.7 Kb)
 
Ответить
СообщениеС обеда изучаю ваши фалы и пытаюсь сделать свое но никак не получается ввиду того что у меня двоичный массив примерно на 500x500 значении.
У каждой точки координаты, и нужно вычислить расстояние между точками вот на этом застрял. Задача найти самые близкие точки.
Файл с коммивояжерами не подходит, так как не показывает расстояние между точками.
Помогите пжл решить данную задачу.
Заранее спасибо!

Автор - dadade
Дата добавления - 07.10.2019 в 19:11
MCH Дата: Вторник, 08.10.2019, 08:16 | Сообщение № 34
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

нужно вычислить расстояние между точками вот на этом застрял

Нужно вычислить расстояния между точками по их координатам (широте и долготе)?
Без учета движения по дорогам это можно сделать по формуле:
Код
=6371*ACOS(SIN(РАДИАНЫ($B4))*SIN(РАДИАНЫ(D$2))+COS(РАДИАНЫ($B4))*COS(РАДИАНЫ(D$2))*COS((РАДИАНЫ($C4-D$3))))

в файле заполнил формулами несколько строк, заполните остальные
далее сформулируйте задачу, что нужно сделать зная расстояния между точками
К сообщению приложен файл: GEOcoord.xlsb(89.2 Kb)
 
Ответить
Сообщение
нужно вычислить расстояние между точками вот на этом застрял

Нужно вычислить расстояния между точками по их координатам (широте и долготе)?
Без учета движения по дорогам это можно сделать по формуле:
Код
=6371*ACOS(SIN(РАДИАНЫ($B4))*SIN(РАДИАНЫ(D$2))+COS(РАДИАНЫ($B4))*COS(РАДИАНЫ(D$2))*COS((РАДИАНЫ($C4-D$3))))

в файле заполнил формулами несколько строк, заполните остальные
далее сформулируйте задачу, что нужно сделать зная расстояния между точками

Автор - MCH
Дата добавления - 08.10.2019 в 08:16
dadade Дата: Вторник, 08.10.2019, 09:25 | Сообщение № 35
Группа: Пользователи
Ранг: Новичок
Сообщений: 11
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
MCH, О, отлично, супер!!! hands
Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши?
Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах. Как можно это быстро сделать, есть формула?
 
Ответить
СообщениеMCH, О, отлично, супер!!! hands
Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши?
Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах. Как можно это быстро сделать, есть формула?

Автор - dadade
Дата добавления - 08.10.2019 в 09:25
dadade Дата: Среда, 09.10.2019, 14:54 | Сообщение № 36
Группа: Пользователи
Ранг: Новичок
Сообщений: 11
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Есть решение?
 
Ответить
СообщениеЕсть решение?

Автор - dadade
Дата добавления - 09.10.2019 в 14:54
dadade Дата: Суббота, 12.10.2019, 16:53 | Сообщение № 37
Группа: Пользователи
Ранг: Новичок
Сообщений: 11
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
?
 
Ответить
Сообщение?

Автор - dadade
Дата добавления - 12.10.2019 в 16:53
MCH Дата: Понедельник, 14.10.2019, 08:52 | Сообщение № 38
Группа: Админы
Ранг: Старожил
Сообщений: 1961
Репутация: 731 ±
Замечаний: ±

Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах.

Ваш вопрос не относится к задаче коммивояжера, поэтому лучше создать отдельную тему и там задать вопрос.
На вскидку, задача решается функциями МИН() и ПОИСКПОЗ()
 
Ответить
Сообщение
Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах.

Ваш вопрос не относится к задаче коммивояжера, поэтому лучше создать отдельную тему и там задать вопрос.
На вскидку, задача решается функциями МИН() и ПОИСКПОЗ()

Автор - MCH
Дата добавления - 14.10.2019 в 08:52
dadade Дата: Среда, 13.11.2019, 17:29 | Сообщение № 39
Группа: Пользователи
Ранг: Новичок
Сообщений: 11
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
MCH, что насчет вот этой части вопроса, можно узнать как было это сделано?

Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши?
 
Ответить
СообщениеMCH, что насчет вот этой части вопроса, можно узнать как было это сделано?

Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши?

Автор - dadade
Дата добавления - 13.11.2019 в 17:29
analitolog Дата: Понедельник, 06.01.2020, 21:24 | Сообщение № 40
Группа: Пользователи
Ранг: Прохожий
Сообщений: 9
Репутация: 0 ±
Замечаний: 0% ±

Excel 2013
Прошу направить решение усложнённой задачи коммивояжера.
Есть 80 точек на плоскости, из них 20 нужно посещать через день, остальные - раз в неделю. Время на каждой точке Х минут.
Опорная точка одна - из нее выезжаем и возвращаемся каждый день. Список точек для примера в эксель.
Как распределить точки по маршрутам по критерию а) минимального общего расстояния и б) минимального общего времени , не более Y часов в день?

Видится путь распределения точек по группам близости, где в каждой группе будут приоритетные точки и неприоритетные. Перебором не решить.
К сообщению приложен файл: 1434416.xlsm(85.7 Kb)
 
Ответить
СообщениеПрошу направить решение усложнённой задачи коммивояжера.
Есть 80 точек на плоскости, из них 20 нужно посещать через день, остальные - раз в неделю. Время на каждой точке Х минут.
Опорная точка одна - из нее выезжаем и возвращаемся каждый день. Список точек для примера в эксель.
Как распределить точки по маршрутам по критерию а) минимального общего расстояния и б) минимального общего времени , не более Y часов в день?

Видится путь распределения точек по группам близости, где в каждой группе будут приоритетные точки и неприоритетные. Перебором не решить.

Автор - analitolog
Дата добавления - 06.01.2020 в 21:24
Мир MS Excel » Вопросы и решения » Готовые решения » Задача коммивояжера (Excel)
  • Страница 2 из 3
  • «
  • 1
  • 2
  • 3
  • »
Поиск:

Яндекс цитирования Jobsora jooble
© 2010-2021 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!