В таких сферах, как исследование операций (Operations Research) и наука о данных (Data Science) чрезвычайно актуально сближение теории и её практического применения в виде программных проектов. Теоретические выкладки формируют базу программ для оптимизации чего‑либо, так как теория даёт средства для решения разнообразных задач. Но очень важно помнить и о том, что подобные программы должны быть доступны конечному пользователю, что с ними должно быть удобно работать.

Задача коммивояжёра (Traveling Salesman Problem, TSP) — это, без сомнения, та самая задача комбинаторной оптимизации, которая изучена лучше всего (Rego, C., Gamboa, D., Glover, F., & Osterman, C., 2011. Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211(3), 427–441). Её легко описать (по крайней мере — на словах), её можно использовать для того чтобы продемонстрировать некоторые из возможных компонентов API современной программы по построению маршрутов. В результате я просто не мог подобрать ничего лучше этой задачи в качестве основы для примера, который разобран в этой статье.

Здесь вы узнаете о том, как использовать Python‑библиотеку Streamlit для создания веб‑приложения, которое позволяет решать задачу коммивояжёра с использованием входных данных, предоставленных пользователем. Так как нас интересует создание приложения, пригодного для решения реальных задач, мы, анализируя пути перемещения между некими географическими точками, будем интересоваться не только евклидовым расстоянием между ними, но и другими характеристиками путей. В частности, наша программа, используя координаты точек, должна уметь получать данные о том, какое расстояние по автомобильным дорогам нужно преодолеть для перемещения между ними. Эти данные должны учитываться при выполнении оптимизации. Для этого мы воспользуемся API OpenStreetMap.

Если вы хотите лучше разобраться в теоретических аспектах числовой оптимизации — вам, возможно, интересно будет почитать мои статьи о линейном программировании и о задаче маршрутизации транспорта (это — обобщение задачи коммивояжёра).

Готовы поработать? Взгляните на то, что у нас должно в итоге получиться…

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

Задача коммивояжёра

Задача коммивояжёра заключается в поиске кратчайшего маршрута, соединяющего N точек. По мере того, как число рассматриваемых точек растёт, нахождение оптимального, или близкого к оптимальному решения становится очень непростым делом. Это так из‑за комбинаторной природы задачи.

Для решения задачи коммивояжёра нужно принимать во внимание попарные расстояния между элементами. Это справедливо для самых разных методов её решения — от точных, до эвристических и метаэвристических. Хотя в этом материале я и не буду подробно рассказывать о методах решения нашей задачи, я предлагаю вам считать, что функция, подходящая для реализации разных методов решения, обладает следующей сигнатурой:

solve_tsp(distances: np.ndarray) -> List[int]

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

Структура папки репозитория

Я применил простую одноуровневую структуру папки репозитория. Она содержит следующие элементы:

• .streamlit: здесь будут находиться общие настройки Streamlit.

• data: эта папка хранит наборы данных, используемые в ходе разработки. Они могут представлять собой обычные примеры данных для решаемой задачи.

• assets: в этой папке хранятся элементы, которые используются в главном скрипте. Среди них — изображения, логотипы и прочее подобное.

• optimizer: внутренний Python-пакет, используемый в приложении.

• app.py: главный скрипт Streamlit.

• Dockerfile: инструкции по сборке Docker-образа для приложения.

• requirements.txt: python-зависимости, необходимые для обеспечения работы приложения.

• README.md: описание проекта.

• .dockerignore и .gitignore: имена этих файлов подсказывают нам, что они содержат списки материалов, которые, соответственно, игнорируют Docker и Git.

tsp-app/
│
├── .streamlit/                # Общие настройки streamlit
│   └── config.toml
│
├── data/                      # Директория для данных, если таковые имеются
│   ├── dataset.csv
│   └── ...
│
├── assets/                    # Этим будет пользоваться приложение
│   ├── dataset.csv
│   └── ...
│
├── optimizer/                 # Внутренний пакет TSP-оптимизатора
│   ├── __init__.py
│   └── ...
│
├── app.py                     # Главный скрипт Streamlit
│
├── Dockerfile                 # Конфигурационный файл
├── .dockerignore
│
├── .gitignore                 # Файлы, игнорируемые в Git
├── requirements.txt           # Python-зависимости
└── README.md                  # Описание проекта

