Advanced Search
MyIDEAS: Login to save this article or follow this journal

Branch-and-Price and Heuristic Column Generation for the Generalized Truck-and-Trailer Routing Problem || Branch-and-Price y generación heurística de columnas para el problema generalizado de rutas de trenes de carretera

Contents:

Author Info

  • Drexl, Michael

    ()
    (Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz Fraunhofer Centre for Applied Research on Supply Chain Services SCS, Nuremberg)

Registered author(s):

    Abstract

    The generalized truck-and-trailer routing problem (GTTRP) constitutes a unified model for vehicle routing problems with trailers and a fixed lorry-trailer assignment. The GTTRP is a generalization of the truck-and-trailer routing problem (TTRP), which itself is an extension of the well-known vehicle routing problem (VRP). In the GTTRP, the vehicle fleet consists of single lorries and lorry-trailer combinations. Some customers may be visited only 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 its trailer 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. || El problema generalizado de rutas de trenes de carretera (generalized truck-and-trailer routing problem, GTTRP) constituye un modelo unificado para problemas de rutas de vehículos con remolques y asignación fija camión-remolque. El GTTRP es una generalización del truck-and-trailer routing problem (TTRP), que es una extensión del conocido problema de rutas de vehículos (vehicle routing problem, VRP). En el GTTRP, la flota de vehículos consiste en camiones sin remolque (camiones solos) y trenes de carretera. Algunos clientes pueden ser visitados exclusivamente por un camión solo o un camión sin su remolque, otros pueden ser visitados también por un tren de carretera. Además de las ubicaciones de los clientes hay otro tipo de localización llamada ubicación de trasbordo. Allí los remolques pueden ser aparcados, y es posible efectuar un trasbordo de carga desde un camión a su remolque. En este trabajo se presentan dos modelos de programación lineal entero mixto (MIP). Además, se describen un algoritmo exacto branch-and-price y variantes heurísticas de este algoritmo. Se presentan y analizan estudios computacionales con los algoritmos. Se usan problemas generados aleatoriamente, diseñados para semejar situaciones reales, y problemas TTRP de la literatura. Los resultados muestran que, utilizando un algoritmo heurístico basado en generación de columnas, se pueden resolver problemas de estructura y tamaño real en poco tiempo y con solución de alta calidad.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://www.upo.es/RevMetCuant/pdf/vol12/art51.pdf
    Download Restriction: no

    File URL: http://www.upo.es/RevMetCuant/bibtex.php?id=51
    Download Restriction: no

    Bibliographic Info

    Article provided by Universidad Pablo de Olavide, Department of Quantitative Methods for Economics and Business Administration in its journal Revista de Métodos Cuantitativos para la Economía y la Empresa.

    Volume (Year): 12 (2011)
    Issue (Month): 1 (December)
    Pages: 5-38

    as in new window
    Handle: RePEc:pab:rmcpee:v:12:y:2011:i:1:p:5-38

    Contact details of provider:
    Postal: Carretera de Utrera km.1, 41013 Sevilla
    Phone: + 34 954 34 8913
    Fax: + 34 954 34 9339
    Email:
    Web page: http://www.upo.es/economia/metodos/
    More information through EDIRC

    Related research

    Keywords: vehicle routing; transshipment; fleet planning; elementary shortest path problem with resource constraints; rutas de vehículos; trasbordo; planificación de flotas; problema del camino más corto con limitaciones de recursos.;

    Find related papers by JEL classification:

    References

    No references listed on IDEAS
    You can help add them by filling out this form.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:pab:rmcpee:v:12:y:2011:i:1:p:5-38. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Publicación Digital - UPO).

    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.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with 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 profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.