Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Failure disjoint paths

In English

Författare

  • W. Ben-Ameur
  • M. Żotkiewicz
  • Michal Pioro

Summary, in English

Given a set of commodities and a network where some arcs can fail while others are reliable,

we first consider the problem of computing a minimum-cost pair of paths not sharing failing

links. If a reliable link belongs to both paths then its cost is counted only once. We show

that this problem can be solved in strongly polynomial time. Second, we consider a routing

problem where each commodity can be split among pairs of failure-disjoint paths. We

present a compact linear formulation of the problem. Also three non-compact formulations

solvable by column generation are introduced. All formulations are numerically compared.

Publiceringsår

2014

Språk

Engelska

Dokumenttyp

Konferensbidrag

Ämne

  • Electrical Engineering, Electronic Engineering, Information Engineering

Nyckelord

  • Shortest paths
  • disjoint paths
  • compact formulations
  • column generation
  • capacitated network design

Conference name

2014 INFORMS Telecommunications Conference

Conference date

2014-03-02 - 2014-03-04

Conference place

Lisbon, Portugal

Status

Published