1. Де взяти дані
2. геном комівояжера
3. Назад, в реальний світ
4. підсумки

12 травня ми з товаришами зайшли в московське метро з його відкриттям вранці і, не вибираючись наверх, відвідали всі 199 доступних в даний момент станцій до закриття метрополітену. Навіщо ми все це зробили - абсолютно не ясно, але я спробую розповісти, як так вийшло.

Давним-давно, здається, з рік тому дружина сказала мені, що хотіла б як-небудь сфотографувати все станції метро в Москві. Я тоді пожартував, що під таку справу можна розрахувати оптимальний маршрут, що дозволяє відвідати всі станції, напружуючись по-мінімуму. Пожартував і забув, а тут взимку згадав і вирішив спробувати.

У міру вивчення питання я виявив, що ідея сама по собі не те щоб дуже нова - в нью-йоркській підземці аналогічні змагання проходять з 1966 року. Що ж стосується московського метро, ​​то ЖЖ-користувач estrella-de-sur пів року назад проїхав його за 12 годин 36 хвилин (розрахунковий час - 11 годин 50 хвилин) за правилом «один крок на кожну станцію». Але у нас було інше завдання - ми хотіли вийти на кожній станції і по можливості красиво її сфотографувати. Це означало, що нам в більшості випадків доведеться чекати на неї наступного поїзда. Виходячи з цього я і будував розрахунок.

Попередження: якщо ви вмієте вирішувати задачу комівояжера на 200 вузлах (за допомогою генетичних алгоритмів або без них) - вас, швидше за все, чекають в іншому місці. Можете просто перегорнути пост і подивитися картинки.

Де взяти дані

Насамперед для цього потрібно було оцифрувати граф метро (вузли - станції, ребра - переїзди і переходи) і доповнити його елементи різної корисної інформації: для станцій - географічні координати, час відкриття-закриття і інтервали проходження поїздів в різний час доби; для ребер - час перегону або переходу між станціями.

Станцій в Москві багато (Саларьево на той момент ще не відкрили, але все одно вистачало), і руками все це робити не хотілося зовсім. Тоді я звернувся до сайту Яндекс.Метро . Для старту це було в самий раз, але цей сервіс використовує усереднені оцінки часу, а для серйозного розрахунку потрібно було мати більш точні відомості. Тут я згадав пару досить древніх програм з народними вимірами часу - pMetro і mMetro - це, якщо хто не знає, такі десктопні калькулятори метромаршрутов. Перша майже перестала офіційно оновлюватися в 2011 році, друга - ще раніше, але все краще, ніж нічого.

Серед файлів в папці pMetro виявився Moscow.pmz, на ділі виявився звичайним zip-архівом з купою файлів в архаїчному .ini-форматі. Там знайшлася майже вся потрібна інформація (на схемі не вистачало кількох найсвіжіших станцій). Я наваял одноразовий парсер всього цього в tsv і Довбах руками відсутні станції і перегони, «продзвонивши» тайминги для них на Яндекс.Метро . Координати нових станцій я взяв зі статей Вікіпедії.

Схема в підсумку вийшла ось такий (проекція, звичайно, не Меркатора, але суть передає):

(Тут я намалював ще й лінію монорельса, але, в подальшому, було вирішено від неї відмовитися)

Тепер треба було спробувати з усім цим злетіти.

геном комівояжера

Отже, потрібно було вирішити класичну завдання комівояжера в постановці на неповному графі над 200 вершинами. Досвід предків вчить нас, що завдання це NP-повна і навіть, ймовірно, трансобчислювальної . У перекладі на російську перше означає, приблизно, що нам не відомо способу знаходження її найкращого рішення, крім перебору всіх можливих відповідей, а друге - що перебирати нам доведеться досить довго (не менше, ніж мільярди років). На практиці, однак, можна спробувати організувати перебір таким хитрим способом, щоб поступово знаходити все більш гарні рішення і зупинитися «по готовності».

Перед тим, як продовжити, зауважу, що першим нормальним спонуканням здорової людини є спроба прокласти оптимальний маршрут самостійно, вручну, або хоча б накидати його великими мазками, а потім доводити автоматично. Але тому що в нашому випадку ціна ребра залежить від його положення в маршруті (тобто від часу доби), а 51 станція знаходиться на досить щільному ділянці графа (всередині кільця і ​​на ньому, включаючи пересадки), проходження якого істотно залежить від точки входу і виходу , використовувати здоровий глузд не так вже й просто. Цікаво також, що в залежності від того, чи збираємося ми виходити на кожній станції і чекати наступного поїзда, чи ні, оптимальний маршрут може бути зовсім різним (тому що інтервали руху поїздів на різних лініях різні).

Але продовжимо. Як я вже сказав, можна організувати перебір таким способом, щоб поступово знаходити все більш гарні рішення, і, якщо нам не потрібно гарантій того, що знайдене рішення найкраще, ми можемо зупинитися в будь-який момент, коли будемо вважати, що поточний кращий результат «досить хороший »для нас. Один із стародавніх класичних підходів в такій ситуації - використання генетичних алгоритмів .

