Premium
A GRASP algorithm for a capacitated, fixed charge, multicommodity network flow problem with uncertain demand and survivability constraints
Author(s) -
Olivera Alfredo,
Amoza Franco Robledo,
Testuri Carlos E.
Publication year - 2010
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00755.x
Subject(s) - grasp , survivability , mathematical optimization , multi commodity flow problem , solver , computer science , heuristic , flow network , metaheuristic , key (lock) , path (computing) , mathematics , computer network , computer security , programming language
An extension of the capacitated, fixed charge, multicommodity network flow problem with an uncertain demand of services and survivability constraints was designed and modeled as a stochastic programming problem. A polynomial algorithm based on the GRASP metaheuristic with a construction phase of a survivable topology and a local search phase based on a key‐path decomposition of the graph and a feasible key‐path replacement was proposed to solve it. The heuristic algorithm was tested for several problem instances, and its solutions were compared with a branch‐and‐cut solver. The heuristic reached good quality solutions for the tested cases.