A nonlinear mathematical model for autonomous vehicle routing problem by considering traffic congestion for each route

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

2 Department of Industrial Engineering and Management Systems, Amirkabir University of Technology, Tehran, Iran

10.22070/jqepo.2023.16426.1238

Abstract

Emerging technologies, such as vehicle-to-road infrastructure connectivity via wireless telecommunications systems, in addition to reducing the role of humans in driving activities, can meaningfully improve road performance compared to traditional traffic control systems. Today, automated vehicles (AVs), as an emerging player in modern urban transportation, would significantly influence customer satisfaction. For AVs, the optimal routes must be found by a decision support system. This problem becomes more challenging when a suitable route is concurrently chosen by the majority of vehicles and network congestion occurs. In this research, a mathematical model for seeking the optimal route and scheduling of AVs by considering road traffic is presented. GAMS software is used for solving and analyzing the mathematical model. The results for a sample example show that the optimal routes are successfully obtained for the AVs. Sensitivity analysis reveals that as traffic time increases, so do the cost and service time. This model calls for government agencies to allocate portions of road networks to AVs to regulate vehicle movement and thus increase the output and performance of the network.

Keywords

References

Abdullah, Z. (2016) Grab to partner with nuTonomy for driverless car trial, users can book vehicles for free, http://www.straitstimes.com/singapore/transport/grab-to-partner-with-nutonomy-for-driverless-car-trial-users-can-book-vehicles, Accessed 19 December 2016.
Abdulaal, M., LeBlanc, L.J., 1979. Methods for combining modal split and equilibrium assignment models. Transp. Sci. 13 (4), 292–314.
Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., & Rus, D. (2017). On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, 114(3), 462-467.
Alam, M. J., & Habib, M. A. (2018). Investigation of the impacts of shared autonomous vehicle operation in halifax, canada using a dynamic traffic microsimulation model. Procedia computer science, 130, 496-503.
Alkaabneh, F., Diabat, A., & Elhedhli, S. (2019). A Lagrangian heuristic and GRASP for the hub-and-spoke network system with economies-of-scale and congestion. Transportation Research Part C: Emerging Technologies, 102, 249-273.
Bracy, J. M. B., Bao, K. Q., & Mundy, R. A. (2019). Highway infrastructure and safety implications of AV technology in the motor carrier industry. Research in transportation economics, 77, 100758.
Becker, F., & Axhausen, K. W. (2017). Literature review on surveys investigating the acceptance of automated vehicles. Transportation, 44(6), 1293-1306.
Burghout, W., Rigole, P. J., & Andreasson, I. (2015). Impacts of shared autonomous taxis in a metropolitan area. In Proceedings of the 94th annual meeting of the Transportation Research Board, Washington DC, 2015.
BMW Group, 2016. BMW Group, Intel and Mobileye Team up to Bring Fully Autonomous Driving to Streets by 2021. https://www.press.bmwgroup.com/global/article/detail/ T0261586EN/bmw-group-intel-and-mobileye-team-up-to-bring-fully-autonomous-driving-to- streets-by-2021?language¼en.
Boesch, P. M., Ciari, F., & Axhausen, K. W. (2016). Autonomous vehicle fleet sizes required to serve different levels of demand. Transportation Research Record, 2542(1), 111-119.
Cao, P., Hu, Y., Miwa, T., Wakita, Y., Morikawa, T., & Liu, X. (2017). An optimal mandatory lane change decision model for autonomous vehicles in urban arterials. Journal of Intelligent Transportation Systems, 21(4), 271-284.
Chen, Z., He, F., Zhang, L., & Yin, Y. (2016). Optimal deployment of autonomous vehicle lanes with endogenous market penetration. Transportation Research Part C: Emerging Technologies, 72, 143-156.
Chen, T. D., & Kockelman, K. M. (2016). Management of a shared autonomous electric vehicle fleet: Implications of pricing schemes. Transportation Research Record, 2572(1), 37-46.
Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573-586.
Dandl, F., Hyland, M., Bogenberger, K., & Mahmassani, H. S. (2019). Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets. Transportation, 46(6), 1975-1996.
Dandl, F., Engelhardt, R., Hyland, M., Tilg, G., Bogenberger, K., & Mahmassani, H. S. (2021). Regulating mobility-on-demand services: Tri-level model and Bayesian optimization solution approach. Transportation Research Part C: Emerging Technologies, 125, 103075.
Dia, H., & Javanshour, F. (2017). Autonomous shared mobility-on-demand: Melbourne pilot simulation study. Transportation Research Procedia, 22, 285-296.
Drexl, M. (2013). Applications of the vehicle routing problem with trailers and transshipments. European Journal of Operational Research, 227(2), 275-283.
Dresner, K., & Stone, P. (2008). A multiagent approach to autonomous intersection management. Journal of artificial intelligence research, 31, 591-656.
Fagnant, D. J., & Kockelman, K. M. (2018). Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in Austin, Texas. Transportation, 45(1), 143-158.
Fisher, M. L. (2004). The Lagrangian relaxation method for solving integer programming problems. Management science, 50(12_supplement), 1861-1871.
Fu, Y. M., & Diabat, A. (2015). A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem. Applied Mathematical Modelling, 39(3-4), 1194-1201.
Friedrich, B. (2015). Verkehrliche wirkung autonomer fahrzeuge. In Autonomes Fahren (pp. 331-350). Springer Vieweg, Berlin, Heidelberg.
Fortune (2016) Uber Debuts Self-Driving Cars in Pittsburgh, http://fortune.com/2016/09/14/uber-self-driving-cars- pittsburgh/, Accessed 20 September 2016.
Geoffrion, A. M. (2010). Lagrangian Relaxation for Integer Programming, 50 Years of Integer Programming, 1958-2008.
Gkartzonikas, C., & Gkritza, K. (2019). What have we learned? A review of stated preference and choice studies on autonomous vehicles. Transportation Research Part C: Emerging Technologies, 98, 323-337.
Gurumurthy, K. M., Kockelman, K. M., & Simoni, M. D. (2019). Benefits and costs of ride-sharing in shared automated vehicles across Austin, Texas: Opportunities for congestion pricing. Transportation Research Record, 2673(6), 548-556.
Gurumurthy, K. M., & Kockelman, K. M. (2018). Analyzing the dynamic ride-sharing potential for shared autonomous vehicle fleets using cellphone data from Orlando, Florida. Computers, Environment and Urban Systems, 71, 177-185.
Guignard, M. (2003). Lagrangean relaxation. Top, 11(2), 151-200.
Godsmark, P., & Kakkar, G. (2014). Why automated vehicle zones make sense. The Canadian Automated Vehicles Centre of Excellence.
Gong, S., & Du, L. (2018). Cooperative platoon control for a mixed traffic flow including human drive vehicles and connected and autonomous vehicles. Transportation research part B: methodological, 116, 25-61.
International Transport Forum. 2018. Safer roads with automated vehicles? https://www.itf- oecd.org/sites/default/files/docs/safer-roads-automated-vehicles.pdf
Imai, A., Nishimura, E., & Current, J. (2007). A Lagrangian relaxation-based heuristic for the vehicle routing with full container load. European journal of operational research, 176(1), 87-105.
Hamdan, B., & Diabat, A. (2020). Robust design of blood supply chains under risk of disruptions using Lagrangian relaxation. Transportation Research Part E: Logistics and Transportation Review, 134, 101764.
Hörl, S. (2017). Agent-based simulation of autonomous taxi services with dynamic demand responses. Procedia Computer Science, 109, 899-904.
Hosni, H., Naoum-Sawaya, J., & Artail, H. (2014). The shared-taxi problem: Formulation and solution methods. Transportation Research Part B: Methodological, 70, 303-318.
Hyland, M., & Mahmassani, H. S. (2018). Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AVs to immediate traveler demand requests. Transportation Research Part C: Emerging Technologies, 92, 278-297.
Jiang, N., Xie, C., Duthie, J. C., & Waller, S. T. (2014). A network equilibrium analysis on destination, route and parking choices with mixed gasoline and electric vehicular flows. EURO Journal on Transportation and Logistics, 3(1), 55-92.
Kakimoto, Y., Iryo-Asano, M., Orhan, E., & Nakamura, H. (2018). A study on the impact of AV-HDV mixed traffic on flow dynamics of single-lane motorway. Transportation research procedia, 34, 219-226.
Kesting, A., Treiber, M., & Helbing, D. (2010). Enhanced intelligent driver model to access the impact of driving strategies on traffic capacity. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 368(1928), 4585-4605.
Kang, D., Li, Z., & Levin, M. W. (2021). Evasion planning for autonomous intersection control based on an optimized conflict point control formulation. Journal of Transportation Safety & Security, 1-37.
Kang, D., Hu, F., & Levin, M. W. (2022). Impact of automated vehicles on traffic assignment, mode split, and parking behavior. Transportation research part D: transport and environment, 104, 103200.
Kang, D., & Miller, J. (2018). Low-effort techniques for incorporating driverless vehicles in legacy regional planning models (No. 18-01490).
Krueger, R., Rashidi, T. H., & Rose, J. M. (2016). Preferences for shared autonomous vehicles. Transportation research part C: emerging technologies, 69, 343-355.
Kim, S. H., Circella, G., & Mokhtarian, P. L. (2019). Identifying latent mode-use propensity segments in an all-AV era. Transportation Research Part A: Policy and Practice, 130, 192-207.
Korosec, K., 2018. Ford Plans to Spend $4 Billion on Autonomous Vehicles by 2023. https://techcrunch.com/2018/07/24/ford-plans-to-spend-4-billion-on-autonomous-vehicles-by-2023.
Lamotte, R., De Palma, A., & Geroliminis, N. (2017). On the use of reservation-based autonomous vehicles for demand management. Transportation Research Part B: Methodological, 99, 205-227.
Lai, J., Hu, J., Cui, L., Chen, Z., & Yang, X. (2020). A generic simulation platform for cooperative adaptive cruise control under partially connected and automated environment. Transportation Research Part C: Emerging Technologies, 121, 102874.
Levin, M. W., & Boyles, S. D. (2016). A multiclass cell transmission model for shared human and autonomous vehicle roads. Transportation Research Part C: Emerging Technologies, 62, 103-116.
Levin, M. W. (2017). Congestion-aware system optimal route choice for shared autonomous vehicles. Transportation Research Part C: Emerging Technologies, 82, 229-247.
Li, T., Guo, F., Krishnan, R., Sivakumar, A., & Polak, J. (2020). Right-of-way reallocation for mixed flow of autonomous vehicles and human driven vehicles. Transportation research part C: emerging technologies, 115, 102630.
Li, T., Han, X., Ma, J., Ramos, M., & Lee, C. (2021). Operational safety of automated and human driving in mixed traffic environments: A perspective of car-following behavior. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 1748006X211050696.
Liu, H., Lu, X. Y., & Shladover, S. E. (2019). Traffic signal control by leveraging cooperative adaptive cruise control (CACC) vehicle platooning capabilities. Transportation research part C: emerging technologies, 104, 390-407.
Liu, Z., Miwa, T., Zeng, W., Bell, M. G., & Morikawa, T. (2019). Dynamic shared autonomous taxi system considering on-time arrival reliability. Transportation Research Part C: Emerging Technologies, 103, 281-297.
Liu, Z., Miwa, T., Zeng, W., & Morikawa, T. (2018). An agent-based simulation model for shared autonomous taxi system. Asian Transport Studies, 5(1), 1-13.
Lioris, J., Cohen, G., Seidowsky, R., & Salem, H. H. (2016, October). Dynamic evolution and optimisation of an urban collective taxis systems by discrete-event simulation. In ITS World Congress 2016 (p. 10p).
Litman, T. (2017). Autonomous vehicle implementation predictions (p. 28). Victoria, BC, Canada: Victoria Transport Policy Institute.
Lokhandwala, M., & Cai, H. (2018). Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of NYC. Transportation Research Part C: Emerging Technologies, 97, 45-60.
Mahmassani, H. S., de Farias Pinto, H. K. R., Hyland, M. F., & Verbas, İ. Ö. (2018). Integrating Shared Autonomous Vehicle Fleet Services in Overall Urban Mobility: Dynamic Network Modeling Perspective.
Ma, J., Li, X., Zhou, F., & Hao, W. (2017). Designing optimal autonomous vehicle sharing and reservation systems: A linear programming approach. Transportation Research Part C: Emerging Technologies, 84, 124-141.
Ma, S., Zheng, Y., & Wolfson, O. (2014). Real-time city-scale taxi ridesharing. IEEE Transactions on Knowledge and Data Engineering, 27(7), 1782-1795.
Mao, C., Liu, Y., & Shen, Z. J. M. (2020). Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach. Transportation Research Part C: Emerging Technologies, 115, 102626.
Mousavi, S. M., Osman, O. A., Lord, D., Dixon, K. K., & Dadashova, B. (2021). Investigating the safety and operational benefits of mixed traffic environments with different automated vehicle market penetration rates in the proximity of a driveway on an urban arterial. Accident Analysis & Prevention, 152, 105982.
Mitchell, W. J., Borroni-Bird, C. E., & Burns, L. D. (2010). Reinventing the automobile: Personal urban mobility for the 21st century. MIT press.
Miller, J., & How, J. P. (2017, September). Demand estimation and chance-constrained fleet management for ride hailing. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 4481-4488). IEEE.
Navya (2016) Launch of NAVLY in the confluence district of Lyon, http://navya.tech/2016/09/launch-of-navly-in-the-confluence-district-of-lyon/?lang=en, Accessed 10 July 2016.
O’Kane, S. (2018). Former google self-driving wiz will help volkswagen and hyundai build fully autonomous cars. The Verge.
Oh, S., Seshadri, R., Azevedo, C. L., Kumar, N., Basak, K., & Ben-Akiva, M. (2020). Assessing the impacts of automated mobility-on-demand through agent-based simulation: A study of Singapore. Transportation Research Part A: Policy and Practice, 138, 367-388.
Oke, J. B., Akkinepally, A. P., Chen, S., Xie, Y., Aboutaleb, Y. M., Azevedo, C. L., ... & Ben-Akiva, M. (2020). Evaluating the systemic effects of automated mobility-on-demand services via large-scale agent-based simulation of auto-dependent prototype cities. Transportation Research Part A: Policy and Practice, 140, 98-126.
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.
Pimenta, V., Quilliot, A., Toussaint, H., & Vigo, D. (2017). Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles. European Journal of Operational Research, 257(2), 601-613.
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.
SAE International, 2021. Taxonomy and definitions for terms related to driving automated systems for on-road motor vehicles. Warrendale, Pennsylvania, U.S.A. https://www.sae.org/standards/content/j3016_202104/
Skinner, R. and N. Bidwell (2015) Making Better Places: Autonomous vehicles and future opportunities, WSP — Parsons Brinckerhoff.
Simoni, M. D., Kockelman, K. M., Gurumurthy, K. M., & Bischoff, J. (2019). Congestion pricing in a world of self-driving vehicles: An analysis of different strategies in alternative future scenarios. Transportation Research Part C: Emerging Technologies, 98, 167-185.‏
Simonetto, A., Monteil, J., & Gambella, C. (2019). Real-time city-scale ridesharing via linear assignment problems. Transportation Research Part C: Emerging Technologies, 101, 208-232.
Soltanzadeh, S., Mardan, E., & Kamran Rad, R. (2020). An Electric Vehicle Routing Problem with Battery Swap and Battery Recharge Approach. Journal of Quality Engineering and Production Optimization, 5(2), 1-20.
Su, Q., & Wang, D. Z. (2021). Spatial parking planning design with mixed conventional and autonomous vehicles. arXiv preprint arXiv:2104.01773.
Soteropoulos, A., Berger, M., & Ciari, F. (2019). Impacts of automated vehicles on travel behaviour and land use: an international review of modelling studies. Transport reviews, 39(1), 29-49.
Spieser, K., Treleaven, K., Zhang, R., Frazzoli, E., Morton, D., & Pavone, M. (2014). Toward a systematic approach to the design and evaluation of automated mobility-on-demand systems: A case study in Singapore. In Road vehicle automation (pp. 229-245). Springer, Cham.
Tao, C. C. (2007, September). Dynamic taxi-sharing service using intelligent transportation system technologies. In 2007 International Conference on Wireless Communications, Networking and Mobile Computing (pp. 3209-3212). IEEE.
Tientrakool, P., Ho, Y. C., & Maxemchuk, N. F. (2011, September). Highway capacity benefits from using vehicle-to-vehicle communication and sensors for collision avoidance. In 2011 IEEE Vehicular Technology Conference (VTC Fall) (pp. 1-5). IEEE.
 The Ford Company. 2021. Ford targets fully autonomous vehicle for ride sharing in 2021; invests in new tech companies, doubles Silicon Valley team. https://media.ford.com/content/fordmedia/fna/us/en/news/2016/08/16/ford-targets-fully-autonomous-vehicle-for-ride-sharing-in-2021.html
