The Stochastic Eulerian Tour Problem

Srimathy Mohan (), Michel Gendreau () and Jean-Marc Rousseau ()
Additional contact information
Srimathy Mohan: School of Global Management and Leadership, Arizona State University, Phoenix, Arizona 85069
Michel Gendreau: Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montréal, Québec, H3C 3J7 Canada
Jean-Marc Rousseau: Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montréal, Québec, H3C 3J7 Canada

Transportation Science, 2008, vol. 42, issue 2, 166-174

Abstract: 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.

Keywords: arc routing; Eulerian tour problem; stochastic demand (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1080.0232 (application/pdf)

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:inm:ortrsc:v:42:y:2008:i:2:p:166-174

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().