A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP)
This paper presents a hybrid algorithm for solving the Capacitated Vehicle Routing Problem with practical three-dimensional loading constraint. This problem is known as 3L-CVRP (Three-dimensional Loading Capacitated Vehicle Routing Problem). The proposed methodology consists of two phases. The firs...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad de Antioquia
2016-03-01
|
| Series: | Revista Facultad de Ingeniería Universidad de Antioquia |
| Subjects: | |
| Online Access: | https://revistas.udea.edu.co/index.php/ingenieria/article/view/21180 |
| _version_ | 1827981450369040384 |
|---|---|
| author | Luis Miguel Escobar-Falcón David Álvarez-Martínez Mauricio Granada-Echeverri John Willmer-Escobar Rubén Augusto Romero-Lázaro |
| author_facet | Luis Miguel Escobar-Falcón David Álvarez-Martínez Mauricio Granada-Echeverri John Willmer-Escobar Rubén Augusto Romero-Lázaro |
| author_sort | Luis Miguel Escobar-Falcón |
| collection | DOAJ |
| description |
This paper presents a hybrid algorithm for solving the Capacitated Vehicle Routing Problem with practical three-dimensional loading constraint. This problem is known as 3L-CVRP (Three-dimensional Loading Capacitated Vehicle Routing Problem). The proposed methodology consists of two phases. The first phase uses an optimization procedure based on cuts to obtain solutions for the well-known Capacitated Vehicle Routing Problem (CVRP). The second phase validates the results of the first phase of a GRASP algorithm (Greedy Randomized Adaptive Search Procedure). In particular, the GRASP approach evaluates the packing constraints for each performed route of the CVRP. The proposed hybrid algorithm uses a relaxation of the classical model of two sub-indices for the vehicle routing problem. Specifically different types of cuts are added: subtour elimination, capacity-cut constraints, and packing-cut constrains. The proposed algorithm is compared with the most efficient approaches for the 3L-CVRP on the set of benchmark instances considered in the literature. The computational results indicate that the proposed approach is able to obtain good solutions, improving some of the best-known solutions from the literature.
|
| first_indexed | 2024-04-09T22:09:46Z |
| format | Article |
| id | doaj.art-99b35a674cc049f8aa204c3a4e9ca6df |
| institution | Directory Open Access Journal |
| issn | 0120-6230 2422-2844 |
| language | English |
| last_indexed | 2024-04-09T22:09:46Z |
| publishDate | 2016-03-01 |
| publisher | Universidad de Antioquia |
| record_format | Article |
| series | Revista Facultad de Ingeniería Universidad de Antioquia |
| spelling | doaj.art-99b35a674cc049f8aa204c3a4e9ca6df2023-03-23T12:30:36ZengUniversidad de AntioquiaRevista Facultad de Ingeniería Universidad de Antioquia0120-62302422-28442016-03-017810.17533/udea.redin.n78a02A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP)Luis Miguel Escobar-Falcón0David Álvarez-Martínez1Mauricio Granada-Echeverri2John Willmer-Escobar3Rubén Augusto Romero-Lázaro4Technological University of PereiraSão Paulo State UniversityTechnological University of PereiraValley UniversitySão Paulo State University This paper presents a hybrid algorithm for solving the Capacitated Vehicle Routing Problem with practical three-dimensional loading constraint. This problem is known as 3L-CVRP (Three-dimensional Loading Capacitated Vehicle Routing Problem). The proposed methodology consists of two phases. The first phase uses an optimization procedure based on cuts to obtain solutions for the well-known Capacitated Vehicle Routing Problem (CVRP). The second phase validates the results of the first phase of a GRASP algorithm (Greedy Randomized Adaptive Search Procedure). In particular, the GRASP approach evaluates the packing constraints for each performed route of the CVRP. The proposed hybrid algorithm uses a relaxation of the classical model of two sub-indices for the vehicle routing problem. Specifically different types of cuts are added: subtour elimination, capacity-cut constraints, and packing-cut constrains. The proposed algorithm is compared with the most efficient approaches for the 3L-CVRP on the set of benchmark instances considered in the literature. The computational results indicate that the proposed approach is able to obtain good solutions, improving some of the best-known solutions from the literature. https://revistas.udea.edu.co/index.php/ingenieria/article/view/21180vehicle routing problemmatheuristicsbranch-and-cutpacking |
| spellingShingle | Luis Miguel Escobar-Falcón David Álvarez-Martínez Mauricio Granada-Echeverri John Willmer-Escobar Rubén Augusto Romero-Lázaro A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP) Revista Facultad de Ingeniería Universidad de Antioquia vehicle routing problem matheuristics branch-and-cut packing |
| title | A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP) |
| title_full | A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP) |
| title_fullStr | A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP) |
| title_full_unstemmed | A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP) |
| title_short | A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP) |
| title_sort | matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem 3l cvrp |
| topic | vehicle routing problem matheuristics branch-and-cut packing |
| url | https://revistas.udea.edu.co/index.php/ingenieria/article/view/21180 |
| work_keys_str_mv | AT luismiguelescobarfalcon amatheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT davidalvarezmartinez amatheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT mauriciogranadaecheverri amatheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT johnwillmerescobar amatheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT rubenaugustoromerolazaro amatheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT luismiguelescobarfalcon matheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT davidalvarezmartinez matheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT mauriciogranadaecheverri matheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT johnwillmerescobar matheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp AT rubenaugustoromerolazaro matheuristicalgorithmforthethreedimensionalloadingcapacitatedvehicleroutingproblem3lcvrp |