В более сложных приложениях могут использоваться отдельные пакеты для вспомогательных функций самого интерфейса Streamlite.

...
├── optimizer/                 # Внутренний пакет TSP-оптимизатора
│   ├── __init__.py
│   └── ...
│
├── interface/                 # Вспомогательные функции для интерфейса
│   ├── __init__.py
│   └── ...
│
├── app.py                     # Главный скрипт Streamlit
...

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

Прежде чем приступить к экспериментам, проверьте, чтобы в вашем Python‑окружении были бы установлены все необходимые зависимости:

pip install -r requirements.txt

При работе с приложением TSP можно столкнуться с конфликтами зависимостей. Поэтому рекомендуется устанавливать ortools отдельно, пользуясь опцией --no-deps.

pip install --no-deps ortools==9.7.2996

Используя предложенную плоскую структуру проекта, приложение можно запустить из корневой директории, выполнив в командной строке следующее:

streamlit run app.py

Ещё для запуска приложения можно собрать Docker-образ, воспользовавшись для этого файлом Dockerfile, который имеется в репозитории. Делается это такой командой:

docker build -t tsp_app:latest .

В этой команде tsp_app можно заменить на имя любого репозитория, а вместо версии latest можно использовать любую версию.

При использовании Docker запустить приложение можно так:

docker run -p 8501:8501 tsp_app:latest

Разберёмся теперь с тем, как устроен файл app.py.

Общая структура скрипта

Общую структуру скрипта app.py можно кратко описать следующим псевдокодом:

Команды импорта

Определения вспомогательных функций (могут быть в отдельном файле)
Объявления констант
Объявления атрибутов session_state, используемых по умолчанию
Парсинг параметров решателя
Парсинг входного файла

если входные данные не None:
    читать (и кешировать) входные данные

     если нажата кнопка запуска поиска решения (Optimize)
        решить задачу с использованием входных данных
        сохранить решение в виде атрибута session_state

если решение не None:
    сделать доступными выходные данные
    визуализировать результаты

Хотя всё тут может выглядеть простым, некоторые фрагменты этого псевдокода чрезвычайно важны.

При нажатии на кнопку Streamlit запускает код, связанный с этой кнопкой, выполняющийся при выполнении условия наподобие if st.button('Click me'):, и сбрасывает её состояние. Это говорит нам о том, что при работе с кнопками нужно следовать указаниям, данным в документации Streamlit. А именно, не надо вкладывать в условные конструкции, связанные с кнопкой, следующие элементы:

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

• Другие виджеты, которые при использовании вызывают перезапуск скрипта.

• Процессы, которые не модифицируют состояние сессии и не записывают данные в файл или базу данных.

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

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

Основные настройки проекта

Выше было сказано о том, что общие настройки Streamlit можно задавать в файле config.toml, который находится в директории.streamlit. В примере TSP я использовал этот файл для того чтобы задать цвета и шрифт. У меня получилось что‑то в светло‑фиолетовых тонах, а вы вполне можете попробовать другие цвета. Главное — описывать их, пользуясь шестнадцатеричными кодами цветов.

[theme]
primaryColor = "#5300A5"
backgroundColor = "#403E43"
secondaryBackgroundColor = "#1C1B1E"
textColor = "#F5F3F7"
font = "sans serif"
base = "dark"

Первым, что попадёт в файл app.py, будут команды импорта. Пакет os будет использоваться для работы с файлами в операционной системе. Пакетом BytesIO мы воспользуемся для того, чтобы организовать хранение загружаемого файла с выходными данными не на диске, а в памяти. Пакет json применяется для сериализации выходных данных программы, то есть — решения задачи. А List из typing — это всего лишь подсказка типа.

