IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v35y2018i2d10.1007_s10878-017-0188-z.html
   My bibliography  Save this article

From theory to practice: maximizing revenues for on-line dial-a-ride

Author

Listed:
  • Ananya Christman

    (Middlebury College)

  • William Forcier

    (Abbott Laboratories)

  • Aayam Poudel

    (Middlebury College)

Abstract

We consider the on-line dial-a-ride problem, where a server fulfills requests that arrive over time. Each request has a source, destination, and release time. We study a variation of this problem where each request also has a revenue that the server earns for fulfilling the request. The goal is to serve requests within a time limit while maximizing the total revenue. We first prove that no deterministic online algorithm can be competitive unless the input graph is complete and edge weights are unit. We therefore focus on these graphs and present a 2-competitive algorithm for this problem. We also consider two variations of this problem: (1) the input graph is complete bipartite and (2) there is a single node that is the source for every request, and present a 1-competitive algorithm for the former and an optimal algorithm for the latter. We also provide experimental results for the complete and complete bipartite graphs. Our simulations support our theoretical findings and demonstrate that our algorithms perform well under settings that reflect realistic dial-a-ride systems.

Suggested Citation

  • Ananya Christman & William Forcier & Aayam Poudel, 2018. "From theory to practice: maximizing revenues for on-line dial-a-ride," Journal of Combinatorial Optimization, Springer, vol. 35(2), pages 512-529, February.
    • Handle: RePEc:spr:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0188-z
    DOI: 10.1007/s10878-017-0188-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-017-0188-z
    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/s10878-017-0188-z?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. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    2. Patrick Jaillet & Michael R. Wagner, 2008. "Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses," Operations Research, INFORMS, vol. 56(3), pages 745-757, June.
    3. Kergosien, Y. & Lenté, Ch. & Piton, D. & Billaut, J.-C., 2011. "A tabu search heuristic for the dynamic transportation of patients between care units," European Journal of Operational Research, Elsevier, vol. 214(2), pages 442-452, October.
    4. Nabila Azi & Michel Gendreau & Jean-Yves Potvin, 2012. "A dynamic vehicle routing problem with multiple delivery routes," Annals of Operations Research, Springer, vol. 199(1), pages 103-112, October.
    5. Willem E. de Paepe & Jan Karel Lenstra & Jiri Sgall & René A. Sitters & Leen Stougie, 2004. "Computer-Aided Complexity Classification of Dial-a-Ride Problems," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 120-132, May.
    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. Shiri, Davood & Akbari, Vahid & Hassanzadeh, Ali, 2024. "The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy," Transportation Research Part B: Methodological, Elsevier, vol. 185(C).
    2. Ananya D. Christman & Christine Chung & Nicholas Jaczko & Tianzhi Li & Scott Westvold & Xinyue Xu & David Yuen, 2021. "Improved Bounds for Revenue Maximization in Time-Limited Online Dial-a-Ride," SN Operations Research Forum, Springer, vol. 2(3), pages 1-38, 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. 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. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    3. Ouyang, Zhiyuan & Leung, Eric K.H. & Huang, George Q., 2023. "Community logistics and dynamic community partitioning: A new approach for solving e-commerce last mile delivery," European Journal of Operational Research, Elsevier, vol. 307(1), pages 140-156.
    4. 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.
    5. Hai Wang, 2019. "Routing and Scheduling for a Last-Mile Transportation System," Service Science, INFORMS, vol. 53(1), pages 131-147, February.
    6. Reyes, Damián & Erera, Alan L. & Savelsbergh, Martin W.P., 2018. "Complexity of routing problems with release dates and deadlines," European Journal of Operational Research, Elsevier, vol. 266(1), pages 29-34.
    7. Jozefowiez, Nicolas & Semet, Frédéric & Talbi, El-Ghazali, 2009. "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 195(3), pages 761-769, June.
    8. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    9. Chen, Xinwei & Wang, Tong & Thomas, Barrett W. & Ulmer, Marlin W., 2023. "Same-day delivery with fair customer service," European Journal of Operational Research, Elsevier, vol. 308(2), pages 738-751.
    10. Moreira, Mayron César O. & Costa, Alysson M., 2013. "Hybrid heuristics for planning job rotation schedules in assembly lines with heterogeneous workers," International Journal of Production Economics, Elsevier, vol. 141(2), pages 552-560.
    11. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    12. C Schumacher & P R Chandler & M Pachter & L S Pachter, 2007. "Optimization of air vehicles operations using mixed-integer linear programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 516-527, April.
    13. Marlin W. Ulmer & Alan Erera & Martin Savelsbergh, 2022. "Dynamic service area sizing in urban delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 763-793, September.
    14. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    15. Aringhieri, Roberto & Cordone, Roberto & Grosso, Andrea, 2015. "Construction and improvement algorithms for dispersion problems," European Journal of Operational Research, Elsevier, vol. 242(1), pages 21-33.
    16. Vinicius M. Ton & Nathália C. O. da Silva & Angel Ruiz & José E. Pécora & Cassius T. Scarpin & Valérie Bélenger, 2024. "Real-time management of intra-hospital patient transport requests," Health Care Management Science, Springer, vol. 27(2), pages 208-222, June.
    17. Zhang, Huili & Tong, Weitian & Xu, Yinfeng & Lin, Guohui, 2015. "The Steiner Traveling Salesman Problem with online edge blockages," European Journal of Operational Research, Elsevier, vol. 243(1), pages 30-40.
    18. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    19. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    20. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2014. "The Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 140006, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.

    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:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0188-z. 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.