A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem

We propose a heuristic approach based on the Clarke-Wright algorithm (CW) to solve the open version of the well-known capacitated vehicle routing problem in which vehicles are not required to return to the depot after completing service. The proposed CW has been presented in four procedures composed...

Descripción completa

Detalles Bibliográficos
Autores principales: Pichpibul, Tantikorn, Kawtummachai, Ruengsak
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2013
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3870871/
https://www.ncbi.nlm.nih.gov/pubmed/24382948
http://dx.doi.org/10.1155/2013/874349
_version_ 1782296739682713600
author Pichpibul, Tantikorn
Kawtummachai, Ruengsak
author_facet Pichpibul, Tantikorn
Kawtummachai, Ruengsak
author_sort Pichpibul, Tantikorn
collection PubMed
description We propose a heuristic approach based on the Clarke-Wright algorithm (CW) to solve the open version of the well-known capacitated vehicle routing problem in which vehicles are not required to return to the depot after completing service. The proposed CW has been presented in four procedures composed of Clarke-Wright formula modification, open-route construction, two-phase selection, and route postimprovement. Computational results show that the proposed CW is competitive and outperforms classical CW in all directions. Moreover, the best known solution is also obtained in 97% of tested instances (60 out of 62).
format Online
Article
Text
id pubmed-3870871
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-38708712014-01-01 A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem Pichpibul, Tantikorn Kawtummachai, Ruengsak ScientificWorldJournal Research Article We propose a heuristic approach based on the Clarke-Wright algorithm (CW) to solve the open version of the well-known capacitated vehicle routing problem in which vehicles are not required to return to the depot after completing service. The proposed CW has been presented in four procedures composed of Clarke-Wright formula modification, open-route construction, two-phase selection, and route postimprovement. Computational results show that the proposed CW is competitive and outperforms classical CW in all directions. Moreover, the best known solution is also obtained in 97% of tested instances (60 out of 62). Hindawi Publishing Corporation 2013-12-05 /pmc/articles/PMC3870871/ /pubmed/24382948 http://dx.doi.org/10.1155/2013/874349 Text en Copyright © 2013 T. Pichpibul and R. Kawtummachai. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Pichpibul, Tantikorn
Kawtummachai, Ruengsak
A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem
title A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem
title_full A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem
title_fullStr A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem
title_full_unstemmed A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem
title_short A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem
title_sort heuristic approach based on clarke-wright algorithm for open vehicle routing problem
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3870871/
https://www.ncbi.nlm.nih.gov/pubmed/24382948
http://dx.doi.org/10.1155/2013/874349
work_keys_str_mv AT pichpibultantikorn aheuristicapproachbasedonclarkewrightalgorithmforopenvehicleroutingproblem
AT kawtummachairuengsak aheuristicapproachbasedonclarkewrightalgorithmforopenvehicleroutingproblem
AT pichpibultantikorn heuristicapproachbasedonclarkewrightalgorithmforopenvehicleroutingproblem
AT kawtummachairuengsak heuristicapproachbasedonclarkewrightalgorithmforopenvehicleroutingproblem

Ejemplares similares