Как "застолбить"/опубликовать непроверенную идею?

[Quentin1]

Ну вот, рассмотрим вырожденный случай: рассмотрим движение каждого отдельного автомобиля и попробуем оптимизировать движение всей совокупности автомобилей (например, по критерию минимального времени проезда через улично-дорожную сеть). Понятно, что полный перебор всех возможных маршрутов всех машин потребует слишком больших вычислительных ресурсов. Поэтому его надо маленько оптимизировать, то есть, другим словами, подсократить.

[photon]

Quentin1 в сообщении #1251994 писал(а):

попробуем оптимизировать движение всей совокупности автомобилей (например, по критерию минимального времени проезда через улично-дорожную сеть).

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

[Quentin1]

То есть для разных автолюбителей надо как-то задавать разные приоритеты? И как это сделать? По степени важности (VIP), срочности и т.д.? Может быть, за более быстрый маршрут доплачивать дополнительные денюжки?

[grizzly]

Quentin1 в сообщении #1252777 писал(а):

И как это сделать?

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

А вот когда дойдёт до полной централизации управления, тогда Ваши алгоритмы (если они действительно эффективны) могут пригодиться. Так что запас времени у Вас ещё есть.

[photon]

Quentin1 в сообщении #1252777 писал(а):

То есть для разных автолюбителей надо как-то задавать разные приоритеты? И как это сделать? По степени важности (VIP), срочности и т.д.? Может быть, за более быстрый маршрут доплачивать дополнительные денюжки?

Понятия не имею - это же ваша модель - вам и разбираться с тем, как можно (и можно ли вообще) ее воплотить в жизнь.
А доплачивать кому и за что, простите?

[Vladimir-80]

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

[photon]

Vladimir-80 в сообщении #1252787 писал(а):

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

А еще интереснее, мне кажется, учитывая возможность в режиме реального времени оценивать загруженность дорог, делать это "на лету" - подстраивать циклы по ходу в зависимости от загруженности тех или иных направлений - транспортные потоки могут носить не только суточный характер, но также зависеть от дня недели / сезона / погодных условий / перекрытия каких-то отдельных улиц для ремонта/проведения мероприятий / произошедших ДТП и т.д.

-- Tue Oct 03, 2017 17:37:58 --

Vladimir-80 в сообщении #1252787 писал(а):

после чего настроить светофорные объекты так, чтобы они давали приоритет в движении наиболее загруженному направлению

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

[Dmitriy40]

grizzly в сообщении #1252779 писал(а):

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

Это лишь в указанной полносью централизованной модели. Но весь можно пойти и другим путём, представить каждого водителя в качестве простого автомата состояний с локально ограниченной информацией - и подбирать такой алгоритм работы этого автомата, чтобы максимизировать некий показатель, и для каждого водителя и для системы в целом. Здесь можно даже преодолеть локальность информации сообщая водителям некую информацию из-за горизонта их анализа, например центральный узел собирает информацию о загруженности дорог и рассылая её на светофоры, откуда её будут запрашивать водители, причём лишь в желаемых направления движения. Задача оптимизации при этом будет решаться не центральным узлом, а каждым водителем в отдельности. Роль центрального узла сведётся к сбору и рассылке информации о текущем глобальном состоянии (ладшафте), путь в котором каждый водитель будет искать/выбирать сам, основываясь на своей цели. Т.е. часто цели не локализованы кучно в пространстве, решения тоже кучковаться не будут, ну разумеется лишь при достаточной развитости дорожной сети. В "бедной" сети (на количество альтернативных маршрутов) никакие алгоритмические трюки неэффективны, всё будет ограничиваться параметрами узостей дорожной сети.
В общем модель с полностью централизованным управлением не единственна. Хотя и самая простая. Зато серьёзно ограниченная.
Писал всё это и для Quentin1 тоже.

[photon]

Dmitriy40 в сообщении #1252808 писал(а):

Задача оптимизации при этом будет решаться не центральным узлом, а каждым водителем в отдельности. Роль центрального узла сведётся к сбору и рассылке информации о текущем глобальном состоянии (ладшафте), путь в котором каждый водитель будет искать/выбирать сам, основываясь на своей цели.

По сути, сейчас так и есть: водитель смотрит на яндексовский, гугловский или др. навигатор и принимает решение, а навигаторы и сейчас умеют прокладывать самый короткий или самый быстрый маршрут, в том числе с учетом пробок.

[Dmitriy40]

По сути, но не совсем так же: сейчас "алгоритм" принятия решения у каждого водителя учитывает лишь его цель, безотносительно ухудшения параметров всей системы. Я же говорил об модификациях этого алгоритма для кардинального улучшения глобальных показателей при незначительном ухудшении локальных (своих). В результате построенные маршруты будут не точно оптимальными, но отличаться от них незначительно, а вот общая пропускная способность дорожной сети будет выше значительно. Пример: при наличии альтернативного чуть более долгого маршрута можно выбрать его для балансировки нагрузки на все дороги. Как именно выбирать альтернативный маршрут - вопрос обсуждаемый, стратегий много разных может быть, в том числе и не статических (я бы сделал на вероятностях обратно пропорционально "длине (времени)" маршрута - это само собой сбалансирует потоки и не приведёт к колебаниям пробок между альтернативными дорогами).

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

[Quentin1]

Dmitriy40, придется Вас брать в соавторы.

[photon]

Dmitriy40 в сообщении #1252827 писал(а):

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

Dmitriy40 в сообщении #1252827 писал(а):

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

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

[Dmitriy40]

photon в сообщении #1252865 писал(а):

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

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

Quentin1 в сообщении #1252848 писал(а):

Dmitriy40, придется Вас брать в соавторы.

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

PS. Вообще, я данной темой не занимался, максимум читал несколько научпоп статей об исследованиях, потому не слишком адекватен в суждениях.

-- 03.10.2017, 23:09 --

И да, нейронные сети для прогнозирования транспортного потока в мегаполисе и управлении светофорами - уже пару-тройку лет как исследуются и были публикации. Ссылок не вспомню, но видел. Так что это уже не ноу-хау. Надо что-то более глубокое.

[Rasool]

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

[photon]

Rasool в сообщении #1253017 писал(а):

Можно получить для каждого автомобиля исходную точку и точку назначения

Это ж каким образом?