Route relaxations for the pickup and delivery problem with time windows
Luciano Costa  1, *@  , Claudio Contardo  2@  , Guy Desaulniers  1@  
1 : Ecole Polytechnique de Montréal and GERAD
* : Corresponding author

The pickup and delivery problem with time windows (PDPTW) aims at finding routes to satisfy a set of requests, each associated with pickup and delivery points. Like several other vehicle routing problems, the leading technique to solve the PDPTW is column generation (CG). In the literature, all the CG based algorithms developed to solve the PDPTW consider a set-partitioning formulation at the master and rely on a pricing problem to generate feasible routes. The inconvenient associated with this strategy is that, due to the pairing and precedence relations arising by the PDPTW definition, devising an efficient CG algorithm to solve this problem may be a challenging task. In this work, we investigate the impact of not directly addressing the pairing and precedence constraints in the CG pricing problem. Instead, we exploit the underlying structure induced by PDPTW feasible routes and solve a relaxed pricing problem by disregarding partially (or completely) pairing and precedence constraints. We introduce a new set of variables representing commodity paths from each origin point to its destination to ensure that the precedence and pairing constraints are met, at the master problem level. These new variables along with additional constraints incorporated into the master problem make the new formulation valid. Even if the proposed method may yield degradation of the lower bounds achieved, the also less restrictive dominance rules allow for gains in the overall running times. Preliminary computational experiments are presented to assess the validity and efficiency of the proposed methodology.

Online user: 2 RSS Feed