Моделирование проблемы путешествующего продавца с нуля

Создание идеального образа для путешествующего продавца моделируем проблему с нуля

Концепция впереди, математика вторична: моделирование наиболее известной проблемы маршрутизации в исследовании операций

👁️ Это статья №2 из серии, посвященной проекту «Интеллектуальная система поддержки принятия решений для туризма на Python». Рекомендую вам ознакомиться с ней, чтобы получить общую представление о всем проекте. Если вас интересует только моделирование TSP, то вы находитесь в правильном месте, так как эта статья самодостаточна. Если вас также интересует решение проблемы, а не только ее моделирование, то вы полюбите следующие 5 статей серии. Поверьте мне, они предоставят вам все, что вам нужно и то, о чем вы не знали 😉

Содержание

1. Мотивация и цель

2. Понимание данных

3. Определение концептуальной модели на основе описания проблемы

4. Построение математической модели на основе концептуальной модели

• 4.1. Помещение данных в множества и параметры
• 4.2. Кодирование решений в переменные
• 4.3. Определение цели
• 4.4. Установка ограничений

1. Мотивация и цель

Эта статья продолжает там, где закончилась статья для спринта 1. Вам не обязательно читать ее, чтобы понять, что мы делаем здесь, но позвольте мне дать вам краткое изложение (если вы уже прочитали предыдущую статью, вы можете перейти к разделу 2). Вкратце, мы определили основные проблемы, с которыми сталкиваются туристы при планировании поездки, и решили создать систему, которая может помочь нам более эффективно планировать поездки, ускоряя принятие решений или даже полностью автоматизируя расписание для любой поездки. Мы заметили, что в такой формулировке проблема слишком сложна, поэтому мы разбили ее на более простую версию, которую назвали минимально ценной проблемой. В конце мы пришли к выводу, что она принимает форму проблемы коммивояжера (TSP), где «города», которые должен посетить поговоривший коммивояжер, соответствуют, в нашей версии, «достопримечательностям» в городе, которые турист хочет посетить.

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

Вернемся к нашим делам, у нас есть описание проблемы TSP:

• Самая сложная часть определение цели для классификации
• Все, что вам нужно знать, чтобы развиваться, используя большие языковые модели.
• Введение в энтропию и индекс Джини

• Цель: пройти минимальное расстояние пути
• Требования: посетить каждое место только один раз и вернуться в исходное место отправления (в нашем случае – отель).

Поскольку мы знаем, что эта проблема не наша реальная проблема, а лишь простое приближение к ней, мы хотим построить модель проблемы, так как модель можно уточнять, дополнять и настраивать. И мы знаем, что нам придется делать это для решения нашей реальной проблемы. Поэтому нашей целью является построение модели, в отличие от поиска непосредственного решения или разработки некоего эвристического алгоритма, который найдет решение за вас. Когда вы научитесь логически представлять такую модель, у вас будет хорошее представление для изучения статьи следующего спринта, где мы реализуем модель на Python.

2. Понимание данных

Если вы помните из нашего последнего спринта, основным входным параметром для задачи TSP является просто список мест, которые мы хотим посетить в один день. В этом концептуальном проекте мы выбрали Париж, поэтому я выбрал восемь известных и обязательных для посещения мест:

• Сакре-Кер
• Лувр
• Монмартр
• Порт де Сюффрен
• Триумфальная арка
• Авеню Шанз-Элизе
• Нотр-Дам
• Эйфелева башня

Поскольку цель состоит в том, чтобы найти маршрут с минимальным расстоянием, реальные данные, которые нам нужны, – это данные о расстоянии, которые зависят от мест и их относительного географического расположения. Как вычислить данные о расстоянии от географических мест будет рассмотрено в 4-м спринте, поскольку рассмотрение этой темы сейчас отведет нас от главной цели – построения модели.

