Математика и транспортные сетиКогда Боб Сантилли, старший менеджер проектов в UPS(United Parcel Service – логистическая компания), был приглашен в 2009 году в пятый класс своей дочери в “День карьеры”, он изо всех сил пытался описать, чем именно он зарабатывал на жизнь. В конце концов, он решил показать классу задачу оптимизации путешествий, над которой он работал, и поразить их тем, насколько это было весело и сложно. Задача состояла в том, чтобы выбрать наиболее эффективный маршрут из шести различных остановок в типичных пригородных поездках. Класс разработал соответствующие маршруты, а затем начал выбирать их. Но одна девушка задумалась над вопросом эффективности. Она говорит - моя мама никогда бы не пошла в магазин и не купила скоропортящиеся продукты.
Ее комментарий отражает основную правду о математике, которая скрывается под поверхностью почти каждой современной транспортной системы, от перебалансировки до планирования работы экипажа авиакомпании и доставки продуктов. Моделирование упрощенной версии транспортной задачи представляет один набор проблем (и они могут быть значительными). Но моделирование реального мира с такими ограничениями, как тающее мороженное и неповторимое поведение человека, часто является главной проблемой. Как математики, специалисты по исследованию операций и руководители корпораций намереваются математизировать и оптимизировать транспортные сети, которые связывают наш современный мир, они вновь открывают для себя некоторые наши самые человеческие причуды и возможности. Они обнаруживают, что их работа заключается в том, чтобы открыть мир так же, как изменить его.
Проблема, которую Сантилли поставил перед классом своей дочери, известна как проблема коммивояжера. Алгоритмы решения этой проблемы являются одними из самых важных и наиболее часто используемых в транспортной отрасли. Вообще говоря, проблема коммивояжера спрашивает: учитывая список остановок, какой самый эффективный по времени способ для продавца сделать эти остановки? Например, в 1962 году реклама «Проктер энд Гэмбл» поставила перед читателями такую задачу: помочь «Туди и Малдуну», снимающимся в удостоенной наград Эмми телевизионной передаче «Автомобиль 54, где ты?», Разработать 33- экскурсия по континентальной части США. «Вы должны спланировать для них маршрут от места к месту, - пошли инструкции, - что приведет к наименьшему суммарному пробегу от Чикаго, штат Иллинойс, до Чикаго, штат Иллинойс».
Математик выиграл приз и 10 000 долларов. Но организаторы конкурса могли только проверить, что его решение было самым коротким из представленных, а не то, что это был самый короткий возможный маршрут. Это связано с тем, что для решения проблемы 33 городов путем расчета каждого маршрута в отдельности потребуется 28 триллионов лет - на суперкомпьютере Министерства энергетики на 129 000 ядер Roadrunner (который входит в число самых быстрых кластеров в мире). Именно по этой причине Уильям Дж. Кук в своей книге «В погоне за коммивояжером» называет проблему коммивояжера «фокусом более широких дискуссий о природе сложности и возможных ограничениях человеческих знаний» как масштаб сложности. Тур по шести городам имеет всего 720 возможных путей, а тур по 20 городам - по быстрым расчетам Кука на его Mac - более 100 квадриллионов возможных путей.
