[카이스트 명강으로 읽는 과학] 교통 체증의 비밀, 네트워크에 있다

카이스트 명강으로 읽는 과학

KAIST 명강 1. 『구글 신은 모든 것을 알고 있다』

교통 체증의 비밀, 네트워크에 있다

아침저녁 교통 체증 때문에 엄청 짜증나시죠? 특히 설날, 추석 같은 대명절의 꽉 막힌 도로들을 생각하면 벌써부터 스트레스가 쌓이는 기분이 듭니다. 이 성가신 교통 체증을 해결하기 위해, 많은 사람들이 이 문제에 달려들고 있는데요. 알고 보면 교통 체증은 교통 네트워크 위에서 움직이는 자동차들의 동역학 문제입니다.

간단한 게임으로 알아볼까요?

위의 그림을 여러분의 출근길이라고 생각해 보죠. 왼쪽이 여러분의 집이고 오른쪽은 직장입니다. 출근을 하는데, 두 가지 선택지가 있습니다.

위의 넓은 길은 고속도로입니다. 대신 좀 돌아서 가야 해요. 그리고 아래에는 짧은 대신에 무척 좁은 지름길이 하나 있습니다.

고속도로에는 차가 1대 지나가면 10분이 걸립니다. 2대가 가도 10분이 걸립니다. 3대도, 4대도 10분입니다. 고속도로라서 아주 넓기 때문에 많은 차들을 동시에 수용할 수 있는 거죠. 그 대신 돌아서 가기 때문에 언제나 10분이 소요됩니다.

하지만 지름길은 상황이 좀 달라요. 여기는 1대가 가면 1분이 걸립니다. 대신 2대가 가면 2분이 걸립니다. 3대가 가면 차가 더 막히기 때문에 3분이 걸리고, x대가 가면 x분이 걸립니다. 좁은 길이기 때문에 차가 몰릴수록 정체돼서 오래 걸리죠.

만약 이런 상황이라면 아침에 출근할 때 어떻게 이동하면 좋을까요?

10대 모두가 지름길로 가면 차가 몰려서 오래 걸릴 겁니다. 그렇다면 시차를 두어서 갈까요? 아니죠. 출근 시간은 똑같잖아요. 9시 전에는 도착해야 하거든요.

수식을 써서 푼다면 2차식으로 정리되어, 시간이 가장 적게 걸리는 최솟값이 나옵니다. 정답은 x=5입니다. 5명은 위의 길로, 5명은 아래의 길로 가야 한다는 거죠. 그러면 위로 가는 사람은 고속도로니까 10분씩 걸립니다. 아래로 가는 사람은 5명이므로 각 5분씩 걸립니다. 그래서 10분이 걸리는 사람 5명과, 5분이 걸리는 사람 5명을 합치면, 총 75분이 걸린 거죠.

이것이 수학적으로 제일 좋은, 소위 말하는 절대적 최적화 답입니다.

그런데 저런 방식이 실제로 먹힐까요? 안 먹힙니다. 5대/5대로 나눠 이동하는 것이 모두에게 제일 좋은 답이라고는 하지만, 개인에게는 그렇지 않거든요. 고속도로로 가는 사람은 지름길로 옮겨 갈 수밖에 없습니다. 10분이나 걸리던 출근길에서 4분이나 줄어드니까 무조건 가야 합니다. 그런데 한 사람이 가잖아요? 그러면 다른 사람도 눈치를 챕니다. 머릿속으로 시뮬레이션해 보니까 내가 지름길로 가면 이제 차량이 총 7대가 되거든요. 그러니까 7분이 걸린단 이야기죠. 고속도로에 있었을 때는 10분이었는데 3분이 이익입니다. 당연히 가야죠. 이제 탄력을 받습니다.

원래 지름길로 5분 만에 가던 5명은 불만이겠지만, 처음에 어떻게 각기 5대를 배정하느냐 하는 문제를 생각해 보면, 누구나 지름길로 가는 이 상황은 모두의 불만을 잠재울 답이 됩니다. 그런데 따져 보면 10명이 각각 10분씩 걸리면 총 소요 시간은 100분입니다. 한 사람당 10분씩이에요. 아까 틀림없이 더 빠른 7.5분짜리 답이 있었거든요. 그런데도 이런 일을 막을 수가 없는 겁니다.

여기서 7.5분씩 걸리는 첫 번째 답안이 수학적인 최적화, 절대적 최적화이고, 모두 지름길로 몰려서 10분씩 걸리게 되는 내시 평형에 따른 답안이 상대적 최적화입니다. 개인들은 자신의 이익을 극대화할 수밖에 없기에 어쩔 수 없이 발생하는 상황인 셈이죠.

결국 평균 7.5분이면 갈 수 있는 거리를 가는데 10분이 걸리는 교통 체증이 일어날 수밖에 없습니다. 이걸 통제가 없는 무질서의 대가라고 볼 수 있는 PoA(Price of Anarchy)*로 계산해 보면 1.33(10분/7.5분)쯤 됩니다. 33퍼센트의 비용이 낭비되는 거죠. 1로 막을 수 있는 것을 0.33만큼 더 쓰고, 75달러로 막을 수 있는 것을 100달러를 내고 다니는 겁니다. 이것이 바로 무질서의 대가입니다.

* PoA(Price of Anarchy): 무정부 상태, 통제가 없는 무질서의 상태에서의 대가라고 생각하면 됩니다. 예를 들어 청바지를 살 때 6분에 33달러를 들이는 게 (수학적으로는) 가장 효율이 높은데 그걸 따르지 않음으로써 낭비되는 시간과 비용이 있는 것입니다. PoA가 1보다 크면 클수록 낭비되는 것이 많고 효율이 나쁜 것입니다.

2편. 도로를 막아야 교통흐름이 나아진다고? [보러가기]

내용 출처: 『구글 신은 모든 것을 알고 있다』, 정하웅 교수님 편

---

정하웅 카이스트 물리학과 교수

서울대학교 물리학과를 졸업하고 동 대학원에서 박사 학위를 받았다. 미국 노터데임 대학교 연구 교수를 거쳐 KAIST 물리학과에서 지정 석좌 교수로 재직 중이다. 복잡계 네트워크라는 새로운 분야를 개척하여 현재 사회학, 경제학, 인터넷 등의 다양한 분야를 넘나들며 네트워크 과학의 발전을 이끌고 있다. 2009년 KAIST 우수 강의 대상, 2010년 이달의 과학 기술자상을 수상했다.

---

단 하나의 명품 과학 강연!

우리가 반드시 알아야할 최신 과학 이슈를

카이스트 명강으로 만나보세요.

『구글 신은 모든 것을 알고 있다』 [도서정보]

『1.4킬로그램의 우주, 뇌』 [도서정보]

『세상 모든 비밀을 푸는 수학』 [도서정보]