Vosooghi, R., Puchinger, J., Jankovic, M., & Vouillon, A. (2019). Shared autonomous vehicle simulation and service design. Transportation Research Part C: Emerging Technologies, 107, 15-33.
Wang, C., Gong, S., Zhou, A., Li, T., & Peeta, S. (2020). Cooperative adaptive cruise control for connected autonomous vehicles by factoring communication-related constraints. Transportation Research Part C: Emerging Technologies, 113, 124-145.
Wu, Y., Chen, H., & Zhu, F. (2019). DCL-AIM: Decentralized coordination learning of autonomous intersection management for connected and automated vehicles. Transportation Research Part C: Emerging Technologies, 103, 246-260.
Wu, W., Liu, W., Zhang, F., & Dixit, V. (2021). A new flexible parking reservation scheme for the morning commute under limited parking supplies. Networks and Spatial Economics, 21(3), 513-545.
Wu, W., Ng, W. S., Krishnaswamy, S., & Sinha, A. (2012, July). To taxi or not to taxi?-enabling personalised and real-time transportation decisions for mobile users. In 2012 IEEE 13th International Conference on Mobile Data Management (pp. 320-323). IEEE.
Yuan, J., Zheng, Y., Xie, X., & Sun, G. (2011). T-drive: Enhancing driving directions with taxi drivers' intelligence. IEEE Transactions on Knowledge and Data Engineering, 25(1), 220-232.
Zhang, W., & Guhathakurta, S. (2021). Residential location choice in the era of shared autonomous vehicles. Journal of Planning Education and Research, 41(2), 135-148.
Zhang, X., Liu, W., & Waller, S. T. (2019). A network traffic assignment model for autonomous vehicles with parking choices. Computer‐Aided Civil and Infrastructure Engineering, 34(12), 1100-1118.
Zheng, Y., Yuan, J., Xie, W., Xie, X., & Sun, G. (2010, October). Drive smartly as a taxi driver. In 2010 7th International Conference on Ubiquitous Intelligence & Computing and 7th International Conference on Autonomic & Trusted Computing (pp. 484-486). IEEE.
Zhu, S., Jiang, G., & Lo, H. K. (2018). Capturing value of reliability through road pricing in congested traffic under uncertainty. Transportation Research Part C: Emerging Technologies, 94, 236-249.
Zhou, M., Le, D. T., Nguyen-Phuoc, D. Q., Zegras, P. C., & Ferreira Jr, J. (2021). Simulating impacts of Automated Mobility-on-Demand on accessibility and residential relocation. Cities, 118, 103345.
Journal of Quality Engineering and Production Optimization
Volume 7, Issue 2
December 2022
Pages 14-33

Files

Share

How to cite

Statistics