Це досить проста ідея часів колишньої популярності еволюційної теорії: опишемо кожне рішення деяким вектором ( «геномом»), сформулюємо функцію якості конкретного генома (в нашому випадку - час проходження всього маршруту) і запустимо еволюцію: додамо випадкові мутації, а то і змусимо кращі з «особин», натурально, спаровуватися. Кілька тисяч поколінь такою собі євгеніки - і у нас готовий непоганий надлюдина маршрут.

Але диявол, як водиться, в деталях. По-перше, треба добре вибрати подання інформації в геномі. Можна, наприклад, зробити геномом вектор з номерами всіх станцій в порядку їх слідування в маршруті. Чим це погано? Геноми різних маршрутів будуть різної довжини - їм буде незручно схрещуватися. А ще серед випадкових значень генома буде багато невалидность маршрутів - таких, які не дозволяють відвідати всі станції. Іншими словами, в просторі значень генома концентрація дійсно можливих кандидатур буде невисокою - а значить, нам окремо доведеться перевіряти кожного кандидата на валідність, витрачаючи на це зайвий час.

Набагато зручніше оголосити геномом перестановку довжини 200 - тобто такий вектор довжини 200, в якому кожна станція зустрічається лише 1 раз. Правда, при такому підході сусідніми в маршруті можуть виявитися станції, між якими немає прямого з'єднання. Не біда - ми можемо перейти до повного графу, розрахувавши найкоротший маршрут по графу між кожною парою вершин (в лоб це нескладно зробити за О (| V | ^ 3) операцій, що в нашому випадку - не так багато). Важливо відзначити, що цей найкоротший маршрут також може бути різним у різний час доби, з урахуванням динаміки розкладу. Тому, має сенс розрахувати такі таблиці для кожного зрізу розкладу інтервалів.

По-друге, потрібно пошаманити з різними видами мутацій і схрещувань. Науки тут особливо немає, суцільна Емпірика, спрямована головним чином на те, щоб, з одного боку забезпечити швидку збіжність, а з іншого - можливість вибратися з еволюційного тупика локального оптимуму. У підсумку, я зупинився на наборі з наступних перетворень:

• випадкова перетасування випадкового інтервалу генома - це швидка мутація, але не дуже акуратна, на фінальних етапах еволюції вона з дуже низькою ймовірністю може поліпшити вже непогане рішення.
• дзеркальне відображення випадкового інтервалу генома - може бути корисно для сильних змін (виходу з локального оптимуму), з шансами зберегти деякий порядок (висока якість) маршруту в контексті нашої задачі
• перестановка X пар випадкових значень в геномі місцями - хороша мутація, але повільна, з тупика на ній не виберешся.
• схрещування ( "crossover") двох геномів - спочатку вибираємо точку схрещування на геномі, відрізаємо по ній хвости наших геномів і міняємо їх місцями. Після цього ми можемо отримати некоректний маршрут - тому унікалізіруем результат і додаємо всі втрачені вузли, наприклад, в випадкові місця генома.

Разом, на кожній ітерації ми деякий підмножина кращих особин піддаємо їх різним мутацій і формуємо з їх нащадків нове покоління, досипляючи до них кілька повністю випадкових маршрутів, щоб не впасти жертвами інбридингу. Розрахунок такої еволюції довжиною в 50000 поколінь наколеночним скриптом на Python займає на моєму домашньому столі в середньому 20 хвилин. А щоб було не так нудно чекати, можна підглядати за ним в динаміці, отрісовивая кращу особина кожного, скажімо, сотого покоління. Ось невелика гифка, що показує фаворитів кількох перших тисяч поколінь в циклі:

Послідовність кроків у маршруті відповідає градієнту сірого. Видно, що на самому початку маршрут змінюється досить хаотично, потім швидко виходить на локальний оптимум і починає доведення по дрібницях. А якщо чекати досить довго (вже за межами даної гифки), можна, якщо пощастить, побачити, як, час від часу, еволюція перестрибує в новий, більш глибокий оптимум і продовжує оптимізацію там.

Важливий момент - якщо ми бачимо, що незалежні прогони оптимізації дають нам істотно різні відповіді, нехай і схожі за якістю, значить, велика ймовірність того, що ми так і не знайшли глобальний оптимум. Але нас влаштує і досить гарне його наближення, яке можна спробувати отримати «мультістартамі» - запустити алгоритм багато разів (у т.ч. з різними настройками, наприклад, задаючи початок і кінець маршруту рівними різним фіксованим гілках) і вибирати кращий з спостережуваних результатів.

Щоб трохи продовжити саспенс, покажу вам маршрут, який посів за моїми розрахунками друге місце (їхати від світлого до темного):

