Анализ графа дорожных сетей

Доброе время суток! Задали задачу составить граф района города, взвесить его, причём, с изменениями во времени (веса меняются в зависимости от времени суток), ну а потом оптимизировать дорожное движение - добавить или убрать полосы движения, быть может, построить новую дорогу. Для удобства я выбрал библиотеку networkx для python, составил ориентированный взвешенный граф. Веса - количество машин/количество полос движения*расстояние. Каким способом лучше обходить граф? Я перелопатил кучу алгоритмов, додумался только количество полос вычислять из наиболее оптимального пути, но это вряд ли будет работать.

0

Очень важно давать дословную цитату задания.

Например, как именно задается граф.
Это граф между "пунктами интереса", или надо строить подобие реальной карты дорог, где "пункты интереса" могут находится где-то посередине квартала, а значит и дороги.
Надо ли учитывать время движения автомобиля по участку дороги, или достаточно только пропускной способности "машин в минуту" (но тогда нам не важно сколько времени машина затрачивает на весь путь или на отдельных участках, мы просто будем считать суммарную пропускную способность между "пунктами интереса")
И без точного описания задачи непонятно как можно в районе города (с плотной застройкой) строить новые дороги... Да и расширять существующие часто невозможно или очень затратно. Надо ли учитывать перекрестки (которые, в некотором приближении, имеют максимальную пропускную способность равную дороге второй по ширине)

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

0