INFORMS Open Forum

Transportation Science and Logistics Society Webinar, April 16th, 10-11am EST: "A branch-price-and-cut algorithm for a two-echelon vehicle routing problem with time windows"

  • 1.  Transportation Science and Logistics Society Webinar, April 16th, 10-11am EST: "A branch-price-and-cut algorithm for a two-echelon vehicle routing problem with time windows"

    Posted 04-06-2021 13:27

    Dear colleagues,

    I invite you to attend the webinar titled "A branch-price-and-cut algorithm for a two-echelon vehicle routing problem with time windows" by Guy Desaulniers. Below you will find a short bio of Guy, and an abstract of his talk.

    The webinar is scheduled for Friday, April 16th, 10-11am ET. The webinar will be delivered via Zoom. The following is a link to the Zoom meeting. https://zoom.us/j/96904468811?pwd=NjZwTmRweksrWVpONU9URmxuSCtFZz09

    This webinar is organized by the Freight Transportation and Logistics Special Interest Group, and it is a part of the 2020 webinar series organized by the Transportation Science and Logistics (TSL) Society. Visit the following page to listen to recent webinars presented in the series.

    https://connect.informs.org/tsl/events/webinars

    I look forward to seeing you there!

     Sandra D. Eksioglu

    Chair, Freight Transportation and Logistics SIG

    Short Bio: Guy Desaulniers

    Guy Desaulniers received his PhD in mathematics from Polytechnique Montreal, where he is a professor in the department of Mathematics and Industrial Engineering. Between 2015 and 2019, he was the director of the GERAD research center. He has supervised more than 65 graduate students, co-authored more than 110 papers published in academic journals, and co-edited a book on column generation. His main research interests are in the areas of large-scale optimization (in particular, column generation), integer programming, combinatorial optimization, and constrained shortest path problems with applications to vehicle routing and crew scheduling in ground, air, rail, and maritime transportation.

    Abstract: A branch-price-and-cut algorithm for a two-echelon vehicle routing problem with time windows

    Guy Desaulniers, Polytechnique Montreal and GERAD, Canada, guy.desaulniers@gerad.ca

    Co-authors: Tayeb Mhamedi, Marilène Cherkesly, Henrik Andersson

    In this talk, we consider the two-echelon vehicle routing problem with time windows (2E-VRPTW). This problem arises in city logistics when high-capacity and low-capacity vehicles are used to transport merchandise from depots to satellites (first echelon), and from satellites to customers (second echelon), respectively. The aim is to determine a set of least-cost first- and second-echelon routes such that the load on the routes respect the capacity of the vehicles, each second-echelon route is supplied by exactly one first-echelon route, and each customer is visited by exactly one second-echelon route within its time window. We model this 2E-VRPTW with a route-based formulation involving first-echelon and second-echelon route variables. We propose to solve it using a branch-price-and-cut algorithm where only the second-echelon routes are generated by column generation. We discuss some specialized components of this algorithm, namely, the labeling algorithm for solving the pricing problems as well as deep dual optimal inequalities that are added to reduce degeneracy. We report computational results that show that our BPC algorithm outperforms a state-of-the-art algorithm. We also present sensitivity analysis results on the different components of our algorithm, and derive managerial insights related to the structure of the first-echelon routes.



    ------------------------------
    Sandra Eksioglu
    Professor
    University of Arkansas
    Fayetteville AR
    ------------------------------