Для работы с датафреймами мы будем пользоваться pandas. Из пакета pyomo мы импортируем решатель Highs, с помощью которого и будем решать нашу задачу (в случае выбора стратегии оптимизации MIP). Пакет streamlit — это основа интерфейса приложения. Тут импортируются и дополнительные вспомогательные функции, определённые во внутреннем пакете.

import os
from io import BytesIO
import json
from typing import List

import pandas as pd
from pyomo.contrib.appsi.solvers.highs import Highs
import streamlit as st
from streamlit_folium import st_folium

from optimize.tsp import get_distance_xy, build_mip, solve_mip, TSP, plot_tour, request_matrix,\
    plot_map, get_coord_path

Атрибуты session_state будут хранить переменную tour для текущего решения, а так же — датафрейм pandas, соответствующий заданному входному файлу, значение, соответствующее решению, и координаты, описывающие маршрут (полученные из OpenStreetMap).

# Создание переменных для хранения текущего решения в виде атрибутов session_state
if "tour" not in st.session_state:
    st.session_state.tour = None

if "dataframe" not in st.session_state:
    st.session_state.dataframe = None

if "sol" not in st.session_state:
    st.session_state.sol = None

if "route_path" not in st.session_state:
    st.session_state.route_path = None

Вот некоторые из используемых здесь вспомогательных функций:

• driving_distances: применяется для получения матрицы расстояний из OpenStreetMap. Принимает датафрейм (тут важно кешировать результаты).

• upload_callback: сбрасывает атрибуты session_state при выгрузке в приложение нового файла с входными данными.

• update_path: принимает tour и получает географические координаты соответствующих автодорог для визуализации результатов.

# Поиск матрицы расстояний
@st.cache
def driving_distances(dataframe: pd.DataFrame):
    return request_matrix(dataframe)["distances"] / 1000


# Коллбэк выгрузки в приложение нового файла
def upload_callback():
    st.session_state.tour = None
    st.session_state.sol = None
    st.session_state.route_path = None


# Обновление маршрута после нахождения решения
def update_path(tour: List[int], dataframe: pd.DataFrame):
    coord_rt = dataframe.loc[tour, :]
    path = get_coord_path(coord_rt)
    st.session_state.route_path = path

Теперь настроим макет приложения. В следующем скрипте мы задаём значок и заголовок веб-страницы. Далее — мы назначаем тот же значок боковой панели и выводим текст приветствия. После того, как вы добавите в свой проект соответствующий код — советую вам выполнить команду streamlit run app.py и проверить то, как выглядит ваш вариант приложения на данном этапе работы.

# Путь к значку
icon_path = os.path.join("assets", "icon_tsp.png")

# Настройка параметров страницы и установка для неё "широкого" макета
st.set_page_config(
    page_title="TSP",
    page_icon=icon_path,
    layout="wide",
)

st.sidebar.image(icon_path)

st.title("TSP")
st.write("Welcome to the Traveling Salesman Problem solver.")

Одна из объявленных мной вспомогательных функций считывает содержимое файла README.md и занимается его выводом в том случае, если пользователь выбрал соответствующую опцию. Так как мне хотелось бы сделать так, чтобы условие, по которому выводятся эти данные, не зависело бы от возможных перезапусков скрипта, я, вместо элемента button, использую тут элемент selectbox.

display_tutorial = st.checkbox("Display tutorial")
if display_tutorial:
    section = st.selectbox("Choose a section", ["Execution", "Solutions", "Contact"], index=1)
    tutorial = read_section(section)
    st.markdown(tutorial)

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

Входные данные и параметры решателя

Я предусмотрел возможность использования входных данных в двух форматах:

• ‘xy’: используются евклидовы расстояния. Во входных данных должны быть столбцы ‘x’ и ‘y’.

• ‘lat-long’: используются расстояния, соответствующие длине дорог между точками. Во входных данных должны присутствовать столбцы ‘lat’ и ‘long’.

