d라이브러리

해마다 이맘 때가 되면 우체국 집배원은 눈코 뜰새 없이 바빠진다. 밀려드는 카드와 연하장을 제때에 배달하려면 잠깐이라도 한 눈을 팔 시간이 없기 때문 이다. 카드나 연하장을 부치는 입장에서는 자신의 카드가 정확한 날짜에 원하는 사람에게 배달되기를 바랄 것이다. 하지만 이를 배달해야 하는 입장은 어떨까.

전국 방방곡곡에서 밀려드는 우편물의 양은 그야말로 엄청나다. 특히 연말연시에는 배달해야 할 양이 급격히 늘어나기 때문에 자칫하면 ‘배달 사고’가 일어날 수있다. 그러나 이런 일은 좀처럼 일어나지 않는다. 집배원은 각자에게 할당된 임무를 잘 짜여진 스케줄에 따라 움직임으로써 배달 임무를 무사히 완수한다.

어떻게 이런 일이 가능할까. 단지 집배원 수만 많으면 가능할까.
 

외판원 순회 문제

KAIST 산업공학과 박성수 교수가 이끄는 시스템 최적화 연구실에서는 최적화 이론과 이를 핵심엔진으로 하는 지능형 소프트웨어 연구로 가장 효율적인 집배원 배달 시스템을 개발하고 있다. 좀더 정확히 말하면, 최소의 비용으로 최대의 효과를 얻을 수 있도록 특정 시스템을 설계하고 이를 구현하기 위한 이론적 연구를 수행하고 있다.

집배원 배달 시스템의 예를 통해 시스템 최적화에 대해 알아보자. 집배원 K씨는 오늘 10군데를 들러 배달 업무를 수행하고 다시 우체국으로 돌아오는 임무를 맡았다. 우체국을 나선 K씨는 가장 가까운 곳부터들렀다. 그런데 K씨가 선택한 길이 시간과 거리에서 가장 효율적인 것이었을까

이같은 문제를 수학에서는 ‘외판원 순회 문제’라고 한다. 말 그대로 여러 도시를 모두 방문하는 가장 짧은 길을 찾는 문제다. 얼른 생각하기에는 쉬워 보이지만 K씨와 마찬가지로 들러야 할 도시의 수가 10개만 되도 10!(3백62만8천8백)의 경우의 수를 모두 계산해야 하는 매우 복잡한 문제다. 이 때문에 수학의 대표적 난제로 꼽히고 있다. 1천5백 도시를 여행하는 모든 경우의 수를 계산해 최소거리를 구하려면 현재 세계 최고 수준의 컴퓨터를 병렬로 연결해 계산한다고 해도 22년 7개월이 걸린다. 이것이 지난해 독일에서 열린 수학학회에 보고된 현재 최고의 기록이다.

이 때문에 전세계 많은 과학자들이 외판원 순회 문제를 빨리 풀 수 있는 알고리듬을 개발하는데 몰두하고 있다. 하지만 이 문제는 순수한 수학 분야뿐 아니라 시스템 최적화 분야에서도 매우 중요하다. 특정 시스템을 설계할 때 복잡한 경로 문제를 해결하는 기본 도구가 되기 때문이다. 그런데 시스템 최적화 분야에 서는 외판원 순회 문제를 약간 다르게 접근한다.

수학에서는 경로를 지정하는 정확한 해를 찾아야 하고 계속해서 들러야하는 도시의 수를 늘려간다. 하지만 최적화 분야에서는 해의 근사치만 구해도 현실에서 충분히 의미를 가질 수 있고, 또한 경로의 수가 특별한 경우를 제외하고는 그렇게 많지 않다.

쉽게 말해 시스템 최적화 분야에서는 외판원 순회 문제가 해결 불가능하지는 않다는 것이다. 이는 이 분야의 탄생과 관련된 태생적 특성이기도 하다. 시스템 최적화 분야는 2차 세계대전 중 연합군이 독일의 공습에 맞서기 위해 방공망을 구축하면서부터 생겨났다.

어떻게 하면 최소의 방공기지로 독일 폭격기를 막아 낼 수 있을까를 해결하기 위해 시작된 것이다.

2차 세계대전이 끝나면서 시스템 최적화 분야는 산업적 응용을 찾기 시작했다. 오늘날에 와서는 굴뚝산업의 저효율성 문제 해결은 물론, e-비지니스 산업에서 디지털 정보의 획득과 저장, 가공, 유통 분야까지를 다루고 있어 전 산업분야에서 없어서는 안될 필수 도구로 자리잡았다.
 

시스템 건강 돌보는 산업계의 명의

집배원의 최적 경로를 찾으면 배달 시스템이 완성 되는 것일까. 그렇지 않다. 배달 시스템에는 배달원의 경로뿐 아니라 배달지의 지리적 위치와 배달 차량의 종류, 우편 분류 시스템, 그리고 우체국의 수 등 여러 요소들이 함께 섞여 있다. 효율적인 배달 시스템을 구축하기 위해서는 이 모든 요소를 한꺼번에 고려해야 한다. 우편 집중국은 전국적으로 어디에 두며, 집중국 아래 속하는 우체국은 몇개 정도로 유지하고, 집배원을 몇명 고용했을 때 시스템 전체가 최대의 효과를 얻을 수 있나 등 시스템을 하나의 유기체로 보고 이것이‘건강’할 수 있도록 모든 요소를 고려하는 것이다. 산업공학계의‘명의’가 바로 시스템 최적화 연구실의 최대 목표다.

연구실은 1990년대 이후 현재까지‘경영 과학’(Management Science) 등 세계적 학술지에 30여편의 논문을 발표했다. 산업공학 분야는 산학협동연구를 진행하는 경우가 많기 때문에 연구 주제가 응용분야로 치우치기 쉽다. 이런 점을 고려할 때 연구실의 업적은 의의가 크다. 박교수는“현재 국내의 최적화 분야는 주로 응용소프트웨어 개발에 치중하는 편이지만, 연구실은 이를 개발하기 위한 이론적 작업을 강조하고 있다”고 말한다. 이론적 발전이 있어야 좀더 훌륭한 소프트웨어가 계속해서 개발될 수 있다고 믿기 때문이다.

연구실에서는 우편물 배달 시스템 이외에도 KT와 함께 국내 광통신 네트워크 최적 설계, 조선소 등의 제조시스템에서 생산성을 최대화하기 위한 연구 등을 하고 있으며 앞으로 이동단말기, GPS 등과 연계해 실시간으로 수·배송을 최적화할 수 있는 소프트웨어를 개발할 계획이다.

현재 연구실에는 박성수 교수를 중심으로 석사과정 5명과 박사과정 6명이 시스템 최적화 분야의 최고 명의를 꿈꾸며 소프트웨어 개발에 힘쓰고 있다.