Robust constrained shortest path problems under budgeted uncertainty. Issue 2 (19th May 2015)

• Record Type: Journal Article
• Authors: Alves Pessoa, Artur; Di Puglia Pugliese, Luigi; Guerriero, Francesca; Poss, Michael
• Is Part Of: Networks. Volume 66:Issue 2(2015:Sep.)
• Page Start: 98
• Page End: 111
• Publication Date: 2015-05-19
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21615
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2d2mmqwn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:00283045:media:net21615:net21615-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">N</mml:mi><mml:mi mathvariant="script">P</mml:mi><mml:mo>‐</mml:mo><mml:mtext>hard</mml:mtext></mml:math></alternatives></inline-formula> in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the problem with capacity constraints can be solved in pseudopolynomial time. However, we prove that the problem with time windows is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2d2mmqv3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:00283045:media:net21615:net21615-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">N</mml:mi><mml:mi mathvariant="script">P</mml:mi><mml:mo>‐</mml:mo><mml:mtext>hard</mml:mtext></mml:math></alternatives></inline-formula> in the strong sense when <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2d2mmqtj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:00283045:media:net21615:net21615-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">N</mml:mi><mml:mi mathvariant="script">P</mml:mi></mml:math></alternatives></inline-formula> is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudopolynomial when <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2d2mmqs0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:00283045:media:net21615:net21615-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">N</mml:mi><mml:mi mathvariant="script">P</mml:mi></mml:math></alternatives></inline-formula> is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label‐setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 98–111 2015</p> </abstract>