Я, кроме того, включил в программу два варианта настройки решателя, соответствующие различным стратегиям поиска решения:

• ‘MIP’: используются модели, созданные с помощью pyomo, для решения задачи применяется HiGHS.

• ‘Heuristic’: используются алгоритмы маршрутизации Google OR-Tools, применяются эвристические методы конструктивного и локального поиска с несколькими начальными точками.

Эти параметры, а так же сведения о том, сколько времени выделяется на работу решателя, будут размещены в боковой панели приложения с использованием следующего кода:

problem_type = st.sidebar.selectbox("Choose an input type:", ["xy", "lat-long"], index=0)
method = st.sidebar.selectbox("Choose a strategy:", ["MIP", "Heuristic"], index=0)
time_limit = st.sidebar.number_input("Time limit", min_value=0, value=5, step=1)

Для выгрузки файла в приложение будет использоваться функция file_uploader. Обратите внимание на то, что наша функция для сброса атрибутов session_state вызывается при обнаружении изменений, связанных с входными данными.

file = st.file_uploader("Upload input file", type=["csv"], on_change=upload_callback)

В том случае, если входной файл не является пустым (None), мы должны прочитать его и подготовить матрицу расстояний для её использования в ходе оптимизации…

if file is not None:
    dataframe = pd.read_csv(file)
    st.session_state.dataframe = dataframe
    distances = FORMATS[problem_type](dataframe)
    start_button = st.button("Optimize")

Обратите внимание на то, что ранее сущность FORMATS была определена в виде словаря с функциями, выбор которых зависит от типа задачи. Эти функции возвращают матрицу расстояний, пользуясь датафреймом. Соответствующие функции определены во внутреннем модуле и импортированы в приложение.

FORMATS = {
    "xy": get_distance_xy,
    "lat-long": driving_distances
}

Выполнение оптимизации

Для запуска оптимизации нужно нажать на кнопку Optimize. Это — тот случай, когда одному нажатию на кнопку соответствует один процесс. Тут проверяются некоторые условия, выбирается оптимизатор, который нужно использовать, а после завершения его работы результаты сохраняются в атрибутах session_state.

# Запуск производится в том случае, если была нажата кнопка start_button
if file is not None and start_button:

    # Решение задачи с помощью MIP
    if method == "MIP":
        solver = Highs()
        solver.highs_options = {"time_limit": time_limit}
        model = build_mip(distances)
        tour = solve_mip(model, solver)
        st.session_state.tour = tour

    # Решение задачи с помощью эвристического метода
    elif method == "Heuristic":
        model = TSP(distances)
        tour = model.solve(time_limit=time_limit)
        st.session_state.tour = tour

    # Вывод результатов
    sol = model.obj()
    st.session_state.sol = sol

    # Обновление маршрута при использовании входных данных в формате lat-long
    if problem_type == "lat-long":
        update_path(tour, dataframe)

В ходе выполнения этих вызовов функций можно воспользоваться дополнительными виджетами. Например — при выполнении оптимизации можно проинформировать пользователя о ходе решения задачи, показав ему Streamlit-элемент spinner или progress.

А затем, за пределами кода, связанного с проверкой условий, относящихся к кнопке, можно сделать выходные данные доступными пользователю, основываясь только на факте их существования.

# Нахождение текущих переменных, хранящихся в session_state
sol = st.session_state.sol
tour = st.session_state.tour
dataframe = st.session_state.dataframe

if sol is not None and tour is not None:
    col_left, col_right = st.columns(2)  # Разделение данных на две колонки
    col_left.write(f"Current solution: {sol:.3f}")
    col_right.download_button(
        label="Download Output",
        data=json.dumps(tour),
        file_name='output.json',
        mime='json',
    )

В этом простом примере мы делаем доступным пользователю json-файл, содержащий описание последовательности точек, посещённых при обходе точек из входных данных. Если нам нужно готовить выходные данные в более сложном формате, например — в виде Excel-файла, интересной альтернативой может стать использование BytesIO. Представьте, что нужно создать кнопку для загрузки данных из приложений, которая выдаёт пользователю словарь датафреймов Pandas. Для этого можно воспользоваться кодом, подобным следующему:

