[Перевод] От теории к практике: создаём веб-приложение для решения задачи коммивояжёра.

В таких сферах, как исследование операций (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.

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

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

Читать далееhttps://habr.com/ru/companies/wunderfund/articles/767618