Skip to main content
SpringerLink
Log in

The paired many-to-many pickup and delivery problem: an application

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

This paper addresses a variation of pickup and delivery problems, named the paired many-to-many pickup and delivery problem (PMPDP), which has never been formally classified in the literature. Given “paired” demands between customer nodes, the PMPDP is to find a set of feasible vehicle routes starting from and ending at the depot such that the constructed objective function can be optimized subject to a set of desired constraints. When the PMPDP is applied to public library delivery operations, interchangeably used with the library vehicle routing problem (LVRP) hereafter, the customer nodes are replaced by library branches and the items to be delivered and picked up become books, videos and materials. To explore the LVRP, a mathematical model is rigorously formulated and a two-stage solution algorithm involving a modified bee colony optimization method is elaborately developed. Using real data from the San Francisco library system, the computational results show that our approach performs fairly well as compared with those approaches that have appeared in the literature. Provided each customer node is visited once, the sensitivity analysis indicates that when the number of dispatched library vehicles is more than what are needed, then the obtained result may get worse.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  • Agee J, Naper S (2007) Off-site storage: an analysis. Collect Build 26(1):20–25

    Article  Google Scholar 

  • Ai TJ, Kachitvichyanukul V (2009) A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Comput Oper Res 36:1693–1702

    Article  Google Scholar 

  • Alvarado-Iniesta A, Garcia-Alcaraz JL, Rodriguez-Borbon MI, Maldonado A (2013) Optimization of the material flow in a manufacturing plant by use of artificial bee colony algorithm. Expert Syst Appl 40:4785–4790

    Article  Google Scholar 

  • Apte UM, Mason FM (2006) Analysis and improvement of delivery operations at the San Francisco public library. J Oper Manag 24:325–346

    Article  Google Scholar 

  • Attanasio A, Cordeau JF, Ghiani G, Laporte G (2004) Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Comput 30:377–387

    Article  Google Scholar 

  • Ben-Akiva M, Lerman S (1985) Discrete choice analysis: theory and application to travel demand. MIT Press, Cambridge

    Google Scholar 

  • Berbeglia G, Cordeau JF, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202:8–15

    Article  Google Scholar 

  • Berry JN III (2005) The library Haines built. Libr J 130(1):38–41

    Google Scholar 

  • Bhagade AS, Puranik PV (2012) Artificial bee colony (ABC) algorithm for vehicle routing optimization problem. Int J Soft Comput Eng 2:329–333

    Google Scholar 

  • Brajevic I (2011) Artificial bee colony algorithm for the capacitated vehicle routing problem. In: Proceeding ECC’11 proceedings of the 5th European conference on European computing conference, pp 239–244

  • Chen HY (2009) Library vehicle routing problem. Master Thesis, Department of Civil Engineering, National Central University, Chung-Li (in Chinese)

  • Cordeau JF, Laporte G (2003) A Tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp Res Part B 37:579–594

    Article  Google Scholar 

  • Cordeau JF, Laporte G (2007) The dial-a-ride problem: models and algorithms. Ann Oper Res 153(1):29–46

    Article  Google Scholar 

  • Cordeau JF, Laporte G, Ropke S (2008) Recent models and algorithms for one-to-one pickup and delivery problems. In: Golden B, Raghavan S, Wasil E (eds) The vehicle routing problem. Springer, LLC, New York, pp 327–358

    Google Scholar 

  • Cree CL, Yoon M (2005) Public library circulation decreases, expenditures rise. Am Libr 36(9):57–58

    Google Scholar 

  • Dubberly R (1977) Options to improve delivery. Libr J 102:170–171

    Google Scholar 

  • Fisher M, Jaikumar R (1981) A generalized assignment heuristics for vehicle routing. Networks 11:109–124

    Article  Google Scholar 

  • Fu L (2002) Scheduling dial-a-ride paratransit under time-varying stochastic congestion. Transp Res Part B 36:485–506

    Article  Google Scholar 

  • Fu L (2003) Analytical model for paratransit capacity and quality-of-service analysis. Transp Res Rec 1841:81–89

    Article  Google Scholar 

  • Gajpal Y, Abad P (2009) An ant colony system for vehicle routing problem with simultaneous delivery and pickup. Comput Oper Res 36:3215–3223

    Article  Google Scholar 

  • Gribkovskaia I, Halskau Q, Laporte G, Vlček M (2007) General solutions to the single vehicle routing problem with pickups and deliveries. Eur J Oper Res 180:568–584

    Article  Google Scholar 

  • Hersey DP (2004) The future of access services: should there be one? J Access Serv 2(3):1–6

    Article  Google Scholar 

  • Huesmann J, Downing D (1996) Extending access and delivery (far) beyond the library walls (cover story). Comput Libr 16(4):28–31

    Google Scholar 

  • Ji P, Wu Y (2011) An improved artificial bee colony algorithm for the capacitated vehicle routing problem with time-dependent travel times. In: The 10th international symposium on operations research and its applications (ISORA 2011), Dunhuang, pp 75–82

  • Jorgensen RM, Larsen J, Bergvinsdottir KB (2007) Solving the dial-a-ride problem using genetic algorithms. J Oper Res Soc 58:1321–1331

    Article  Google Scholar 

  • Jun Y, Kim BI (2012) New best solutions to VRPSPD benchmark problems by a perturbation based algorithm. Expert Syst Appl 39:5641–5648

    Article  Google Scholar 

  • Little JDC, Murty KG, Sweeney DW, Karel C (1963) An algorithm for the traveling salesman problem. Oper Res 11:972–989

    Article  Google Scholar 

  • Lučić P, Teodorović D (2001) Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence. Preprints of the TRISTAN IV triennial symposium on transportation analysis. Sao Miguel, Azores Islands, pp 441–445

    Google Scholar 

  • Lučić P, Teodorović D (2003a) Computing with bees: attacking complex transportation engineering problems. Int J Artif Intell Tools 12:375–394

    Article  Google Scholar 

  • Lučić P, Teodorović D (2003b) Vehicle routing problem with uncertain demand at nodes: the bee system and fuzzy logic approach. In: Verdegay JL (ed) Fuzzy sets optimization. Springer-Verlag, Heidelberg, pp 67–82

    Google Scholar 

  • Lučić P, Teodorović D (2002) Transportation modeling: an artificial life approach. In: Proceedings of the 14th IEEE international conference on tools with artificial intelligence, Washington, pp 216–223

  • Luo Y, Schonfeld P (2007) A rejected-reinsertion heuristic for the static dial-a-ride problem. Transp Res Part B 41:736–755

    Article  Google Scholar 

  • Min H (1989) The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transp Res Part A 23:377–386

    Article  Google Scholar 

  • Monroe W (2005) Libraries return on investment study. Libr Mosaics 16(5):12–13

    Google Scholar 

  • Parragh SN, Doerner KF, Hartl RF (2008) A survey on pickup and delivery problems, Part II: transportation between pickup and delivery locations. J Betr 58:81–117

    Article  Google Scholar 

  • Parragh SN, Doerner KF, Hartl RF (2010) Variable neighborhood search for the dial-a-ride problem. Comput Oper Res 37:1129–1138

    Article  Google Scholar 

  • Parragh S, Schmid V (2013) Hybrid column generation and large neighborhood search for the dial-a-ride problem. Comput Oper Res 40(1):490–497

    Article  Google Scholar 

  • Ryder J (2004) Can’t get to the library? Then we will come to you. A survey of library services to people in their own homes in the United Kingdom. Health Inf Libr J 21:5–13

    Article  Google Scholar 

  • Şahin M, Aksu DT, Çavuşlar G, Öncan T, Şahin G (2012) An efficient heuristic for the multi-vehicle one-to-one pickup and delivery problem with split loads. Transp Res Part C 27:169–178

    Google Scholar 

  • Shi YJ, Meng FW, Shen GJ (2012) A modified artificial bee colony algorithm for vehicle routing problems with time windows. Inf Technol J 11:1490–1495

    Article  Google Scholar 

  • Stephens C, Franklin P (2005) To circulate or not to circulate: that is the question!. School Libr Media Act Mon 22(1):43–44

    Google Scholar 

  • Subramanian A, Uchoa E, Pessoa AA, Ochi LS (2011) Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Oper Res Lett 39:338–341

    Article  Google Scholar 

  • Szeto WY, Wu Y, Ho SC (2011) An artificial bee colony algorithm for the capacitated vehicle routing problem. Eur J Oper Res 215:126–135

  • Teodorovi D, Lučić P, Marković G, Dell’Orco M (2006) Bee colony optimization: principles and applications. In: Reljin B, Stankovic’ S (eds) Proceedings of the eighth seminar on neural network applications in electrical engineering—NEUREL 2006. University of Belgrade, Belgrade, pp 151–156

    Chapter  Google Scholar 

  • Teodorovi D (2008) Swarm intelligence systems for transportation engineering: principles and applications. Transp Res Part C 16:651–667

    Article  Google Scholar 

  • Wright LA (2001) Public library circulation and spending increase. Am Libr 32(9):64–65

    Google Scholar 

  • Zachariadis EE, Tarantilis CD, Kiranoudis CT (2010) An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. Eur J Oper Res 202:401–411

    Article  Google Scholar 

  • Zhang NZ, Sun GH, Wu YH and Geng FH (2009) A modified particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. In: Proceedings of the 7th Asian control conference, pp 1679–1684

Download references

Acknowledgments

The authors would like to acknowledge Mr. Hsuan Wang for revising the earlier version of our computer codes.

Author information

Authors and Affiliations

  1. Department of Civil Engineering, National Central University, Taoyuan, 32001, Taiwan

    Huey-Kuo Chen & Yen-Ju Yu

  2. Department of Information Management, National Central University, Taoyuan, 32001, Taiwan

    Huey-Wen Chou

  3. Department of Marketing and Distribution Management, Chien Hsin University of Science and Technology, Taoyuan, 32097, Taiwan

    Che-Fu Hsueh

Authors
  1. Huey-Kuo Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Huey-Wen Chou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Che-Fu Hsueh
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yen-Ju Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Che-Fu Hsueh.

Appendix

Appendix

The following route structures are the results of the numerical examples in Sect. 5.2. See Fig. 7.

Fig. 7
figure 7

Route structures. a Status Quo method, b Apte and Mason method, c this study (MBCO) and d LINGO

Full size image

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, HK., Chou, HW., Hsueh, CF. et al. The paired many-to-many pickup and delivery problem: an application. TOP 23, 220–243 (2015). https://doi.org/10.1007/s11750-014-0335-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-014-0335-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation