WeLoveDoctor

여행 이동 경로 최적화

Written by

byun1114

in

지난 번 공주와 서천 여행에서 여행 경로를 최적화하지 못해서 조금 시간이 촉박했다. 그래서 이번 경주 여행은 사전에 경로를 최적화해보고 싶었다. 여행 일정이야 얼마든지 변경되지만 사전에 최적 경로는 설정해 두어도 괜찮으니까 말이다.

시작점(집)과 도착지(숙소)가 정해져 있다. 그리고 중간에는 사전에 골라둔 경유지들이 있다. 그리고 이동 시간을 최소화 할 수 있는 경유지 순서를 정하는 것을 문제로 한다. 이렇게 문제를 정의해두면 이것은 외판원 순회 문제(traveling salesman problem, TSP)와 유사해 진다.

경유지가 3군데라면 3!(=6) 조합을 검토해 보아야 한다. 그러면 다음과 같은 방식이 될 것이다.

시작 – 경유지1 – 경유지2 – 경유지3 – 목적지

국내에서 쉽게 이용할 수 있는 지도 API는 T map, 카카오, 네이버가 있다. 이 중에서 네이버는 설명을 알아볼 수 없으므로 제외한다. 카카오의 경우 두 지점 사이의 이동 시간을 계산해주는 기능은 없다. 그러므로 T map 을 이용하도록 한다.

T map API는 SK open API (https://openapi.sk.com/)를 통해서 키를 발급받을 수 있다. 앱을 만들어서 사용하지 않는다면 개인 사용자가 무료 사용량을 넘기는 것도 쉽지 않을 것이다. 기술 문서가 불친절한 것은 아닌데 웹으로 구현하는 부분은 Javascript를 잘 알지 못하면 매우 진입 장벽이 높다. 그렇기 때문에 여러 부분으로 나누어서 프로그래밍 난이도를 낮추도록 한다.

T map API에서 경유지를 포함하여 이동 시간을 계산할 수는 있다. 그런데 경유지 지정하는 부분에서 손이 좀 많이 간다. 시작 지점과 도착 지점을 이용해서 개별 이동 시간을 구한 후 더하는 방법으로 구현하도록 한다.

여기까지 도달했으면 정말 중요한 것을 확인해야 한다. 바로 여러 지점의 정확한 좌표이다. 보통 유사 검색으로 결과를 제공받는다. 그러면 비슷한 이름 혹은 위치의 여러 결과를 얻게 된다. 비슷한 위치에 있다면 별 문제는 없다. 그런데 비슷한 이름이 서로 다른 지역에 있다면 결과가 매우 어긋나게 되므로 이를 확인해야 한다.

url = 'https://apis.openapi.sk.com/tmap/pois'
params ={
	'version' : 'F00',
	'searchKeyword' : loc,
	'appKey' : key
}
data = requests.get(url, params=params, timeout=10)
response = json.loads(bytes.decode(data.content))

이러면 아래의 같은 결과를 얻을 수 있고, 이 중에서 frontLon과 frontLat이 출입 가능한 장소의 WGS84 좌표이다.

{'id': '693489', 'pkey': '69348901', 'navSeq': '1', 'collectionType': 'poi', 'name': '천주교우곡성지', 'telNo': '054-673-7093', 'frontLat': '36.94561570', 'frontLon': '128.82953881', 'noorLat': '36.94550459', 'noorLon': '128.82928884', 'upperAddrName': '경북', 'middleAddrName': '봉화군', 'lowerAddrName': '봉성면', 'detailAddrName': '우곡리', 'mlClass': '1', 'firstNo': '150', 'secondNo': '1', 'roadName': '', 'firstBuildNo': '', 'secondBuildNo': '', 'radius': '0.0', 'bizName': '', 'upperBizName': '여행/레저', 'middleBizName': '관광명소', 'lowerBizName': '문화유적지', 'detailBizName': '기타', 'rpFlag': '16', 'parkFlag': '1', 'detailInfoFlag': '0', 'desc': '', 'dataKind': '', 'zipCode': '', 'newAddressList': {'newAddress': [{'centerLat': '36.94550459', 'centerLon': '128.82928884', 'frontLat': '36.94561570', 'frontLon': '128.82953881', 'roadName': '', 'bldNo1': '', 'bldNo2': '', 'roadId': '', 'fullAddressRoad': '경북 봉화군 봉성면'}]}, 'evChargers': {'evCharger': []}}

다음에는 시작 지점과 도착 지점을 기준으로 소형 차량의 이동 시간을 구하도록 한다.

url = 'https://apis.openapi.sk.com/tmap/routes'

params ={
	'version' : '1',
	'reqCoordType' : 'WGS84GEO',
	'resCoordType' : 'WGS84GEO',
	'carType' : '1',
	'endX' : endX,
	'endY' : endY,
	'startX' : startX,
	'startY' : startY,
	'appKey' : key,
	'totalValue' : '1'
}

data = requests.get(url, params=params, timeout=10)
response = json.loads(bytes.decode(data.content))

이러면 매우 기~인 결과를 확인할 수 있다. 이 중에서 totalTime이 이동 시간(초)이다. 그리고 LineString 으로 이동 경로를 나타내는 WGS84 좌표를 확인할 수 있다.

{'type': 'FeatureCollection', 'features': [{'type': 'Feature', 'geometry': {'type': 'Point', 'coordinates': [127.12430457889762, 37.38419236522808]}, 'properties': {'totalDistance': 148043, 'totalTime': 7004, 'totalFare': 7300, 'taxiFare': 136620, 'index': 0, 'pointIndex': 0, 'name': '', 'description': '성남대로 을 따라  방면으로 319m 이동', 'nextRoadName': '성남대로', 'turnType': 200, 'pointType': 'S'}}, {'type': 'Feature', 'geometry': {'type': 'LineString', 'coordinates': [[127.12430457889762, 37.38419236522808], [127.12287418116846, 37.38320356529847], [127.12245478304723, 37.3829119249148], [127.1220131688769, 37.38247307898179], [127.12171320239246, 37.38225087713673], [127.12168542776442, 37.38222865699216]]}, 'properties': {'index': 1, 'lineIndex': 0, 'name': '성남대로', 'description': '성남대로, 319m', 'distance': 319, '

개별 경로 이동 시간을 모두 더해서 총 이동 시간을 구하고, 이동 시간이 가장 짧은 경로를 선택해서 전체 이동 시간과 전체 이동 경로를 구하도록 한다.

More posts