Highlights Studied a new variant of the multi-trip vehicle routing problem. Considered unloading time and capacity at depot. Formulated a trip-based set partitioning model for the problem. Proposed a branch-and-price-and-cut algorithm. Substantiated the effectiveness of algorithms in the computational experiments.

    Abstract Motivated by the practice of urban waste collection, we introduce a new variant of the multi-trip vehicle routing problem with time windows, where vehicles unload cargos collected from customers at a depot that owns a limited unloading capacity, and therefore some vehicles need to wait at a queue once the unloading capacity is fully occupied. Unloading queue at depot significantly compicates this problem since it makes a trip involve traveling, waiting, and unloading stages. We first formulate this problem into a trip-based set partitioning model, which has two sets of mutual exclusion constraints. To solve the model, we propose a branch-and-price-and-cut algorithm (BPC), in which the linear relaxation of the model is solved by column generation, and moreover, the relaxation gap is tightened by incorporating rounded capacity inequalities. Particularly, the mutual exclusion constraints induce a new and challening pricing problem, and we design a novel label-setting algorithm with tailored label structure to solve it. We conduct compuational experiments on a set of random instances generated from the Solomon’s benchmark, and the results demonstrate the effectiveness of the proposed model and algorithm.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    The multi-trip vehicle routing problem with time windows and unloading queue at depot


    Contributors:
    Huang, Nan (author) / Li, Jiliu (author) / Zhu, Wenbin (author) / Qin, Hu (author)


    Publication date :

    2021-05-13




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Multi-depot multi-trip vehicle routing problem with time windows and release dates

    Zhen, Lu / Ma, Chengle / Wang, Kai et al. | Elsevier | 2020



    The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates

    Cattaruzza, Diego / Absi, Nabil / Feillet, Dominique | British Library Online Contents | 2016