A review of Vehicle Routing Problem with Selective Pickup Point and Delivery

Shi Qi

doi:10.62051/ijcsit.v2n2.33

Authors

Shi Qi

DOI:

https://doi.org/10.62051/ijcsit.v2n2.33

Keywords:

Vehicle Routing; Multiple pickup points; Selective pickup delivery problem; Time Windows

Abstract

The problem of picking up and delivery vehicle routing is that one delivery point can correspond to multiple pickup points, and one of these pickup points needs to be selected for pickup before delivery. With the reform of the retail industry, the omnichannel retail model has gradually become popular, which provides consumers with a variety of choice of pick-up points in collaboration with online e-commerce and offline stores. This paper gives a systematic overview of the relevant operational research model and its solution for the pick-up and delivery vehicle routing problem considering the selection of pick-up points, hoping to encourage logistics community and transportation science to do more research in this emerging field.

Downloads

Download data is not yet available.

References

Gribkovskaia I, Laporte G, Shyshou A. The single vehicle routing problem with deliveries and selective pickups[J]. Computers & Operations Research, 2008, 35(9): 2908–2924.

Yu Y, Wang S, Wang J, 等. A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows[J]. Transportation Research Part B: Methodological, 2019, 122: 511–527.

Erdoğan S, Miller-Hooks E. A Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100–114.

Takada Y, Shimazaki M, Hu Y, 等. Efficient algorithms for optimal pickup-point selection in the selective pickup and delivery problem with time-window constraints[J]. Journal of Advanced Mechanical Design, Systems, and Manufacturing, 2020, 14(5): JAMDSM0074–JAMDSM0074.

Berbeglia G, Cordeau J-F, Gribkovskaia I, 等. Static pickup and delivery problems: a classification scheme and survey[J]. TOP, 2007, 15(1): 1–31.

Li Y, Chen H, Prins C. Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier, 2016, 252(1): 27–38.

Riedler M, Raidl G. Solving a selective dial-a-ride problem with logic-based Benders decomposition[J]. COMPUTERS & OPERATIONS RESEARCH, Oxford: Pergamon-Elsevier Science Ltd, 2018, 96: 30–54.

Baniamerian A, Bashiri M, Zabihi F. A modified variable neighborhood search hybridized with genetic algorithm for vehicle routing problems with cross-docking[J]. Electron. Notes Discret. Math., 2018.

Al Chami Z, Manier H, Manier M-A. A lexicographic approach for the bi-objective selective pickup and delivery problem with time windows and paired demands[J]. ANNALS OF OPERATIONS RESEARCH, Dordrecht: Springer, 2019, 273(1–2): 237–255.

Qiu X, Feuerriegel S, Neumann D. Making the most of fleets: A profit-maximizing multi-vehicle pickup and delivery selection problem[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier Science Bv, 2017, 259(1): 155–168.

Bruni M E, Toan D Q, Nam L H. The multi-vehicle profitable pick up and delivery routing problem with uncertain travel times[J]. Transportation Research Procedia, 2021, 52: 509–516.

Anily S, Hassin R. The swapping problem[J]. Networks, 1992, 22(4): 419–433.

Hernández-Pérez H, Salazar-González J-J. A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery[J]. Discrete Applied Mathematics, 2004, 145(1): 126–139.

Hernández-Pérez H, Salazar-González J-J. Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem[J]. Transportation Science, INFORMS, 2004, 38(2): 245–255.

Zhao F, Li S, Sun J, 等. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers & Industrial Engineering, 2009, 56(4): 1642–1648.

Mladenović N, Urošević D, Hanafi S, 等. A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem[J]. European Journal of Operational Research, 2012, 220(1): 270–285.

Shi X, Zhao F, Gong Y. Genetic algorithm for the one-commodity pickup-and-delivery vehicle routing problem[A]. 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems[C]. 2009, 1: 175–179.

Ai T J, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J]. Computers & Operations Research, 2009, 36(5): 1693–1702.

Hernández‐Pérez H, Salazar‐González J. The multi‐commodity pickup‐and‐delivery traveling salesman problem[J]. Networks, 2014, 63(1): 46–59.

Qiao J, He M, Sun N, 等. Factors affecting the final solution of the bike-sharing rebalancing problem under heuristic algorithms[J]. Computers & Operations Research, 2023, 159: 106368.

