IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v174y2006i2p1117-1139.html
   My bibliography  Save this article

A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints

Author

Listed:
  • Xiang, Zhihai
  • Chu, Chengbin
  • Chen, Haoxun

Abstract

No abstract is available for this item.

Suggested Citation

  • Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    • Handle: RePEc:eee:ejores:v:174:y:2006:i:2:p:1117-1139
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(05)00334-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. 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.
    2. 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.
    3. Irina Ioachim & Jacques Desrosiers & Yvan Dumas & Marius M. Solomon & Daniel Villeneuve, 1995. "A Request Clustering Algorithm for Door-to-Door Handicapped Transportation," Transportation Science, INFORMS, vol. 29(1), pages 63-78, February.
    4. Nanry, William P. & Wesley Barnes, J., 2000. "Solving the pickup and delivery problem with time windows using reactive tabu search," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 107-121, February.
    5. 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.
    6. Psaraftis, Harilaos N., 1983. "k-Interchange procedures for local search in a precedence-constrained routing problem," European Journal of Operational Research, Elsevier, vol. 13(4), pages 391-402, August.
    7. 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.
    8. Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
    9. Harilaos N. Psaraftis, 1983. "An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows," Transportation Science, INFORMS, vol. 17(3), pages 351-357, August.
    10. Paolo Toth & Daniele Vigo, 1997. "Heuristic Algorithms for the Handicapped Persons Transportation Problem," Transportation Science, INFORMS, vol. 31(1), pages 60-71, February.
    11. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    12. Healy, Patrick & Moll, Robert, 1995. "A new extension of local search applied to the Dial-A-Ride Problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 83-104, May.
    13. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    14. Hang Xu & Zhi-Long Chen & Srinivas Rajagopal & Sundar Arunapuram, 2003. "Solving a Practical Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 37(3), pages 347-364, 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. Fink, Martin & Desaulniers, Guy & Frey, Markus & Kiermaier, Ferdinand & Kolisch, Rainer & Soumis, François, 2019. "Column generation for vehicle routing problems with multiple synchronization constraints," European Journal of Operational Research, Elsevier, vol. 272(2), pages 699-711.
    2. Velaga, Nagendra R. & Beecroft, Mark & Nelson, John D. & Corsar, David & Edwards, Peter, 2012. "Transport poverty meets the digital divide: accessibility and connectivity in rural communities," Journal of Transport Geography, Elsevier, vol. 21(C), pages 102-112.
    3. 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.
    4. Amine Masmoudi, M. & Mancini, Simona & Baldacci, Roberto & Kuo, Yong-Hong, 2022. "Vehicle routing problems with drones equipped with multi-package payload compartments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    5. Zixuan Peng & Wenxuan Shan & Peng Jia & Bin Yu & Yonglei Jiang & Baozhen Yao, 2020. "Stable ride-sharing matching for the commuters with payment design," Transportation, Springer, vol. 47(1), pages 1-21, February.
    6. Karabuk, Suleyman, 2009. "A nested decomposition approach for solving the paratransit vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(4), pages 448-465, May.
    7. 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.
    8. Masmoudi, Mohamed Amine & Hosny, Manar & Braekers, Kris & Dammak, Abdelaziz, 2016. "Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 96(C), pages 60-80.
    9. Shangyao Yan & Chun-Ying Chen & Chuan-Che Wu, 2012. "Solution methods for the taxi pooling problem," Transportation, Springer, vol. 39(3), pages 723-748, May.
    10. Amine Masmoudi, M. & Coelho, Leandro C. & Demir, Emrah, 2022. "Plug-in hybrid electric refuse vehicle routing problem for waste collection," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    11. Mohamed Amine Masmoudi & Manar Hosny & Emrah Demir & Erwin Pesch, 2020. "Hybrid adaptive large neighborhood search algorithm for the mixed fleet heterogeneous dial-a-ride problem," Journal of Heuristics, Springer, vol. 26(1), pages 83-118, February.
    12. 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).
    13. 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.
    14. Shangyao Yan & Chun-Ying Chen, 2011. "An optimization model and a solution algorithm for the many-to-many car pooling problem," Annals of Operations Research, Springer, vol. 191(1), pages 37-71, November.
    15. Reinhardt, Line Blander & Clausen, Tommy & Pisinger, David, 2013. "Synchronized dial-a-ride transportation of disabled passengers at airports," European Journal of Operational Research, Elsevier, vol. 225(1), pages 106-117.
    16. 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.
    17. 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.
    18. Garaix, Thierry & Artigues, Christian & Feillet, Dominique & Josselin, Didier, 2010. "Vehicle routing problems with alternative paths: An application to on-demand transportation," European Journal of Operational Research, Elsevier, vol. 204(1), pages 62-75, July.
    19. 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).
    20. 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.
    21. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    22. 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.
    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. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    25. Braekers, Kris & Caris, An & Janssens, Gerrit K., 2014. "Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 166-186.

    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. 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.
    2. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    3. 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.
    4. Hou, Liwen & Li, Dong & Zhang, Dali, 2018. "Ride-matching and routing optimisation: Models and a large neighbourhood search heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 143-162.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    11. 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.
    12. 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).
    13. 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.
    14. Lauri Häme & Harri Hakula, 2015. "A Maximum Cluster Algorithm for Checking the Feasibility of Dial-A-Ride Instances," Transportation Science, INFORMS, vol. 49(2), pages 295-310, May.
    15. Luo, Ying & Schonfeld, Paul, 2007. "A rejected-reinsertion heuristic for the static Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 736-755, August.
    16. Quan Lu & Maged Dessouky, 2004. "An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 503-514, November.
    17. Mahmoudi, Monirehalsadat & Chen, Junhua & Shi, Tie & Zhang, Yongxiang & Zhou, Xuesong, 2019. "A cumulative service state representation for the pickup and delivery problem with transfers," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 351-380.
    18. Dessouky, Maged M. & Aldaihani, Majid & Shah, Rutvij, 2002. "Evaluating the Impact of ITS on Personalized Public Transit," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt7fb4h2dg, Institute of Transportation Studies, UC Berkeley.
    19. 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.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:ejores:v:174:y:2006:i:2:p:1117-1139. 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/locate/eor .

    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.