IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v191y2011i1p37-7110.1007-s10479-011-0948-6.html
   My bibliography  Save this article

An optimization model and a solution algorithm for the many-to-many car pooling problem

Author

Listed:
  • Shangyao Yan
  • Chun-Ying Chen

Abstract

Car pooling is one method that can be easily instituted and can help to resolve a variety of problems that continue to plague urban areas, ranging from energy demands and traffic congestion to environmental pollution. Although car pooling is becoming more common, in practice, participant matching results are still being obtained by an inefficient manual approach, which may possibly result in an inferior solution. In the past, when car pooling studies have been done the problem has been treated as either a to-work problem (from different origins to the same destination) or return-from-work problem (from the same origin to different destinations). However, in this study we employ a time-space network flow technique to develop a model for the many-to-many car pooling problem with multiple vehicle types and person types. The model is formulated as an integer multiple commodity network flow problem. Since real problem sizes can be huge, it could be difficult to find optimal solutions within a reasonable period of time. Therefore, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model. To test how well the model and the solution algorithm can be applied to real world, we randomly generated several examples based upon data reported from a past study carried out in northern Taiwan, on which we performed numerical tests. The test results show the effectiveness of the proposed model and solution algorithm. Copyright Springer Science+Business Media, LLC 2011

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:191:y:2011:i:1:p:37-71:10.1007/s10479-011-0948-6
    DOI: 10.1007/s10479-011-0948-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0948-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-011-0948-6?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. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    2. 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.
    3. Yan, Shangyao & Young, Hwei-Fwa, 1996. "A decision support framework for multi-fleet routing and multi-stop flight scheduling," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(5), pages 379-398, September.
    4. 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.
    5. Yan, Shangyao & Chen, Shin-Chin & Chen, Chia-Hung, 2006. "Air cargo fleet routing and timetable setting with multiple on-time demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 42(5), pages 409-430, September.
    6. Yan, Shangyao & Yang, Dah-Hwei, 1996. "A decision support framework for handling schedule perturbation," Transportation Research Part B: Methodological, Elsevier, vol. 30(6), pages 405-419, December.
    7. 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.
    8. 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.
    9. 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.
    10. Roberto Baldacci & Vittorio Maniezzo & Aristide Mingozzi, 2004. "An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation," Operations Research, INFORMS, vol. 52(3), pages 422-439, June.
    11. 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.
    12. 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.
    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. Moon, Ilkyeong & Feng, Xuehao, 2017. "Supply chain coordination with a single supplier and multiple retailers considering customer arrival times and route selection," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 78-97.
    2. Bian, Zheyong & Liu, Xiang & Bai, Yun, 2020. "Mechanism design for on-demand first-mile ridesharing," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 77-117.
    3. Byungjun Ju & Minsu Kim & Ilkyeong Moon, 2021. "Vehicle Routing Problem Considering Reconnaissance and Transportation," Sustainability, MDPI, vol. 13(6), pages 1-19, March.
    4. André Palma & Lucas Javaudin & Patrick Stokkink & Léandre Tarpin-Pitre, 2024. "Ride-sharing with inflexible drivers in the Paris metropolitan area," Transportation, Springer, vol. 51(3), pages 963-986, June.
    5. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem & Yacine Rekik, 2022. "Environmental and social implications of incorporating carpooling service on a customized bus system," Post-Print hal-03598768, HAL.
    6. Hu, Shichun & Dessouky, Maged M. & Uhan, Nelson A. & Vayanos, Phebe, 2021. "Cost-sharing mechanism design for ride-sharing," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 410-434.
    7. Schulz, Arne & Pfeiffer, Christian, 2024. "A Branch-and-Cut algorithm for the dial-a-ride problem with incompatible customer types," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    8. André de Palma & Lucas Javaudin & Patrick Stokkink & Léandre Tarpin-Pitre, 2021. "Modelling Ridesharing in a Large Network with Dynamic Congestion," THEMA Working Papers 2021-16, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.

    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. 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.
    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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    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. 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.
    11. 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.
    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. Andrew Lim & Zhenzhen Zhang & Hu Qin, 2017. "Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals," Transportation Science, INFORMS, vol. 51(2), pages 688-705, May.
    14. 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.
    15. 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).
    16. Thomas Hanne & Teresa Melo & Stefan Nickel, 2009. "Bringing Robustness to Patient Flow Management Through Optimized Patient Transports in Hospitals," Interfaces, INFORMS, vol. 39(3), pages 241-255, June.
    17. 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.
    18. 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.
    19. Zhang, Zhenzhen & Liu, Mengyang & Lim, Andrew, 2015. "A memetic algorithm for the patient transportation problem," Omega, Elsevier, vol. 54(C), pages 60-71.
    20. 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.

    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:annopr:v:191:y:2011:i:1:p:37-71:10.1007/s10479-011-0948-6. 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.