IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v18y2020i4d10.1007_s10288-019-00429-7.html
   My bibliography  Save this article

Bi-objective autonomous vehicle repositioning problem with travel time uncertainty

Author

Listed:
  • Hadi Charkhgard

    (University of South Florida)

  • Mahdi Takalloo

    (University of South Florida)

  • Zulqarnain Haider

    (University of South Florida)

Abstract

We study the problem of repositioning autonomous vehicles in a shared mobility system in order to simultaneously minimize the unsatisfied demand and the total operating cost. We first present a mixed integer linear programming formulation for the deterministic version of the problem. We extend this formulation to make it easier to work with in the non-deterministic setting. We then show how the travel time uncertainty can be incorporated into this extended deterministic formulation using chance-constraint programming. Finally, two new reformulations for the proposed chance-constraint program are developed. We show a critical result that the size of one of the reformulations (in terms of the number of variables and constraints) does not depend on the number of scenarios, and so it outperforms the other reformulation. Both reformulations are bi-objective mixed integer linear programs with a finite number of nondominated points and so they can be solved directly by algorithms such as the balanced box method (Boland et al. in INFORMS J Comput 27(4):735–754, 2015). A computational study demonstrates the efficacy of the proposed reformulations.

Suggested Citation

  • Hadi Charkhgard & Mahdi Takalloo & Zulqarnain Haider, 2020. "Bi-objective autonomous vehicle repositioning problem with travel time uncertainty," 4OR, Springer, vol. 18(4), pages 477-505, December.
    • Handle: RePEc:spr:aqjoor:v:18:y:2020:i:4:d:10.1007_s10288-019-00429-7
    DOI: 10.1007/s10288-019-00429-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-019-00429-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-019-00429-7?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. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.
    3. Martin, Elliot & Shaheen, Susan Alison & Lidicker, Jeffrey, 2010. "Carsharing’S Impact On Household Vehicle Holdings: Results From A North American Shared-Use Vehicle Survey," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt0850h6r5, Institute of Transportation Studies, UC Berkeley.
    4. Martin, Elliot & Shaheen, Susan A & Lidicker, Jeffrey, 2010. "Impact of Carsharing on Household Vehicle Holdings: Resultsvfrom a North American Shared-Use Vehicle Survey," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt3bn9n6pq, Institute of Transportation Studies, UC Berkeley.
    5. Chebbi, Olfa & Chaouachi, Jouhaina, 2016. "Reducing the wasted transportation capacity of Personal Rapid Transit systems: An integrated model and multi-objective optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 236-258.
    6. Martin, Elliot & Shaheen, Susan Alison & Lidicker, Jeffrey, 2010. "Carsharing’S Impact On Household Vehicle Holdings: Results From A North American Shared-Use Vehicle Survey," Institute of Transportation Studies, Working Paper Series qt0850h6r5, Institute of Transportation Studies, UC Davis.
    7. John D. Lees-Miller, 2016. "Minimising average passenger waiting time in personal rapid transit systems," Annals of Operations Research, Springer, vol. 236(2), pages 405-424, January.
    8. Correia, Gonçalo Homem de Almeida & Antunes, António Pais, 2012. "Optimization approach to depot location and trip selection in one-way carsharing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 233-247.
    9. Shaheen, Susan A & Cohen, Adam P & Roberts, J. Darius, 2006. "Carsharing in North America: Market Growth, Current Developments, and Future Potential," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt46b7n137, Institute of Transportation Studies, UC Berkeley.
    10. Shaheen, Susan A & Cohen, Adam P, 2007. "Growth in Worldwide Carsharing: An International Comparison," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt2zv240pp, Institute of Transportation Studies, UC Berkeley.
    11. John Lees-Miller, 2016. "Minimising average passenger waiting time in personal rapid transit systems," Annals of Operations Research, Springer, vol. 236(2), pages 405-424, January.
    12. Kek, Alvina G.H. & Cheu, Ruey Long & Meng, Qiang & Fung, Chau Ha, 2009. "A decision support system for vehicle relocation operations in carsharing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 149-158, January.
    13. A. Charnes & W. W. Cooper, 1959. "Chance-Constrained Programming," Management Science, INFORMS, vol. 6(1), pages 73-79, October.
    14. Thomas Stidsen & Kim Allan Andersen & Bernd Dammann, 2014. "A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs," Management Science, INFORMS, vol. 60(4), pages 1009-1032, April.
    15. Liang, Xiao & Correia, Gonçalo Homem de Almeida & van Arem, Bart, 2016. "Optimizing the service area and trip selection of an electric automated taxi system used for the last mile of train trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 115-129.
    16. M. C. Campi & S. Garatti, 2011. "A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality," Journal of Optimization Theory and Applications, Springer, vol. 148(2), pages 257-280, February.
    17. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 735-754, November.
    18. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 597-618, November.
    19. B. K. Pagnoncelli & S. Ahmed & A. Shapiro, 2009. "Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications," Journal of Optimization Theory and Applications, Springer, vol. 142(2), pages 399-416, August.
    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. Najmesadat Nazemi & Sophie N. Parragh & Walter J. Gutjahr, 2022. "Bi-objective facility location under uncertainty with an application in last-mile disaster relief," Annals of Operations Research, Springer, vol. 319(2), pages 1689-1716, December.

    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. Golalikhani, Masoud & Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando & Antunes, António Pais, 2021. "Carsharing: A review of academic literature and business practices toward an integrated decision-support framework," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    2. Xiaowei Chen & Hongyu Zheng & Ze Wang & Xiqun Chen, 2021. "Exploring impacts of on-demand ridesplitting on mobility via real-world ridesourcing data and questionnaires," Transportation, Springer, vol. 48(4), pages 1541-1561, August.
    3. Yoon-Young Chun & Mitsutaka Matsumoto & Kiyotaka Tahara & Kenichiro Chinen & Hideki Endo, 2019. "Exploring Factors Affecting Car Sharing Use Intention in the Southeast-Asia Region: A Case Study in Java, Indonesia," Sustainability, MDPI, vol. 11(18), pages 1-26, September.
    4. Mehdi Nourinejad & Matthew Roorda, 2015. "Carsharing operations policies: a comparison between one-way and two-way systems," Transportation, Springer, vol. 42(3), pages 497-518, May.
    5. Susan Shaheen & Nelson Chan & Helen Micheaux, 2015. "One-way carsharing’s evolution and operator perspectives from the Americas," Transportation, Springer, vol. 42(3), pages 519-536, May.
    6. Irfan Ullah & Kai Liu & Tran Vanduy, 2019. "Examining Travelers’ Acceptance towards Car Sharing Systems—Peshawar City, Pakistan," Sustainability, MDPI, vol. 11(3), pages 1-16, February.
    7. Junhee Kang & Keeyeon Hwang & Sungjin Park, 2016. "Finding Factors that Influence Carsharing Usage: Case Study in Seoul," Sustainability, MDPI, vol. 8(8), pages 1-12, July.
    8. Cartenì, Armando & Cascetta, Ennio & de Luca, Stefano, 2016. "A random utility model for park & carsharing services and the pure preference for electric vehicles," Transport Policy, Elsevier, vol. 48(C), pages 49-59.
    9. Firnkorn, Jörg & Müller, Martin, 2011. "What will be the environmental effects of new free-floating car-sharing systems? The case of car2go in Ulm," Ecological Economics, Elsevier, vol. 70(8), pages 1519-1528, June.
    10. Nadine Gatzert & Katrin Osterrieder, 2020. "The future of mobility and its impact on the automobile insurance industry," Risk Management and Insurance Review, American Risk and Insurance Association, vol. 23(1), pages 31-51, March.
    11. Pierpaolo D’Urso & Alessio Guandalini & Francesca Romana Mallamaci & Vincenzina Vitale & Laura Bocci, 2021. "To Share or not to Share? Determinants of Sharing Mobility in Italy," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 154(2), pages 647-692, April.
    12. Long He & Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2017. "Service Region Design for Urban Electric Vehicle Sharing Systems," Manufacturing & Service Operations Management, INFORMS, vol. 19(2), pages 309-327, May.
    13. Nourinejad, Mehdi & Roorda, Matthew J., 2014. "A dynamic carsharing decision support system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 66(C), pages 36-50.
    14. Elliot Martin & Susan Shaheen, 2011. "The Impact of Carsharing on Public Transit and Non-Motorized Travel: An Exploration of North American Carsharing Survey Data," Energies, MDPI, vol. 4(11), pages 1-21, November.
    15. Frank, Laura & Dirks, Nicolas & Walther, Grit, 2021. "Improving rural accessibility by locating multimodal mobility hubs," Journal of Transport Geography, Elsevier, vol. 94(C).
    16. Firnkorn, Jörg, 2012. "Triangulation of two methods measuring the impacts of a free-floating carsharing system in Germany," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(10), pages 1654-1672.
    17. Diana, Marco & Chicco, Andrea, 2022. "The spatial reconfiguration of parking demand due to car sharing diffusion: a simulated scenario for the cities of Milan and Turin (Italy)," Journal of Transport Geography, Elsevier, vol. 98(C).
    18. Susanna Ulinski, 2015. "Corporate Social Innovation as a Driver of Performance and Welfare. WWWforEurope Policy Paper No. 25," WIFO Studies, WIFO, number 58500, Juni.
    19. Rotaris, Lucia & Danielis, Romeo & Maltese, Ila, 2019. "Carsharing use by college students: The case of Milan and Rome," Transportation Research Part A: Policy and Practice, Elsevier, vol. 120(C), pages 239-251.
    20. Maria Juschten & Timo Ohnmacht & Vu Thi Thao & Regine Gerike & Reinhard Hössinger, 2019. "Carsharing in Switzerland: identifying new markets by predicting membership based on data on supply and demand," Transportation, Springer, vol. 46(4), pages 1171-1194, August.

    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:spr:aqjoor:v:18:y:2020:i:4:d:10.1007_s10288-019-00429-7. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.