울산 여행을 계획하면서 여러 지점을 모두 버스로 이동하고 싶었다. 어느 버스를 언제 타고, 어디에서 갈아타야 하는지가 보이지 않았다. 공공데이터포털 API로 한 지점을 지나는 노선을 모아 두면, 각 버스가 어디에서 출발해 어디를 거쳐 그 지점을 지나 어디로 가는지 바로 보면서 일정을 짤 수 있을 것 같았다.
Bus Explorer에서 출발 정류장과 도착 정류장을 고르면 갈아타는 경로를 최대 3개 보여 줍니다.
처음 방식: 상태를 우선순위 큐로
처음에는 “(노선, 정류장 순번)“을 하나의 상태로 보고, 우선순위 큐로 가장 비용이 낮은 상태부터 펼쳐 나가는 다익스트라 방식으로 짰습니다. 환승은 모든 정류장에서 다른 노선으로 옮겨 타는 간선으로 표현했습니다.
문제는 목표를 “정류장 수 최소”로 잡을 때 드러났습니다. 환승 자체에 비용을 매기지 않았더니, 비용이 같은 상태가 폭발적으로 늘었습니다. 환승이 정류장 수 기준으로는 공짜였기 때문입니다. 울산 노선으로 물어보면 0.33초 만에 확장 횟수 상한(20만)에 걸렸고, 그때까지 경로를 하나도 돌려주지 못했습니다.
발상을 바꾼다: 정류장이 아니라 “탑승 횟수”로 나눈다
그래서 탐색을 탑승 횟수별 라운드로 나눴습니다. k번째 라운드에는 정확히 k번 탔을 때 각 정류장에 닿는 가장 싼 방법을 담습니다.
라운드 1: 출발지에서 한 번 타서 갈 수 있는 모든 정류장
라운드 2: 그 정류장들에서 한 번 더 타서 갈 수 있는 모든 정류장
라운드 3: ...각 라운드에서는 후보 노선을 딱 한 번씩 훑습니다. 노선을 타고 가면서 지나는 정류장마다 “이 정류장에 더 싸게 도착하는가”를 확인할 뿐입니다. 비용은 정류장이 아니라 (라운드 수 × 노선의 정류장 수)에 비례합니다(O(라운드 × 노선의 정류장 총수)). 환승이 몇 번이든 라운드 수는 최대 환승 횟수 + 1로 묶입니다.
# 라운드 k: 한 번 더 타서 닿는 곳
for round_index in range(1, budget + 1):
scan = {} # 이번 라운드에 살펴볼 노선과 시작 위치
for node in marked: # 지난 라운드에서 새로 닿은 정류장
for route_id, index in self.by_stop.get(node, ()):
scan[route_id] = min(scan.get(route_id, INF), index)
for route_id, start in scan.items(): # 노선마다 한 번씩만 훑는다
# 노선을 따라가며 각 정류장의 도착 비용을 갱신
...이 방식에는 덤이 있습니다. 라운드 k의 결과는 “환승 k−1번으로 갈 수 있는 최선”이므로, 라운드들의 결과가 그대로 (환승 횟수, 비용) 두 축의 파레토 프런티어가 됩니다. “환승은 적게, 정류장은 적게”처럼 서로 다투는 기준의 후보를 한 번에 얻습니다.
한국 버스에서 걸리는 것: 길 건너편은 다른 정류장
라운드 탐색으로 바꾸고 나서도 못 찾는 경로가 있었습니다. 울산은 길 반대편 정류장이 별개의 node_id로 등록되어 있습니다. 반대편으로 걸어서 건너가야만 탈 수 있는 노선은 탐색에서 아예 닿지 못했습니다. 정류장의 88%가 100m 안에 id가 다른 이웃 정류장을 가지고 있었습니다.
그래서 각 라운드가 끝날 때마다 걷기를 추가합니다.
WALK_RADIUS_M = 150.0 # 이 안의 정류장끼리만 걸어서 연결
WALK_NEIGHBOURS = 6 # 가장 가까운 여섯 곳까지만걷기에는 세 가지 규칙을 두었습니다.
- 걷기는 탑승으로 세지 않는다. 걸어도 환승 횟수가 늘지 않습니다.
- 걷기는 연달아 이어지지 않는다. 이번 라운드에 탈 것으로 닿은 정류장에서만 한 번 걷습니다. “걷고 또 걷고”로 도시를 가로지르는 경로가 나오지 않게 합니다.
- 걷기에는 대가가 있다. 고정 벌점에 거리 항을 더해서, 걷는 것이 충분히 이득일 때만 선택됩니다.
# 걷기 비용 = 고정 벌점 + 거리 항
def _walk_cost(meters, optimize):
if optimize == 'distance':
return WALK_PENALTY_M + WALK_DISTANCE_FACTOR * meters # 250m + 1.5 × 걸은 거리
return WALK_PENALTY_HOPS + meters / WALK_METERS_PER_HOP # 정류장 1개 + 거리 / 150m이웃 정류장을 찾는 것도 작은 최적화가 필요했습니다. 모든 정류장 쌍을 비교하는 대신 거친 격자로 나누어 같은 칸과 주변 칸만 비교합니다.
후보를 어떻게 고르나
찾은 경로가 많아도 화면에는 최대 3개만 보여 줍니다. 무엇을 남길지에 규칙이 있습니다(_shortlist).
- 환승 횟수마다 하나씩 먼저 내놓고, 그다음에 차선책을 채웁니다. 직통 하나만 3개 나열하지 않습니다.
- 모든 면에서 더 나쁜 경로는 버립니다. 정류장 수, 환승, 거리, 걷는 거리 중 어느 것에서도 나을 것이 없는 후보입니다.
- 터무니없이 돌아가는 경로는 버립니다. 가장 짧은 경로보다 2.5배 넘게(또는 2km 넘게, 둘 중 더 넉넉한 기준으로) 타고 가는 경로는 환승이 적더라도 순환 노선이 만든 착시로 봅니다.
- 걷기만 하는 경로는 버스 경로와 비교하지 않습니다. 걸어갈 수 있는 거리라면 걷기 경로가 모든 항목에서 이겨 버스 후보를 전부 가려 버리기 때문입니다.
경유 정류장을 지정하면 구간별로 따로 탐색한 뒤 이어 붙입니다. 경유지에서 같은 차에 그대로 머무는 경우는 환승으로 세지 않습니다.
결과
무작위 정류장 300쌍을 환승 최대 3회로 재 보았습니다.
| 못 찾은 경우 | 중앙값(경로의 정류장 수) | 걸린 시간 | |
|---|---|---|---|
| 걷기 도입 전 | 49 / 300 | 29 | 12ms |
| 걷기 도입 후 | 0 / 300 | 20 | 18ms |
걷기를 넣자 못 찾던 49쌍이 모두 풀렸고, 경로도 더 짧아졌습니다(정류장 29개 → 20개). 시간은 12ms에서 18ms로 조금 늘었습니다. 무작위 네트워크 400개에서 전수 탐색과 맞춰 보았을 때 최소 정류장 수는 같았고, 걷기를 켜도 구간이 끊기지 않았습니다.
테스트에는 이런 사례가 들어 있습니다. 가로 노선 60개와 세로 노선 40개로 된 격자망에서 5초 안에 끝나는지, 길 건너편으로 걸어야만 탈 수 있는 노선이 열리는지, 걷기가 연달아 이어지지 않는지, 걸을 수 있는 쌍에도 버스 경로가 함께 나오는지를 하나씩 확인합니다.
시간표와 실제 보행 경로는 별도
이 탐색은 시간표를 모릅니다. 비용은 정류장 수, 추정 거리, 환승 횟수뿐이고, 배차 간격이나 실제 소요 시간은 들어 있지 않습니다. 소요 시간은 따로 추정합니다.
걷는 거리는 직선거리입니다. 횡단보도나 육교 위치는 모릅니다. 환승으로 인정하는 걷기도 150m 안, 가까운 여섯 곳까지라 그보다 먼 갈아타기는 찾지 못합니다.