А підсумкова оцінка тривалості найкращого маршруту вийшла рівною 19 години 51 хвилині. Нагадаю, інтервал роботи московського метро - приблизно 20 годин, а всі вихідні дані про інтервали проходження потягів я взяв з аматорських вимірів. Якби у мене вийшов маршрут в 10 або 40 годин - все було б, так чи інакше, ясно. Але тут запас становив всього 9 хвилин при невідомої (але явно не маленькою) похибки.

Назад, в реальний світ

Приблизно в цей момент ідея перевірити цю карту на практиці зміцніла. На той час кілька моїх друзів вже були в курсі моїх дивних досліджень. Пара з них виявилися досить божевільними, і ось - ми зібрали команду для перевірки боєм. Але, так як ризики «не попасти» у відведений час були досить високими, я вирішив спочатку перевірити ряд альтернативних варіантів.

Варіант «Повернути монорельс». Цікавий факт: проїзд від Тимирязевской до ВДНГ на метро з пересадкою через кільце займає менше часу, ніж з переходом на монорельс і назад (за даними pMetro, без необхідності виходити на кожній станції). Варіант відкинутий.

Варіант «Додати наземний транспорт». Ідея в тому, що можна спробувати переміщатися між кінцевими різних ліній на громадському транспорті по землі. За даними з пересадки на наземний траспорт я пішов до Діми Крюкову з Яндекс.Распісаній. Виявилося, що точної інформації про пересадках між метро і наземному транспортом у нас зараз немає, зате є докладна інформація про всіх наземних зупинках і маршрутах автобусів / тролейбусів / трамваїв.

Нічого не вдієш, довелося робити матчінг зупинок зі станціями за назвами. Там виявилося досить багато підводних граблів, про які розповідати не дуже цікаво. Скажу тільки, що в Москві знайшлося рівно 999 наземних зупинок, названих «в честь» тієї чи іншої станції метро (не рахуючи кількох «Метромена», «метродепо», «метрогородков» та іншого). А ще, деякі зупинки досі названі в честь вже перейменованих станцій метро. Але це дрібниці.

Ось вам, до речі, схема зі знайденими наземними «хордами»:

Але, так чи інакше, коли я додав оцінки за часом виходу + очікування наземного транспорту + проїзду + повернення в метро, ​​виявилося, що ці «хорди" не дуже допомагають - концепція «метро-тріп» втрачає вихідну чистоту, а розрахунковий виграш становить всього 15-20 хвилин. Варіант відкинутий.

Варіант «Додати таксі». По суті, це модифікація попереднього варіанту, але замість громадського транспорту передбачається використання таксі. Для цього я руками вибрав для кожної кінцевої странцу кожної радіальної гілки географічно найближчі до неї станції на сусідніх гілках і додав для таких пар «хорди» з оцінкою часу по Яндекс.Навігатор.

Після оптіміазаціі вийшов ось такий цікавий маршрут з чотирма «хордами»:

Такий маршрут за розрахунками виявився приблизно на 30 хвилин коротше, ніж мій оптимальний. Варіант відкинутий, як «не спортивний».

підсумки

Після бурхливих дебатів ми вирішили їхати оптимальний маршрут без «хорд» і з виходом на кожній станції. Зрештою, якщо б ми хотіли просто номінально об'їхати всі станції, можна було б взагалі не виходити з вагона і отримати час близько 12 годин. Але московське метро по праву вважається одним з найкрасивіших метрополітенів світу, так що краще насолодитися частиною станцій, ніж відвідати всі, але не побачити нічого.

Настрій був серйозним, тому на даному етапі ми звернулися в Московський метрополітен, і провалідіровалі з їх допомогою наш маршрут. Нам виділили спеціального супроводжуючого з Центру забезпечення мобільності пасажирів, дозволили вести фото-і відеозйомку і навіть дозволили зрідка користуватися службовими туалетами, які, як з'ясувалося, є на кожній станції.

Отже, 12 травня ми з товаришами зайшли в московське метро рано вранці і, не вибираючись наверх, відвідали всі 199 доступних в даний момент станцій до закриття метрополітену. Навіщо ми все це зробили - абсолютно не ясно, але суть не в цьому, головне - нам це вдалося.

У нас не було завдання проїхати все метро «на час», скоріше ми хотіли дійсно подивитися всі станції за один день. Ми виходили на кожній станції, робили фотографії (пару сотень фото можна знайти в наших різних стрічках в соцмережах ) І їхали далі - іноді в тому ж потязі, а іноді пропускаючи по кілька поїздів до ряду, якщо станція була настільки цікавою, що нам хотілося провести на ній більше часу.

Наше підсумкове час склало 16 годин 22 хвилини, і ми з задоволенням публікуємо наш маршрут , З тим, щоб будь-який бажаючий міг спробувати поліпшити цей час.

Я з величезним задоволенням дякую всім, хто так чи інакше допомагав нам в цій божевільній затії -і саму команду марафонців, і команду онлайн-супроводу, і численних людей, які допомагали нам в підготовці.
Докладні подяки можна прочитати в нашому закриває пості на ФБ .