Abstract
This paper considers the problem of routing and rebalancing a shared fleet of autonomous (i.e., self-driving) vehicles providing on-demand mobility within a capacitated transportation network, where congestion might disrupt throughput. We model the problem within a network flow framework and show that under relatively mild assumptions the rebalancing vehicles, if properly coordinated, do not lead to an increase in congestion (in stark contrast to common belief). From an algorithmic standpoint, such theoretical insight suggests that the problems of routing customers and rebalancing vehicles can be decoupled, which leads to a computationally-efficient routing and rebalancing algorithm for the autonomous vehicles. Numerical experiments and case studies corroborate our theoretical insights and show that the proposed algorithm outperforms state-of-the-art point-to-point methods by avoiding excess congestion on the road. Collectively, this paper provides a rigorous approach to the problem of congestion-aware, system-wide coordination of autonomously driving vehicles, and to the characterization of the sustainability of such robotic systems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
For any subset of nodes \(\mathcal {S}\subseteq \mathcal {V}\), we define a cut \((\mathcal {S}, \bar{\mathcal {S}})\subseteq \mathcal {E}\) as the set of edges whose origin lies in \(\mathcal {S}\) and whose destination lies in \(\bar{\mathcal {S}}=\{\mathcal {V}\setminus \mathcal {S}\}\). Formally, \((\mathcal {S},\bar{\mathcal {S}}):=\{(u,v)\in \mathcal {E}: u\in \mathcal {S}, v \in \bar{\mathcal {S}}\}\).
The source code for the modified taxi extension is available at http://dx.doi.org/10.5281/zenodo.1048415.
References
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms and applications. Upper Saddle River: Prentice Hall.
Balmer, M., Rieser, M., Meister, K., Charypar, D., Lefebvre, N., & Nagel, K. (2009). MATSim-t: Architecture and simulation times. In A. Ana Bazzan & F. Klügl (Eds.), Multi-agent systems for traffic and transportation engineering (pp. 57–78).
Barnard, M. (2016). Autonomous cars likely to increase congestion. Available at http://cleantechnica.com/2016/01/17/autonomous-cars-likely-increase-congestion. Accessed 15 Feb 2017.
Berbeglia, G., Cordeau, J. F., & Laporte, G. (2010). Dynamic pickup and delivery problems. European Journal of Operational Research, 202(1), 8–15.
Bureau of Public Roads. (1964). Traffic assignment manual. Technical Report, U.S. Department of Commerce, Urban Planning Division.
Cornuejols, G., Nemhauser, G. L., & Wolsey, L. A. (1990). The uncapacitated facility location problem. In P. B. Mirchandani & R. L. Francis (Eds.), Discrete location theory (pp. 119–171). Hoboken: Wiley.
Daganzo, C. F. (1994). The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological, 28(4), 269–287.
Even, S., Itai, A., & Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4), 691–703.
Fagnant, D. J., & Kockelman, K. M. (2014). The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transportation Research Part C: Emerging Technologies, 40, 1–13.
Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. Princeton: Princeton University Press.
Goldberg, A., Oldham, J., Plotkin, S., & Stein, C. (1998). An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. In International conference on integer programming and combinatorial optimization.
Goldberg, A. V., Tardos, E., & Tarjan, R. E. (1990). Network flow algorithms. In B. H. Korte (Ed.), Algorithms and combinatorics. Volume 9: paths, flows, and VLSI-layout (pp. 101–161). Springer-Verlag.
Haklay, M., & Weber, P. (2008). OpenStreetMap: User-generated street maps. IEEE Pervasive Computing, 7(4), 12–18.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems, Science, & Cybernetics, 4(2), 100–107.
Horni, A., Nagel, K., & Axhausen, K. W. (Eds.). (2016). The multi-agent transport simulation MATSim. London: Ubiquity Press.
Janson, B. N. (1991). Dynamic traffic assignment for urban road networks. Transportation Research Part B: Methodological, 25(2–3), 143–161.
Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373–395.
Karp, R. M. (1975). On the computational complexity of combinatorial problems. Networks, 5(1), 45–68.
Kerner, B. S. (2009). Introduction to modern traffic flow theory and control: The long road to three-phase traffic theory (1st ed.). Berlin: Springer.
Le, T., Kovács, P., Walton, N., Vu, H. L., Andrew, L. L. H., & Hoogendoorn, S. S. P. (2015). Decentralized signal control for urban road networks. Transportation Research Part C: Emerging Technologies, 58, 431–450.
Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, É., & Tragoudas, S. (1995). Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2), 228–243.
Levin, M. W., Kockelman, K. M., Boyles, S. D., & Li, T. (2017). A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application. Computers, Environment and Urban Systems, 64, 373–383.
Lighthill, M. J., & Whitham, G. B. (1955). On kinematic waves. II. A theory of traffic flow on long crowded roads. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 229(1178), 317–345.
Maciejewski, M., & Bischoff, J. (2017). Congestion effects of autonomous taxi fleets. Transport, 9, 1–10.
Maciejewski, M., Bischoff, J., Hrl, S., & Nagel, K. (2018). Towards a testbed for dynamic vehicle routing algorithms. In International conference on practical applications of agents and multi-agent systems—Workshop on the application of agents to passenger transport (PAAMS-TAAPS) (in press).
Mitchell, W. J., Borroni-Bird, C. E., & Burns, L. D. (2010). Reinventing the automobile: Personal urban mobility for the 21st century. Cambridge: MIT Press.
Neuburger, H. (1971). The economics of heavily congested roads. Transportation Research, 5(4), 283–293.
Osorio, C., & Bierlaire, M. (2009). An analytic finite capacity queueing network model capturing the propagation of congestion and blocking. European Journal of Operational Research, 196(3), 996–1007.
Papageorgiou, M., Hadj-Salem, H., & Blosseville, J. M. (1991). ALINEA: A local feedback control law for on-ramp metering. Transportation Research Record: Journal of the Transportation Research Board, 1320, 58–64.
Pavone, M., Smith, S. L., Frazzoli, E., & Rus, D. (2012). Robotic load balancing for mobility-on-demand systems. International Journal of Robotics Research, 31(7), 839–854.
Peeta, S., & Mahmassani, H. S. (1995). System optimal and user equilibrium time-dependent traffic assignment in congested networks. Annals of Operations Research, 60(1), 81–113.
Pérez, J., Seco, F., Milanés, V., Jiménez, A., Díaz, J. C., & De Pedro, T. (2010). An RFID-based intelligent vehicle speed controller using active traffic signals. Sensors, 10(6), 5872–5887.
Raghavan, P., & Tompson, C. D. (1987). Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4), 365–374.
Seow, K. T., Dang, N. H., & Lee, D. H. (2010). A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Sciences and Engineering, 7(3), 607–616.
Spieser, K., Treleaven, K., Zhang, R., Frazzoli, E., Morton, D., & Pavone, M. (2014). Toward a systematic approach to the design and evaluation of autonomous mobility-on-demand systems: A case study in Singapore. In: G. Meyer & S. Beiker (Eds.), Road vehicle automation (pp. 229–245). Springer.
Srinivasan, A. (1999). A survey of the role of multicommodity flow and randomization in network design and routing. In P. M. Pardalos, S. Rajasekaran, & J. D. P. Rolim (Eds.), Randomization methods in algorithm design: DIMACS Workshop, December 12–14, 1997 (pp. 271–302). American Mathematical Society.
Tardos, É. (1985). A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3), 247–255.
Templeton, B. (2010). Traffic congestion & capacity. Available at http://www.templetons.com/brad/robocars/congestion.html. Accessed 15 Feb 2017.
Treiber, M., Hennecke, A., & Helbing, D. (2000). Microscopic simulation of congested traffic. In D. Helbing, H. J. Herrmann, M. Schreckenberg, & D. E. Wolf (Eds.), Traffic and granular flow ’99 (pp. 365–376). Berlin, Heidelberg: Springer.
Treleaven, K., Pavone, M., & Frazzoli, E. (2011). An asymptotically optimal algorithm for pickup and delivery problems. In Proceedings of IEEE Conference on decision and control.
Treleaven, K., Pavone, M., & Frazzoli, E. (2012). Models and efficient algorithms for pickup and delivery problems on roadmaps. In Proceedings of IEEE conference on decision and control.
Treleaven, K., Pavone, M., & Frazzoli, E. (2013). Asymptotically optimal algorithms for one-to-one pickup and delivery problems with applications to transportation systems. IEEE Transactions on Automatic Control, 58(9), 2261–2276.
Urmson, C. (2014). Just press go: Designing a self-driving vehicle. Available at http://googleblog.blogspot.com/2014/05/just-press-go-designing-self-driving.html. Accessed 15 Feb 2017.
Wardrop, J. G. (1952). Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, 1(3), 325–362.
Wilkie, D., van den Berg, J. P., Lin, M. C., & Manocha, D. (2011). Self-aware traffic route planning. In Proceedings of AAAI conference on artificial intelligence.
Wilkie, D., Baykal, C., & Lin, M. C. (2014). Participatory route planning. In ACM SIGSPATIAL.
Xiao, N., Frazzoli, E., Luo, Y., Li, Y., Wang, Y., & Wang, D. (2015). Throughput optimality of extended back-pressure traffic signal control algorithm. In Mediterranean conference on control and automation.
Yang, Q., & Koutsopoulos, H. N. (1996). A microscopic traffic simulator for evaluation of dynamic traffic management systems. Transportation Research Part C: Emerging Technologies, 4(3), 113–129.
Zhang, R., & Pavone, M. (2016). Control of robotic mobility-on-demand systems: A queueing-theoretical perspective. International Journal of Robotics Research, 35(1–3), 186–203.
Zhang, R., Rossi, F., & Pavone, M. (2016). Model predictive control of autonomous mobility-on-demand systems. In Proceedings of IEEE conference on robotics and automation.
Acknowledgements
The authors would like to thank Zachary Sunberg for his analysis on the road network symmetry of U.S. cities.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This is one of several papers published in Autonomous Robots comprising the “Special Issue on Robotics Science and Systems”.
An earlier version of this paper was presented at the Robotics: Science and Systems Conference, 2016. This extended and revised version includes a full proof of all theorems and lemmas presented in the paper. It also includes a significantly extended simulation section, including a numerical investigation of the capacity-symmetry of major U.S. cities and a characterization of the performance of the proposed real-time algorithm with a state-of-the-art microscopic agent-based simulator, MATSim. This research was supported by the National Science Foundation under CAREER Award CMMI-1454737, the Toyota Research Institute (TRI), and the Dr. Cleve B. Moler Stanford Graduate Fellowship. This article solely reflects the opinions and conclusions of its authors and not NSF, TRI, or any other Toyota entity. Rick Zhang worked on this paper while he was a Ph.D. student at Stanford University.
Electronic supplementary material
Below is the link to the electronic supplementary material.
Supplementary material 1 (mp4 10550 KB)
Rights and permissions
About this article
Cite this article
Rossi, F., Zhang, R., Hindy, Y. et al. Routing autonomous vehicles in congested transportation networks: structural properties and coordination algorithms. Auton Robot 42, 1427–1442 (2018). https://doi.org/10.1007/s10514-018-9750-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-018-9750-5