IDEAS home Printed from https://ideas.repec.org/a/ids/ijisen/v29y2018i4p453-477.html
   My bibliography  Save this article

A probabilistic granular tabu search for the distance constrained capacitated vehicle routing problem

Author

Listed:
  • Jose Bernal
  • John Willmer Escobar
  • Juan Camilo Paz
  • Rodrigo Linfati
  • Gustavo Gatica

Abstract

We address the well-known distance constrained capacitated vehicle routing problem (DCVRP) by considering Euclidean distances, in which the aim is to determine the routes to be performed to fulfil the demand of the customers by using a homogeneous fleet. The objective is to minimise the sum of the variable costs associated with the distance travelled by the performed routes. In this paper, we propose a metaheuristic algorithm based on a probabilistic granular tabu search (pGTS) by considering different neighbourhoods. In particular, the proposed algorithm selects a neighbourhood by using a probabilistic discrete function, which is modified dynamically during the search by favouring the moves that have improved the best solution found so far. A shaking procedure is applied whenever the best solution found so far is not improved for a given number of iterations. Computational experiments on benchmark instances taken from the literature show that the proposed approach is able to obtain high quality solutions, within short computing times.

Suggested Citation

  • Jose Bernal & John Willmer Escobar & Juan Camilo Paz & Rodrigo Linfati & Gustavo Gatica, 2018. "A probabilistic granular tabu search for the distance constrained capacitated vehicle routing problem," International Journal of Industrial and Systems Engineering, Inderscience Enterprises Ltd, vol. 29(4), pages 453-477.
    • Handle: RePEc:ids:ijisen:v:29:y:2018:i:4:p:453-477
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=94267
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Matías Núñez-Muñoz & Rodrigo Linfati & John Willmer Escobar, 2023. "Two-stage optimization scheme of routing scheduling from a single distribution center to multiple customers," Operational Research, Springer, vol. 23(2), pages 1-29, June.
    2. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    3. César Flores-Fonseca & Rodrigo Linfati & John Willmer Escobar, 2022. "Exact algorithms for production planning in mining considering the use of stockpiles and sequencing of power shovels in open-pit mines," Operational Research, Springer, vol. 22(3), pages 2529-2553, July.

    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:ids:ijisen:v:29:y:2018:i:4:p:453-477. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=188 .

    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.