Journées de l'optimisation 2007 Optimizations days

This paper presents several column generation algorithms for the elementary shortest path problem with resource constraints. In a straight forward approach a non-elementary relaxation of the shortest path is found and elementarity is imposed in the master problem of the column generation. Another approach is to combine partial paths with bounded lengths. In the first approach the pricing problem does not impose elementarity. In the latter approach the pricing problem impose elementarity but is bounded in size of a resource. The Elementary Shortest Path Problem with Resource Constraints (ESPPRC) can be stated as: Given a graph G(V,A) with nodes V and edges A, a set R of resources that for each resource r have a lower bound $a^r_i$ for $i \in V$, an upper bound $b^r_i$ for $i \in V$, and a consumption $t^r_(ij)$ when using edge $(i, j) \in A$, then find the shortest path from an origin $o \in V$ to a destination $d \in V$ satisfying all resource limits. The ESPPRC with time and capacity as resource is among the most studied variant as it appears as a subproblem when solving the Vehicle Routing Problem with Time Windows. The most popular approach to solving the ESPPRC has been with label-setting algorithms. However, these algorithms have some weaknesses when dealing with very long (in the number of visited nodes) paths when resource constraints are not tight. Furthermore, it is doubtful how well label-setting algorithms scales on very large graphs. A straight forward decomposition approach suggests to solve a relaxed ESPPRC as a subproblem, namely the non-elementary version (SPPRC). The SPPRC can be solved in pseudopolynomial time and thus scales much better than ESPPRC. However, there are examples where even solving the relaxation is too time consuming. We propose a decomposition approach based on the generation of partial paths and the concatenation of these. In the bounded partial paths decomposition approach the main idea is to bound the solution space by bounding some resource, e.g., the number of nodes on a path. The master problem combines up to a certain number of bounded partial paths.

This paper presents a Branch-and-Cut-and-Price algorithm for the Vehicle Routing Problem with Time Windows based on earlier work (Jepsen et al. 2007). The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a Set Partitioning Problem as the master problem and an Elementary Shortest Path Problem with Resource Constraints as the pricing problem. To strengthen the formulation we derive Chvatal-Gomory rank-1 cuts based on the master problem formulation. Applying the Chvatal-Gomory rank-1 cuts in the master problem increases the complexity of the label algorithm used to solve the pricing problem since an additional resource is added for each inequality. It is possible to dominate a larger amount of labels by exploiting the step-like structure of the objective function of the pricing problem caused by the additional dual values of the Chvatal-Gomory rank-1 cuts. Hence, an improved dominance criterion was earlier proposed for specific cuts of the master problem. In this paper we introduce an extension to handle more general cuts. Computational experiments have been performed on the Solomon benchmarks showing that lower bounds are significantly improved. In most instances it is possible to prove integer optimality in the root node of the branch-and-bound tree. [Jepsen et al. 2007] M. Jepsen, B. Petersen, S. Spoorendonk, and D. Pisinger, "Subset row inequalities applied to the vehicle routing problem with time windows", Operations Research, 2007. Forthcoming.