Classic OR Problems Applied in Transportation

SE26.1 A Solvable Case of the Rural Postman Problem Shoshana Anily, Michel Gendreau, Gilbert Laporte --- Tel Aviv Univ., Fac. of Mgmt., Campus PO Box 3901, Ramat Aviv, Tel Aviv, , Israel 69978 (anily@taunivm.tau.ac.il)

We propose a polynomial time algorithm for the mixed rural postman¨ problem on a tree structure. This problem has applications in¨ transportation, network maintenance and manufacturing.

SE26.2 Heuristics for the Symmetric Generalized Traveling Salesman Problem Jacques Renaud, Fayez F. Boctor --- Univ. du Quebec, Quebec, Quebec, , Canada G1S 4W2

We present 4 composite heuristics for solving the generalized TSP.¨ Each of the proposed heuristics is composed of a tour construction¨ phase and a solution improvement phase. We provide some performance¨ evaluation measurements based on 36 TSPLIB problems which have been¨ solved to optimality by other researchers.

SE26.3 The Stochastic, Dynamic Resource Allocation Problem Greg Godfrey, Warren B. Powell --- Princeton Univ., CASTLE Lab., Dept. of Civil Eng. & OR, Princeton, NJ 08544 ,

The dynamic resource allocation problem arises in the context of¨ managing large fleets of vehicles over time. We present a stochastic¨ formulation and a new solution algorithm that combines an¨ approximation of the expected recourse function with stochastic¨ gradient information. The new approach is easily applied to very¨ large problems. Numerical results will be presented.