Решение задачи о коммивояжере в Excel
Обновлено: 21.11.2024
Аннотация
Проблема коммивояжера (TSP) — важная проблема в управлении операциями. Применение TSP появляется в задачах маршрутизации, но также встречается во множестве других областей, таких как планирование рабочих мест и даже в спорте. В этой статье представлено учебное упражнение, в котором небольшой экземпляр задачи коммивояжёра решается до оптимального уровня. Упражнение выполняется в программе для работы с электронными таблицами Microsoft Excel с установленной по умолчанию надстройкой Solver. Эта статья считается первой демонстрацией использования Excel и Solver для решения задачи коммивояжера с использованием ограничений и переменных Миллера, Такера и Землина, исключающих подтур. Также представлены предложения по освещению тем, связанных с задачей коммивояжёра, и пример задачи, подходящей для домашнего задания или экзамена. Это тематическое исследование было рассмотрено редакционным советом журнала Operations Management Education Review (OMER).
О нас
Аннотация
Проблема коммивояжера (TSP) — важная проблема в управлении операциями. Применение TSP появляется в задачах маршрутизации, но также встречается во множестве других областей, таких как планирование рабочих мест и даже в спорте. В этой статье представлено учебное упражнение, в котором небольшой экземпляр задачи коммивояжёра решается до оптимального уровня. Упражнение выполняется в программе для работы с электронными таблицами Microsoft Excel с установленной по умолчанию надстройкой Solver. Эта статья считается первой демонстрацией использования Excel и Solver для решения задачи коммивояжера с использованием ограничений и переменных Миллера, Такера и Землина, исключающих подтур. Также представлены предложения по освещению тем, связанных с задачей коммивояжёра, и пример задачи, подходящей для домашнего задания или экзамена. Это тематическое исследование было рассмотрено редакционным советом журнала Operations Management Education Review (OMER).
Связанные
The Case Center — это некоммерческая компания с ограниченной ответственностью, зарегистрированная в Англии под номером 1129396 и внесенная в Реестр благотворительных организаций под номером 267516.
НДС № GB 870 9608 93. Это также торговое название. The Case Center USA, некоммерческой компании. ИНН 04-31-43431.
Цель этой статьи — показать, как использовать ограничение "Все разные" в программе "Поиск решения" в MS Excel для решения задачи коммивояжера (TSP). Предыдущее исследование по этой теме использовало ограничение «Все разные» в сочетании с функцией ИНДЕКС в MS Excel для выбора кратчайшего пути, который достигает всех клиентов. В этой статье предлагается другой подход к решению TSP с помощью инструмента MS Excel Solver с использованием функции ВПР. Ограничения по минимальному расстоянию пути и однократному посещению каждого места выполняются. Решение TSP дается как следствие мест, которые можно посетить. Практическое применение предлагаемого подхода находится в сфере дистрибуционной и транспортной логистики. Пример, описанный в этой статье, является инновационным. Он может использоваться другими исследователями и коммерческими организациями для расширения своих программных продуктов путем адаптации предложенной технологии.
Откройте для себя мировые исследования
- 20 миллионов участников
- 135 миллионов публикаций
- Более 700 тыс. исследовательских проектов
U radu se razmatra određivanje optimalne rute po turističkim atrakcijama. Na primjeru odabranih deset atrakcija u gradu Puli, dokazuje se da je problem optimalne rute rješiv modeliranjem po uzoru na model putućega trgovačkog predstavnika (TSP) te primjenom evolucijske methode. Postavljeni проблема odnosi se на određivanje pješačke rute i modeliran je iz perspektiva minimizacije udaljenosti i minimizacije vremena potrebnog za obilazak. Prikaz rješavanja korištenjem MS Excela upućuje na mogućnost jednostavne i intuitivne pripreme podataka za analizu te relativno brzog utvrđivanja rješenja. Rezultati upućuju na mogućnosti upotrebe pri organizaciji obilaska u turističkoj destinaciji, prednosti i nedostatke primijenjene methode, ali i prednosti upotrebe kvantitativnih metoda uupravljanju turističkim attrakcijama. Uočena flexibilnost primjene rezultata otvara mogućnosti daljnjeg obogaćivanja modela, ali i daljnji razvoj u obliku integracije u sustav potpore u upravljanju destinacijom kvantitativnim methodama, uz doprinos održivosti turizma destinacije.
Сокращение расстояния службы доставки от распределительного центра до дочерних компаний может быть достигнуто за счет хорошо управляемой маршрутизации, известной как проблема маршрутизации транспортных средств VRP. Это исследование было проведено в пищевой промышленности PT. XYZ. Для получения минимального расстояния между распределительным центром и торговыми точками в Жабодетабекском районе использовались два метода: алгоритм Cluster First Route Second и линейное программирование. Второй метод первого маршрута кластера был улучшен с помощью линейного программирования-решателя. Усовершенствованный метод показывает, что 774,18 км лучше, чем второй маршрут кластера Firs, 832,19 км, который короче на 6,97%. Ключевые слова: кластер задач маршрутизации транспортных средств первый маршрут второй гибридный маршрут программирование
Задача коммивояжера (TSP) – это хорошо известная бизнес-задача, и такие ее варианты, как TSP с максимальной выгодой или TSP со сбором цен, могут иметь множество экономических применений. Мы рассматриваем несколько различных вариантов TSP; все решено в электронных таблицах, без использования специализированных решателей для TSP. Поскольку эти задачи являются NP-сложными, решение тех, которые используют стандартные LP/MIP-решатели, считалось возможным только для очень небольших задач. Однако тщательное рассмотрение структуры электронной таблицы может способствовать эффективному использованию программного обеспечения. Для задач реального мира это может иметь значительные последствия, и с последними достижениями в решателях проблемы, ранее считавшиеся большими, теперь легко решаются в электронных таблицах. В этой статье показано, как; и как гибкость электронных таблиц делает их удобным инструментом для решения многих вариантов TSP, где специализированные решатели просто не подходят.
Задачи коммивояжера (TSP) десятилетиями были очень важной темой для изучения операционными исследователями и математиками. Достижения компьютерного оборудования и программного обеспечения в последние годы предоставили несколько альтернативных подходов к этой классической комбинаторной задаче. Цель этой статьи — представить подход к задачам коммивояжера с использованием Microsoft Excel Solver и платформы Premium Solver. В статье показан подход к решению, который эффективно решает небольшие задачи коммивояжёра.
Рекомендации
«Разработка инновационной методики преподавания бизнес-информатики
ИТ-решения для управления бизнес-процессами
Цифровизация экономики в среде больших данных (DEBD)
Цифровизация и цифровые компетенции – тренды и инновационные практики в сфере высшего образования и на рынке труда
Целью проекта является изучение, сопоставление и систематизация мнений и оценок широкого круга заинтересованных сторон (организаций работодателей и профсоюзов, некоммерческих юридических лиц, высших учебных заведений, образовательных и академических учреждений, волонтерских организаций) в отношении наиболее значимые вопросы, связанные с влиянием цифровизации на рынок труда и высшее образование. На этой основе следует наметить возможности и выдвинуть ориентиры на повышение эффективности управления и законодательного регулирования соответствующих процессов и отношений. В частности, ожидаемый результат включает в себя предложения заинтересованным сторонам по улучшению взаимодействия и достижению синергии в рамках усилий, предпринимаемых несколькими учреждениями, а также предложения по изменению правового регулирования трудовых отношений, социальной защиты и страхования работающих лиц в Болгарии в условиях цифрового общества. . [подробнее]
Целочисленное программирование: логические ограничения
В этой главе расширено использование двоичных переменных в связи с отношениями, которые называются логическими ограничениями; ограничения ограничивают рассмотрение определенными комбинациями переменных. Линейные целевые функции предполагают строгую пропорциональность: в частности, затраты, связанные с деятельностью, пропорциональны уровню деятельности. Сама модель целочисленного программирования представляет собой файл . [Показать полный текст] Вариант включения фиксированных затрат и использования связывающих ограничений. Модель местоположения объекта можно рассматривать как стратегическую версию транспортной задачи в том смысле, что расположение склада или распределительного центра (ЦЦ) рассматривается как заданное в транспортной задаче, но как выбор в задаче размещения объекта. Приложения задачи коммивояжера (TSP) часто встречаются в производстве и логистике, и некоторые очень мощные методы решения, адаптированные к TSP, были разработаны для многократного использования или для работы с особенно большими версиями. Проблема расположения объекта; целочисленное программирование; Задача коммивояжера
Введение
Цель этой статьи — продемонстрировать решение задачи коммивояжёра (TSP) с помощью метаэвристики в Microsoft Excel. Проблема может быть сформулирована следующим образом:
"Учитывая список городов и расстояния между каждой парой городов, каков кратчайший возможный маршрут, который проходит через каждый город ровно один раз?"
Это хорошо изученная NP-сложная задача комбинаторной оптимизации. Если N — количество городов, возможное решение дается как перестановка от 1 до N, указывающая порядок посещения городов. Для ее решения будет использоваться общий генетический алгоритм для задач перестановки (PermGA) xlOptimizer.
В этой статье предполагается, что вы прочитали и поняли процедуры, описанные в игрушечных задачах. К ним относятся оптимизация с использованием чистых формул Microsoft Excel и оптимизация с использованием VBA (Visual Basic для приложений).
Шаг 1. Настройка электронной таблицы
Мы уже создали для вас электронную таблицу. Хотя он настроен на 10 городов (чтобы его можно было использовать с демонстрационной версией надстройки xlOptimizer), вы можете легко изменить количество городов, изменив ячейку B1 и нажав кнопку «Случайный выбор городов». Столбец F содержит текущее решение, то есть порядок посещения городов.
Оценка общего расстояния для текущего выбранного маршрута выполняется специальной процедурой VBA, т. е. Sheet1.UpdateXYDistance. Код можно проверить, если вы создадите редактор VBA (нажав Alt+F11). Обратите внимание, что реализация не включает обратный путь из последнего города в первый, но код можно легко изменить.
Шаг 2. Настройка целевой функции
Выберите ячейку I2. Это содержит нашу целевую функцию, то есть общее расстояние текущего выбранного маршрута. На ленте xlOptimizer нажмите Цели, чтобы открыть список целей. Затем нажмите кнопку «Добавить» «+»:
По умолчанию цель установлена на минимизацию. Нажмите кнопку Цели на ленте еще раз, чтобы скрыть список целей.
Шаг 3. Настройка переменных дизайна
Выберите желтые ячейки столбца F. Они содержат переменные нашего дизайна, т.е.е. порядок городов.
На ленте xlOptimizer нажмите Переменные дизайна, чтобы открыть список переменных дизайна. Затем нажмите кнопку «Добавить» «+», чтобы добавить ячейки в список:
Нет необходимости изменять свойства переменных проекта. При выборе PermGA все ячейки будут содержать перестановку целых чисел (от 1 до N, где N — количество проектных переменных). Нажмите кнопку "Переменные проекта" еще раз на ленте, чтобы скрыть список переменных проекта.
Шаг 4. Настройка ограничений
В настоящей реализации нет ограничений, связанных с проблемой TSP. Вы можете добавить любые ограничения, которые вам нравятся, изменив код и добавив штраф к целевой функции (т. е. искусственно увеличив общее расстояние маршрута) или используя список ограничений xlOptimizer.
Например, можно настроить список барьерных линий, определяемых координатами их начальной и конечной точек, чтобы маршрут не пересекал их. Однако это выходит за рамки данной статьи.
Шаг 5. Настройка последовательности выполнения
На ленте xlOptimizer нажмите Последовательность выполнения, чтобы открыть список команд выполнения. По умолчанию отображается одна команда Calculate. Это вызов внутренней процедуры вычислений Microsoft Excel, которая оценивает такие формулы, как «=СУММ(C2:C6)». Наша пользовательская подпрограмма обрабатывает все, поэтому мы можем заменить ее вызовом макроса подпрограммы Sheet1.UpdateXYDistance:
Нажмите "ОК", чтобы сохранить изменения. Нажмите кнопку Последовательность выполнения еще раз на ленте, чтобы скрыть список последовательности выполнения.
Шаг 6. Настройка сценария оптимизации
На ленте нажмите кнопку Сценарий оптимизации. Затем нажмите кнопку «Добавить» «+» на панели инструментов, чтобы добавить новый сценарий. Появится следующая форма:
Выберите PermGA (перестановка) в качестве решателя. Это назначит перестановки всем активным переменным проекта (целые числа от 1 до N). Кроме того, выбор метода кроссовера Order лучше работает с TSP. Сделайте соответствующий выбор и нажмите Ok. Сценарий будет добавлен в список.
Ввод данных завершен. На ленте снова нажмите кнопку Сценарий оптимизации, чтобы скрыть список.
Шаг 7. Оптимизация
Теперь мы можем перейти к оптимизации, нажав кнопку Запустить активный сценарий.
Файл для этого примера можно скачать здесь. Обратите внимание, что сохраняется книга с поддержкой макросов с расширением .xlsm. Для его запуска необходимо включить макросы.
Человек хочет объехать все города. Путешествие начнется из города, причем каждый город будет посещен только один раз, и вернется в исходный город после посещения всех городов. Цель состоит в том, чтобы свести к минимуму расстояние/стоимость поездки.
Задача TSP очень популярна в области компьютерных наук. Впервые он был определен в 1800 году. Проблема TSP трудно разрешима. Это NP-сложная задача. Это означает, что если есть n городов для путешествия, существует (n-1) факторных возможностей для последовательности путешествий. Предполагая одинаковое расстояние для обоих направлений движения между двумя городами, для задачи с 10 городами нужно будет попробовать 9!/2 или 181 440 комбинаций.
Полная формулировка TSP с исключением подцикла может быть записана следующим образом:
Давайте попробуем решить проблему 10 столиц АСЕАН. Это относительно большая проблема, но благодаря современному мощному компьютерному оборудованию и программному обеспечению мы можем решить ее даже с помощью Excel Solver.
Расстояния между городами следующие.
| Страна | Столица | Аэропорт | BWN | PNH | CGK | VTE | KUL | NYT | MNL | SIN | BKK | HAN |
| Бруней | Бандар Сери Бегаван | BWN | 1330 | 1534 | 1977 | 1487 | 2603 | 1255 | 1278 | 1833 | 2060 | |
| Камбоджа | Пномпень | PNH | 1330 | 1975 | 757 | 1038 | 1289 | 1782 | 1138 | 504 | 1081 | Индонезия | Джакарта | CGK | 1534 | 1975 | 2719 | 1129 | 3083 | 2788 | 882 | 2297 | 3042 |
| Лаос | Вьентьян | VTE | 1977 | 75 7 | 2719 | 1697 | 694 | 2007 | 1857 | 517< /td> | 495 | |
| Малайзия | Куала-Лумпур | KUL | 1487 | 1038 | 1129 | 1697 | 1970 | 2490 | 297 | < td>12212102 | ||
| Мьянма | Нейпьидо | NYT | 2603 | 1289 | 3083 | 694 | 1970 | 2696 | 2202 | 819 | 1016 | |
| Филиппины | Манила | MNL | < td>12551782 | 2788 | 2007 | 2490 | 2696 | 2375 | 2188 | 1773 | ||
| Сингапур | Сингапур | SIN | 1278 | 1138 | 882 | 1857 | 297 | 2202 | 2375 | 1417 | 2218 | |
| Таиланд | Бангкок | БКК | 1833 | 504 | 2297 | 517 | 1221 | 819< /td> | 2188 | 1417 | 995 | |
| Вьетнам | Ханой | HAN | 2060< /td> | 1081 | 3042 | 495 | 2102 | 1016 | 1773 | 2218 | 995 |
Мы вводим эти данные в электронную таблицу Excel. Мы также устанавливаем прямоугольную область в Excel, которая будет использоваться в качестве переменной решения в модели.
Требуемые формулировки и именованные диапазоны показаны ниже.
Нам нужно включить Excel Solver, прежде чем мы сможем его использовать. В Excel выберите «Файл», затем «Параметры». Выберите надстройки. После этого появится диспетчер надстроек. В нижней части экрана нажмите переключатель «Перейти» рядом с «Управление надстройками Excel». Установите флажок Надстройка Solver, и Solver будет включен. Чтобы получить доступ к Решателю Excel, перейдите в раздел «Данные» и появится переключатель «Решатель».
Математическая формулировка TSP частично находится в ячейках электронной таблицы. Нам нужно ввести целевую ячейку, переменные решения и ограничения в диалоговое окно Excel Solver, как показано ниже.
Нажмите "Решить", чтобы получить решение, как показано ниже.
Вышеприведенное решение можно изобразить графически, как показано ниже:
Формулировку из учебника TSP можно применять непосредственно для решения реальных задач. В электронной сборке TSP используется для минимизации перемещения буровой головки во время сверления печатных плат и времени размещения компонентов на станках для поверхностного монтажа. Расширенная версия модели TSP используется транспортными компаниями для определения маршрутов вывоза и доставки транспортных средств.
Пожалуйста, пришлите мне электронное письмо, если вы хотите узнать больше об этом и хотите получить модель TSP Excel Solver.
Найти нас
Адрес
Эксперт по оптимизации PLT
(LLP0010370-LGN)
9 Солок Букит Джамбул
11900 Баян Лепас
Пенанг, Малайзия
Читайте также: