research-article

Distributed algorithm for traffic dissemination in manhattan networks with optimal routing-time

Authors:

Sayan Sen Sarma,

Koushik Sinha,

Goutam Chakraborty,

Bhabani P. SinhaAuthors Info & Claims

SAC '17: Proceedings of the Symposium on Applied Computing

Pages 499 - 505

https://doi.org/10.1145/3019612.3019702

Published: 03 April 2017 Publication History

Get Access

Abstract

We consider the problem of traffic routing in a road network in the event of a disaster, when there is a surge in vehicle movement from dense residential areas to designated safe-shelters. We address the problem with multiple sources and a fixed sink in a k × k Manhattan grid road network to find a traffic distribution over the network such that the average time of travel from sources to sink is minimized. We consider queuing delay at each grid point of the Manhattan network when multiple grid points can become potential sources of new traffic generation, and then propose an optimal traffic distribution algorithm to minimize the total queuing delay of all vehicles to reach the given destination point. We then extend our technique to consider variable link delay (as a function of the volume of traffic flow through a link) along the links of the network.

References

[1]

Ahuja, R. K., Mehlhorn, K., Orlin, J., and Tarjan, R. E. Faster algorithms for the shortest path problem. Journal of the ACM (JACM) 37, 2 (1990), 213--223.

Digital Library

Google Scholar

[2]

Chiu, Y.-C., Bottom, J., Mahut, M., Paz, A., Balakrishna, R., Waller, T., and Hicks, J. Dynamic traffic assignment: A primer. Transportation Research E-Circular, E-C153 (2011).

Google Scholar

[3]

Delling, D., Pajor, T., and Wagner, D. Accelerating multi-modal route planning by access-nodes. In Algorithms-Esa 2009. Springer, 2009, pp. 587--598.

Crossref

Google Scholar

[4]

Fredman, M. L., and Tarjan, R. E. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM) 34, 3 (1987), 596--615.

Digital Library

Google Scholar

[5]

Hamacher, H. W., and Tjandra, S. A. Mathematical modelling of evacuation problems: A state of art. Fraunhofer-Institut für Techno-und Wirtschaftsmathematik, Fraunhofer (ITWM), 2001.

Google Scholar

[6]

Hoppe, B., and Tardos, É. Polynomial time algorithms for some evacuation problems. In SODA (1994), vol. 94, pp. 433--441.

Digital Library

Google Scholar

[7]

Kamiyama, N., Katoh, N., and Takizawa, A. An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity. IEICE Trans. Inf. Syst. 89, 8 (2006), 2372--2379.

Digital Library

Google Scholar

[8]

Mamada, S., Makino, K., and Fujishige, S. Evacuation problems and dynamic network flows. In SICE 2004 Annual Conference (2004), vol. 1, IEEE, pp. 530--535.

Google Scholar

[9]

Mamada, S., U.-T. M. K., and Fujishige, S. An O(n log2n) Algorithm for a Sink Location Problem in Dynamic Tree Networks, vol. 155. Springer, Boston, MA, 2004, pp. 251--264.

Google Scholar

[10]

Principles, O. S. Operating System Principles. Prentice Hall of India: New Delhi, 1984.

Google Scholar

[11]

Pyrga, E., Schulz, F., Wagner, D., and Zaroliagis, C. Efficient models for timetable information in public transportation systems. Journal of Experimental Algorithmics (JEA) 12 (2008), 2--4.

Digital Library

Google Scholar

[12]

r pa, C. S., and Chakraborty, G. Dynamic distribute route recommendation system for multiple destinations. In 12th Intl Conf. Elect. Engg./Elect. Comp., Telecomm, and Inf. Tech. (June 2015), pp. 1--5.

Google Scholar

[13]

Rehrl, K., Bruntsch, S., and Mentz, H.-J. Assisting multimodal travelers: Design and prototypical implementation of a personal travel companion. IEEE Trans. Intell. Transp. Syst. 8, 1 (2007), 31--42.

Digital Library

Google Scholar

[14]

Sarma, S. S., and Chakraborty, G. Queuing model-based optimal traffic flow in a grid network. In IEEE Int. Conf. on Advanced Networking and Telecomm. Sys. (Dec 2015), pp. 1--3.

