IDEAS home Printed from https://ideas.repec.org/a/gam/jlogis/v8y2024i1p14-d1333315.html
   My bibliography  Save this article

A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems

Author

Listed:
  • Cornelius Rüther

    (Operations Research Department, Institute for Business Administration and Information Systems, University of Hildesheim, Universitätsplatz 1, 31141 Hildesheim, Germany)

  • Julia Rieck

    (Operations Research Department, Institute for Business Administration and Information Systems, University of Hildesheim, Universitätsplatz 1, 31141 Hildesheim, Germany)

Abstract

Background : The Multi Depot Pickup and Delivery Problem with Time Windows and Heterogeneous Vehicle Fleets (MDPDPTWHV) is a strongly practically oriented routing problem with many real-world constraints. Due to its complexity, solution approaches with sufficiently good quality ideally contain several operators with certain probabilities.Thus, automatically selecting the best parameter configurations enhances the overall solution quality. Methods : To solve the MDPDPTWHV, we present a Grouping Genetic Algorithm (GGA) framework with several operators and population management variants. A Bayesian Optimization (BO) approach is introduced to optimize the GGA’s parameter configuration. The parameter tuning is evaluated on five data sets which differ in several structural characteristics and contain 1200 problem instances. The outcomes of the parameter-tuned GGA are compared to both the initial GGA parameter configuration and a state-of-the-art Adaptive Large Neighborhood Search (ALNS). Results : The presented GGA framework achieves a better solution quality than the ALNS, even for the initial parameter configuration used. The mean value of the relative error is less than 0.9% and its standard deviation is less than 1.31% for every problem class. For the ALNS, these values are up to three times higher and the GGA is up to 38% faster than the ALNS. Conclusions : It is shown that the BO, as a parameter tuning approach, is a good choice in improving the performance of the considered meta-heuristic over all instances in each data set. In addition, the best parameter configuration per problem class with the same characteristics is able to improve both the frequency of finding the best solution, as well as the relative error to this solution, significantly.

Suggested Citation

  • Cornelius Rüther & Julia Rieck, 2024. "A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems," Logistics, MDPI, vol. 8(1), pages 1-26, February.
    • Handle: RePEc:gam:jlogis:v:8:y:2024:i:1:p:14-:d:1333315
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2305-6290/8/1/14/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2305-6290/8/1/14/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    2. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    3. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    4. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, December.
    5. Renaud Masson & Fabien Lehuédé & Olivier Péton, 2013. "An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers," Transportation Science, INFORMS, vol. 47(3), pages 344-355, August.
    6. S. Irnich, 2008. "A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 270-287, May.
    Full references (including those not matched with items on IDEAS)

    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. Margaretha Gansterer & Richard F. Hartl & Sarah Wieser, 2021. "Assignment constraints in shared transportation services," Annals of Operations Research, Springer, vol. 305(1), pages 513-539, October.
    2. Abdulkader, M.M.S. & Gajpal, Yuvraj & ElMekkawy, Tarek Y., 2018. "Vehicle routing problem in omni-channel retailing distribution systems," International Journal of Production Economics, Elsevier, vol. 196(C), pages 43-55.
    3. Dirk Männel & Andreas Bortfeldt, 2015. "A Hybrid Algorithm for the Vehicle Routing Problem with Pickup and Delivery and 3D Loading Constraints," FEMM Working Papers 150015, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    4. Männel, Dirk & Bortfeldt, Andreas, 2016. "A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 254(3), pages 840-858.
    5. 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.
    6. Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    7. Paul Buijs & Jose Alejandro Lopez Alvarez & Marjolein Veenstra & Kees Jan Roodbergen, 2016. "Improved Collaborative Transport Planning at Dutch Logistics Service Provider Fritom," Interfaces, INFORMS, vol. 46(2), pages 119-132, April.
    8. Michael Drexl, 2018. "On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers," Working Papers 1816, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Ohad Eisenhandler & Michal Tzur, 2019. "The Humanitarian Pickup and Distribution Problem," Operations Research, INFORMS, vol. 67(1), pages 10-32, January.
    10. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2019. "Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 150-177.
    11. Bombelli, Alessandro & Fazi, Stefano, 2022. "The ground handler dock capacitated pickup and delivery problem with time windows: A collaborative framework for air cargo operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    12. Wang, Zheng, 2018. "Delivering meals for multiple suppliers: Exclusive or sharing logistics service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 496-512.
    13. Byungjun Ju & Minsu Kim & Ilkyeong Moon, 2021. "Vehicle Routing Problem Considering Reconnaissance and Transportation," Sustainability, MDPI, vol. 13(6), pages 1-19, March.
    14. Zhu, Lin & Sheu, Jiuh-Biing, 2018. "Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 271(3), pages 896-912.
    15. Adria Soriano & Margaretha Gansterer & Richard F. Hartl, 2018. "The two-region multi-depot pickup and delivery problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1077-1108, October.
    16. Huang, Baobin & Tang, Lixin & Baldacci, Roberto & Wang, Gongshu & Sun, Defeng, 2023. "A metaheuristic algorithm for a locomotive routing problem arising in the steel industry," European Journal of Operational Research, Elsevier, vol. 308(1), pages 385-399.
    17. Timothy Curtois & Dario Landa-Silva & Yi Qu & Wasakorn Laesanklang, 2018. "Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 151-192, June.
    18. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    19. Neves-Moreira, F. & Amorim, P. & Guimarães, L. & Almada-Lobo, B., 2016. "A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations," European Journal of Operational Research, Elsevier, vol. 248(2), pages 487-506.
    20. Ulsrud, Karl Petter & Vandvik, Anders Helgeland & Ormevik, Andreas Breivik & Fagerholt, Kjetil & Meisel, Frank, 2022. "A time-dependent vessel routing problem with speed optimization," European Journal of Operational Research, Elsevier, vol. 303(2), pages 891-907.

    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:gam:jlogis:v:8:y:2024:i:1:p:14-:d:1333315. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.