선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
가설 설정
- 대규모 지역은 자전거를 출·퇴근에 이용할 경우, 본실험에서는 여수 도심 주택가에서 여수 국가 산업단지까지 자전거를 타고 이동하고자 할 경우를 가정하여, 이동 거리 및 시간을 기준으로 최단 경로를 선정하였다.
제안 방법
- 안진호 등(2010)은 최단 경로를 고속으로 찾기 위하여 A* 알고리즘과 하드웨어의 구조를 개선하였다. A* 기반의 경로탐색에서 가장 시간이 많이 걸리는 오픈리스트 구조를 우선순위 큐로 구현하여 노드정보 탐색 과 정보처리 기능을 분산처리하는 기술을 제시하였다. 무인자동차 주행 분야에서도 최단 경로 선정 알고리즘이 다양하게 연구되고 있다.
- GIS 네트워크 분석 기법을 이용하여 지형공간에 최적 경로탐색을 적용하여 자전거 경로 선정방법에 대하여 연구한 결과 다음과 같은 결론을 얻을 수 있었다.
- 0을 이용하였다. 네트워크 분석과정에서 일부 알고리즘 처리를 위하여 스크립트 코드를 작성하였다.
- 자전거도로에 대한 GIS 데이터베이스에서 경사도를 계산하고, 경사에 따른 운행 속도, 횡단보도 대기시간을 이용하여 구간별 소요시간을 얻는다. 본 연구에서 구축한 GIS 데이터베이스의 필드는 이동거리, 경사도, 이 동시간, 이동속도 등이다. 그림5는 구간별 경사도 및 이동시간을 나타내는 테이블이다.
- 본 연구에서는 여수시 일대를 10구역으로 나누어 각 구역별 시점과 종점을 지정하여 최적 경로 선정을 하였다. 표 3은 여수시를 권역별로 구분한 것이다.
- 본 연구에서는 여수시와 산업단지 권역을 연구 대상 지역으로 선정하고, GIS 데이터베이스 구축 방법 및 경로 선정 알고리즘을 적용분석하였다. 연구 대상 지역은 주거지역, 상업지역과 학교들이 분포되어 있어 자전거 이용이 많을 것으로 예상되며 출퇴근으로 인한 대중교통과의 연계가 가능한 지역이다.
- 본 연구에서는 자전거 최적 경로 분석을 위하여 대표적으로 사용되는 다익스트라 알고리즘과 A* 알고리즘을 적용하여 비교하고 자전거 최적 경로 선정을 하였다. 연구대상 지역은 여수시 일대로 국토해양부의 “자전거 이용시설의 구조ㆍ 시설기준에 관한 규칙”, “자전거도로시설 기준 및 관리지침”, “도로의 구조ㆍ 시설기준에 관한 규칙”등관련 지침을 파악하고, 자전거도로의 최적 경로 선정을 위해 다익스트라 알고리즘과 A* 알고리즘의 최적 경로 선정 알고리즘을 적용하였다.
- 자전거도로의 최적 경로를 찾기 위한 비용으로 자전거 이동거리와 소요시간을 선정하였다. 비용함수의 주요 인자인 이동거리는 자전거도로의 공간 데이터로부터 추출하였다. 소요시간의 경우 자전거도로공간자료의 노드간경사도를 계산하고, 이에 따른 자전거 이동 속도를 고려하여 이동시간을 계산하였다 (이광원, 2011).
- 소규모 지역은 자전거를 여가에 이용할 경우, 본 실험에서는 여수 무선지역 주택지에서 롯데마트까지 자전거를 타고 가고자 할 경우, 이동거리 및 시간을 기준으로 경로를 찾았다. 출발점은 롯데마트 주변 주택지 485곳이며, 도착점은 롯데마트 4점으로 선정하였다.
- 시간과 거리의 다른 단위를 직접 비교하기 어렵기 때문에 감소율로 전체적인 양상을 분석하였다. 10개 권역의 10개 경우를 볼 때, 이동거리 기준에 의한 거리 감소율보다 이동시간 기준에 의한 시간 감소율이 크게 나타났다.
- 각 노드에 우선순위를 부여하는 휴리스틱을 사용하여 이 알고리즘을 사용하면 최적이 되므로 A* 알고리즘이라고 불린다. 알고리즘의 기본 개념은 조사하지 않은 state들 중 가장 유용한 state을 반복 조사하는 것이고, 목표에 도달하지 않으면 계속 인접 state을 조사한다. A* 알고리즘은 추정 방향으로의 경로탐색으로 전체적인 탐색 횟수가 적고 적은 메모리 사용으로 알고리즘의 수행시간이 단축될 수 있다.
- 최재화 등(1991)은 GIS를 이용하여 최적 경로 선정을 위한 공간자료를 정규형 격자로 생성하고, 각 정규형 격자에 토지이용 현황, 지가, 경사도 등을 고려하여 얻은 가중치를 적용하였다. 이를 GIS의 속성 데이터로 사용하고 세 개의 노선을 선정하여 실제 노선의 선정 과정에서 GIS의 활용 가능성을 제시하였다. 이신준 등(1999)은 노드를 이용해 거리를 계산하고, 방향성을 갖는 깊이우선탐색 방법과 너비우선탐색 방법을 사용하여, 경로탐색 분석 시스템을 구현하였다.
- 연구대상 지역은 여수시 일대로 국토해양부의 “자전거 이용시설의 구조ㆍ 시설기준에 관한 규칙”, “자전거도로시설 기준 및 관리지침”, “도로의 구조ㆍ 시설기준에 관한 규칙”등관련 지침을 파악하고, 자전거도로의 최적 경로 선정을 위해 다익스트라 알고리즘과 A* 알고리즘의 최적 경로 선정 알고리즘을 적용하였다. 자전거도로 네트워크는 경사에 따른 거리와 평균 운행 속도를 계산하고, 절점 및 경계선과 네트워크 모델을 구축하였다. 최적경로 탐색을 이용하여 알고리즘의 선정 경로를 살펴보고, 연산시간을 평가하였다.
- 자전거도로의 네트워크는 수치 지형도로부터 추출된 차도 경계선과 횡단보도 레이어를 이용하여 경계와 정점으로 구축하고, 일정한 정밀도의 거리와 경사를 구하기 위해, 그림 4와 같이 최소 10m에서 최대 20m까지 일정한 구간 거리가 되도록 정점을 추가 또는 삭제하여 구축하였다.
- 자전거도로의 최적 경로를 찾기 위한 비용으로 자전거 이동거리와 소요시간을 선정하였다. 비용함수의 주요 인자인 이동거리는 자전거도로의 공간 데이터로부터 추출하였다.
- 자전거의 평균 이용 속도는 지형의 경사에 따라 다르지만, 표 1과 같이 기존 자료를 참고하여 평지에서의 평균 속도, 오르막 도로에서의 최저 속도와 내리막 도로에서의 최고 속도를 한계 속도로 활용하였다.
- 자전거도로 네트워크는 경사에 따른 거리와 평균 운행 속도를 계산하고, 절점 및 경계선과 네트워크 모델을 구축하였다. 최적경로 탐색을 이용하여 알고리즘의 선정 경로를 살펴보고, 연산시간을 평가하였다. 상세한 실험방법의 연구 흐름은 그림 1과 같다.
대상 데이터
- 경사자료를 구하기 위한 표고값은 항공 LiDAR 데이터를 이용하였다. 자전거도로에 대한 GIS 데이터베이스에서 경사도를 계산하고, 경사에 따른 운행 속도, 횡단보도 대기시간을 이용하여 구간별 소요시간을 얻는다.
- 출발점은 롯데마트 주변 주택지 485곳이며, 도착점은 롯데마트 4점으로 선정하였다. 실험 대상 지역은 도로의 경사가 완만한 지역으로 최단 경로를 선정한 결과 1940개의 노선이 탐색되었고, 탐색된 노선은 그림 8 및 그림 9와 같다. 그림에는 485개의 겹쳐진 노선과 출발점 485점, 도착점 4점이 표현되어 있다.
- 본 연구에서는 여수시와 산업단지 권역을 연구 대상 지역으로 선정하고, GIS 데이터베이스 구축 방법 및 경로 선정 알고리즘을 적용분석하였다. 연구 대상 지역은 주거지역, 상업지역과 학교들이 분포되어 있어 자전거 이용이 많을 것으로 예상되며 출퇴근으로 인한 대중교통과의 연계가 가능한 지역이다.
- 연구대상지역은 여수시 일대로 국토해양부의 “자전거 이용시설의 구조ㆍ시설기준에 관한 규칙”, “자전거도로 시설 기준 및 관리 지침”, “ 도로의 구조ㆍ시설기준에 관한 규칙”등관련지침을 파악하고, 자전거도로의 최적 경로 선정을 위해 다익스트라 알고리즘과 A* 알고리즘의 최적 경로 선정 알고리즘을 적용하였다.
- 소규모 지역은 자전거를 여가에 이용할 경우, 본 실험에서는 여수 무선지역 주택지에서 롯데마트까지 자전거를 타고 가고자 할 경우, 이동거리 및 시간을 기준으로 경로를 찾았다. 출발점은 롯데마트 주변 주택지 485곳이며, 도착점은 롯데마트 4점으로 선정하였다. 실험 대상 지역은 도로의 경사가 완만한 지역으로 최단 경로를 선정한 결과 1940개의 노선이 탐색되었고, 탐색된 노선은 그림 8 및 그림 9와 같다.
이론/모형
- 표 2와 그림 3은 1:1,000수치지형도와 추출된 공간 분석용 레이어, 구축된 공간정보를 나타내고 있다. 공간정보 구축 및 노선 선정은 ArcGIS 10.0을 이용하였다. 네트워크 분석과정에서 일부 알고리즘 처리를 위하여 스크립트 코드를 작성하였다.
성능/효과
- 시간과 거리의 다른 단위를 직접 비교하기 어렵기 때문에 감소율로 전체적인 양상을 분석하였다. 10개 권역의 10개 경우를 볼 때, 이동거리 기준에 의한 거리 감소율보다 이동시간 기준에 의한 시간 감소율이 크게 나타났다.
- A* 알고리즘을 이용하여 최단 거리 기반에 의해 결정된 노선과 최단 시간 기반에 의하여 결정된 노선 간 이동거리의 차이가 1.7%~2.3%인 노선은 전체의 20.57%이고, 이동시간의 차이가 0.1~2.0%인 노선은 전체의 28.41%이었다. 이동거리에 따른 경로 선정 연산은 2분41초가 소요되었고, 이동 시간은3분6초가 소요되었다.
- A* 알고리즘의 최단 시간 노선 선정 결과는 최단거리 선정 결과보다 소요시간 감소율이 5.39%로 가장 크다. 그림 7은 표 4의 결과를 그래프로 표현한 것으로 그래프에서 일정한 경향을 찾기는 어렵다.
- 그러나, 대규모 지역에서 다익스트라 알고리즘의 소요시간은 약 50분의 경과 시간이 걸렸고, A* 알고리즘의 결과는 다익스트라 알고리즘의 절반인 약 27분 정도가 소요됐다. 그리고 이동시간을 기반으로 수행했을 시에도 약 25분이 단축되었다.
- 둘째, 다익스트라와 A* 알고리즘의 자전거 경로 탐색 처리시간이 소규모지역에선 2∼3분대로 비슷한 결과가 나왔다.
- 이동거리에 따른 경로 선정 연산은 2분41초가 소요되었고, 이동 시간은3분6초가 소요되었다. 소규모 지역으로 실험된 대상 지역의 특성, 직각의 단순한 도로망 구조가 반영되어 감소율0인비율이 높고, 시간과거리감소 비율도크지않았다.
- 4%가 단축되었다. 즉 감소율 측면에서, 출발지에서 목적지까지의 경로 선정 기준 선택 시에 최단거리 기준보다 최단 시간 기준으로 경로를 잡을 때 더 효과적일 수 있다는 것이다.
- A* 알고리즘이 다 익스트라 알고리즘에 비해서 수행시간이 감소됨을 알 수 있다. 즉, 대상지역이 소규모이고 자료의 처리양이 적을 경우에는 다익스트라 알고리즘을 사용하는 것이 적절하지만, 대상 지역이 크고 공간 해상도를 증가하여 정밀 분석할 경우 수행시간을 고려하여 A* 알고리즘을 사용하는 것이 대안이 될 수 있음을 보여준다.
- 첫째, 권역별 자전거 노선 선정 결과 다익스트라와 A*알고리즘은 이동거리 감소율이 3.5%, 이동시간 감소율이 3.5∼5.4%가 단축되었다.
- 최단거리 기준에서 다익스트라와 A*의 알고리즘의 경로 선정 결과는 같게 나왔다. 최단 시간 기준의 결과는 최단거리 기준의 결과와 다르게 나타났으며, 수평 인 도로 부분보다 경사지역에서 더 다르게 나타났다.
후속연구
- 본 연구에서는 다익스트라 알고리즘과 A* 알고리즘을 통하여 자전거 경로 선정 방법에 대하여 비교하였으며, 향후 경로 선정 시에 자전거 이용자 의견 수렴, 대중교통과의 연계성을 고려한 추가적인 연구가 이루어져야 할 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.