Nodal aggregation of resource constraints in a shortest path problem

• Published in: European journal of operational research 2006-07, Vol.172 (2), p.500-514
• Main Authors: Nagih, Anass, Soumis, François
• Format: Article
• Language: English
• Subjects: Applied sciences; Column generation; Dynamic programming; Exact sciences and technology; Heuristic; Lagrange multiplier; Lagrangian relaxation; Operational research and scientific management; Operational research. Management science; Operations research; Resource aggregation; Resource constraints; Scheduling, sequencing; Shortest path; Shortest path algorithms; Studies; Surrogate relaxation
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2004.09.052

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.