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. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Schneider, M., 2016. "The vehicle-routing problem with time windows and driver-specific times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65941, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    10. 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.
    11. 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.
    12. 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.
    13. Du, Timon C. & Li, Eldon Y. & Chou, Defrose, 2005. "Dynamic vehicle routing for online B2C delivery," Omega, Elsevier, vol. 33(1), pages 33-45, February.
    14. Cruijssen, F., 2006. "Horizontal cooperation in transport and logistics," Other publications TiSEM ab6dbe68-aebc-4b03-8eea-d, Tilburg University, School of Economics and Management.
    15. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    16. Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
    17. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    18. 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.
    19. Jesus Gonzalez-Feliu, 2009. "The N-echelon Location routing problem: concepts and methods for tactical and operational planning," Working Papers halshs-00422492, HAL.
    20. Christos D. Tarantilis & Afroditi K. Anagnostopoulou & Panagiotis P. Repoussis, 2013. "Adaptive Path Relinking for Vehicle Routing and Scheduling Problems with Product Returns," Transportation Science, INFORMS, vol. 47(3), pages 356-379, August.

    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.