Итак, на данный момент предполагается, что вам даны расстояния между всеми возможными парами мест. Они будут представлены в виде CSV-файла в следующем спринте, когда мы реализуем модель на Python. Данные выглядят следующим образом:

Мы будем называть эту таблицу матрицей расстояний. Обратите внимание, что хотя они могут быть не особенно привлекательными для открыток, в таблицу также включен отель, так как он также является местом, которое должно быть в конечном маршруте. Для этого минимального рабочего варианта мы просто используем симметричную матрицу расстояний, что означает, что расстояние от 𝐴 до 𝐵 такое же, как расстояние от 𝐵 до 𝐴, для любых A и B. В более сложных случаях это может не быть важным в достаточной степени, делая эту аппроксимацию неэффективной.

3. Определение концептуальной модели на основе описания проблемы

Теперь мы находимся на этапе, представленном зеленым блоком на схеме ниже:

Целью концептуальной модели является сформулировать проблему с использованием слов, но в стандартизированном формате, чтобы связь между “предложениями” и “математическими объектами” стала понятной в следующей фазе (формирование математической модели). Мы можем сформулировать нашу концептуальную модель следующим образом:

(Знание)

Исходные данные (наборы и параметры):

• Список мест для посещения
• Расстояние между любой парой мест

(Нам нужно принять решение)

Решение: В каком порядке посещать места

(Так, чтобы мы)

Цель: Минимизировать общее пройденное расстояние

(При условии)

Ограничения:

• Все места посещены
• Каждое место посещается только один раз
• Последнее посещенное место – это место, с которого мы начали (мы делаем закрытый маршрут)

👁️ Следуйте хорошим практикам, и, на практике, доброта последует за вами

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

4. Создание математической модели на основе концептуальной модели

Мы только что достигли “этапа 3” рабочего процесса, который обозначен зеленым цветом ниже. “Этап создания математической модели“, вероятно, самый сложный этап из всех, это то место, где естественный язык становится математикой.

Именно на этом этапе не допускается ни малейшей степени неоднозначности.

Хорошо определенная математическая модель стоит сотню пояснений

На этом этапе нашего рабочего процесса мы строим чистую модель для TSP, а в следующей фазе (рассматривается в “этапе спринта 3”) мы создадим экземпляр модели из CSV-набора данных, который мы ранее объяснили, с помощью Python.

📝 Напоминание о теории: “абстрактная модель” против “экземпляра модели”

Математические модели (в ОР) состоят из “компонентов”. Это все элементы (уравнения, данные и т. д.), которые коллективно представляют проблему определенной структуры. То, что действительно определяет модель, это ее структура, т. е. то, как эти компоненты относятся друг к другу, независимо от конкретных числовых значений, которые эти компоненты принимают в любом конкретном примере.

Экземпляр модели является конкретной “материализацией” “абстрактной модели” с конкретными данными. Таким образом, мы обычно определяем абстрактные модели, а затем заполняем их данными о конкретных сценариях, что приводит к получению экземпляров моделей. Именно эти экземпляры моделей мы оптимизируем, чтобы получить конкретные результаты.

В подразделах ниже я кратко описываю компоненты, составляющие модель, и их цели, пока их определяю. Если вы уже являетесь опытным пользователем и уже знаете функции компонентов модели, можете пропустить эти объяснения и перейти непосредственно к математическим определениям.

4.1. Помещение данных в Наборы и Параметры

Все данные, которые нам требуются, находятся в таблице, отображенной на рисунке 2.1. Мы могли бы хранить данные только там, извлекая все числа из этой таблицы при создании ограничений и цели модели. Фактически, многие используют этот подход, но это плохая привычка, которая плохо масштабируется с ростом размера модели. По мере увеличения сложности модели, этот подход требует все более клеевого кода (для работы с операциями над таблицами), который можно избежать, если данные будут храниться систематизировано в других структурах данных, более подходящих для создания оптимизационных моделей. Эти структуры данных – это наборы и параметры модели.