Gutierrez-Jarpa G, Marianov V, Obreque C. A single vehicle routing problem with fixed delivery and optional collections[J]. IIE TRANSACTIONS, Philadelphia: Taylor & Francis Inc, 2009, 41(12): 1067–1079.

Gutierrez-Jarpa G, Desaulniers G, Laporte G, 等. A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier, 2010, 206(2): 341–349.

Assis L P, Maravilha A L, Vivas A, 等. Multiobjective vehicle routing problem with fixed delivery and optional collections[J]. OPTIMIZATION LETTERS, Heidelberg: Springer Heidelberg, 2013, 7(7): 1419–1431.

Coelho I M, Munhoz P L A, Haddad M N, 等. A hybrid heuristic based on General Variable Neighborhood Search for the Single Vehicle Routing Problem with Deliveries and Selective Pickups[J]. Electronic Notes in Discrete Mathematics, 2012, 39: 99–106.

Bruck B P, dos Santos A G. Hybrid approach for the Multiple Vehicle Routing Problem with Deliveries and Selective Pickups[A]. A. Abraham, A. Zomaya, V. Wadhai, 等. 2012 12TH INTERNATIONAL CONFERENCE ON HYBRID INTELLIGENT SYSTEMS (HIS)[C]. New York: IEEE, 2012: 265–270.

Coelho I M, Munhoz P L A, Ochi L S, 等. An integrated CPU-GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups[J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, Abingdon: Taylor & Francis Ltd, 2016, 54(4): 945–962.

Bruck B P, Iori M. Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries[J]. OPERATIONS RESEARCH, Catonsville: Informs, 2017, 65(6): 1597–1614.

Lee C-G, Epelman M A, White C C, 等. A shortest path approach to the multiple-vehicle routing problem with split pick-ups[J]. Transportation Research Part B: Methodological, 2006, 40(4): 265–284.

Nowak M, Ergun Ö, White C C. Pickup and Delivery with Split Loads[J]. Transportation Science, 2008, 42(1): 32–43.

Nowak M, Ergun O, White C C. An empirical study on the benefit of split loads with the pickup and delivery problem[J]. European Journal of Operational Research, 2009, 198(3): 734–740.

Nowak M, Hewitt M, White C C. Precedence constrained pickup and delivery with split loads[J]. International Journal of Logistics Research and Applications, 2012, 15(1): 1–14.

Andersson H, Christiansen M, Fagerholt K. The Maritime Pickup and Delivery Problem with Time Windows and Split Loads[J]. INFOR: Information Systems and Operational Research, 2011, 49(2): 79–91.

Azadian F, Murat A, Chinnam R B. An unpaired pickup and delivery problem with time dependent assignment costs: Application in air cargo transportation[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier Science Bv, 2017, 263(1): 188–202.

Salazar-González J-J, Santos-Hernández B. The split-demand one-commodity pickup-and-delivery travelling salesman problem[J]. Transportation Research Part B: Methodological, 2015, 75: 58–73.

Hernandez-Perez H, Jose Salazar-Gonzalez J, Santos-Hernandez B. Heuristic algorithm for the Split-Demand One-Commodity Pickup-and-Delivery Travelling Salesman Problem[J]. COMPUTERS & OPERATIONS RESEARCH, Oxford: Pergamon-Elsevier Science Ltd, 2018, 97: 1–17.

Erdogan G, Battarra M, Calvo R W. An exact algorithm for the static rebalancing problem arising in bicycle sharing systems[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier Science Bv, 2015, 245(3): 667–679.

Cruz F, Subramanian A, Bruck B P, 等. A heuristic algorithm for a single vehicle static bike sharing, rebalancing problem[J]. COMPUTERS & OPERATIONS RESEARCH, Oxford: Pergamon-Elsevier Science Ltd, 2017, 79: 19–33.

Bulhoes T, Subramanian A, Erdogan G, 等. The static bike relocation problem with multiple vehicles and visits[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier Science Bv, 2018, 264(2): 508–523.

Casazza M, Ceselli A, Calvo R W. A route decomposition approach for the single commodity Split Pickup and Split Delivery Vehicle Routing Problem[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Amsterdam: Elsevier, 2021, 289(3): 897–911.