Cover Inequalities For the Vehicle Routing Problem with Time Windows and Shifts

Said Dabia, Stefan Ropke, Tom Van Woensel

    Research output: Contribution to JournalArticleAcademicpeer-review

    Abstract

    This paper introduces the Vehicle Routing Problem with Time Windows and Shifts (VRPTWS). At the depot, several shifts with non–overlapping operating periods are available to load the planned trucks. Each
    shift has a limited loading capacity. We solve the VRPTWS exactly by a branch–and–cut–and–price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint
    requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing sub-problem is solved by a label setting algorithm. Shift capacity constraints define knapsack inequalities,
    hence we use valid inequalities inspired from knapsack inequalities to strengthen the LP-relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust cover
    inequalities and a family of new non-robust cover inequalities. Numerical results show that non-robust cover inequalities significantly improve the algorithm.
    Original languageEnglish
    JournalTransportation Science
    Publication statusAccepted/In press - 2019

    Fingerprint

    Vehicle routing
    Trucks
    Labels
    pricing
    time
    Costs

    Cite this

    @article{9cc59dbf63f54e67990235bf56257368,
    title = "Cover Inequalities For the Vehicle Routing Problem with Time Windows and Shifts",
    abstract = "This paper introduces the Vehicle Routing Problem with Time Windows and Shifts (VRPTWS). At the depot, several shifts with non–overlapping operating periods are available to load the planned trucks. Eachshift has a limited loading capacity. We solve the VRPTWS exactly by a branch–and–cut–and–price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraintrequires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing sub-problem is solved by a label setting algorithm. Shift capacity constraints define knapsack inequalities,hence we use valid inequalities inspired from knapsack inequalities to strengthen the LP-relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust coverinequalities and a family of new non-robust cover inequalities. Numerical results show that non-robust cover inequalities significantly improve the algorithm.",
    author = "Said Dabia and Stefan Ropke and {Van Woensel}, Tom",
    year = "2019",
    language = "English",
    journal = "Transportation Science",
    issn = "0041-1655",
    publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

    }

    Cover Inequalities For the Vehicle Routing Problem with Time Windows and Shifts. / Dabia, Said; Ropke, Stefan; Van Woensel, Tom.

    In: Transportation Science, 2019.

    Research output: Contribution to JournalArticleAcademicpeer-review

    TY - JOUR

    T1 - Cover Inequalities For the Vehicle Routing Problem with Time Windows and Shifts

    AU - Dabia, Said

    AU - Ropke, Stefan

    AU - Van Woensel, Tom

    PY - 2019

    Y1 - 2019

    N2 - This paper introduces the Vehicle Routing Problem with Time Windows and Shifts (VRPTWS). At the depot, several shifts with non–overlapping operating periods are available to load the planned trucks. Eachshift has a limited loading capacity. We solve the VRPTWS exactly by a branch–and–cut–and–price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraintrequires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing sub-problem is solved by a label setting algorithm. Shift capacity constraints define knapsack inequalities,hence we use valid inequalities inspired from knapsack inequalities to strengthen the LP-relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust coverinequalities and a family of new non-robust cover inequalities. Numerical results show that non-robust cover inequalities significantly improve the algorithm.

    AB - This paper introduces the Vehicle Routing Problem with Time Windows and Shifts (VRPTWS). At the depot, several shifts with non–overlapping operating periods are available to load the planned trucks. Eachshift has a limited loading capacity. We solve the VRPTWS exactly by a branch–and–cut–and–price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraintrequires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing sub-problem is solved by a label setting algorithm. Shift capacity constraints define knapsack inequalities,hence we use valid inequalities inspired from knapsack inequalities to strengthen the LP-relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust coverinequalities and a family of new non-robust cover inequalities. Numerical results show that non-robust cover inequalities significantly improve the algorithm.

    M3 - Article

    JO - Transportation Science

    JF - Transportation Science

    SN - 0041-1655

    ER -