IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v141y2020icp98-115.html
   My bibliography  Save this article

Optimal assignment for the single-household shared autonomous vehicle problem

Author

Listed:
  • Cokyasar, Taner
  • Larson, Jeffrey

Abstract

Autonomous vehicles have the potential to transform the way people are transported. While driverless technology may mean fewer vehicles are required to transport people to and from their daily activities, such changes may result in increased congestion or total miles traveled. In this study, we solve the single-household shared autonomous vehicle problem to identify cost-optimal routings of vehicles throughout the day. Such a tool will be useful for consumers seeking to minimize cost and for regulators seeking to understand and predict how people may behave in different scenarios. We provide a thorough literature review and construct a mixed-integer linear program to minimize the daily travel cost of a household attending a given set of activities. Since solution time is a determinant for applicability of such a model, we present the model in a component-wise fashion. This approach allows us to understand which features most affect the problem complexity and solution time. We note that modeling carpooling is the feature that most increases time to find an optimal solution, and we therefore propose a novel modeling technique for carpooling two people. We illustrate the performance of our model by comparing it with other models from the literature and note that our model can solve significantly larger problem instances and in a time that is short enough to facilitate real-time scheduling. We also highlight the utility of our model for regulators, who can use it to analyze quickly produced optimal routes under different cost/tax scenarios.

