최적의 순찰경로 추천 시스템 및 위험도 모니터링 시스템(순찰 경로 추천 알고리즘 개발)

서울 시 격자의 순위를 기반으로 순찰 경로 추천 알고리즘 및 위험도 산출 알고리즘을 개발하였습니다.

 

 

순찰 경로 추천 알고리즘 개발

  1. 노드 활용 DB 생성

class Node(Base):
    __tablename__ = 'nodes'
    
    id = Column(Integer, primary_key=True)
    lat = Column(Float)
    lon = Column(Float)
    rank = Column(Integer)
    g = Column(Float)
    f = Column(Float)
    parent_id = Column(Integer, ForeignKey('nodes.id'))
    parent = relationship("Node", remote_side=[id], backref="children")

class Neighbor(Base):
    __tablename__ = 'neighbors'
    
    node_id = Column(Integer, ForeignKey('nodes.id'), primary_key=True)
    neighbor_id = Column(Integer, ForeignKey('nodes.id'), primary_key=True)
    node = relationship("Node", foreign_keys=[node_id], backref="neighbor_links")
    neighbor = relationship("Node", foreign_keys=[neighbor_id])

# 테이블 생성
Base.metadata.create_all(engine)

 

서울 시 격자의 위험도 기반 계산을 효율적으로 수행하기 위해, 노드화된 데이터를 적재할 수 있는 DB 테이블을 생성하였습니다.

  2. 노드화 적용

# Handling
import pandas as pd
import requests 
import heapq
import warnings
import time
import dill as pickle
import sys

# Math
from math import radians, cos, sin, asin, sqrt

# Visualize
import matplotlib.pyplot as plt

# Warings
warnings.filterwarnings('ignore')

# Moduel
from selectDatasetFluid import *
from calculateRiskIndex import *
from loadDatabase import *

def load_nodes(df):
    """
    데이터프레임으로부터 그래프를 생성합니다. radius는 이웃을 결정하기 위한 반경(km)입니다.
    """
    node_bowl = []
    
    for index, row in df.iterrows():
        
        # 1.각 격자의 노드 생성 
        # 비용 함수,휴리스틱 디폴트 값 설정        
        node_dict={'ID':row['ID'],'LAT':row['LAT'],'LON':row['LON'],'RANK':row['RANK'],'G':sys.maxsize, 'F':sys.maxsize}
        node_bowl.append(node_dict)
        
    node = pd.DataFrame(node_bowl)
    
    #2. 격자 노드 적재
    load_database(node,'nodes')

import pandas as pd
from sklearn.neighbors import KDTree
import numpy as np

def create_graph(df, radius=0.40):
    # 좌표를 radians로 변환 (KDTree는 이를 요구함)
    coords = np.radians(df[['LAT', 'LON']].values)

    # KDTree 생성
    tree = KDTree(coords)

    # 반경 내의 모든 이웃 찾기
    indices = tree.query_radius(coords, r=radius/6371., count_only=False)  # 6371km는 지구의 반경

    # 결과를 저장할 리스트
    neighbor_bowl = []
    
    # 이웃을 데이터프레임으로 변환
    for idx, neighbors in enumerate(indices):
        current_grid = df.iloc[idx]['ID']
        for neighbor in neighbors:
            if idx != neighbor:  # 자기 자신을 제외
                neighbor_dict = {'ID': current_grid, 'NEIGHBOR_ID': df.iloc[neighbor]['ID']}
                neighbor_bowl.append(neighbor_dict)
                
    neighbor_node = pd.DataFrame(neighbor_bowl)

    load_database(neighbor_node,'neighbors')

 

각 격자의 정보(위도, 경도, 점수, 이웃)를 알고리즘을 활용하여 노드 테이블에 적재합니다. 이 데이터는 각 격자의 위치와 위험도 점수, 인접 격자와의 관계를 포함합니다. 노드 데이터를 적재하는 주된 목적은 휴리스틱 알고리즘을 적용하여 최적의 순찰 경로를 추천하기 위함입니다. 이를 통해 순찰 경로의 효율성을 극대화하고, 위험도가 높은 지역을 우선적으로 커버할 수 있도록 합니다.

 

 

  3.  순찰 경로 추천 알고리즘 

# Handling
import pandas as pd
import requests 
import heapq
import warnings
import time
import dill as pickle
import sys

# Math
from math import radians, cos, sin, asin, sqrt

# Visualize
import matplotlib.pyplot as plt

# Warings
warnings.filterwarnings('ignore')

# Moduel
from selectDatasetFluid import *
from calculateRiskIndex import *
from loadDatabase import *


# <span style='background-color:rgba(0,0,255,0.3); color:white; padding: 5px; border-radius:5px;'> 알고리즘 프로세스 </span>
# 
# * 주소 → 위도, 경도 반환 알고리즘 
# * 노드 클래스 생성
# * 격자 이웃 거리 산출 알고리즘 
# * 노드 생성 알고리즘
# * 휴리스틱 산출 함수 
# * 경로 찾기 알고리즘 


