IDEAS home Printed from https://ideas.repec.org/p/mag/wpaper/160004.html
   My bibliography  Save this paper

A Genetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes

Author

Listed:
  • Henriette Koch

    (Department of Management Science, Otto-von-Guericke University Magdeburg)

  • Tino Henke

    (Department of Management Science, Otto-von-Guericke University Magdeburg)

  • Gerhard Wäscher

    (Department of Management Science, Otto-von-Guericke University Magdeburg; School of Mechanical, Electronic and Control Engineering, Beijing Jiaotong University)

Abstract

In this paper, a genetic algorithm for the multi-compartment vehicle routing problem with continuously flexible compartment sizes is proposed. In this problem, supplies of several product types have to be collected from customer locations and transported to a depot at minimal cost. In order to avoid mixing of different product types which are transported in the same vehicle, the vehicle’s capacity can be separated into a limited number of compartments. The size of each compartment can be selected arbitrarily within the limits of the vehicle’s capacity, and in each compartment one or several supplies of the same product type can be transported. For solving this problem, a genetic algorithm is presented. The performance of the proposed algorithm is evaluated by means of extensive numerical experiments. Furthermore, the economic benefits of using continuously flexible compartments are investigated.

Suggested Citation

  • Henriette Koch & Tino Henke & Gerhard Wäscher, 2016. "A Genetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 160004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    • Handle: RePEc:mag:wpaper:160004
    as

    Download full text from publisher

    File URL: http://www.fww.ovgu.de/fww_media/femm/femm_2016/2016_04.pdf
    File Function: First version, 2011
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. Jorge E. Mendoza & Bruno Castanier & Christelle Guéret & Andrés L. Medaglia & Nubia Velasco, 2011. "Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 45(3), pages 346-363, August.
    3. Al-Khayyal, Faiz & Hwang, Seung-June, 2007. "Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part I: Applications and model," European Journal of Operational Research, Elsevier, vol. 176(1), pages 106-130, January.
    4. Muyldermans, L. & Pang, G., 2010. "On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm," European Journal of Operational Research, Elsevier, vol. 206(1), pages 93-103, October.
    5. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    6. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    7. Coelho, Leandro C. & Laporte, Gilbert, 2015. "Classification, models and exact algorithms for multi-compartment delivery problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 854-864.
    8. K Fagerholt & M Christiansen, 2000. "A combined ship scheduling and allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(7), pages 834-842, July.
    9. Gerald G. Brown & Glenn W. Graves, 1981. "Real-Time Dispatch of Petroleum Tank Trucks," Management Science, INFORMS, vol. 27(1), pages 19-32, January.
    10. Lahyani, Rahma & Coelho, Leandro C. & Khemakhem, Mahdi & Laporte, Gilbert & Semet, Frédéric, 2015. "A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia," Omega, Elsevier, vol. 51(C), pages 1-10.
    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. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2019. "A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes," Annals of Operations Research, Springer, vol. 275(2), pages 321-338, April.
    2. Frank, Markus & Ostermeier, Manuel & Holzapfel, Andreas & Hübner, Alexander & Kuhn, Heinrich, 2021. "Optimizing routing and delivery patterns with multi-compartment vehicles," European Journal of Operational Research, Elsevier, vol. 293(2), pages 495-510.
    3. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    4. Ostermeier, Manuel & Hübner, Alexander, 2018. "Vehicle selection for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 269(2), pages 682-694.
    5. Katrin Heßler, 2020. "Exact Algorithms for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," Working Papers 2007, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Heßler, Katrin, 2021. "Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 294(1), pages 188-205.
    7. Manuel Ostermeier & Sara Martins & Pedro Amorim & Alexander Hübner, 2018. "Loading constraints for a multi-compartment vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 997-1027, October.
    8. Tino Henke & Grazia Speranza & Gerhard Wäscher, 2017. "A Branch-and-Cut Algorithm for the Multi Compartment vehicle Routing Problem with Flexbile Compartment Sizes," FEMM Working Papers 170004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.

    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. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    2. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2019. "A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes," Annals of Operations Research, Springer, vol. 275(2), pages 321-338, April.
    3. Heßler, Katrin, 2021. "Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 294(1), pages 188-205.
    4. Katrin Heßler, 2020. "Exact Algorithms for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," Working Papers 2007, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    5. Ostermeier, Manuel & Hübner, Alexander, 2018. "Vehicle selection for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 269(2), pages 682-694.
    6. Yan Cheng Hsu & Jose L. Walteros & Rajan Batta, 2020. "Solving the petroleum replenishment and routing problem with variable demands and time windows," Annals of Operations Research, Springer, vol. 294(1), pages 9-46, November.
    7. Tino Henke & Grazia Speranza & Gerhard Wäscher, 2017. "A Branch-and-Cut Algorithm for the Multi Compartment vehicle Routing Problem with Flexbile Compartment Sizes," FEMM Working Papers 170004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    8. Alexander Hübner & Manuel Ostermeier, 2019. "A Multi-Compartment Vehicle Routing Problem with Loading and Unloading Costs," Service Science, INFORMS, vol. 53(1), pages 282-300, February.
    9. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    10. Samira Mirzaei & Sanne Wøhlk, 2019. "A Branch-and-Price algorithm for two multi-compartment vehicle routing problems," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(1), pages 1-33, March.
    11. Samira Mirzaei & Sanne Wøhlk, 2017. "Erratum to: A Branch-and-Price algorithm for two multi-compartment vehicle routing problems," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 185-218, June.
    12. Sun, Lijun & Zhang, Yuankai & Hu, Xiangpei, 2021. "Economical-traveling-distance-based fleet composition with fuel costs: An application in petrol distribution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    13. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    14. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2014. "The Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 140006, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    15. Katrin Heßler & Stefan Irnich, 2023. "Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 50-65, January.
    16. Alinaghian, Mahdi & Shokouhi, Nadia, 2018. "Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search," Omega, Elsevier, vol. 76(C), pages 85-99.
    17. Muyldermans, L. & Pang, G., 2010. "On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm," European Journal of Operational Research, Elsevier, vol. 206(1), pages 93-103, October.
    18. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    19. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
    20. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.

    More about this item

    Keywords

    vehicle routing; multiple compartments; genetic algorithm; heuristics;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:mag:wpaper:160004. 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: Guido Henkel (email available below). General contact details of provider: https://edirc.repec.org/data/fwmagde.html .

    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.