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

Choice-driven dial-a-ride problem for demand responsive mobility service

Author

Listed:
  • Sharif Azadeh, Sh.
  • Atasoy, Bilge
  • Ben-Akiva, Moshe E.
  • Bierlaire, M.
  • Maknoon, M.Y.

Abstract

Urban mobility services face the challenge of planning their operations efficiently while complying with user preferences. In this paper, we introduce a new mathematical model called a choice-driven dial-a-ride problem (CD-DARP) which is a generalization of the dynamic DARP where passenger behavior is integrated in the operational planning using choice models and assortment optimization. We look at two types of mobility services, private and shared. Our problem extends the dynamic DARP by (i) changing its objective function to profit maximization, where both cost and revenue are variables, and (ii) incorporating assortment optimization with routing decisions in a dynamic setting. We propose a pricing scheme based on a choice model designed to offer service alternatives at the time a customer makes a request. We introduce a tailored algorithm to efficiently solve the dynamic CD-DARP. Computational results indicate that our proposed approach outperforms dynamic DARP in terms of reducing routing costs and improving the number of customers served.

Suggested Citation

  • Sharif Azadeh, Sh. & Atasoy, Bilge & Ben-Akiva, Moshe E. & Bierlaire, M. & Maknoon, M.Y., 2022. "Choice-driven dial-a-ride problem for demand responsive mobility service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 128-149.
    • Handle: RePEc:eee:transb:v:161:y:2022:i:c:p:128-149
    DOI: 10.1016/j.trb.2022.04.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261522000716
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2022.04.008?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. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    2. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    3. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    4. Pacheco Paneque, Meritxell & Bierlaire, Michel & Gendron, Bernard & Sharif Azadeh, Shadi, 2021. "Integrating advanced discrete choice models in mixed integer linear optimization," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 26-49.
    5. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    6. R M Jorgensen & J Larsen & K B Bergvinsdottir, 2007. "Solving the Dial-a-Ride problem using genetic algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(10), pages 1321-1331, October.
    7. Gerardo Berbeglia & Gilles Pesant & Louis-Martin Rousseau, 2011. "Checking the Feasibility of Dial-a-Ride Instances Using Constraint Programming," Transportation Science, INFORMS, vol. 45(3), pages 399-412, August.
    8. A. Gürhan Kök & Marshall L. Fisher & Ramnath Vaidyanathan, 2008. "Assortment Planning: Review of Literature and Industry Practice," International Series in Operations Research & Management Science, in: Narendra Agrawal & Stephen A. Smith (ed.), Retail Supply Chain Management, chapter 0, pages 99-153, Springer.
    9. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    10. Felipe F. Dias & Patrícia S. Lavieri & Venu M. Garikapati & Sebastian Astroza & Ram M. Pendyala & Chandra R. Bhat, 2017. "A behavioral choice model of the use of car-sharing and ride-sourcing services," Transportation, Springer, vol. 44(6), pages 1307-1323, November.
    11. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    12. Kyle D. Chen & Warren H. Hausman, 2000. "Technical Note: Mathematical Properties of the Optimal Product Line Selection Problem Using Choice-Based Conjoint Analysis," Management Science, INFORMS, vol. 46(2), pages 327-332, February.
    13. Kalyan Talluri & Garrett van Ryzin, 2004. "Revenue Management Under a General Discrete Choice Model of Consumer Behavior," Management Science, INFORMS, vol. 50(1), pages 15-33, January.
    14. James M. Davis & Guillermo Gallego & Huseyin Topaloglu, 2014. "Assortment Optimization Under Variants of the Nested Logit Model," Operations Research, INFORMS, vol. 62(2), pages 250-273, April.
    15. Mitrovic-Minic, Snezana & Laporte, Gilbert, 2004. "Waiting strategies for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(7), pages 635-655, August.
    16. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    17. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2008. "The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments," European Journal of Operational Research, Elsevier, vol. 185(2), pages 534-551, March.
    18. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    19. Bösch, Patrick M. & Becker, Felix & Becker, Henrik & Axhausen, Kay W., 2018. "Cost-based analysis of autonomous mobility services," Transport Policy, Elsevier, vol. 64(C), pages 76-91.
    20. Jean-François Cordeau, 2006. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem," Operations Research, INFORMS, vol. 54(3), pages 573-586, June.
    21. Sayarshad, Hamid R. & Chow, Joseph Y.J., 2015. "A scalable non-myopic dynamic dial-a-ride and pricing problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 539-554.
    22. Train,Kenneth E., 2009. "Discrete Choice Methods with Simulation," Cambridge Books, Cambridge University Press, number 9780521747387, November.
    23. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    24. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    25. Gerardo Berbeglia & Jean-François Cordeau & Gilbert Laporte, 2012. "A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 343-355, August.
    26. Köhler, Charlotte & Ehmke, Jan Fabian & Campbell, Ann Melissa, 2020. "Flexible time window management for attended home deliveries," Omega, Elsevier, vol. 91(C).
    27. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    28. Schilde, M. & Doerner, K.F. & Hartl, R.F., 2014. "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 18-30.
    29. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    30. A. Charnes & W. W. Cooper, 1962. "Programming with linear fractional functionals," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 9(3‐4), pages 181-186, September.
    31. Bruck, Bruno P. & Cordeau, Jean-François & Iori, Manuel, 2018. "A practical time slot management and routing problem for attended home services," Omega, Elsevier, vol. 81(C), pages 208-219.
    32. Coslovich, Luca & Pesenti, Raffaele & Ukovich, Walter, 2006. "A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1605-1615, December.
    33. Paat Rusmevichientong & Zuo-Jun Max Shen & David B. Shmoys, 2010. "Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint," Operations Research, INFORMS, vol. 58(6), pages 1666-1680, December.
    34. Ulmer, Marlin W. & Thomas, Barrett W., 2020. "Meso-parametric value function approximation for dynamic customer acceptances in delivery routing," European Journal of Operational Research, Elsevier, vol. 285(1), pages 183-195.
    35. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    36. Qian, Xinwu & Zhang, Wenbo & Ukkusuri, Satish V. & Yang, Chao, 2017. "Optimal assignment and incentive design in the taxi group ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 208-226.
    37. Fabien Lehuédé & Renaud Masson & Sophie N Parragh & Olivier Péton & Fabien Tricoire, 2014. "A multi-criteria large neighbourhood search for the transportation of disabled people," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(7), pages 983-1000, July.
    38. Paquette, Julie & Cordeau, Jean-François & Laporte, Gilbert & Pascoal, Marta M.B., 2013. "Combining multicriteria analysis and tabu search for dial-a-ride problems," Transportation Research Part B: Methodological, Elsevier, vol. 52(C), pages 1-16.
    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. Chen, Shijie & Rahman, Md Hishamur & Marković, Nikola & Siddiqui, Muhammad Imran Younus & Mohebbi, Matthew & Sun, Yanshuo, 2024. "Schedule negotiation with ADA paratransit riders under value of time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    2. Rahman, Md Hishamur & Chen, Shijie & Sun, Yanshuo & Siddiqui, Muhammad Imran Younus & Mohebbi, Matthew & Marković, Nikola, 2023. "Integrating dial-a-ride with transportation network companies for cost efficiency: A Maryland case study," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    3. Queiroz, Michell & Lucas, Flavien & Sörensen, Kenneth, 2024. "Instance generation tool for on-demand transportation problems," European Journal of Operational Research, Elsevier, vol. 317(3), pages 696-717.

    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. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    2. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    3. Ge, Qian & Han, Ke & Liu, Xiaobo, 2021. "Matching and routing for shared autonomous vehicles in congestible network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    4. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    5. Gaul, Daniela & Klamroth, Kathrin & Stiglmayr, Michael, 2022. "Event-based MILP models for ridepooling applications," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1048-1063.
    6. Tafreshian, Amirmahdi & Abdolmaleki, Mojtaba & Masoud, Neda & Wang, Huizhu, 2021. "Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 227-259.
    7. Lian, Ying & Lucas, Flavien & Sörensen, Kenneth, 2024. "Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system," European Journal of Operational Research, Elsevier, vol. 312(1), pages 338-356.
    8. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    9. Dong, Xiaotong & Chow, Joseph Y.J. & Waller, S. Travis & Rey, David, 2022. "A chance-constrained dial-a-ride problem with utility-maximising demand and multiple pricing structures," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    10. Zhan, Xingbin & Szeto, W.Y. & Shui, C.S. & Chen, Xiqun (Michael), 2021. "A modified artificial bee colony algorithm for the dynamic ride-hailing sharing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    11. 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.
    12. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    13. Hua, Shijia & Zeng, Wenjia & Liu, Xinglu & Qi, Mingyao, 2022. "Optimality-guaranteed algorithms on the dynamic shared-taxi problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    14. Hosni, Hadi & Naoum-Sawaya, Joe & Artail, Hassan, 2014. "The shared-taxi problem: Formulation and solution methods," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 303-318.
    15. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    16. Johnsen, Lennart C. & Meisel, Frank, 2022. "Interrelated trips in the rural dial-a-ride problem with autonomous vehicles," European Journal of Operational Research, Elsevier, vol. 303(1), pages 201-219.
    17. Christian Pfeiffer & Arne Schulz, 2022. "An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(1), pages 87-119, March.
    18. Häme, Lauri, 2011. "An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows," European Journal of Operational Research, Elsevier, vol. 209(1), pages 11-22, February.
    19. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    20. Bongiovanni, Claudia & Kaspi, Mor & Cordeau, Jean-François & Geroliminis, Nikolas, 2022. "A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).

    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:161:y:2022:i:c:p:128-149. 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.