열차 좌석 배당 알고리즘

열차의 승차권을 구입하면 좌석은 어떤 식으로 배당될까?
객차 하나당 좌석은 차량에 따라 60~70개 정도가 있으며, 열차 한 편성은 일반실만 생각하더라도 최하 4량부터 시작하고 KTX의 경우 거의 15량에 가깝다. 수백 개의 좌석들은 어떤 순서와 원칙대로 승객에게 팔려 나갈까?

난 철덕후로서 그 알고리즘이 예전부터 굉장히 궁금했다. 여러분은 그렇지 않은가?

버스 정도면 그냥 아무렇게나 랜덤으로 배당해도 별 무리가 없을 것이다.
우등 고속버스는 가장 쉽다. 승차 정원부터가 30명이 채 안 되는 소규모인 데다, 좌석이 구조적으로 2개짜리와 1개짜리로 나뉘어 있으니 말이다.

단독 승객에게는 진행 방향 기준으로 오른쪽의 단독 좌석부터 먼저 배당해 주고, 그게 매진되거나 2인 승객이 있으면 2인 좌석을 준다. 상석인 맨 앞자리는 약간 나중에 팔리도록 다른 가중치를 부여하고, 반대로 최악의 자리인 맨 뒷자리는 최하위 우선순위로 팔리게 하면 될 것이다.

그러나 열차는 단순하게만 좌석을 배당해서는 대략 곤란하다.
1부터 n호차까지, 그리고 진짜 무식하게 1번부터 m호석까지 앞에서 뒤로 순서대로 꽉꽉 승객을 채워 넣어서 뒤의 객차는 텅 빈 채로 달리게 할 리는 없을 테고..

그렇다고 좌석을(특히 단독 승객) 완전 랜덤으로만 여기저기 들쭉날쭉으로 배당하면 좌석의 단편화(fragmentation)가 너무 심해진다. 그래서 승객이 얼마 타지도 않은 상태인데 이따금씩 타는 2인 이상의 다수 승객은 이어진 좌석을 못 구해서 서로 찢어져서 앉아야 하는 일이 벌어질 수 있다.

결국 본인이 추측하기로는 열차의 좌석 배당은 저 양 극단의 중간을 절충하는 방식으로 이뤄질 것 같다.
두세 개의 객차를 묶음으로 나눠서 한 묶음 안에서 좌석을 무작위로 배당한 뒤, 그 묶음의 좌석이 다 매진되면 다음 묶음으로 간다. 각 묶음은 1~3호차, 4~6호차, 7~9호차 같은 규칙으로 만들 수도 있고, 반대로 1, 4, 7호차와 2, 5, 8호차, 3, 6, 9호차 같은 규칙으로 만들 수도 있다.

그리고 각 객차 안에서는 전체의 50~60% 정도는 단독 승객이 무작위로 띄엄띄엄 앉을 수 있게 배려한다. 즉, 2개짜리 좌석이라도 한 자리에 단독 승객이 있으면 거기는 일단 건너뛰고 다른 빈 자리를 찾는다는 뜻이다. 그러나 나머지 자리는 가능한 한 2인 승객이 한꺼번에 찜할 수 있게 비워 두며, 한 객차의 좌석의 10~20% 정도는 마치 KTX 동반석처럼 4인 가족이 연속해서 앉을 수 있게, 가능한 한 1~2인 승객에게 금세 팔리지 않도록 비워 둔다.

단독 승객의 경우 창측 좌석이 내측 좌석보다 먼저 팔리게 하는 건 기본이다. 또한 열차에서는 출입문과 가까운 맨 앞이나 맨 뒤 좌석이 '안 좋은 자리'이므로 이것 역시 다른 좌석이 모두 팔린 뒤에 나중에 팔리게 해야 할 것이다.
단독 승객용 좌석과 2인 이상 승객용 좌석 영역을 정하는 것 역시 '엿장수 마음대로' 무작위로 하면 되며, 그 비율 역시 평소에 승차권이 팔리는 단위 통계를 근거로 합리적으로 정하면 될 것이다.

저런 균형적인 요소에 덧붙여 환승 동선도 고려 대상이 된다.
국내의 예를 들면 KTX 천안아산 역과 장항선 아산 역은 남쪽 끝에서 만난다. 그리고 KTX는 한 편성이 무려 400m가 약간 안 되는 매우 긴 열차이다. 그렇기 때문에 경부선 KTX를 타다가 천안아산 역에서 장항선으로 환승하는 승객은 부산 방면(하행) 열차의 경우 최대한 앞쪽 객차로 좌석이 배당되고, 서울 방면 열차는 뒤쪽 객차로 좌석이 배당된다. 지하철에서 환승을 빨리 할 수 있는 객차의 위치와 정확히 같은 개념이며, 한국 철도도 그 정도 센스는 이미 갖추고 있다.

