Транспортная связность географической области

17.12.2014

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

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

Примерно так решается задача управления работой транспортного флота. Хотя границы подобластей не являются строгим требованием - так, к примеру, в случае когда две соседние подобласти имеют мало точек доставки, они обе могут быть обслужены одной машиной, или, наоборот, одна область может быть обслужена более чем одной машиной, - тем не менее, выбор подобластей важен для начала решения задачи.

На данный момент подобласти выбираются заранее и навсегда. Выбор этот делается только на основе опыта и приблизительных оценок.

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

Всегда остается вопрос: а будет ли решение лучше, если выбрать подобласти по-другому? На данный момент у меня нет решения для данной задачи, кроме прямого перебора всех возможных решений на множестве всех возможных разбиений. Адский труд.

Может быть на этом все? Нет.

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

Отношение географического расстояния к расстоянию по дороге между двумя точками назовем коеффициентом сложности пути между этими двумя точками. Очевидно, что чем богаче дорожная сеть между этими двумя точками, тем ближе это отношение к единице, а чем беднее сеть (меньше дорог, а те что есть - ведут черт знает куда) - тем ближе коеффициент к нулю.

Коеффициентом сложности в e-окрестности точки назовем среднюю сложность по всем возможным диаметрам, с центром в этой точке и с концами на противоположных границах области.

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

Далее, предполагается, что точки с более высокими коэффициентами сложности будут сгруппированы и обусловлены естественными препятсвиями - железная дорога, канал, лес.

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

Для проверки этих предположений была построена сетка 1000м на 800м для анализа связности города Москвы и аналогичная, но меньшая, для города Барселоны.

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

Связность МосквыТраспортая связность для БарселоныБарселона с приближением

Для Москвы видно, что основной сложностью является МКАД, Москва-река и основные шоссе с радиальными железными дорогами. Центр также не слишком благополучен. Для Барселоны, которая считается одним из эталонов дорожной сети также выделяется опоясывающая дорога. Плюс к тому центральный парк и район порта. Вполне ожидаемо.

Построенный инструмент позволяет производить расчеты на сетке с наперед заданной точностью (например 500 на 500 метров) или с наперед заданной плотностью сетки.

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