The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	A combined simulated annealing and TABU search strategy to solve network design problem with two classes of users
Author:	Zeng, Qifeng
View Online:	njit-etd1998-032 (xix, 222 pages ~ 13.1 MB pdf)
Department:	Executive Committee for the Interdisciplinary Program in Transportation
Degree:	Doctor of Philosophy
Program:	Transportation
Document Type:	Dissertation
Advisory Committee:	Mouskos, Kyriacos (Committee chair) Bladikas, Athanassios K. (Committee member) Oppenheim, Norbert (Committee member) Pignataro, Louis J. (Committee member) Spasovic, Lazar (Committee member)
Date:	1998-05
Keywords:	Transportation --Planning. Highway planning. Network analysis (Planning). Heuristic programming.
Availability:	Unrestricted
Abstract:	A methodology to solve a transportation network design problem (TCNDP) with two classes of users (passenger cars and trucks) is developed. Given an existing highway system, with a capital investment budget constraint, the methodology selects the best links to be expanded by an extra lane by considering one of three types of traffic operations: exclusive for passenger cars, exclusive for trucks, and for both passenger cars and trucks such that the network total user equilibrium (UE) travel time is minimized. The problem is formulated as an NP-hard combinatorial nonlinear integer programming problem. The classical branch and bound methodology for the integer programming problem is very inefficient in solving this computationally hard problem. A combined simulated annealing and tabu search strategy (SA-TABU), was developed which is shown to perform in a robust and efficient manner in solving five networks ranging from 36 to 332 links. A comprehensive heuristic evaluation function (HEF), a core for the heuristic search strategy, was developed which can be adjusted to the characteristics of the problem and the search strategy used. It is composed of three elements: the link volume to capacity ratio, the historical contribution of the link to the objective function, and a random variable which resembles the error term of the HEF. The principal characteristics of the SA-TABU are the following: HEF, Markov chain length, “temperature” dropping rate and the tabu list length. Sensitivity analysis was conducted in identifying the best parameter values of the main components of the SA-TABU. Sufficiently “good” solutions were found in all the problems within a rather short computational time. The solution results suggest that in most of the scenarios, the shared lane option, passenger cars and trucks, was found to be the most favored selection. Expanding approximately 10% of the links, results in a very high percentage improvement ranging from 73% to 97% for the five test networks.