Branch-and-Price and Heuristic Column Generation for the Generalized Truckand- Trailer Routing Problem
Fuente:
Redalyc
Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | en |
| Published: |
Universidad Pablo de Olavide
2011
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1876474635520835584 |
|---|---|
| author | Michael Drexl |
| author_facet | Michael Drexl |
| contents | Branch-and-Price and Heuristic Column Generation for the Generalized Truckand- Trailer Routing Problem Michael Drexl Economía y Finanzas transshipment feet planning vehicle routing elementary short est path problem with resource constraints The generalized truck-and-trailer routing problem (GTTRP) constitutes aunifed model for vehicle routing problems with trailers and a fxed lorry-trailer assignment. The GTTRP is a generalization of the truck-and-trailerrouting problem (TTRP), which itself is an extension of the well-known vehicle routing problem (VRP). In the GTTRP, the vehicle feet consists of single lorries and lorry-trailer combinations. Some customers may be visitedonly by a single lorry or by a lorry without its trailer, some may also be visited by a lorry-trailer combination. In addition to the customer locations,there is another relevant type of location, called transshipment location,where trailers can be parked and where a load transfer from a lorry to itstrailer can be performed. In this paper, two mixed-integer programming (MIP) formulations for the GTTRP are presented. Moreover, an exact solution procedure for the problem, a branch-and-price algorithm, and heuristic variants of this algorithm are described. Computational experiments with the algorithms are presented and discussed. The experiments are performed on randomly generated instances structured to resemble real-world situations and on TTRP benchmark instances from the literature. The results of the experiments show that instances of realistic structure and size can be solved in short time and with high solution quality by a heuristic algorithm based on column generation. 2011 artículo científico 1886-516X https://www.redalyc.org/articulo.oa?id=233122469002 en http://www.redalyc.org/revista.oa?id=2331 Revista de Métodos Cuantitativos para la Economía y la Empresa application/pdf Universidad Pablo de Olavide Revista de Métodos Cuantitativos para la Economía y la Empresa (España) Vol.12 |
| format | Artículo científico |
| id | redalyc_233122469002 |
| institution | Redalyc |
| language | en |
| publishDate | 2011 |
| publisher | Universidad Pablo de Olavide |
| spellingShingle | Branch-and-Price and Heuristic Column Generation for the Generalized Truckand- Trailer Routing Problem Michael Drexl Economía y Finanzas transshipment feet planning vehicle routing elementary short est path problem with resource constraints Branch-and-Price and Heuristic Column Generation for the Generalized Truckand- Trailer Routing Problem Michael Drexl Economía y Finanzas transshipment feet planning vehicle routing elementary short est path problem with resource constraints The generalized truck-and-trailer routing problem (GTTRP) constitutes aunifed model for vehicle routing problems with trailers and a fxed lorry-trailer assignment. The GTTRP is a generalization of the truck-and-trailerrouting problem (TTRP), which itself is an extension of the well-known vehicle routing problem (VRP). In the GTTRP, the vehicle feet consists of single lorries and lorry-trailer combinations. Some customers may be visitedonly by a single lorry or by a lorry without its trailer, some may also be visited by a lorry-trailer combination. In addition to the customer locations,there is another relevant type of location, called transshipment location,where trailers can be parked and where a load transfer from a lorry to itstrailer can be performed. In this paper, two mixed-integer programming (MIP) formulations for the GTTRP are presented. Moreover, an exact solution procedure for the problem, a branch-and-price algorithm, and heuristic variants of this algorithm are described. Computational experiments with the algorithms are presented and discussed. The experiments are performed on randomly generated instances structured to resemble real-world situations and on TTRP benchmark instances from the literature. The results of the experiments show that instances of realistic structure and size can be solved in short time and with high solution quality by a heuristic algorithm based on column generation. 2011 artículo científico 1886-516X https://www.redalyc.org/articulo.oa?id=233122469002 en http://www.redalyc.org/revista.oa?id=2331 Revista de Métodos Cuantitativos para la Economía y la Empresa application/pdf Universidad Pablo de Olavide Revista de Métodos Cuantitativos para la Economía y la Empresa (España) Vol.12 |
| title | Branch-and-Price and Heuristic Column Generation for the Generalized Truckand- Trailer Routing Problem |
| topic | Economía y Finanzas transshipment feet planning vehicle routing elementary short est path problem with resource constraints |
| url | https://www.redalyc.org/articulo.oa?id=233122469002 |