💡 Различные структуры данных для разных целей

Возможно, вам интересно, “Почему создавать наборы и параметры, когда у нас уже есть нужные данные в таблице?”, краткий ответ таков: потому что это упрощает создание модели, делает ее более общей и защищает от ошибок.

“Наборы” – это компоненты модели, используемые для хранения основных “сущностей” или “элементов” проблемы, в то время как “параметры” используются для хранения числовых свойств этих сущностей или их взаимоотношений. В нашем примере сайты являются основными “сущностями”, поэтому они будут храниться в наборе, а расстояния между парами сайтов – “числовые свойства” их взаимоотношений, поэтому они будут храниться в виде параметров. На уровне реализации это также очень полезно, потому что каждый компонент выполняет разные функции, которые облегчают создание модели:

• Функция наборов – это удобное хранение и манипулирование индексами. Эти индексы представляют собой идентификаторы или имена, которые представляют различные “сущности” проблемы, и они используются для индексации параметров удобным способом для создания ограничений и целей.

• Функция параметров – это удобное хранение и манипулирование числовыми свойствами “сущностей”, по которым они индексируются, и это числа, которые действительно присутствуют в ограничениях и целях.

Из нашей концептуальной модели у нас есть:

• Список сайтов для посещения, который мы определяем как множество 𝕊:

Фраза “индексированная с помощью 𝑖, 𝑗” расположена рядом с определением множества, чтобы указать на то, что при использовании индексов 𝑖 или 𝑗 в модели они представляют собой элементы 𝕊. Таким образом, когда у нас есть несколько множеств и, следовательно, несколько используемых индексов, легче помнить, что каждый индекс означает.

• Расстояние между любой парой сайтов, которое мы определяем как индексированный параметр 𝐷ᵢⱼ:

Параметр называется “индексированным”, просто чтобы указать, что это не скалярный параметр (т.е. одно число), а 2-мерная матрица чисел. Чтобы получить число из этого индексированного параметра, вам нужно указать два индекса, 𝑖 и 𝑗, которые, в свою очередь, будут взяты из множества 𝕊.

𝕊 и 𝐷ᵢⱼ – единственные “компоненты данных”, присутствующие в концептуальной модели. Но это не должно ограничивать нашу способность создавать другие множества или параметры, которые оказываются полезными при построении модели.

В качестве иллюстрации, обратите внимание, что индексы 𝐷ᵢⱼ, 𝑖 и 𝑗, являются членами 𝕊, но не могут совпадать. Если бы они совпали, расстояние было бы равно нулю, что является тривиальным значением. Кроме того, мы никогда не пошли бы от одного места к самому себе, поэтому нет смысла рассматривать пары (𝑖, 𝑖) вообще. Таким образом, полезно ограничить комбинации, которые могут принимать пары (𝑖, 𝑗), чтобы моделирование стало проще (и вероятность ошибок меньше). С этой целью мы создаем другое множество, 𝔸, полученное из 𝕊, которое содержит все пары (𝑖, 𝑗) разных сайтов. Каждая пара представляет собой дугу, соединяющую сайт 𝑖 с сайтом 𝑗, отсюда и символ 𝔸.

📝 Дуга – это просто “направленная связь” между двумя узлами “сети”. Просто представьте себе дугу (𝑖, 𝑗) как вектор, начинающийся в 𝑖 и заканчивающийся в 𝑗. Когда “связь” между двумя узлами не направлена (т.е. направление неважно), используется слово “ребро”, как сказать “ненаправленная дуга” каждый раз было бы слишком многословно. Людям в теории графов тоже нравится быть эффективными.

Хорошим свойством 𝔸 является то, что это область, на которой определено 𝐷ᵢⱼ и это делает его многократно используемым для других компонентов модели и это тоже удобно.

• Множество возможных дуг между разными сайтами:

