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

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


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

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

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


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

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

 Профиль  
                  
 
 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
11057
Россия, Москва
photon в сообщении #1252865 писал(а):
чтобы не получилось, что система показала пробку, и все ломанулись по соседней дороге, создав там пробку и продолжая ухудшать там ситуацию, потому что информация не обновилась, хотя по первой дороге уже пробка рассосалась.
Ага, вот в этом и одна из проблем. И дело даже не только в оперативности реакций, кажется при любом ненулевом времени реакции возможны колебания, а то и вообще "разгон" этих колебаний. Нулевое же - не физично.
Потому или вводить функцию подавления колебаний (и в централизованной системе это сильно проще), или изначально создавать условия для хотя бы неразвития колебаний. Методов много могу придумать, анализировать и программировать их морока ещё та. Мои слова про вероятность как раз один из методов, препятствующих возникновению колебаний.

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

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

-- 03.10.2017, 23:09 --

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

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


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

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


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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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