This paper addresses a new vehicle routing problem that simultaneously involves time windows, split delivery, and linear weight-related cost. This problem is a generalization of the split delivery vehicle routing problem with time windows (SDVRPTW), which consists of determining a set of least-cost vehicle routes to serve all customers while respecting the restrictions of vehicle capacity and time windows. The travel cost per unit distance is a linear function of the vehicle weight and the customer demand can be fulfilled by multiple vehicles. To solve this problem, we propose an exact branch-and-price-and-cut algorithm, where the pricing subproblem is a variant of the resource-constrained elementary shortest path problem. We first prove that at least one optimal solution to the pricing subproblem is associated with an extreme delivery pattern, and then we design a tailored and novel label-setting algorithm to solve the pricing subproblem. Computational results show that our proposed algorithm can handle both the SDVRPTW and our new problem effectively.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost



    Erschienen in:

    Transportation science ; 51 , 2 ; 668-687


    Erscheinungsdatum :

    2017




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch



    Klassifikation :

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



    Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost

    Luo, Zhixing / Qin, Hu / Zhu, Wenbin et al. | British Library Online Contents | 2017



    Branch-and-Price on the Split Delivery Vehicle Routing Problem with Time Windows and Alternative Delivery Periods

    Breier, H. / Gossler, T. / Gesellschaft fur Operations Research; Dutch Society of Operations Research; Erasmus Universiteit Rotterdam | British Library Conference Proceedings | 2014



    Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows

    Dabia, S. / Ropke, S. / van Woensel, T. et al. | British Library Online Contents | 2013