Optimization in Electrified and Demand-Aware Transportation System - Routing and Relocation on Urban Networks -
전기화 및 수요를 고려한 교통 시스템 최적화 - 도시 네트워크에서의 라우팅 및 재배치 -
- 주제(키워드) Electric Vehicle , Battery Recuperation , Traveling Salesman Problem , Ambulance Relocation Problem , Integer Programming
- 발행기관 고려대학교 대학원
- 지도교수 정태수
- 발행년도 2024
- 학위수여년월 2024. 2
- 학위명 박사
- 학과 대학원 산업경영공학과
- 세부전공 산업경영공학전공
- 원문페이지 90 p
- 실제URI http://www.dcollection.net/handler/korea/000000279387
- UCI I804:11009-000000279387
- DOI 10.23186/korea.000000279387.11009.0000389
- 본문언어 영어
초록/요약
In this dissertation, the methodologies for solving the electric vehicle routing optimization and ambulance relocation problems are presented. In the electric vehicle routing problem, battery recuperation and swapping station visits are considered. In the presence of cost graph and energy graph, a methodology is presented to explore the feasible routes that minimize the cost. In this study, a mathematical modeling based on dynamic programming is presented, and a heuristic algorithm based on exploratory search and splitting algorithm is proposed for efficient solution finding. The solutions between the two methodologies are compared, and managerial insights based on the altitude distribution of nodes are presented through a case study. In transportation, the location of related infrastructure is very important, especially for ambulances that serve the public, it is more efficient to relocate them according to the demand and traffic patterns than to dispatch them from a fixed area. In this dissertation, a methodology for solving the multi-period ambulance relocation problem is presented as the second problem. A method for generating a graph suitable for relocation based on historical ambulance call data is presented, and a mathematical model based on the integer programming method is presented.
more초록/요약
이 논문에서는 전기자동차 라우팅 및 구급차 재배치 문제를 해결하기 위한 방법론을 제시합니다. 전기자동차 라우팅 최적화 문제에서는 배터리 회복과 교환소 방문을 고려합니다. 비용 그래프와 에너지 그래프가 존재하는 경우, 비용을 최소화하는 실현 가능한 경로를 탐색하는 방법론을 제시합니다. 본 연구에서는 동적 프로그래밍 기반의 수학적 모델링을 제시하고, 효율적인 해법 탐색을 위해 탐색 탐색 및 분할 알고리즘 기반의 휴리스틱 알고리즘을 제안합니다. 두 방법론 간의 해법을 비교하고, 케이스 스터디를 통해 노드의 고도 분포에 따른 인사이트를 제시합니다. 교통 분야에서는 관련 인프라의 위치가 매우 중요한데, 특히 대민 서비스를 제공하는 구급차의 경우 고정된 지역에서 출동하는 것보다 수요와 교통 패턴에 따라 재배치하는 것이 더 효율적입니다. 본 논문에서는 두 번째 문제로 다기간 구급차 재배치 문제를 해결하기 위한 방법론을 제시합니다. 과거 구급차 출동 데이터를 기반으로 재배치에 적합한 그래프를 생성하는 방법을 제시하고, 정수 프로그래밍 방식에 기반한 수학적 모델을 제시합니다.
more목차
1 Introduction 1
2 Electric Vehicle Traveling Salesman Problem with Battery Swapping Technology under the Consideration of Battery Recuperation 4
2.1 Introduction 4
2.2 Literature review 6
2.3 MODEL 11
2.3.1 Problem description 11
2.3.2 Illustrative Example 13
2.3.3 Formulation 15
2.4 Heuristic method 18
2.4.1 Preprocessing and initialization 19
2.4.2 Master problme: Tabu search 21
2.4.3 Subproblem 23
2.5 Computational experimetns 28
2.5.1 Benchmark instances 29
2.5.2 Parameter tuning 29
2.5.3 Computational results 30
2.5.4 Case study 34
2.6 Summary 38
3 Optimizing Ambulance Allocation in Dynamic Urban Environments: A Historic Data-Driven Approach 39
3.1 Introduction 39
3.2 Literature Review 40
3.3 Problem Description and Mathematical Model 44
3.3.1 Problem Description 44
3.3.2 Notations 45
3.3.3 Mathematical Model 47
3.4 Numerical Experiments 49
3.4.1 Dataset 49
3.4.2 Result 51
3.4.3 Validation of results 55
3.4.4 Insight for multiple solutions 57
3.4.5 Case Study 58
3.5 Summary 60
4 Conclusion 61
Reference 65