with pd.ExcelWriter(buffer) as writer:
    for name, df in dataframes.items():
        df.to_excel(writer, sheet_name=name)

st.download_button(
    label="Download Output",
    data=buffer,
    file_name='output.xlsx',
    mime='xlsx',
)

Подробные маршруты, подготовленные с помощью OpenStreetMap

Ранее в приложении мы использовали функцию request_matrix, определённую во внутреннем пакете. Она применяется для получения матрицы расстояний с использованием API OpenStreetMap и Python-библиотеки requests. Внутри этой функции мы выполняем запрос, подобный следующему:

f"https://router.project-osrm.org/table/v1/driving/{points}?sources={sources_str}&destinations={dest_str}&annotations={annotations}"

Вот что в нём используется:

• points: строка, в которой расположены пары координат долготы (longitude) и широты (latitude). Пары координат отделены друг от друга точкой с запятой (;), а отдельные координаты разделены запятой (,).

• sources: список целых чисел, соответствующих пунктам отправления (from).

• destinations: список, аналогичный sources, но содержащий сведения о пунктах назначения (to).

• annotations: ‘distance’ (расстояние), ‘duration’ (длительность) или ‘duration,distance’.

Теперь нам, чтобы вывести найденный путь на экран, нужно получить подробные координаты, представляющие маршрут, построенный в ходе решения задачи. Чтобы это сделать — мы воспользуемся другим запросом. Ниже показаны две функции, на вход которых подаётся датафрейм, содержащий элементы уже найденного маршрута. На основе выходных данных, полученных из API, мы создадим список кортежей, содержащих долготу и широту, и передадим его folium для создания карты.

def get_request_points(coordinates: pd.DataFrame) -> List[str]:
    return coordinates.apply(lambda x: f"{x['long']},{x['lat']}", axis=1).to_list()


def get_coord_path(coordinates: pd.DataFrame) -> List[Tuple[float, float]]:
    pts = get_request_points(coordinates)
    pts_req = ";".join(pts)
    r = session.get(
        f"http://router.project-osrm.org/route/v1/car/{pts_req}?overview=false&steps=true"
    )
    result = r.json()
    first_route = result["routes"][0]
    coords = [(p["location"][1], p["location"][0])
              for l in first_route["legs"]
              for s in l["steps"]
              for p in s["intersections"]]
    return coords

Построение карты с помощью Folium

Теперь у нас имеется список кортежей, ранее сформированный функцией get_coord_path. Пришло время использовать этот список для создания карты с помощью folium.

def plot_map(
    path: List[Tuple[float, float]],
    color: Union[str, tuple] = "darkblue",
    zoom_start=8,
    **kwargs
):
    # Координаты из path
    lat, long = zip(*path)

    # Создание карты
    m = folium.Map(zoom_start=zoom_start)
    new_line = folium.PolyLine(
        path, weight=4, opacity=1.0,
        color=color, tooltip=f"Route",
        **kwargs
    )
    new_line.add_to(m)

    # Подгонка карты, содержащей путь, под пространство для её вывода
    sw = [min(lat), min(long)]
    ne = [max(lat), max(long)]

    m.fit_bounds([sw, ne])
    return m

И наконец — мы можем передать эту карту библиотеке streamlit_folium и получить приятно выглядящую визуализацию нашей работы.

if tour is not None and dataframe is not None:

    # Вывод решения задачи
    if problem_type == "xy":
        pass  # Тут заглушка, так как это в приложении не реализовано

    elif problem_type == "lat-long":
        map = plot_map(st.session_state.route_path)
        st_folium(map, width=700, height=500, returned_objects=[]

Воспользовавшись файлом с входными данными, который имеется в моём репозитории, вы можете найти и визуализировать самый короткий автодорожный маршрут по всем столицам континентальных штатов США.