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

A scalable non-myopic dynamic dial-a-ride and pricing problem

Author

Listed:
  • Sayarshad, Hamid R.
  • Chow, Joseph Y.J.

Abstract

Non-myopic dial-a-ride problem and other related dynamic vehicle routing problems often ignore the need for non-myopic pricing under the assumption of elastic demand, which leads to an overestimation of the benefits in level of service and resulting inefficiencies. To correct this problem, a new dynamic dial-a-ride policy is introduced, one that features non-myopic pricing based on optimal tolling of queues to fit with the multi-server queueing approximation method proposed by Hyttiä et al. (2012) for large-scale systems. By including social optimal pricing, the social welfare of the resulting system outperforms the marginal pricing assumed for previous approaches over a range of test instances. In the examples tested, improvements in social welfare of the non-myopic pricing over the myopic pricing were in the 20–31% range. For a given demand function, we can derive the optimal fleet size to maximize social welfare. Sensitivity tests to the optimal price confirm that it leads to an optimal social welfare while the marginal pricing policy does not. A comparison of single passenger taxis to shared-taxis shows that system cost may reduce at the expense of decreased social welfare, which agrees with the results of Jung et al. (2013).

Suggested Citation

  • 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.
  • Handle: RePEc:eee:transb:v:81:y:2015:i:p2:p:539-554
    DOI: 10.1016/j.trb.2015.06.008
    as

    Download full text from publisher

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

    File URL: https://libkey.io/10.1016/j.trb.2015.06.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. Quadrifoglio, Luca & Dessouky, Maged M. & Ordonez, Fernando, 2008. "Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints," European Journal of Operational Research, Elsevier, vol. 185(2), pages 481-494, March.
    2. Chandra, Shailesh & Quadrifoglio, Luca, 2013. "A model for estimating the optimal cycle length of demand responsive feeder transit services," Transportation Research Part B: Methodological, Elsevier, vol. 51(C), pages 1-16.
    3. Dror, Moshe, 1993. "Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution," European Journal of Operational Research, Elsevier, vol. 64(3), pages 432-441, February.
    4. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    5. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    6. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    7. Patrick Jaillet, 1988. "A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited," Operations Research, INFORMS, vol. 36(6), pages 929-936, December.
    8. Kirchler, Dominik & Wolfler Calvo, Roberto, 2013. "A Granular Tabu Search algorithm for the Dial-a-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 120-135.
    9. De Borger, Bruno & Fosgerau, Mogens, 2012. "Information provision by regulated public transport companies," Transportation Research Part B: Methodological, Elsevier, vol. 46(4), pages 492-510.
    10. Michael Z. Spivey & Warren B. Powell, 2004. "The Dynamic Assignment Problem," Transportation Science, INFORMS, vol. 38(4), pages 399-419, November.
    11. Chow, Joseph Y.J. & Regan, Amelia C. & Ranaiefar, Fatemeh & Arkhipov, Dmitri I., 2011. "A network option portfolio management framework for adaptive transportation planning," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(8), pages 765-778, October.
    12. 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.
    13. Gregory A. Godfrey & Warren B. Powell, 2002. "An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, I: Single Period Travel Times," Transportation Science, INFORMS, vol. 36(1), pages 21-39, February.
    14. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    15. Miguel Andres Figliozzi & Hani S. Mahmassani & Patrick Jaillet, 2007. "Pricing in Dynamic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 41(3), pages 302-318, August.
    16. Agatz, Niels A.H. & Erera, Alan L. & Savelsbergh, Martin W.P. & Wang, Xing, 2011. "Dynamic ride-sharing: A simulation study in metro Atlanta," Transportation Research Part B: Methodological, Elsevier, vol. 45(9), pages 1450-1464.
    17. Mulley, Corinne & Nelson, John D., 2009. "Flexible transport services: A new market opportunity for public transport," Research in Transportation Economics, Elsevier, vol. 25(1), pages 39-45.
    18. 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.
    19. Psaraftis, Harilaos N., 1983. "Analysis of an O(N2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 17(2), pages 133-145, April.
    20. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    21. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    22. 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.
    23. Jaw, Jang-Jei & Odoni, Amedeo R. & Psaraftis, Harilaos N. & Wilson, Nigel H. M., 1986. "A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 243-257, June.
    24. Moshe Dror & Warren Powell, 1993. "Stochastic and Dynamic Models in Transportation," Operations Research, INFORMS, vol. 41(1), pages 11-14, February.
    25. Mitrovic-Minic, Snezana & Krishnamurti, Ramesh & Laporte, Gilbert, 2004. "Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 669-685, September.
    26. Yang, Hai & Huang, Hai-Jun, 1998. "Principle of marginal-cost pricing: how does it work in a general road network?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 32(1), pages 45-54, January.
    27. Chow, Joseph Y.J. & Regan, Amelia C., 2011. "Network-based real option models," Transportation Research Part B: Methodological, Elsevier, vol. 45(4), pages 682-695, May.
    28. 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.
    29. Naor, P, 1969. "The Regulation of Queue Size by Levying Tolls," Econometrica, Econometric Society, vol. 37(1), pages 15-24, January.
    30. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    31. Moshe Dror & Gilbert Laporte & Pierre Trudeau, 1989. "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, INFORMS, vol. 23(3), pages 166-176, August.
    32. Knudsen, Niels Chr, 1972. "Individual and Social Optimization in a Multiserver Queue with a General Cost-Benefit Structure," Econometrica, Econometric Society, vol. 40(3), pages 515-528, May.
    33. 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)

    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. Sayarshad, Hamid R. & Gao, H. Oliver, 2018. "A non-myopic dynamic inventory routing and pricing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 83-98.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Joseph Y. J. Chow & Hamid R. Sayarshad, 2016. "Reference Policies for Non-myopic Sequential Network Design and Timing Problems," Networks and Spatial Economics, Springer, vol. 16(4), pages 1183-1209, December.
    4. 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).
    5. 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).
    6. 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.
    7. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    8. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    9. 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.
    10. 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.
    11. Dikas, G. & Minis, I., 2014. "Scheduled paratransit transport systems," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 18-34.
    12. Sayarshad, Hamid R. & Gao, H. Oliver, 2020. "Optimizing dynamic switching between fixed and flexible transit services with an idle-vehicle relocation strategy and reductions in emissions," Transportation Research Part A: Policy and Practice, Elsevier, vol. 135(C), pages 198-214.
    13. 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.
    14. Naoum-Sawaya, Joe & Cogill, Randy & Ghaddar, Bissan & Sajja, Shravan & Shorten, Robert & Taheri, Nicole & Tommasi, Pierpaolo & Verago, Rudi & Wirth, Fabian, 2015. "Stochastic optimization approach for the car placement problem in ridesharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 173-184.
    15. 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.
    16. Rui Yao & Shlomo Bekhor, 2021. "A Dynamic Tree Algorithm for Peer-to-Peer Ridesharing Matching," Networks and Spatial Economics, Springer, vol. 21(4), pages 801-837, December.
    17. Kirchler, Dominik & Wolfler Calvo, Roberto, 2013. "A Granular Tabu Search algorithm for the Dial-a-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 120-135.
    18. Agatz, Niels & Erera, Alan & Savelsbergh, Martin & Wang, Xing, 2012. "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, Elsevier, vol. 223(2), pages 295-303.
    19. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    20. Srour, F.J. & Agatz, N.A.H. & Oppen, J., 2014. "Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows," ERIM Report Series Research in Management ERS-2014-015-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    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:81:y:2015:i:p2:p:539-554. 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.