Branch-and-price algorithm for the location-routing problem with time windows
Affiliation:
1. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA;2. Department of Industrial Engineering, Bilkent University, Ankara 06800, Turkey
Abstract:
This study proposes a branch-and-price algorithm to solve the Location-Routing Problem with Time Windows (LRPTW) which has never been attempted with the exact solutions before. The problem is solved by the simplex algorithm in the master problem and elementary shortest path problems with resource constraint corresponding to column generation in the subproblem until only the non-negative reduced cost columns remain. The proposed algorithm can solve many testing instances effectively. The computational results and the effect of time windows are also compared and discussed.