Elise Miller-Hooks

Publications: Journal 12

“Approximate Procedures for the Probabilistic Traveling Salesperson Problem”

Transportation Research Record 1882, 27-36.
Tang, H. and E. Miller-Hooks (2005)


In this paper, approximate expressions for evaluating a priori PTSP solutions are introduced. The approximate expressions are incorporated in heuristic improvement procedures for the PTSP to provide high quality solutions with significantly reduced computational complexity as compared to identical improvement procedures with exact solution evaluation. The link between this approximation evaluation scheme and a metaheuristic is discussed. Additionally, a progressive approximation extension is provided.

Numerical experiments were conducted to assess the effectiveness of a proposed approximate
evaluation expression and the progressive approximation scheme. Experimental results indicate that improvement procedures incorporated with the approximate evaluation expressions can produce comparable solutions to improvement procedures employing exact solution evaluation with significantly reduced computational complexity.

The results also show that the progressive approximation scheme is able to provide consistently improved solutions with considerably reduced computational effort as compared with that of a similar approach employing exact calculation of expected length.

Elise Miller-Hooks, Ph.D.
Bill & Eleanor Hazel Chair in Infrastructure Engineering

Phone: 703.993.1685
Email: miller@gmu.edu

Office: 4614 Nguyen Engineering Building

Sid and Reva Dewberry Department of Civil, Environmental and Infrastructure Engineering
George Mason University
4400 University Drive, MS 6C1
Fairfax, VA 22030


More Publications

Volgenau School of Engineering
George Mason University