Clustering Algorithms for Transit Network Design

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. The proposed work would approach the TNDP from a stop-based perspective: first seeking to optimally group stops together in metric space leveraging the considerable amount of recent work on clustering algorithms in telecommunications and social networks. In particular, a local search-based k-mediods clustering approximation method will be adapted to solve the problem. The second stage of the problem will seek an optimal sequencing/routing of stops within clusters. A modified Genetic Algorithm (GA) will be employed, which will allow variants on traditional cost minimization, such as equity maximization. The techniques will be demonstrated on a large Connecticut transit network with data from the transit database initiative, t-HUB.

Language

  • English

Project

  • Status: Active
  • Funding: $271150.00
  • Contract Numbers:

    DTRT13-G-UTC31

    UCNR25-35

  • Sponsor Organizations:

    Research and Innovative Technology Administration

    University Transportation Centers Program
    1200 New Jersey Avenue, SE
    Washington, DC  United States  20590
  • Start Date: 20131001
  • Expected Completion Date: 0
  • Actual Completion Date: 20180930
  • Source Data: RiP Project 39343

Subject/Index Terms

Filing Info

  • Accession Number: 01557729
  • Record Type: Research project
  • Source Agency: New England University Transportation Center
  • Contract Numbers: DTRT13-G-UTC31, UCNR25-35
  • Files: UTC, RiP
  • Created Date: Mar 25 2015 1:00AM