United States Department of Transportation
[PDF-1.49 MB]
Details:
-
Creators:
-
Corporate Creators:
-
Corporate Contributors:
-
Subject/TRT Terms:
-
Publication/ Report Number:
-
Resource Type:
-
Geographical Coverage:
-
TRIS Online Accession Number:01701722
-
Edition:Year 25 Final Report
-
Corporate Publisher:
-
Abstract:The transit network design problem (TNDP) dates back over five decades, receiving increasing attention over the past two. Simply put, the TNDP seeks to do two things: 1) Select groups of transit stops that should form routes and 2) Establish a sequence in which those stops should be visited. Because the underlying optimization problems are combinatorial in nature and fall into the class of NP-Hard problems, approximation algorithms are used in any realistically-sized network. Previous attempts to solve the TNDP have taken path-based approaches; working from an initial route set and perturbing, extending or shortening routes in that initial set. This approach remains the standard today, though it’s concepts originated in an era where computational power was limited and prohibitively expensive. A modified Genetic Algorithm (GA) will be employed, which will allow variants on traditional cost minimization, such as equity maximization. This report contains a detailed discussion and validation of the genetic algorithm (GA) used to solve equitable Traveling Salesman Problem (EqTSP). First, each step of the GA will be discussed, focusing on the procedures and algorithmic structures which are unique to this specific algorithm. Then experimental evidence will be provided to validate decisions regarding its algorithmic structure, including the decision to clone winning solutions into the next generation and the use of rogue parents. Finally, a sensitive analysis is conducted on the five input parameters: population size, tournament size, number of rogue parents, mutation rate, and convergence criteria. All of the preliminary experiments and sensitive analysis were conducted on the Sioux Falls network. Once the best algorithmic structure and input parameters were determined, the GA was tested on the Qatar national network.
-
Format:
-
Funding:
-
Collection(s):
-
Main Document Checksum:
-
Download URL:
-
File Type:
