IDEAS home Printed from https://ideas.repec.org/p/pra/mprapa/66121.html
   My bibliography  Save this paper

Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem

Author

Listed:
  • Okitonyumbe Y.F., Joseph
  • Ulungu, Berthold E.-L.
  • Kapiamba Nt., Joel

Abstract

Solving a classical vehicle routing problem (VRP) by exact methods presents many difficulties for large dimension problem. Consequently, in multi-objective framework, heuristic or metaheuristic methods are required. Due to particular VRP structure, it seems that a dedicated heuristic is more suitable than a metaheuristic. The aim of this article is to collapse different heuristics solving classical VRP and adapt them for to solve the multi-objective vehicle routing problem (MOVRP). The so-called Cobweb Algorithm simulates spider’s behavior when weaving cobweb. This paper presents the algorithm, a didactic example, concluding remarks and way for further researches.

Suggested Citation

  • Okitonyumbe Y.F., Joseph & Ulungu, Berthold E.-L. & Kapiamba Nt., Joel, 2015. "Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem," MPRA Paper 66121, University Library of Munich, Germany.
    • Handle: RePEc:pra:mprapa:66121
    as

    Download full text from publisher

    File URL: https://mpra.ub.uni-muenchen.de/66121/1/MPRA_paper_66121.pdf
    File Function: original version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    2. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    3. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    4. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    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.
    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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    2. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    3. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    4. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    5. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    6. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    7. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    8. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    9. A Ostertag & K F Doerner & R F Hartl & E D Taillard & P Waelti, 2009. "POPMUSIC for a real-world large-scale vehicle routing problem with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 934-943, July.
    10. Chebbi, Olfa & Chaouachi, Jouhaina, 2016. "Reducing the wasted transportation capacity of Personal Rapid Transit systems: An integrated model and multi-objective optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 236-258.
    11. Jesus Gonzalez-Feliu, 2012. "Cost optimisation in freight distribution with cross-docking: N-echelon location routing problem," Post-Print halshs-00565329, HAL.
    12. Ostermeier, Manuel, 2024. "The supply of convenience stores: Challenges of short-distance routing within the constraints of working time regulations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 997-1012.
    13. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    14. 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.
    15. Cruijssen, F. & Braysy, O. & Dullaert, W. & Fleuren, H.A. & Salomon, M., 2006. "Joint Route Planning under Varying Market Conditions," Other publications TiSEM 3de2ec0a-7424-43ec-a419-5, Tilburg University, School of Economics and Management.
    16. Tagmouti, Mariam & Gendreau, Michel & Potvin, Jean-Yves, 2007. "Arc routing problems with time-dependent service costs," European Journal of Operational Research, Elsevier, vol. 181(1), pages 30-39, August.
    17. W-C Chiang & R A Russell, 2004. "A metaheuristic for the vehicle-routeing problem with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1298-1310, December.
    18. J Faulin & A García del Valle, 2008. "Solving the capacitated vehicle routing problem using the ALGELECT electrostatic algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1685-1695, December.
    19. Zhu, Stuart X. & Ursavas, Evrim, 2018. "Design and analysis of a satellite network with direct delivery in the pharmaceutical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 190-207.
    20. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.

    More about this item

    Keywords

    Keywords: Savings; Cobweb; Heuristics; Multiobjective; Vehicle Routing Problem.;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    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:pra:mprapa:66121. 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: Joachim Winter (email available below). General contact details of provider: https://edirc.repec.org/data/vfmunde.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.