A Data-Driven Framework for Bus Stop Placement and Route Generation Using Taxi OD Data : A Case Study of the Daegu Medical R＆D District = A Data-Driven Framework for Bus Stop Placement and Route Generation Using Taxi OD Data: A Case Study of the Daegu Medical R＆D District

다국어 초록 (Multilingual Abstract)

Planning public transit in newly developing urban districts is challenging because conventional methods require origin-destination demand matrices that do not exist where existing service does not yet capture local demand. This thesis develops a methodology that infers spatial demand structure from publicly available taxi trip records and translates it into bus stop locations and a route. Unlike conventional transit planning methods, the approach requires neither prior demand volumes nor predefined candidate stop sites. The approach has two phases. In Phase 1, taxi origin-destination points are spatially filtered and clustered using HDBSCAN （Hierarchical Density-Based Spatial Clustering of Applications with Noise）, which identifies stable demand concentrations at varying densities while explicitly filtering noise, addressing the unknown cluster count, heterogeneous density, and data quality challenges inherent in mobility data. A two-stage clustering design applies fine-grained parameters for intra-district stop placement and coarser parameters for transfer point identification. In Phase 2, cluster centroids are projected onto the road network and connected via the Christofides-Serdyukov algorithm, which provides a 3/2-approximation guarantee for the undirected metric TSP relaxation; the final loop is then reconciled against directed road constraints and reported empirically for feasible length and cycle time. Applied to the Daegu Medical R＆D District （1.19 km² study-area polygon）, a transit-underserved development area in South Korea with only one existing bus route covering 33% of identified demand clusters. From 454,563 taxi records, 701 in-zone demand points are extracted and clustered into 15 stops with a 95.3% clustering rate. The resulting 6.67 km loop route achieves complete cluster coverage, reduces the area-weighted average walking distance from 238 m （existing service） to 135 m, and executes in under 30 seconds on a standard workstation. Parameter sensitivity tests show a stable region （ε ∈ [0.03, 0.05], k ∈ [3, 4]）, bootstrap resampling stability （12.7 ± 0.9 clusters with 35 m mean stop displacement under 20% data removal）, and noise injection resilience （cluster structure preserved at 20% random noise）. Comparison against k-means, DBSCAN, and uniform grid baselines confirms HDBSCAN's unique combination of automatic cluster determination, noise rejection, and density- adaptive placement. The result is a reproducible, end-to-end pipeline for transit planning in data- scarce environments, positioning density-based clustering as a demand structure inference stage that precedes formal facility location optimization.

목차 (Table of Contents)

• 1. Introduction 1
• 1.1 Background 1
• 1.2 Problem Statement 2
• 1.3 Research Objectives 3
• 1.4 Contributions 5
• 1.5 Thesis Organization 5
• 2. Literature Review 7
• 2.1 Transit Network Planning 7
• 2.2 Mobility Data for Transit Demand Analysis 9
• 2.2.1 Smart Card Data 10
• 2.2.2 Mobile Phone and GPS Data 11
• 2.2.3 Taxi OD Data as Transit Demand Proxy 11
• 2.3 Density-Based Spatial Clustering 12
• 2.3.1 DBSCAN 12
• 2.3.2 OPTICS 13
• 2.3.3 HDBSCAN 14
• 2.4 Route Optimization and the Travelling Salesman Problem 15
• 2.4.1 Exact and Heuristic Methods 16
• 2.4.2 Christofides-Serdyukov Algorithm 16
• 2.4.3 Network-Constrained TSP 17
• 2.5 Integrated Approaches and Research Gap 17
• 3. Research Design 20
• 3.1 Framework Overview 21
• 3.2 Phase 1: Demand Analysis via Density-Based Spatial Clustering . 22
• 3.2.1 Data Preparation 22
• 3.2.2 HDBSCAN Clustering 22
• 3.2.3 Cluster Representative Point Determination 25
• 3.2.4 Physical Feasibility Adjustment 26
• 3.3 Phase 2: Network-Constrained Route Construction 27
• 3.3.1 Road Network Graph Construction 28
• 3.3.2 Point of Interest (POI) Graph Extraction 28
• 3.3.3 Christofides-Serdyukov Algorithm for TSP Approximation 29
• 3.3.4 Directed Graph Feasibility Reconciliation 29
• 3.4 Transfer Point Integration 31
• 3.5 Computational Complexity and Implementation 31
• 3.6 Study Area Description 32
• 3.7 Data Sources 34
• 3.7.1 Taxi OD Data 34
• 3.7.2 Road Network Data 35
• 3.7.3 Existing Transit Network 35
• 3.8 Parameter Configuration 36
• 3.9 Computational Environment 37
• 4. Results and Analysis 38
• 4.1 Clustering Results 38
• 4.1.1 Cluster Identification 38
• 4.1.2 Cluster Spatial Distribution 40
• 4.1.3 Noise Analysis 41
• 4.2 Route Construction Results 41
• 4.2.1 Graph Construction 41
• 4.2.2 Christofides-Serdyukov Algorithm Output 42
• 4.2.3 Directed Graph Reconciliation 42
• 4.3 Service Improvement Assessment 46
• 4.3.1 Cluster Coverage Comparison 46
• 4.3.2 Spatial Coverage Analysis 47
• 4.3.3 Transit Network Connectivity 48
• 4.4 Parameter Sensitivity Analysis 48
• 4.5 Comparison with Alternative Stop Placement Methods 52
• 4.6 Discussion of Results 53
• 4.6.1 Advantages of HDBSCAN over K-means 53
• 4.6.2 Road-Network vs. Euclidean Distance 54
• 4.6.3 Directed Graph Reconciliation Effectiveness 54
• 4.6.4 Loop Route Configuration 54
• 4.6.5 Dominant Cluster and Service Design Implications 55
• 5. Discussion and Conclusion 56
• 5.1 Summary of Findings 56
• 5.2 Methodological Strengths 56
• 5.3 Comparison with Related Work 58
• 5.4 Limitations 59
• 5.5 Practical Implications 61
• 5.6 Research Contributions 63
• 5.7 Future Work 63
• REFERENCES 66