Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.07.007 Byline: Srimathy Mohan (a), Michel Gendreau (b), Jean-Marc Rousseau (b) Keywords: Routing; Arc routing; Eulerian Tour Problem; Stochastic demand; Heuristics 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. Author Affiliation: (a) Department of Supply Chain Management, W.P. Carey School of Business, MC 2451, Arizona State University, P.O. Box 37100, Phoenix, AZ 85069-7100, USA (b) Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Universite de Montreal, C.P. 6128, Succursale Centre-Ville, Montreal, Canada H3C 3J7 Article History: Received 3 March 2008; Accepted 11 July 2009

A study was conducted to evaluate a parallel route building algorithm. The study considers an application of the algorithm to the vehicle routing and scheduling problem with time windows (VRSPTW). Results show that the parallel approach exhibits much better solutions compared to the sequential approach for pure random and mix random problems. However, the sequential approach outperforms the parallel approach in solving pure clustered problems.

Constraints can be removed or added to constraint programming models without any risk of destroying a certain problem structure on which the solution strategy depends. Such property enhances the resolution of variations in a traveling salesman problem by allowing easy adaptation of a constraint programming (CP) algorithm. Study shows that CP's growing impact in combinatorial optimization can be attributed to its flexible modeling capabilities.