A minmax regret version of the time-dependent shortest path problem

Eduardo Conde, Marina Leal and Justo Puerto

European Journal of Operational Research, 2018, vol. 270, issue 3, 968-981

Abstract: We consider a shortest path problem where the arc costs depend on their relative position on the given path and there exist uncertain cost parameters. We study a minmax regret version of the problem under different types of uncertainty of the involved parameters. First, we provide a Mixed Integer Linear Programming (MILP) formulation by using strong duality in the uncertainty interval case. Second, we develop three algorithms based on Benders decomposition for general polyhedral sets of uncertainty. In order to make the algorithms faster we use constant factor approximations to initialize them. Finally, we report some computational experiments for different uncertainty sets in order to compare the behavior of the proposed algorithms.

Keywords: Integer Programming; Minmax-regret models; Benders decomposition (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718303333
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:270:y:2018:i:3:p:968-981

DOI: 10.1016/j.ejor.2018.04.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().