- PVSM.RU - https://www.pvsm.ru -
Идеи, чем заняться на выходных, ITшники черпают из сотни разных источников. Я, к примеру, недавно увидел конкурс Открытого чемпионата школ по Экономике, заключающегося в том, чтобы сфотографировать максимальное число билбордов Чемпионата. Адреса организаторы любезно предоставили. И несмотря на то, что приз взрослому там не светит (это школьный конкурс), тем не менее крайне интересно было бы узнать, за какое минимальное время можно решить такую задачу.
3 часа на выходных, 35 адресов билбордов в виде достаточно спорно вбитых адресов [1] (почему-то реестр УНОМ достаточно плохо бьётся с привычными картами), 1 Jupyter с готовым к работе вторым (извините) питоном и множество API различных сервисов.
Для начала удобно было бы представить масштаб бедствия на карте. Можно было бы воспользоваться чем-то автоматическим, но 35 адресов быстрее вручную перебить в Конструктор Яндекс.Карт, он сам приведет их к координате. В итоге получилась картинка из ката [2], из которой стало понятно, что
Собственно всего вариантов продолжить такой маршрут , что примерно сопоставимо с числом уникальных шахматных позиций [3] на доске. Так что надо немного разобраться в достижениях народного хозяйства в области P — NP задач [4].
Становится ясно, что наша задача является примером классической задачи коммивояжёра [5] (TSP). Для того, чтобы её решить (приблеженно), нам нужно построить матрицу расстояний (в нашем случае времен) между каждой точкой. Для решения такой задачи воспользуемся Google Maps API, а именно безумно простой и понятной библиотечкой googlemaps. Работа с этой библиотечкой проста и элегантна, получить время между двумя точками на карте можно настолько просто:
import googlemaps
import datetime
gmaps = googlemaps.Client(key='AIxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx')
resp = gmaps.directions(
origin='55.71802 37.573753',
destination='55.73481 37.66521',
mode='driving', # Либо 'transit' для общественного транспорта
region='ru',
language='en',
departure_time=datetime.datetime.now(),
)
distance_time = resp[0]['legs'][0]['duration_in_traffic']['value'] # Для авто
print resp[0]['legs'][0]['duration_in_traffic']
# Out[]: {u'text': u'49 mins', u'value': 2917}
Итак, осталось заполнить матрицу 36×36 всех расстояний. Заметьте, что добраться от точки A->B занимает НЕ столько же времени, сколько из B->A, поэтому сократить работу в два раза не получится (хотя диагональ конечно же заполнена нулями). Можно было бы просто пройтись по заранее созданной пустой матрице и заполнить её, однако мне больше нравится подход, когда я сначала храню все элементы матрицы в виде списка [[x,y,value]]
, а потом делаю .pivot
, «разворачивая» матрицу.
distances = []
for origin,destination in permutations(points['lat lng'], 2):
resp = gmaps.directions(
origin=origin,
destination=destination,
mode='driving',
region='ru',
language='en',
departure_time=now,
)
distance_time = resp[0]['legs'][0]['duration_in_traffic']['value'] # Для авто
distances.append(
[origin,destination,distance_time]
)
distances = pd.DataFrame(distances, columns='origin,destination,distance_time'.split(','))
distances_matrix = distances.pivot_table(
index='origin', columns='destination',
values='distance_time'
).fillna(0)
Тут можно сразу отметить, что я большой фанат Pandas Dataframes, и с ними жизнь становится лучше. Если не слышали, обязательно почитайте, вам понравится. Ну и, конечно, как хорошо писать на Питоне, в котором уже есть готова чудесная функция itertools.permutations
, возвращающая все пары (тройки, четверки, что нужно) элементов заданного списка. Нет костылям!
Итоговая матрица получилась примерно такой:
Кстати, тут ещё сразу можно изучить, а насколько вообще близки друг к другу наши точки? Иными словами, посмотреть на распределение времени в пути между всеми точками:
Хотя в целом всё довольно ожидаемо. Много точек очень близко, распределение достаточно «нормальное», всё из-за того, что на машине ты можешь двигаться в любую сторону. Забегая немного вперед, вот то же распределение, только для общественного транспорта:
Совсем другая картинка: распределение намного более «вытянуто» вправо, то есть есть относительно мало точек, между которыми может быстро (быстрее 40 минут) переместиться на общественном транспорте. Ну и естественно, что время на транспорте в целом больше (более или менее в два раза).
Итак, теперь по матрице необходимо построить оптимальный маршрут. Надо сказать, что эта задача уже достаточно хорошо изучена, к примеру, есть очень хорошая гугловая библиотека ortools [6], позволяющая перебирать маршруты на тысячах и десятках тысяч точек.
Однако в нашем случае всего десятка точек необходимости в сложных алгоритмах нет. Можно воспользоваться жадным алгоритмом двойного прохода, и получить результат почти не отличающийся от «канонического».
Итак, алгоритм будет таким:
1. Инициируем начальную и финальные точки.
2. Берем две точки с наименьшими расстояниями от инициированных, добавляем их в маршрут.
3. Посторяем до тех пор, пока не наберем полный маршрут.
Здесь очевидно, что алгоритм очень зависим от выбранных начальных точек (и в целом от порядка точек), поэтому есть довольно простой способ избежать локальных оптимумов: несколько раз «перемешать» точки и посторить работу жадного алгоритма.
Программное реализацию этого алгоритма я позаимствовал из библиотеки библиотеку [7] Дмитрия Шинякова.
Библиотека на вход принимает numpy
квадратную матрицу, на выход выдаёт path
: массив индексов точек в порядке по маршруту. Интересно, что Google Maps не позволяют строить маршруты с более чем 23 промежуточными точками, поэтому «на одной карте» построить маршрут не удастся. Я пошел на хитрость, и с помощью той же googlemaps
просто разбил маршрут на два и построил его.
coords_path = distances_matrix.index[path] # Получаем точки в правильном порядке
# Latitude-longitude pairs
start = map(float, coords_path[0].split(' '))
waypoints = map(lambda p: map(float, p.split()), coords_path[1:24]) # первые 24 точки
end = map(float, coords_path[24].split())
m = gmaps.Map(height='650px')
ochDirections = gmaps.directions_layer(start, end, waypoints=waypoints)
m.add_layer(ochDirections)
start = map(float, coords_path[24].split(' '))
waypoints = map(lambda p: map(float, p.split()), coords_path[25:-1])
end = map(float, coords_path[-1].split())
ochDirections = gmaps.directions_layer(start, end, waypoints=waypoints)
m.add_layer(ochDirections)
m
То же самое можно сделать с помощью Яндекс.Карт, уже без разбивания на два куска.
base_yandex = 'https://yandex.ru/maps/213/moscow/?ll=37.519600%2C55.819741&z=10&mode=routes&rtext={rtext}&rtt=mt&rtm=atm'
rtext = '~'.join(i.replace(' ', '%2C') for i in coords_path)
print base_yandex.format(rtext=rtext)
Весь код я выложил к себе на гитхаб [8] в виде jupyter notebook'а, чтобы можно было быстро попробовать сделать что-то аналогичное.
Итак, в итоге алгоритм выдал оценку времени в 8 часов (без пробок 6 часов). В этот момент захотелось выйти из зоны комфорта милого онлайна, и реально проехаться и сфотографировать все билборды. Дело за малым: нашлась компания, и мы поехали строго в соответствии с построенным маршрутом.
Финальный путь занял всего 10 часов. С учетом остановок и поиска многих билбордов мне кажется, что «лишние» 25% времени полностью оправданы. Нам удалось проехать все указанные в списке точки, однако нашли лишь 23 из 35 билбордов. При этом интересно, что щитов формата 6x3 мы нашли 19 из 24, а ситибордов всего 4 из 11. Скорее всего это связано с тем, что ситиформаты в целом рекламодателям более привлекательны (потому что они расположены ближе к центру), и поэтому их быстрее снимают. Не исключаю и банальную версию, что билборды в принципе не вешались.
В итоге, как мне кажется, получилась достаточно интересная смесь из простого алгоритма, упрощающего рутину и дающего намного более хороший результат, чем человек, и реального применения его на дорогах Москвы. Детский конкурс Открытого Чемпионата школ по экономике мы не выиграли, но нашли, кажется, на порядок больше билбордов, чем самый активный участник.
Автор: Андрей Петрин
Источник [9]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/252646
Ссылки в тексте:
[1] в виде достаточно спорно вбитых адресов: https://vk.com/doc37216554_443517692?
[2] картинка из ката: https://yandex.ru/maps/-/C6E~jH8E
[3] числом уникальных шахматных позиций: https://en.wikipedia.org/wiki/Shannon_number
[4] P — NP задач: https://en.wikipedia.org/wiki/P_versus_NP_problem
[5] задачи коммивояжёра: https://en.wikipedia.org/wiki/Travelling_salesman_problem
[6] ortools: https://developers.google.com/optimization/
[7] библиотеку: https://github.com/dmishin/tsp-solver
[8] к себе на гитхаб: https://github.com/apetrin/och_billboards/blob/master/emsch_och_billboards-export.ipynb
[9] Источник: https://habrahabr.ru/post/324864/
Нажмите здесь для печати.