IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v273y2019i1d10.1007_s10479-017-2722-x.html
   My bibliography  Save this article

Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach

Author

Listed:
  • Pawel Sitek

    (Kielce University of Technology)

  • Jarosław Wikarek

    (Kielce University of Technology)

Abstract

The paper presents an optimization model and its implementation using a hybrid approach for the Capacitated Vehicle Routing Problem with Pick-up and Alternative Delivery (CVRPPAD). The development of the CVRPPAD was motivated by postal items distribution issues. The model proposed combines various features of Vehicle Routing Problem variants. The novelty of this model lies in the introduction of alternativeness of item delivery points, differentiation of delivery point types in terms of their capacity (parcel lockers) and possibility of collecting the items during the execution of delivery routes. The model also takes into account a possibility of introducing time windows related to delivery time. The proposed data structure in the form of sets of facts facilitates the implementation of the model in all environments, Constraint Logic Programming (CLP), Mathematical Programming (MP), metaheuristics, databases, etc. The model is implemented in the MP, hybrid CLP/MP, and hybrid CLP/heuristic environments. The hybrid CLP/MP approach is the authors’ original solution, which has already been used to solve Supply Chain Management problems, scheduling problems, routing problems etc. For large size problems, considering their combinatorial character, the proposed CLP/MP approach is ineffective. Its effectiveness will improve when MP is replaced by a heuristic. All implementations were performed on the same data instances (facts), which made it possible to compare them according to the solution search time, number of decision variables and number of constraints. The directions into which the model can be further developed were also presented.

