Learning to Branch-and-Bound to Route an Autonomous Mobility on Demand System
DOI:
https://doi.org/10.47611/jsrhs.v11i4.3606Keywords:
machine learning, branch-and-bound, autonomous mobility on demandAbstract
Autonomous Mobility on Demand (AMoD) is a system consisting of a fleet of centrally-controlled, autonomous vehicles that take customers from their requested origins to their requested destinations. In order to minimize the distance traveled by the fleet, a routing scheme must be developed to service all customer requests. This paper investigates the usage of the branch-and-bound algorithm (BB) to find such a scheme, as well as the usage of a neural network (NN) to speed up BB. Given a fixed road network, sets of randomly generated requests were passed into BB to obtain the ordering of each set that minimized the number of computations, and a NN was trained on this data. New randomly generated request sets were then passed into the trained NN, and runtimes given the NN-predicted orderings were compared to average runtimes over all permutations. For a NN with 1024 nodes in the first and 512 in the second hidden layer and a learning rate of 0.1, using the NN resulted in an average 40% decrease from average runtimes; furthermore, NN-orderings never resulted in increased runtime. Other combinations of NN parameters resulted in around 25% decrease in runtime. Also, BB performed the same number of computations for all permutations with the same first request, simplifying the problem to only finding the next request. These results show that training the NN results in a more efficient, faster routing algorithm that is therefore easier to scale up, enabling at-scale adoption of AMoD.
Downloads
References or Bibliography
Pavone, M. (2015). Autonomous mobility-on-demand systems for future urban mobility. In Autonomes Fahren (pp. 399-416). Springer Vieweg, Berlin, Heidelberg. Available at https://link.springer.com/chapter/10.1007/978-3-662-45854-9_19.
Land, A. H., & Doig, A. G. (2010). An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008 (pp. 105-132). Springer, Berlin, Heidelberg. Available at https://link.springer.com/chapter/10.1007/978-3-540-68279-0_5.
He, H., Daume III, H., & Eisner, J. M. (2014). Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27. Available at https://proceedings.neurips.cc/paper/2014/hash/757f843a169cc678064d9530d12a1881-Abstract.html.
R. Zhang and M. Pavone. Control of robotic Mobility-on-Demand systems: A queueing-theoretical perspective. Int. Journal of Robotics Research, 35(1–3):186–203, 2016. Available at https://journals.sagepub.com/doi/abs/10.1177/0278364915581863.
Iglesias, R., Rossi, F., Zhang, R., & Pavone, M. (2019). A BCMP network approach to modeling and controlling autonomous mobility-on-demand systems. The International Journal of Robotics Research, 38(2-3), 357-374. Available at https://journals.sagepub.com/doi/full/10.1177/0278364918780335?casa_token=celUGTO7nC4AAAAA%3AU9TeABMhkCHjwoQn3X4XruP8ACMaDDFtAZqQeuB4387rgGaK9t9zX9GqS3-hK_4y9FS_73xipoTW.
Hörl, S., Ruch, C., Becker, F., Frazzoli, E., & Axhausen, K. W. (2018). Fleet control algorithms for automated mobility: A simulation assessment for Zurich. In 2018 TRB Annual Meeting Online (pp. 18-02171). Transportation Research Board. Available at https://trid.trb.org/view/1495210.
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. Available at https://www.sciencedirect.com/science/article/pii/S019897151630237X?casa_token=dt530Laj49sAAAAA:c2Jr6ayr7lbPrhlG5BJ__sDAEik1sIBukQRoVHr0eHt96IlM4kthOl_xJHH5t1G8V5z39E-0JQ.
Iglesias, R., Rossi, F., Wang, K., Hallac, D., Leskovec, J., & Pavone, M. (2018, May). Data-driven model predictive control of autonomous mobility-on-demand systems. In 2018 IEEE international conference on robotics and automation (ICRA) (pp. 6019-6025). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/8460966.
Zhang, R., Rossi, F., & Pavone, M. (2016, May). Model predictive control of autonomous mobility-on-demand systems. In 2016 IEEE International Conference on Robotics and Automation (ICRA) (pp. 1382-1389). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/7487272.
Xu, J., Rahmatizadeh, R., Bölöni, L., & Turgut, D. (2017). Real-time prediction of taxi demand using recurrent neural networks. IEEE Transactions on Intelligent Transportation Systems, 19(8), 2572-2581. Available at https://ieeexplore.ieee.org/abstract/document/8082792.
Tsao, M., Milojevic, D., Ruch, C., Salazar, M., Frazzoli, E., & Pavone, M. (2019, May). Model predictive control of ride-sharing autonomous mobility-on-demand systems. In 2019 International Conference on Robotics and Automation (ICRA) (pp. 6665-6671). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/8794194.
Rossi, F., Zhang, R., Hindy, Y., & Pavone, M. (2018). Routing autonomous vehicles in congested transportation networks: Structural properties and coordination algorithms. Autonomous Robots, 42(7), 1427-1442. Available at https://link.springer.com/article/10.1007/s10514-018-9750-5.
Salazar, M., Tsao, M., Aguiar, I., Schiffer, M., & Pavone, M. (2019, June). A congestion-aware routing scheme for autonomous mobility-on-demand systems. In 2019 18th European Control Conference (ECC) (pp. 3040-3046). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/8795897.
Wollenstein-Betech, S., Houshmand, A., Salazar, M., Pavone, M., Cassandras, C. G., & Paschalidis, I. C. (2020, September). Congestion-aware routing and rebalancing of autonomous mobility-on-demand systems in mixed traffic. In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC) (pp. 1-7). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/9294258.
Khalil, E., Le Bodic, P., Song, L., Nemhauser, G., & Dilkina, B. (2016, February). Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 30, No. 1). Available at https://ojs.aaai.org/index.php/AAAI/article/view/10080.
Etheve, M., Alès, Z., Bissuel, C., Juan, O., & Kedad-Sidhoum, S. (2020, September). Reinforcement learning for variable selection in a branch and bound algorithm. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (pp. 176-185). Springer, Cham. Available at https://link.springer.com/chapter/10.1007/978-3-030-58942-4_12.
Diamond, S., & Boyd, S. (2016). CVXPY: A Python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1), 2909-2913. Available at https://www.jmlr.org/papers/volume17/15-408/15-408.pdf.
Rossi, F., Iglesias, R., Alizadeh, M., & Pavone, M. (2019). On the interaction between Autonomous Mobility-on-Demand systems and the power network: Models and coordination algorithms. IEEE Transactions on Control of Network Systems, 7(1), 384-397. Available at https://ieeexplore.ieee.org/abstract/document/8737720.
Estandia, A., Schiffer, M., Rossi, F., Luke, J., Kara, E. C., Rajagopal, R., & Pavone, M. (2021). On the interaction between autonomous mobility on demand systems and power distribution networks—an optimal power flow approach. IEEE Transactions on Control of Network Systems, 8(3), 1163-1176. Available at https://ieeexplore.ieee.org/abstract/document/9354039.
Boewing, F., Schiffer, M., Salazar, M., & Pavone, M. (2020, July). A vehicle coordination and charge scheduling algorithm for electric autonomous mobility-on-demand systems. In 2020 American Control Conference (ACC) (pp. 248-255). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/9147734.
Salazar, M., Lanzetti, N., Rossi, F., Schiffer, M., & Pavone, M. (2019). Intermodal autonomous mobility-on-demand. IEEE Transactions on Intelligent Transportation Systems, 21(9), 3946-3960. Available at https://ieeexplore.ieee.org/abstract/document/8894439.
Wollenstein-Betech, S., Salazar, M., Houshmand, A., Pavone, M., Paschalidis, I. C., & Cassandras, C. G. (2021). Routing and rebalancing intermodal autonomous mobility-on-demand systems in mixed traffic. IEEE Transactions on Intelligent Transportation Systems. Available at https://ieeexplore.ieee.org/document/9541261.
Zgraggen, J., Tsao, M., Salazar, M., Schiffer, M., & Pavone, M. (2019, October). A model predictive control scheme for intermodal autonomous mobility-on-demand. In 2019 IEEE Intelligent Transportation Systems Conference (ITSC) (pp. 1953-1960). IEEE. Available at https://ieeexplore.ieee.org/abstract/document/8917521.
Published
How to Cite
Issue
Section
Copyright (c) 2022 Claire Xu; Robin Brown, Somrita Banerjee, Marco Pavone
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright holder(s) granted JSR a perpetual, non-exclusive license to distriute & display this article.
