2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение30.09.2017, 14:56 


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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение02.10.2017, 20:24 
Экс-модератор
Аватара пользователя


23/12/05
12046
Quentin1 в сообщении #1251994 писал(а):
попробуем оптимизировать движение всей совокупности автомобилей (например, по критерию минимального времени проезда через улично-дорожную сеть).

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 17:28 


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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 17:47 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Quentin1 в сообщении #1252777 писал(а):
И как это сделать?
В теории очень просто -- можно реализовать минимаксную стратегию. На практике, конечно, никто не будет рассчитывать только на худшее развитие событий; решение должно быть ориентировано на статистический оптимум, иметь запас прочности на неблагоприятное стечение обстоятельств и на прогнозируемое будущее. Но пока у Вас нет полностью централизованной системы управления частным транспортом, у Вас просто нет механизма заставить отдельно взятого водителя ехать по тому маршруту, который Вам больше нравится.

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 18:08 
Экс-модератор
Аватара пользователя


23/12/05
12046
Quentin1 в сообщении #1252777 писал(а):
То есть для разных автолюбителей надо как-то задавать разные приоритеты? И как это сделать? По степени важности (VIP), срочности и т.д.? Может быть, за более быстрый маршрут доплачивать дополнительные денюжки?

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 18:15 
Заблокирован


19/02/13

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 18:35 
Экс-модератор
Аватара пользователя


23/12/05
12046
Vladimir-80 в сообщении #1252787 писал(а):
В современных реалиях эффективней будет проанализировать транспортные потоки, после чего настроить светофорные объекты так, чтобы они давали приоритет в движении наиболее загруженному направлению. Для Москвы, например, это будет означать увеличение "зелёной" части цикла для потоков в центр по утрам и для потоков из центра по вечерам.

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

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

Vladimir-80 в сообщении #1252787 писал(а):
после чего настроить светофорные объекты так, чтобы они давали приоритет в движении наиболее загруженному направлению

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 19:33 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 19:50 
Экс-модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 20:31 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 21:33 


02/04/16
41
Областной центр
Dmitriy40, придется Вас брать в соавторы. :-)

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 22:02 
Экс-модератор
Аватара пользователя


23/12/05
12046
Dmitriy40 в сообщении #1252827 писал(а):
Я же говорил об модификациях этого алгоритма для кардинального улучшения глобальных показателей при незначительном ухудшении локальных (своих).

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

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение03.10.2017, 23:05 
Заслуженный участник


20/08/14
11064
Россия, Москва
photon в сообщении #1252865 писал(а):
чтобы не получилось, что система показала пробку, и все ломанулись по соседней дороге, создав там пробку и продолжая ухудшать там ситуацию, потому что информация не обновилась, хотя по первой дороге уже пробка рассосалась.
Ага, вот в этом и одна из проблем. И дело даже не только в оперативности реакций, кажется при любом ненулевом времени реакции возможны колебания, а то и вообще "разгон" этих колебаний. Нулевое же - не физично.
Потому или вводить функцию подавления колебаний (и в централизованной системе это сильно проще), или изначально создавать условия для хотя бы неразвития колебаний. Методов много могу придумать, анализировать и программировать их морока ещё та. Мои слова про вероятность как раз один из методов, препятствующих возникновению колебаний.

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

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

-- 03.10.2017, 23:09 --

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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение04.10.2017, 15:17 


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

 Профиль  
                  
 
 Re: Как "застолбить"/опубликовать непроверенную идею?
Сообщение04.10.2017, 15:41 
Экс-модератор
Аватара пользователя


23/12/05
12046
Rasool в сообщении #1253017 писал(а):
Можно получить для каждого автомобиля исходную точку и точку назначения

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 58 ]  На страницу Пред.  1, 2, 3, 4  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: mihaild


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group