Suggested Citation

  • Pawel Sitek & Jarosław Wikarek, 2019. "Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach," Annals of Operations Research, Springer, vol. 273(1), pages 257-277, February.
    • Handle: RePEc:spr:annopr:v:273:y:2019:i:1:d:10.1007_s10479-017-2722-x
    DOI: 10.1007/s10479-017-2722-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-017-2722-x
    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/s10479-017-2722-x?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. Louis-Martin Rousseau & Michel Gendreau & Gilles Pesant & Filippo Focacci, 2004. "Solving VRPTWs with Constraint Programming Based Column Generation," Annals of Operations Research, Springer, vol. 130(1), pages 199-216, August.
    2. Amal de Silva, 2001. "Combining Constraint Programming and Linear Programming on an Example of Bus Driver Scheduling," Annals of Operations Research, Springer, vol. 108(1), pages 277-291, November.
    3. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.
    4. Rego, César & Gamboa, Dorabela & Glover, Fred & Osterman, Colin, 2011. "Traveling salesman problem heuristics: Leading methods, implementations and latest advances," European Journal of Operational Research, Elsevier, vol. 211(3), pages 427-441, June.
    5. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    6. Paweł Sitek & Jarosław Wikarek, 2015. "A hybrid framework for the modelling and optimisation of decision problems in sustainable supply chain management," International Journal of Production Research, Taylor & Francis Journals, vol. 53(21), pages 6611-6628, November.
    7. Salhi, Said & Wassan, Niaz & Hajarat, Mutaz, 2013. "The Fleet Size and Mix Vehicle Routing Problem with Backhauls: Formulation and Set Partitioning-based Heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 56(C), pages 22-35.
    8. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    9. Michela Milano & Mark Wallace, 2010. "Integrating Operations Research in Constraint Programming," Annals of Operations Research, Springer, vol. 175(1), pages 37-76, March.
    10. Peter Nielsen & Liping Jiang & Niels Gorm Malý Rytter & Gang Chen, 2014. "An investigation of forecast horizon and observation fit's influence on an econometric rate forecast model in the liner shipping industry," Maritime Policy & Management, Taylor & Francis Journals, vol. 41(7), pages 667-682, December.
    11. Gábor Nagy & Niaz A. Wassan & M. Grazia Speranza & Claudia Archetti, 2015. "The Vehicle Routing Problem with Divisible Deliveries and Pickups," Transportation Science, INFORMS, vol. 49(2), pages 271-294, 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. Amira Saker & Amr Eltawil & Islam Ali, 2023. "Adaptive Large Neighborhood Search Metaheuristic for the Capacitated Vehicle Routing Problem with Parcel Lockers," Logistics, MDPI, vol. 7(4), pages 1-27, October.
    2. Xiao Pan & Dongna Lu & Ning Li, 2024. "Route Planning of Supermarket Delivery through Third-Party Logistics Considering Carbon Emission Cost," Mathematics, MDPI, vol. 12(7), pages 1-19, March.
    3. Firoozeh Kaveh & Reza Tavakkoli-Moghaddam & Chefi Triki & Yaser Rahimi & Amin Jamili, 2021. "A new bi-objective model of the urban public transportation hub network design under uncertainty," Annals of Operations Research, Springer, vol. 296(1), pages 131-162, January.
    4. Mancini, Simona & Gansterer, Margaretha & Triki, Chefi, 2023. "Locker box location planning under uncertainty in demand and capacity availability," Omega, Elsevier, vol. 120(C).
    5. Zhaofang Mao & Dian Huang & Kan Fang & Chengbo Wang & Dandan Lu, 2020. "Milk-run routing problem with progress-lane in the collection of automobile parts," Annals of Operations Research, Springer, vol. 291(1), pages 657-684, August.
    6. Christian Tilk & Katharina Olkis & Stefan Irnich, 2021. "The last-mile vehicle routing problem with delivery options," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 877-904, December.
    7. D. G. N. D. Jayarathna & G. H. J. Lanel & Z. A. M. S. Juman, 2022. "Industrial vehicle routing problem: a case study," Journal of Shipping and Trade, Springer, vol. 7(1), pages 1-27, December.
    8. Nima Pourmohammadreza & Mohammad Reza Akbari Jokar, 2023. "A Novel Two-Phase Approach for Optimization of the Last-Mile Delivery Problem with Service Options," Sustainability, MDPI, vol. 15(10), pages 1-25, May.
    9. Chen-Kun Tsung & Tseng-Fung Ho & Hsuan-Yu Huang & Shu-Hui Yang & Po-Nien Tsou & Ming-Cheng Tsai & Yi-Ping Huang, 2020. "Computing the Assembly Guidance for Maximizing Product Quality in the Virtual Assembly," Sustainability, MDPI, vol. 12(11), pages 1-14, June.
    10. Vincent F. Yu & Grace Aloina & Hadi Susanto & Mohammad Khoirul Effendi & Shih-Wei Lin, 2022. "Regional Location Routing Problem for Waste Collection Using Hybrid Genetic Algorithm-Simulated Annealing," Mathematics, MDPI, vol. 10(12), pages 1-23, June.
    11. Pardis Pourmohammadi & Reza Tavakkoli-Moghaddam & Yaser Rahimi & Chefi Triki, 2023. "Solving a hub location-routing problem with a queue system under social responsibility by a fuzzy meta-heuristic algorithm," Annals of Operations Research, Springer, vol. 324(1), pages 1099-1128, May.
    12. Jasmin Grabenschweiger & Karl F. Doerner & Richard F. Hartl & Martin W. P. Savelsbergh, 2021. "The vehicle routing problem with heterogeneous locker boxes," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(1), pages 113-142, March.
    13. Yu, Vincent F. & Jodiawan, Panca & Redi, A.A.N. Perwira, 2022. "Crowd-shipping problem with time windows, transshipment nodes, and delivery options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    14. Vincent F. Yu & Hadi Susanto & Yu-Hsuan Yeh & Shih-Wei Lin & Yu-Tsung Huang, 2022. "The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Parcel Lockers," Mathematics, MDPI, vol. 10(6), pages 1-22, March.

    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. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    2. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    3. Marques, Alexandra & Soares, Ricardo & Santos, Maria João & Amorim, Pedro, 2020. "Integrated planning of inbound and outbound logistics with a Rich Vehicle Routing Problem with backhauls," Omega, Elsevier, vol. 92(C).
    4. Luo, Zhixing & Qin, Hu & Lim, Andrew, 2014. "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints," European Journal of Operational Research, Elsevier, vol. 234(1), pages 49-60.
    5. Santos, Maria João & Jorge, Diana & Ramos, Tânia & Barbosa-Póvoa, Ana, 2023. "Green reverse logistics: Exploring the vehicle routing problem with deliveries and pickups," Omega, Elsevier, vol. 118(C).
    6. Drexl, Michael, 2013. "Applications of the vehicle routing problem with trailers and transshipments," European Journal of Operational Research, Elsevier, vol. 227(2), pages 275-283.
    7. Zhixing Luo & Hu Qin & Wenbin Zhu & Andrew Lim, 2017. "Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost," Transportation Science, INFORMS, vol. 51(2), pages 668-687, May.
    8. Aderemi Oluyinka Adewumi & Olawale Joshua Adeleke, 2018. "A survey of recent advances in vehicle routing problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(1), pages 155-172, February.
    9. Zhen, Lu & Baldacci, Roberto & Tan, Zheyi & Wang, Shuaian & Lyu, Junyan, 2022. "Scheduling heterogeneous delivery tasks on a mixed logistics platform," European Journal of Operational Research, Elsevier, vol. 298(2), pages 680-698.
    10. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    11. Chen, Gang & Rytter, Niels G.M. & Jiang, Liping & Nielsen, Peter & Jensen, Lars, 2017. "Pre-announcements of price increase intentions in liner shipping spot markets," Transportation Research Part A: Policy and Practice, Elsevier, vol. 95(C), pages 109-125.
    12. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    13. Wang, Zutong & Guo, Jiansheng & Zheng, Mingfa & Wang, Ying, 2015. "Uncertain multiobjective traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 478-489.
    14. Weikang Fang & Zailin Guan & Peiyue Su & Dan Luo & Linshan Ding & Lei Yue, 2022. "Multi-Objective Material Logistics Planning with Discrete Split Deliveries Using a Hybrid NSGA-II Algorithm," Mathematics, MDPI, vol. 10(16), pages 1-30, August.
    15. Tang, Jiafu & Yu, Yang & Li, Jia, 2015. "An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 114-132.
    16. Tallys Yunes & Ionuţ D. Aron & J. N. Hooker, 2010. "An Integrated Solver for Optimization Problems," Operations Research, INFORMS, vol. 58(2), pages 342-356, April.
    17. Aliyev, Denis A. & Zirbel, Craig L., 2023. "Seriation using tree-penalized path length," European Journal of Operational Research, Elsevier, vol. 305(2), pages 617-629.
    18. Lancia, Giuseppe & Vidoni, Paolo, 2020. "Finding the largest triangle in a graph in expected quadratic time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 458-467.
    19. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    20. Sebastian Henn & André Scholz & Meike Stuhlmann & Gerhard Wäscher, 2015. "A New Mathematical Programming Formulation for the Single-Picker Routing Problem in a Single-Block Layout," FEMM Working Papers 150005, 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:annopr:v:273:y:2019:i:1:d:10.1007_s10479-017-2722-x. 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.