State‐space relaxation procedures for the computation of bounds to routing problems

TLDR

Dynamic programming struggles with combinatorial problems because of enormous state spaces, and state‑space relaxation is analogous to Lagrangian relaxation in integer programming. The paper proposes a general state‑space relaxation procedure that yields bounds for branch‑and‑bound algorithms and surveys its application to TSP, time‑constrained TSP, and VRP. The authors describe valid state‑space relaxations for TSP, time‑constrained TSP, and VRP, derive several bounds, and propose subgradient optimization and state‑space ascent to maximize the resulting lower bounds. Further details of the surveyed procedures are available in references [2], [3], and [4].

Abstract

Abstract It is well‐known that few combinatorial optimization problems can be solved effectively by dynamic programming alone, since the number of vertices of the state space graph is enormous. What we are proposing here is a general relaxation procedure whereby the state‐space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem. This state space relaxation method is analogous to Langrangian relaxation in integer programming. This paper gives a survey of this new methodology, and gives, as examples, applications to the traveling salesman problem (TSP), the time‐constrained TSP and the vehicle routing problem (VRP). Valid state space relaxations are discussed for these problems and several bounds are derived in each case. Subgradient optimization and “state space ascent” are discussed as methods of maximizing the resulting lower bounds. More details of the procedures surveyed in this paper can be found in [2, 3, 4].