4.2. Кодирование решений в переменных

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

Но как определить такие потенциальные действия? Исходя из нашей концептуальной модели, общим “решением”, которое нам нужно принять, является “порядок посещения сайтов”. Этот “порядок” относится к одному пути из всех возможных путей, которые мы могли бы выбрать при посещении. Ключевая идея заключается в том, что путь состоит из последовательности дуг, соединяющих отдельные узлы (то есть, сайты). Поэтому решение выбрать определенный путь фактически означает решение пройти определенную последовательность дуг. Эти “атомные решения” о том, следовать или нет по конкретной дуге, соединяющей два сайта – это решения, которые мы хотим закодировать в виде переменных.

“Идти ли от сайта A к сайту B” – явно бинарное решение: либо я иду, либо нет. В связи с этим, переменные решения должны быть бинарными (то есть принимать только значения 0 или 1) и определены только для допустимых дуг (для которых теперь полезно производное 𝔸). В математическом отношении:

У каждой возможной дуги (𝑖, 𝑗) есть единственная переменная решения, но при оптимизации модели нас интересуют только переменные, принимающие значение 1, потому что они указывают, какие дуги следует пройти. Например, если переменная 𝛿ᵢⱼ, с 𝑖=отель и 𝑗=Лувр, равна 1, это означает, что мы должны отправиться из отеля в Лувр в рамках нашего тура.

4.3. Определение цели

Представьте, что у нас есть 4 точки, 𝑎, 𝑏, 𝑐, 𝑑, и мы следуем пути 𝑎 → 𝑏 → 𝑐, при котором точка 𝑑 не посещается. Его общее расстояние равно сумме расстояний его дуг: 𝐷ᵃᵇ + 𝐷ᵇᶜ. Но если мы не знаем заранее, какой путь пройдем, как мы можем представить общее расстояние этого неизвестного пути?

💡 Именно потому что оптимальный путь неизвестен, нам нужно выражение, охватывающее все возможные пути, но которое сокращается до расстояния “лучшего пути” при оптимизации модели.

Используя факт, что любая пройденная дуга (𝑖, 𝑗) будет иметь 𝛿ᵢⱼ = 1, а любая непройденная дуга (𝑖′, 𝑗′) будет иметь 𝛿ᵢᑊⱼᑊ = 0, мы можем создать выражение, которое, после принятия решения относительно переменных, сократится до общего расстояния пройденного пути. Способ сделать это – “сложить все потенциалы”, то есть, выполнить суммирование по всем возможным расстояниям между дугами 𝐷ᵢⱼ, взвешенным их бинарными “переменными дуг” 𝛿ᵢⱼ, и позволить 0 и 1 определить, какие расстояния остаются (𝐷ᵢⱼ × 1 = 𝐷ᵢⱼ) и какие исчезают (𝐷ᵢⱼ × 0 = 0) в выражении для общего расстояния. Это “суммирование потенциалов” представляет общее расстояние, которое займет конечный тур, поэтому это будет наша цель (обозначается 𝑍) для минимизации.

Математически это выражается следующим образом:

Обратите внимание, что суммирование справа стало проще для чтения (и реализации) благодаря использованию 𝔸, области (множеству индексов) как для 𝐷ᵢⱼ, так и для 𝛿ᵢⱼ.

Также обратите внимание, что цель составляет наше определение добра. Поскольку мы хотим минимизировать ее, более низкое значение лучше высокого значения, так что очевидно, минимальное значение – это лучшее значение. Значения решающих переменных 𝛿ᵢⱼ, которые соответствуют этому “лучшему” значению цели, составляют (оптимальное) решение проблемы и будут найдены процессом оптимизации.

4.4. Создание ограничений

Из нашей концептуальной модели у нас есть:

1. Посещаются все сайты.
2. Каждый сайт посещается только один раз.
3. Последний посещенный сайт – это сайт, с которого мы начали (мы делаем замкнутый тур).

