IDEAS home Printed from https://ideas.repec.org/a/ids/ijmore/v27y2024i4p458-478.html
   My bibliography  Save this article

Efficient clustering-based constructive heuristics for capacitated vehicle routing

Author

Listed:
  • Ankan Bose
  • Dipak Laha

Abstract

In this paper, we address the capacitated vehicle routing problem, a generalised variant of vehicle routing problems, in which the routes are assigned to a fleet of vehicles to serve customers meeting their demands in order to optimise certain criterion. Here, we aim to minimise total length of the routes. Although a plethora of research on vehicle routing appeared in the literature over many decades, a few good construction heuristics exist, namely, the heuristics of Clark and Wright (1964), Segerstedt (2014, 2018), which are used for minimising the total length of routes in the capacitated vehicle routing problem. In this paper, we have modified the heuristics of Segerstedt (2014, 2018) using K-means++ clustering in conjunction with a route merging procedure to enhance the solution quality for this problem. The computational results reveal that the modified approaches significantly improve their performance while not affecting their time-complexity.

Suggested Citation

  • Ankan Bose & Dipak Laha, 2024. "Efficient clustering-based constructive heuristics for capacitated vehicle routing," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 27(4), pages 458-478.
    • Handle: RePEc:ids:ijmore:v:27:y:2024:i:4:p:458-478
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=138465
    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.

    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:ijmore:v:27:y:2024:i:4:p:458-478. 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=320 .

    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.