This paper proposes an exact method for solving an optimization problem arising in several distribution networks where customers can be served directly, using vehicle routes from a central depot, or through transhipment facilities. The problem consists of optimizing the following inter-dependent decisions: selecting transhipment facilities, allocating customers to these facilities, and designing vehicle routes emanating from a central depot to minimize the total distribution cost. This problem is called the Vehicle Routing Problem with Transhipment Facilities ( vrptf ). The paper describes two integer-programming formulations for the vrptf , i.e., an edge-flow based formulation and a Set Partitioning (SP) based formulation. The LP-relaxation of the two formulations are further strengthened by the addition of different valid inequalities. We also describe two new route relaxations used by dual ascent heuristics to find near-optimal dual solutions of LP-relaxation of the SP model. The valid inequalities and the route relaxations are used in a branch-and-cut-and-price approach to solve the problem to optimality. The proposed method is tested on a large family of instances, including real-world examples. The computational results obtained indicate the effectiveness of the proposed method.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    The Vehicle Routing Problem with Transhipment Facilities



    Published in:

    Transportation science ; 51 , 2 ; 592-606


    Publication date :

    2017




    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



    The Vehicle Routing Problem with Transhipment Facilities

    Baldacci, Roberto | Online Contents | 2016


    The Vehicle Routing Problem with Transhipment Facilities

    Baldacci, Roberto / Ngueveu, Sandra Ulrich / Calvo, Roberto Wolfler | British Library Online Contents | 2017



    Transhipment targets

    Online Contents | 1997


    Seeking cheaper transhipment

    Gonlag, Michel | Online Contents | 1997