def a_star_search(start, goal):
   
    initialize_a_star(start,goal)  # 시작 노드의 g 값을 0으로 초기화
    
    # The open set contains nodes to be evaluated, start with the start node
    open_set = [(start.f, start)]
    heapq.heapify(open_set)  # Transform list into a heap
    
    while open_set:
        # Pop the node with the lowest f score
        current_f, current = heapq.heappop(open_set)

        
        # If the goal has been reached, reconstruct and return the path
        if current == goal:
      
            path = []
            while current:
                path.append((current.lat, current.lon, current.id))
                current = current.parent
            return path[::-1]  # Return reversed path

        # Go through all the neighboring nodes
        for neighbor in current.neighbors:
       
            # The distance from start to a neighbor
            # tentative_g_score = current.g + neighbor.rank / 총 이동비용 
            tentative_g_score = neighbor.rank #현재 격자 이동비용
        
            # If this path to neighbor is better than any previous one, record it
            if tentative_g_score < neighbor.g:
                neighbor.parent = current
                neighbor.g = tentative_g_score
                tentative_g_score_ratio,heuristic_ratio = calculate_by_proportion(tentative_g_score,heuristic(neighbor, goal))
                neighbor.f = (tentative_g_score_ratio*0.25) + (heuristic_ratio*0.75)
                #neighbor.f = tentative_g_score + heuristic(neighbor, goal)
                if neighbor.f not in neighbor_f_bowl:
                    heapq.heappush(open_set, (neighbor.f, neighbor))
                    # 비용함수 추가
                    neighbor_f_bowl.append(neighbor.f)
                
                #heapq.heappush(open_set, (neighbor.f, neighbor))
           
    # 만약 우리가 여기 있다면 목표를 달성하기 위한 길은 없다
    return []

 

 

    A* 검색 알고리즘 분석

A* 알고리즘은 시작 노드에서 목표 노드까지 최적 경로를 찾기 위한 휴리스틱 기반 탐색 알고리즘입니다. 아래는 주어진 A* 검색 알고리즘 코드에 대한 상세한 분석입니다.

함수: a_star_search(start, goal)

목적: 시작 노드에서 목표 노드까지의 최적 경로를 찾습니다.

1. 초기화:
   • initialize_a_star(start, goal): 시작 노드의 g 값을 0으로 초기화합니다.
   • open_set: 평가할 노드들을 포함하는 집합으로, 시작 노드를 포함합니다.
   • heapq.heapify(open_set): open_set을 힙 자료구조로 변환하여 우선순위 큐로 사용합니다.
2. 메인 루프:
   • open_set이 비어있지 않은 동안 반복합니다.
   • heapq.heappop(open_set): f 값이 가장 낮은 노드를 꺼냅니다.
3. 목표 도달 확인:
   • 현재 노드가 목표 노드인 경우 경로를 재구성하고 반환합니다.
   • path: 경로를 저장할 리스트로, 현재 노드부터 부모 노드를 따라가며 경로를 재구성합니다.
   • 최종적으로 역순으로 된 경로를 반환합니다.
4. 이웃 노드 평가:
   • 현재 노드의 모든 이웃 노드를 순회합니다.
   • tentative_g_score: 이웃 노드로의 현재 경로 비용을 계산합니다.
   • 만약 이 경로가 이전 경로보다 더 좋다면, 이웃 노드의 부모 노드를 현재 노드로 설정하고, g 값을 업데이트합니다.
   • calculate_by_proportion(tentative_g_score, heuristic(neighbor, goal)): g 점수와 휴리스틱 점수를 비례 계산하여 새로운 f 값을 구합니다.
   • neighbor.f: 새로 계산된 f 값을 이웃 노드에 할당합니다.
   • heapq.heappush(open_set, (neighbor.f, neighbor)): 이웃 노드를 open_set에 추가하여 다음 평가 대상으로 설정합니다.
5. 경로 없음:
   • open_set이 비어 있고 목표를 찾지 못한 경우 빈 경로를 반환합니다.

요약

이 A* 검색 알고리즘은 시작 지점에서 목표 지점까지의 최적 경로를 효율적으로 탐색합니다. 각 노드는 평가되는 동안 g 값(시작 노드에서 현재 노드까지의 실제 비용)과 휴리스틱 h 값(현재 노드에서 목표 노드까지의 예상 비용)을 사용하여 f 값을 계산합니다. 이 f 값이 가장 낮은 노드를 우선적으로 탐색하여 최적 경로를 찾습니다. 이를 통해 경로의 효율성과 정확성을 높입니다. 

 

A* 알고리즘은 f(n) = 목적지와의 거리 + 위험도 점수로 계산합니다.

위의 알고리즘은 최적의 순찰경로 알고리즘의 일부이며, 전체 코드는 GITHUB에 업로드하겠습니다.

 

 

    4. 알고리즘 적용

관악구 격자

 

 

색이 진할수록 해당 지역의 위험도가 낮음. 빨간 선은 출발지와 도착지를 나타내며, 현재 연한 색 격자를 기준으로 이동하는 것을 확인