Nodal aggregation of resource constraints in a shortest path problem

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 th...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2004.09.052