Program > By speaker > Irnich Stefan

Recently, Meisel and Kopfer (2014, OR Spectrum) introduced the Active-Passive Vehicle-Routing Problem (APVRP). Therein two classes of vehicles are required to fulfill pickup-and-delivery requests: Non-autonomous passive vehicles such as containers transport the cargo from its pickup to its delivery location. Autonomous active vehicles such as trucks can carry passive vehicles from one to another location. In the basic version we consider, each passive vehicle can load only one request at a time and each active vehicle can transport only one passive vehicle at a time. Each request must be executed by the same passive vehicle, while different active vehicles can be involved. For example, one active vehicle may deliver a passive to a pickup location and another active may later transport the passive from the request's pickup to its delivery point. Therefore, synchronization of active and passive vehicles is required. A column-generation algorithm is used to solve the APVRP, where the subproblem is a Shortest Path Problem with Time Windows and linear node costs (SPPRC-LNC). In this second part, we compare different solution methods for the SPPRC-LNC. The baseline approach is a labeling algorithm capable of solving the ng-tour relaxation bidirectionally. We compare is with a direct MIP-formulation, in which routing and resource variables are coupled without big-M technique. Moreover, the SPPRC-LNC can be solved with a column-generation algorithm giving rise to an overall nested column-generation algorithm.