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 |
| Summary: | 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.
|
|---|---|
| ISSN: | 0120-6230 2422-2844 |