This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Mohan, S. Articles by Rousseau, J.-M.

The Stochastic Eulerian Tour Problem

School of Global Management and Leadership, Arizona State University, Phoenix, Arizona 85069
Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montréal, Québec, H3C 3J7 Canada
Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montréal, Québec, H3C 3J7 Canada
srimathy{at}asu.edu
michelg{at}cirrelt.ca
jmr{at}videotron.ca

This paper defines the stochastic Eulerian tour problem (SETP) and investigates several characteristics of this problem. Given an undirected Eulerian graph G = (V, E), a subset R (|R| = n) of the edges in E that require service, and a probability distribution for the number of edges in R that have to be visited in any given instance of the graph, the SETP seeks an a priori Eulerian tour of minimum expected length. We derive a closed-form expression for the expected length of a given Eulerian tour when the number of required edges that have to be visited follows a binomial distribution. We also show that the SETP is NP-hard, even though the deterministic counterpart is solvable in polynomial time. We derive further properties and a worst-case ratio of the deviation of the expected length of a random Eulerian tour from the expected length of the optimal tour. Finally, we present some of the desirable properties in a good a priori tour using illustrative examples.

Key Words: arc routing; Eulerian tour problem; stochastic demand
History: Received: January 2007; revised: October 2007; accepted: December 2007.