In the single truck and trailer routing problem with satellite depots (STTRPSD), a truck with a detachable trailer based at a main depot must serve the demand of a set of customers accessible only by truck. Therefore, before serving the customers, it is necessary to detach the trailer in an appropriate parking place (called either a satellite depot or a trailer point) and transfer goods between the truck and the trailer. This problem has applications in milk collection for farms that cannot be reached using large vehicles. In this work we present an integer programming formulation of the STTRPSD. This formulation is tightened with several families of valid inequalities for which we have developed different (exact and heuristic) separation procedures. Using these elements, we have implemented a branch-and-cut algorithm for the solution of the STTRPSD. A computational experiment with published instances shows that the proposed branch-and-cut algorithm consistently solves problems with up to 50 customers and 10 satellite depots, and it has also been able to solve instances with up to 20 satellite depots and 100 clustered customers.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots



    Published in:

    Publication date :

    2016




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



    A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots

    Belenguer, José Manuel / Benavent, Enrique / Martínez, Antonio et al. | British Library Online Contents | 2016


    GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots

    Villegas, Juan G. / Prins, Christian / Prodhon, Caroline et al. | Tema Archive | 2010


    Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows

    Rothenbächer, Ann-Kathrin / Drexl, Michael / Irnich, Stefan | British Library Online Contents | 2018


    A Memetic Algorithm Approach for Solving the Truck and Trailer Routing Problem

    Lee, Soon-Kyo / Cheong, Taesu | Springer Verlag | 2015