Heuristics for the Stochastic Eulerian Tour Problem

Srimathy Mohan, Michel Gendreau and Jean-Marc Rousseau

European Journal of Operational Research, 2010, vol. 203, issue 1, 107-117

Abstract: The Stochastic Eulerian Tour Problem (SETP) seeks the Eulerian tour of minimum expected length on an undirected Eulerian graph, when demand on the arcs that have to be serviced is probabilistic. The SETP is NP-hard and in this paper, we develop three constructive heuristics for this problem. The first two are greedy tour construction heuristics while the third is a sub-tour concatenation heuristic. Our experimental results show that for grid networks, the sub-tour concatenation heuristic performs well when the probability of service of each edge is greater than 0.1. For Euclidean networks, as the number of edges increases, the second heuristic performs the best among the three. Also, the expected length of our overall best solution is lower than the expected length of a random tour by up to 10% on average for grid networks and up to 2% for Euclidean networks.

Keywords: Routing; Arc; routing; Eulerian; Tour; Problem; Stochastic; demand; Heuristics (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00509-8
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:203:y:2010:i:1:p:107-117

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 ().