Мы понимаем, что требование (1) уже “включено” в требование (2), поскольку если каждый сайт посещается только один раз, это включает в себя и посещение каждого сайта, и, следовательно, все сайты посещены. Поэтому мы отказываемся от необходимости отдельного ограничения для требования (1) и сосредотачиваемся на том, как смоделировать требование (2) в качестве ограничения.

Сказать, что “каждый сайт посещается только один раз”, то же самое, что сказать, что “каждый сайт входит и выходит только один раз”. И эта фраза, в свою очередь, эквивалентна двум этим фразам вместе: “каждый сайт входит только один раз” и “каждый сайт выходит только один раз”. Давайте смоделируем “фразы” отдельно:

• Каждый сайт входит только один раз:

Полезно прочитать всё выражение справа налево. Если сначала вы видите, над какими индексами определено ограничение, проще будет интерпретировать значение ограничения слева. Я бы вслух прочитал это ограничение следующим образом:

для каждого сайта 𝑗, принадлежащего множеству всех сайтов 𝕊, сумма всех потенциальных дуг 𝛿ᵢⱼ, прибывающих в 𝑗, должна быть равна 1, что означает, что только одна входящая дуга должна произойти в 𝑗. Или, более разговорно: каждый сайт должен быть посещен только из одного другого сайта.

• Каждый сайт выходит только один раз:

Я бы прочитал это ограничение следующим образом:

для каждого сайта 𝑖, принадлежащего множеству всех сайтов 𝕊, сумма всех потенциальных дуг 𝛿ᵢⱼ, выходящих из 𝑖, должна быть равна 1, что означает, что только одна исходящая дуга должна произойти в 𝑖. Или, более разговорно: каждый сайт должен отправляться только в одно другое место.

У нас осталось только требование (3). Оно утверждает, что оптимальный путь должен заканчиваться там, где начался, или, иначе говоря, путь должен быть туром (замкнутым циклом). Вот возможный логический ход, который можно иметь с первого взгляда: «Поскольку мы уже создали ограничения, чтобы обеспечить, что каждый сайт входит и выходит один раз, это означает, что полученный путь должен быть замкнутым, поскольку невозможно, чтобы любой сайт был»стоком« (т.е. у сайта только входящая дуга, но нет исходящих дуг) или» источником «(т.е. у сайта есть исходящая дуга, но нет входящих дуг). Следовательно, предыдущие два ограничения, предположительно, заставляют окончательную траекторию быть замкнутым циклом».

Это логическое рассуждение правильное? Давайте попробуем экспериментальный подход. Допустим, это логическое рассуждение верное и попытаемся решить модель так, как она сейчас выглядит. Когда мы посмотрим на решение, мы увидим, выглядит ли оно правильным или есть что-то не так. Если результаты неверные (или не имеют смысла), мы всегда можем вернуться назад и пересмотреть нашу логику (что происходит постоянно в реальных проектах). Реализация, решение и “экспериментальная проверка” включены в нашу “следующую спринтовую задачу”, где создается, решается, проверяется и переформулируется Python-модель на основе полученных результатов.

Таким образом, мы заключаем (предварительно) этап “формулировки математической модели”. Следующий этап: “реализация компьютерной модели“, который выполняется в Реализация, решение и визуализация задачи коммивояжера с использованием Python.

Будут также представлены другие статьи о других “спринтах”, поэтому если вы хотите быть моим спутником в этом путешествии, оставайтесь на связи и проверьте график проекта в разделе 3 первой статьи в этой серии, чтобы перейти к нужному спринту и следить за проделанной работой там.

Также не стесняйтесь следовать за мной, задавать мне вопросы в комментариях, давать обратную связь или связаться со мной на LinkedIn.

Спасибо за чтение и увидимся в следующей статье! 📈😊

Ссылки:

• Википедия. Задача коммивояжера