A GRASP algorithm for a capacitated, fixed charge, multicommodity network flow problem with uncertain demand and survivability constraints

摘要

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.