배송 문제 해결하는 집합 덮개 문제
옷가게에서 마음에 드는 옷을 골랐을 때 가장 난감한 순간은 맞는 사이즈가 없을 때다. 마음에 들어도 옷맵시를 보고 사려면 입어 봐야 하기 때문이다. 그런데 XXS나 XS, XXL와 같은 엑스트라 사이즈는 매장에 상품이 없는 경우가 많다. 애초에 많은 양을 생산하지 않아서다.
문제는 해당 사이즈의 옷을 입어 보기 위해서는 무조건 옷을 구매해야 한다는 점이다. 그렇다고 바로 받아 볼 수 있는 것도 아니다. 적게는 하루, 많게는 며칠을 기다려야 한다. 그래서 이 사이즈의 고객들은 사이즈가 있는 매장을 찾아 쇼핑 여행을 떠나기도 한다.
그런데 유통 현장에서 늘 벌어지는 이런 문제를 수학 이론으로 해결할 수가 있다. KAIST 산업 및 시스템공학과 장영재 교수팀은 코오롱스포츠의 의뢰를 받아 수학 이론을 이용한 ‘빅데이터 로지스틱 시스템’을 개발했다. 몇 년 전부터 이 회사는 엑스트라 사이즈의 옷을 입는 고객들이 매장에 옷이 없어 구매에 불편을 겪는 것을 개선하고자 고심해 왔다. 장 교수팀은 이 문제를 해결하기 위해 ‘집합 덮개 문제’라는 수학 이론을 이용했다.
집합 덮개 문제는 조건을 만족하는 다양한 경우 중에서 겹치는 부분을 최대한 제외해, 최소의 경우만으로 전체를 만족시키는 방법이다. 이를 이용하면 총 220개 매장 중에서 2시간 안에 물품을 배송할 수 있는 최소 매장을 선정할 수 있다.
만약 최소 매장이 30곳이라면 이곳에 물품을 배치하고, 남는 물품은 해당 사이즈의 옷이 가장 많이 팔린 곳에 배치한다. 이때 물품의 개수가 30개보다 적다면 특정지역에서의 판매를 포기하고, 가능한 곳에서만 판다. 구매는 실시간으로 일어나기 때문에 실시간 분석을 통해 3시간마다 매장에 물품을 배송한다.
집합 덮개 문제, 공공 정보에도 활용 가능
세계 최대 온라인 쇼핑몰인 아마존도 2005년부터 구매한 상품을 미국 내에서 2일 안에 받아 볼 수 있는 프리미엄 서비스를 제공하고 있다. 아마존에서도 집합 덮개 문제를 이용해 지역별로 최소의 비용으로 배송이 가능한 곳을 선정한 뒤, 그곳에 물품을 미리 배송해 놓는 방법을 사용하고 있다. 이처럼 집합 덮개 문제는 유통 문제를 해결하는 데 효과적으로 활용되고 있다.
집합 덮개 문제를 공공 정보에 활용하면 저상버스의 노선을 효율적으로 운영할 수도 있다. 저상버스는 노약자나 장애인이 쉽게 탈 수 있도록 일반 버스보다 차체 바닥이 낮고, 출입구에 계단 대신 경사판을 설치한 버스를 말한다. 서울시에서 운행되고 있는 총 7370대의 시내버스 중 2258대(30.6%)가 저상버스다. 서울시는 2017년까지 저상버스의 비중을 55%로 늘릴 계획이다.
하지만 현재 저상버스의 노선은 무작위로 정해져 있다. 즉 장애인들의 이용이 많은 노선에 배치되어 있지는 않기 때문에 효율성이 떨어진다. 하지만 집합 덮개 문제를 이용하면 많은 장애인들이 좀 더 편리하게 버스를 이용할 수 있다.
이를 위해서는 장애인들의 거주 지역과 직장 주소가 필요하다. 각 구청에서는 해당 자료를 가지고 있고, 장애인들이 대중교통을 이용하는지는 장애인 교통카드를 통해 알 수 있다. 즉 이 자료를 이용하면 대중교통을 이용하는 장애인들이 주로 어느 정류장을 이용하는지 추측할 수 있다. 그리고 이를 바탕으로 버스 정류장 별로 그곳을 이용하는 장애인 수를 파악할 수 있다.
그런데 한 정류장에는 많은 버스 노선이 지나고 있다. 이중 어떤 노선에 저상버스를 도입해야 장애인들에게 도움이 될까? 바로 이때 집합 덮개 문제를 이용한다. 그러면 수학적으로 가장 많은 장애인들에게 편의를 제공할 수 있는 최소의 노선을 골라낼 수 있다.
전쟁에서 꽃핀 최적화 이론
지금까지 살펴본 집합 덮개 문제는 수학에서 최적의 해법을 찾는 ‘최적화 이론’ 중 하나다. 그런데 이 이론을 발전시킨 주역은 제2차 세계대전이 한참일 무렵 활약한 수학자들이다. 전쟁이라는 극단적인 상황에서 정확한 의사결정을 내리기 위해 모든 문제를 수식으로 나타내고자 했기 때문이다.
실제로 당시 영국은 식량을 배를 이용해 전쟁터로 운송했는데, 독일의 공격으로 빈번히 실패해 식량 부족이 심각했다. 이에 영국에서는 되도록 적은 수의 함선으로 가능한 많은 배를 지키는 문제를 ‘선형계획법’이라고 불리는 연립방정식으로 나타냈다. 즉 최소의 노력으로 최대를 효과를 내는 ‘최적화 이론’를 생각해 낸 것이다.
이렇게 발전하기 시작한 최적화 이론은 전쟁 이후 산업 현장에서 활용되기 시작했다. 제지회사에서는 화장지의 길이를, 건축회사에서는 빌딩의 화장실이나 엘리베이터의 개수를 최적화 이론을 통해 정하기 시작한 것이다. 오늘날에는 유통, 서비스, 스포츠, 금융 등 산업 곳곳에서 최적화 이론이 쓰이고 있다.
수학 연구로 산업 현장을 누비세요! 엄상일 KAIST 수리과학부 교수
버스나 열차의 운행횟수를 정하거나 메이저리그의 경기 일정을 짜고 좋은 도로망을 설계하는 등 자원을 효율적으로 배분하는 문제에 최적화 이론이 활발하게 활용되고 있어요. 아직까지 국내에서는 이런 사례가 드물지만, 해외에서는 수학자에게 거액의 연봉을 주고 산업 현장 곳곳의 문제를 해결하도록 하고 있답니다. 우리나라에서도 곧 수학자들이 산업 현장을 누비게 될 거예요.
진로가 고민이라면 수학과에 가세요! 장영재 KAIST 산업 및 시스템공학과 교수
저는 때때로 진로를 고민하는 청소년들에게 대학에서 수학을 공부해 보라고 추천합니다. 그러면 대부분 “수학 공부하면 어떤 일을 할 수 있죠? 잘 모르겠어요”라고 대답하죠. 수학을 공부하면 산업 현장에서 일어나는 어려운 문제를 해결할 수 있어요. 보통 회사에서는 최소의 노력으로 최대의 성과를 내길 원하는데, 이것은 최적화 이론을 이용해야 해결할 수 있거든요. 따라서 수학을 공부하면 어떤 산업 분야에서도 일 할 수 있어요.