이 정도면 내가 보기에 열차 좌석 배당 전략을 짜는 건, 마치 열차 시각표를 짜는 것에 필적하는 철도 영업 기술의 결정체가 될 수도 있을 것 같다.
현실성 있는 열차 운행 시각표를 짜기 위해서는 그 나라의 철도 인프라와 지형 특성, 차량 제원, 승객 패턴 등의 알토란 같은 영업 기밀이 총동원되어야 한다. 이런 걸 계획하는 건 인원을 더 투입한다고 신속하게 되는 게 아니며, 핵심 똘똘이 인력 한두 명이 다 도맡아 한다.

좌석 배당도 마찬가지일 거라는 말이다. 철덕이라면 반드시 정복해야 하는 분야 중 하나 되시겠다.
비행기는 무게 배분이(한쪽에만 승객 무게가 지나치게 쏠리지 않게) 좌석 배당에 감안되는 요인이라고 하는데, 철도는 무게 배분 걱정은 할 필요가 없는 대신 길다는 특성상 다른 변수가 존재하는 셈이다.

자, 여기까지만 글을 쓰려고 했는데, 빈 좌석에다 승객을 일정 규칙대로 채워 넣는 과정을 생각하자니 컴퓨터그래픽에서 중요하게 다뤄지는 알고리즘 분야가 문득 떠오르더라.
바로 디더링이다.

디더링은 적은 수의 색깔을 섞어서 더 화려한 색깔을 아쉬운 대로 표현하는 기법이다. 색을 물리적으로 섞을 수는 없으니 결국 서로 다른 색깔을 번갈아가며 늘어놔야 하는데, 한 색깔이 뭉치는 게 아니라 서로 다른 색깔들끼리 최대한 고르게 퍼지도록 픽셀을 배열해야 한다.

본인은 과거에 Windows 3.x 시절에 그림판에서 임의의 RGB 값을 주면 그 색을 16컬러만으로 디더링하여 표현하는 걸 보고 무척 신기해했었다. 가령, 흑에서 백으로 단계를 증가시킬 때, 검은색에서 흰색 점이 차츰 늘어나는 순서가 어떻게 정해지는지가 무척 궁금했다.

그 규칙을 디더링에서 threshold matrix라고 부른다. 일반적인 그래픽 프로그램에서는 8*8짜리를 사용한다. (출처는 위키백과) 저기서 1부터 16까지의 점을 순서대로 채우면 25% 음영이 그려지고, 32까지 채우면 흑백이 딱 반반씩 번갈아가며 등장하는 50% 음영이 되는 식이다.

사용자 삽입 이미지
처음에는 4픽셀 간격으로 띄엄띄엄 점을 그리고, 나중에는 그 사이의 4픽셀 간격을 채우는 식으로, 점들이 뭉치지 않고 어떤 경우에도 최대한 흩어져서 퍼져 있게 한다. 임의의 격자 크기가 주어졌을 때 threshold matrix를 생성하는 프로그램을 만들 수도 있을 법해 보이는데 그리 만만한 일은 아닌 것 같다. 마방진도 아니고 말이다.

더 나아가 임의의 색을 16컬러 디더링 패턴으로 표현해 내는 프로그램을 직접 짜 보면 어떨까? 주어진 색을 가장 가깝게 표현할 수 있는 2색 또는 3색 조합을 구한 뒤, 그 비율만큼 threshold matrix를 각각의 색으로 채우면 될 것이다. 색조합을 구하는 것은 미지수의 개수가 식의 개수보다 더 많아서 답이 하나로 딱 떨어지지 않는 부등식이 될 터이니, LP(선형 계획법) 같은 계산 기법이 동원돼야 하지 않을까 싶다.

그렇게 threshold matrix만을 정석대로 적용하면 ordered dithering이 된다. 그러나 그것만으로는 그림이 칙칙하고 보기가 안 좋기 때문에, 디더링된 색깔의 픽셀이 인접 픽셀에 시각적으로 끼치는 영향을 감안하여(error diffusion) 더 정교하게 디더링을 수행하는 알고리즘이 실생활에서 쓰인다. 더 깊게 들어가는 건 이 글의 범위를 벗어나므로 자세한 설명을 생략하겠다.

뜬금없이 디더링 얘기를 꺼낸 이유는.. 저렇게 디더링 점을 찍어 나가는 게 마치 열차 좌석을 배당하는 것과 비슷한 심상이 느껴져서이다. 열차 좌석의 점유 여부를 흑백 픽셀로 표현하고 시간이 흐름에 따라 픽셀들의 상태를 표시하는 시뮬레이션을 돌려 보면 재미있을 것 같다. 한쪽은 검은 색이 듬성듬성 있고, 한쪽은 검은 색이나 흰 색이 좀 연속해서 있겠지 아마?

철도의 좌석 배당 알고리즘과 래스터 그래픽의 디더링 알고리즘은 서로 따로 생각하고 있었던 주제인데 이렇게 한 글로 연결이 됐다. 마치 예전에 내가 열차의 급행 등급과 셸 정렬을 한데 묶어서 글을 썼듯이 말이다. 참 신기한 일이 아닐 수 없다. ㅋㅋㅋㅋ

Posted by 사무엘

2013/04/08 08:18 2013/04/08 08:18
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/815

Trackback URL : http://moogi.new21.org/tc/trackback/815

Comments List

  1. 김재주 2013/04/08 18:21 # M/D Reply Permalink

    흥미로운 주제로군요. 비슷하다면 비슷한데 또 다르다면 다른 주제로 동영상 압축 기법인 벡터 양자화(vector quantization)가 있습니다. 이를테면... 16x16 크기의 샘플 패턴 N개를 생성합니다. 이후 동영상의 각 프레임들을 16x16 격자로 나눈 후 거기에 대응되는 샘플 패턴의 번호로 나타내는 것이죠. 만일 패턴이 256개라면 1바이트로 표현할 수 있으니까 RGB 각 1바이트로 나타낸 색 공간에서라면 동영상은 1/3크기로 줄어들게 되겠죠.

    샘플 패턴을 어떻게 정할 것인가는 자명한 방법이 있습니다. 해당 샘플 패턴을 사용할 격자들과의 제곱오차를 최소로 하는 패턴을 사용하면 되겠죠. 다시 말해서 그 격자들의 기하평균을 구하면 됩니다.


    그렇다면 결국 각각의 격자값을 어떤 패턴에다 대응시키는 것이 화질 열화를 최소로 하는 방법인지 찾아내야 하는데 고려해야 할 변수가 많기 때문에 그리 쉽지는 않습니다. 이 경우에도 LP 등의 기법을 많이 동원하더군요. 그런데 Genetic algorithm에다가 local optimization을 동원한 알고리즘이 상당히 좋은 성능을 보인다는 얘기를 봤어요.

  2. 김재주 2013/04/08 18:26 # M/D Reply Permalink

    아, 어찌보면 엘리베이터 스케쥴링 문제와도 비슷하군요. 서울대학교 문병로 교수님의 논문을 링크합니다.
    http://soar.snu.ac.kr/papers/journals/9.pdf

    엘리베이터 이용객은 흔히 푸아송 분포를 따른다고 알려져 있는데 이를 이용해서 다양한 평가항목을 가장 잘 만족시키는 스케쥴링 규칙을 GA를 이용해서 adaptive하게 바꿔나간다는 것입니다.

    승객들의 철도 이용 행태도 거의 해마다 비슷할테니 1년 전의 데이터를 바탕으로 현재 최적이라고 할 수 있을 만한 배치 규칙을 찾아내게끔 할 수 있겠습니다. 코레일 나름대로 사용하고 있는 방법이 있겠지만, 이런 쪽으로도 한번 연구개발을 해보는 것이 어떨까 싶습니다.

    1. 사무엘 2013/04/08 22:54 # M/D Permalink

      1. 여러 흥미로운 보충 설명에 감사드립니다. 영상의 손실 압축에서 화질 열화를 최소화하는 기법에도 그런 방식의 문제가 있다는 것도 처음 알았고요. 그리고 문 교수님이 그 분야에도 손대신 적이 있다는 것도요.

      그리고 엘리베이터.. 그것도 좌석 배당만큼이나 경험적인 전략이 필요한 아주 실용적인 주제임이 틀림없어 보입니다. 아주 초창기에 1회 IOI 때 대놓고 엘리베이터 시뮬레이션 문제가 나온 적이 있었지만 그때는 너무 옛날이어서 대회 진행 방식이 정착하기 전이었고, 9회(97년) 6번 문제 컨테이너 쌓기도 비슷하다면 비슷한 주제 같습니다. 승객 대신 컨테이너이고, 좌석의 단편화 대신 스택 구조가 있는 셈이죠.

  3. 김재주 2013/04/09 13:44 # M/D Reply Permalink

    IOI 문제와는 좀 다른 것이 여러 개의 승강기가 있는 경우에 어떤 승강기를 스케쥴링할것인가 하는 문제라서요. 아무튼 열차 배치도 결국 평가함수는 수정되겠지만 거의 비슷한 접근을 할 수 있을 것 같네요.


    그리고 다시 보니까 1/3로 줄어드는 게 아니네요. 16x16격자를 대표하는 것이니까 1/3 * 1/16^2로 줄어듭니다 후덜덜..

Leave a comment
« Previous : 1 : ... 1416 : 1417 : 1418 : 1419 : 1420 : 1421 : 1422 : 1423 : 1424 : ... 2128 : Next »

블로그 이미지

그런즉 이제 애호박, 단호박, 늙은호박 이 셋은 항상 있으나, 그 중에 제일은 늙은호박이니라.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2024/03   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            

Site Stats

Total hits:
2620322
Today:
3321
Yesterday:
1544