Article ID: | iaor20071232 |
Country: | United States |
Volume: | 18 |
Issue: | 3 |
Start Page Number: | 391 |
End Page Number: | 406 |
Publication Date: | Jun 2006 |
Journal: | INFORMS Journal On Computing |
Authors: | Irnich Stefan, Villeneuve Daniel |
Keywords: | networks: path |
The elementary shortest-path problem with resource constraints (ESPPRC) is a widely used modeling tool in formulating vehicle-routing and crew-scheduling applications. The ESPPRC often occurs as a subproblem of an enclosing problem, where it is used to generate implicitly the set of all feasible routes or schedules, as in the column-generation formulation of the vehicle-routing problem with time windows (VRPTW). As the ESPPRC problem is NP-hard in the strong sense, classical solution approaches are based on the corresponding nonelementary shortest-path problem with resource constraints (SPPRC), which can be solved using a pseudo-polynomial labeling algorithm. While solving the enclosing problem by branch and price, this subproblem relaxation leads to weak lower bounds and sometimes impractically large branch-and-bound trees. A compromise between solving ESPPRC and SPPRC is to forbid cycles of small length. In the SPPRC with