Crossref

Google Scholar

Cited By

View all

Akopov ABeklaryan LBeklaryan A(2021)Simulation-Based Optimisation for Autonomous Transportation Systems Using a Parallel Real-Coded Genetic Algorithm with Scalable Nonuniform MutationCybernetics and Information Technologies10.2478/cait-2021-003421:3(127-144)Online publication date: 7-Dec-2021
https://doi.org/10.2478/cait-2021-0034
Sarma SSinha KSub-r-pa CChakraborty GSinha B(2021)Optimal Distribution of Traffic in Manhattan Road Networks for Minimizing Routing-TimeIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.299483622:11(6799-6820)Online publication date: Dec-2021
https://doi.org/10.1109/TITS.2020.2994836
Kurniawan IAsyhari AHe FLiu Y(2021)Mobile computing and communications-driven fog-assisted disaster evacuation techniques for context-aware guidance supportComputer Communications10.1016/j.comcom.2021.07.020179:C(195-216)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.comcom.2021.07.020
Show More Cited By

Index Terms

Distributed algorithm for traffic dissemination in manhattan networks with optimal routing-time
1. Networks
  1. Network algorithms
  2. Network types

Recommendations

Efficient Traffic Routing in Smart Cities to Minimize Evacuation Time During Disasters
Distributed Computing and Intelligent Technology
Abstract
Efficient traffic management during disaster evacuations is an essential component of intelligent transport systems in smart cities. In a natural disaster, a surge of vehicles from dense residential areas may simultaneously move towards the same ...
An Integer Programming Algorithm for Routing Optimization in IP Networks

Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their ...
Traffic distribution for end-to-end QoS routing with multicast multichannel services

With the development of multimedia group applications and multicasting demands, the construction of multicast routing tree satisfying Quality of Service (QoS) is more important. A multicast tree, which is constructed by existing multicast algorithms, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SAC '17: Proceedings of the Symposium on Applied Computing

April 2017

2004 pages

ISBN:9781450344869

DOI:10.1145/3019612

Conference Chair:
Sung Y. Shin
South Dakota State University
,
Program Chairs:
Dongwan Shin
New Mexico Tech
,
Maria Lencastre
University of Pernambuco, Brazil

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC 2017

Sponsor:

SIGAPP

SAC 2017: Symposium on Applied Computing

April 3 - 7, 2017

Marrakech, Morocco

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
71
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Akopov ABeklaryan LBeklaryan A(2021)Simulation-Based Optimisation for Autonomous Transportation Systems Using a Parallel Real-Coded Genetic Algorithm with Scalable Nonuniform MutationCybernetics and Information Technologies10.2478/cait-2021-003421:3(127-144)Online publication date: 7-Dec-2021
https://doi.org/10.2478/cait-2021-0034
Sarma SSinha KSub-r-pa CChakraborty GSinha B(2021)Optimal Distribution of Traffic in Manhattan Road Networks for Minimizing Routing-TimeIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.299483622:11(6799-6820)Online publication date: Dec-2021
https://doi.org/10.1109/TITS.2020.2994836
Kurniawan IAsyhari AHe FLiu Y(2021)Mobile computing and communications-driven fog-assisted disaster evacuation techniques for context-aware guidance supportComputer Communications10.1016/j.comcom.2021.07.020179:C(195-216)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.comcom.2021.07.020
Sarma SSinha KDas SSinha B(2019)Fast Transportation in a Disaster Situation along Real-Life Grid-Structured Road Networks2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall)10.1109/VTCFall.2019.8891600(1-5)Online publication date: Oct-2019
https://doi.org/10.1109/VTCFall.2019.8891600
Sarma SSinha KChakraborty GSinha B(2017)Reduction of congestion in a Manhattan grid road network by detouring of vehicles2017 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS)10.1109/ANTS.2017.8384161(1-6)Online publication date: Dec-2017
https://doi.org/10.1109/ANTS.2017.8384161

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Efficient Traffic Routing in Smart Cities to Minimize Evacuation Time During Disasters

An Integer Programming Algorithm for Routing Optimization in IP Networks

Traffic distribution for end-to-end QoS routing with multicast multichannel services

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations