Heuristics for the stochastic Eulerian tour problem
type: Item
instance of: scholarly article
title: Heuristics for the stochastic Eulerian tour problem
zbMATH Open document ID: 1192.90029
author: Srimathy Mohan
author: Michel Gendreau
author: Jean-Marc Rousseau
published in: European Journal of Operational Research
publication date: 2009-12-07T00:00:00Z
review text: Given an undirected Eulerian graph, a subset of its edges that require a probabilistic service, a designated depot, and a distance between every pair of nodes, the stochastic Eulerian tour problem (SETP) seeks a tour of minimum expected length [\textit{S. Mohan, M. Gendreau} and \textit{J.-M. Rousseau}, ``The stochastic Eulerian tour problem'', Transp. Sci. 42, 166--174 (2008)]. From the authors' summary: ``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.''
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 90B15
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5643704
zbMATH Keywords: arc routing
zbMATH Keywords: Eulerian tour problem
zbMATH Keywords: stochastic demand
zbMATH Keywords: Chinese postman problem
zbMATH Keywords: heuristics
MaRDI profile type: Publication
full work available at URL: j.ejor.2009.07.007
OpenAlex ID: W2061091622
cites work: Matching, Euler tours and the Chinese postman
cites work: New Insertion and Postoptimization Procedures for the Traveling Salesman Problem
cites work: Improvement Procedures for the Undirected Rural Postman Problem
DOI: 10.1016/J.EJOR.2009.07.007
description: scientific article; zbMATH DE number 5643704