Suggested Citation

  • Cokyasar, Taner & Larson, Jeffrey, 2020. "Optimal assignment for the single-household shared autonomous vehicle problem," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 98-115.
  • Handle: RePEc:eee:transb:v:141:y:2020:i:c:p:98-115
    DOI: 10.1016/j.trb.2020.09.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261520303866
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2020.09.003?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    2. Daniel J. Fagnant & Kara M. Kockelman, 2018. "Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in Austin, Texas," Transportation, Springer, vol. 45(1), pages 143-158, January.
    3. Lawrence D. Bodin & Lon Berman, 1979. "Routing and Scheduling of School Buses by Computer," Transportation Science, INFORMS, vol. 13(2), pages 113-129, May.
    4. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    5. Correia, Gonçalo Homem de Almeida & van Arem, Bart, 2016. "Solving the User Optimum Privately Owned Automated Vehicles Assignment Problem (UO-POAVAP): A model to explore the impacts of self-driving vehicles on urban mobility," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 64-88.
    6. Fagnant, Daniel J. & Kockelman, Kara, 2015. "Preparing a nation for autonomous vehicles: opportunities, barriers and policy recommendations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 77(C), pages 167-181.
    7. Fleming, Christopher L. & Griffis, Stanley E. & Bell, John E., 2013. "The effects of triangle inequality on the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 1-7.
    8. Loeb, Benjamin & Kockelman, Kara M., 2019. "Fleet performance and cost evaluation of a shared autonomous electric vehicle (SAEV) fleet: A case study for Austin, Texas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 121(C), pages 374-385.
    9. Chen, T. Donna & Kockelman, Kara M. & Hanna, Josiah P., 2016. "Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions," Transportation Research Part A: Policy and Practice, Elsevier, vol. 94(C), pages 243-254.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tscharaktschiew, Stefan & Reimann, Felix, 2023. "The economics of speed choice and control in the presence of driverless vehicle cruising and parking-as-a-substitute-for-cruising," Transportation Research Part B: Methodological, Elsevier, vol. 178(C).
    2. Bo Zou & Pooria Choobchian & Julie Rozenberg, 2021. "Cyber resilience of autonomous mobility systems: cyber-attacks and resilience-enhancing strategies," Journal of Transportation Security, Springer, vol. 14(3), pages 137-155, December.
    3. Zhang, Li & Liu, Zhongshan & Yu, Lan & Fang, Ke & Yao, Baozhen & Yu, Bin, 2022. "Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    4. Wang, Zhimian & An, Kun & Correia, Gonçalo & Ma, Wanjing, 2024. "Real-time scheduling and routing of shared autonomous vehicles considering platooning in intermittent segregated lanes and priority at intersections in urban corridors," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 186(C).
    5. Mohamad Shatanawi & Ferenc Mészáros, 2022. "Implications of the Emergence of Autonomous Vehicles and Shared Autonomous Vehicles: A Budapest Perspective," Sustainability, MDPI, vol. 14(17), pages 1-19, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Levin, Michael W., 2022. "A general maximum-stability dispatch policy for shared autonomous vehicle dispatch with an analytical characterization of the maximum throughput," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 258-280.
    2. Gurumurthy, Krishna Murthy & Kockelman, Kara M., 2022. "Dynamic ride-sharing impacts of greater trip demand and aggregation at stops in shared autonomous vehicle systems," Transportation Research Part A: Policy and Practice, Elsevier, vol. 160(C), pages 114-125.
    3. Li, Dun & Huang, Youlin & Qian, Lixian, 2022. "Potential adoption of robotaxi service: The roles of perceived benefits to multiple stakeholders and environmental awareness," Transport Policy, Elsevier, vol. 126(C), pages 120-135.
    4. Zwick, Felix & Kuehnel, Nico & Hörl, Sebastian, 2022. "Shifts in perspective: Operational aspects in (non-)autonomous ride-pooling simulations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 165(C), pages 300-320.
    5. Becker, Henrik & Becker, Felix & Abe, Ryosuke & Bekhor, Shlomo & Belgiawan, Prawira F. & Compostella, Junia & Frazzoli, Emilio & Fulton, Lewis M. & Guggisberg Bicudo, Davi & Murthy Gurumurthy, Krishna, 2020. "Impact of vehicle automation and electric propulsion on production costs for mobility services worldwide," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 105-126.
    6. Guo, Yuntao & Souders, Dustin & Labi, Samuel & Peeta, Srinivas & Benedyk, Irina & Li, Yujie, 2021. "Paving the way for autonomous Vehicles: Understanding autonomous vehicle adoption and vehicle fuel choice under user heterogeneity," Transportation Research Part A: Policy and Practice, Elsevier, vol. 154(C), pages 364-398.
    7. Sehyun Tak & Soomin Woo & Sungjin Park & Sunghoon Kim, 2021. "The City-Wide Impacts of the Interactions between Shared Autonomous Vehicle-Based Mobility Services and the Public Transportation System," Sustainability, MDPI, vol. 13(12), pages 1-29, June.
    8. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    9. Sajjad Shafiei & Ziyuan Gu & Hanna Grzybowska & Chen Cai, 2023. "Impact of self-parking autonomous vehicles on urban traffic congestion," Transportation, Springer, vol. 50(1), pages 183-203, February.
    10. Al-Kanj, Lina & Nascimento, Juliana & Powell, Warren B., 2020. "Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1088-1106.
    11. Cui, Hongjun & Yang, Yizhe & Zhu, Minqing & Ma, Xinwei & Chen, Xiuyong & Qie, Binghui, 2023. "The scheduling methods with different demand priorities for shared autonomous vehicle system in hybrid demands mode considering dynamic travel time," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 632(P1).
    12. Zhou, Fan & Zheng, Zuduo & Whitehead, Jake & Perrons, Robert K. & Washington, Simon & Page, Lionel, 2020. "Examining the impact of car-sharing on private vehicle ownership," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 322-341.
    13. Gurumurthy, Krishna Murthy & Kockelman, Kara M., 2021. "Impacts of shared automated vehicles on airport access and operations, with opportunities for revenue recovery: Case Study of Austin, Texas," Research in Transportation Economics, Elsevier, vol. 90(C).
    14. Nadafianshahamabadi, Razieh & Tayarani, Mohammad & Rowangould, Gregory, 2021. "A closer look at urban development under the emergence of autonomous vehicles: Traffic, land use and air quality impacts," Journal of Transport Geography, Elsevier, vol. 94(C).
    15. Nourinejad, Mehdi & Bahrami, Sina & Roorda, Matthew J., 2018. "Designing parking facilities for autonomous vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 110-127.
    16. Mourad, Abood & Puchinger, Jakob & Chu, Chengbin, 2019. "A survey of models and algorithms for optimizing shared mobility," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 323-346.
    17. Milakis, Dimitris & Kroesen, Maarten & van Wee, Bert, 2018. "Implications of automated vehicles for accessibility and location choices: Evidence from an expert-based experiment," Journal of Transport Geography, Elsevier, vol. 68(C), pages 142-148.
    18. Marletto, Gerardo, 2019. "Who will drive the transition to self-driving? A socio-technical analysis of the future impact of automated vehicles," Technological Forecasting and Social Change, Elsevier, vol. 139(C), pages 221-234.
    19. Mo, Dong & Chen, Xiqun (Michael) & Zhang, Junlin, 2022. "Modeling and Managing Mixed On-Demand Ride Services of Human-Driven Vehicles and Autonomous Vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 80-119.
    20. Luo, Qi & Saigal, Romesh & Chen, Zhibin & Yin, Yafeng, 2019. "Accelerating the adoption of automated vehicles by subsidies: A dynamic games approach," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 226-243.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:141:y:2020:i:c:p:98-115. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.