열차의 승차권을 구입하면 좌석은 어떤 식으로 배당될까?
객차 하나당 좌석은 차량에 따라 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% 음영이 되는 식이다.
더 나아가 임의의 색을 16컬러 디더링 패턴으로 표현해 내는 프로그램을 직접 짜 보면 어떨까? 주어진 색을 가장 가깝게 표현할 수 있는 2색 또는 3색 조합을 구한 뒤, 그 비율만큼 threshold matrix를 각각의 색으로 채우면 될 것이다. 색조합을 구하는 것은 미지수의 개수가 식의 개수보다 더 많아서 답이 하나로 딱 떨어지지 않는 부등식이 될 터이니, LP(선형 계획법) 같은 계산 기법이 동원돼야 하지 않을까 싶다.
그렇게 threshold matrix만을 정석대로 적용하면 ordered dithering이 된다. 그러나 그것만으로는 그림이 칙칙하고 보기가 안 좋기 때문에, 디더링된 색깔의 픽셀이 인접 픽셀에 시각적으로 끼치는 영향을 감안하여(error diffusion) 더 정교하게 디더링을 수행하는 알고리즘이 실생활에서 쓰인다. 더 깊게 들어가는 건 이 글의 범위를 벗어나므로 자세한 설명을 생략하겠다.
뜬금없이 디더링 얘기를 꺼낸 이유는.. 저렇게 디더링 점을 찍어 나가는 게 마치 열차 좌석을 배당하는 것과 비슷한 심상이 느껴져서이다. 열차 좌석의 점유 여부를 흑백 픽셀로 표현하고 시간이 흐름에 따라 픽셀들의 상태를 표시하는 시뮬레이션을 돌려 보면 재미있을 것 같다. 한쪽은 검은 색이 듬성듬성 있고, 한쪽은 검은 색이나 흰 색이 좀 연속해서 있겠지 아마?
철도의 좌석 배당 알고리즘과 래스터 그래픽의 디더링 알고리즘은 서로 따로 생각하고 있었던 주제인데 이렇게 한 글로 연결이 됐다. 마치 예전에 내가 열차의 급행 등급과 셸 정렬을 한데 묶어서 글을 썼듯이 말이다. 참 신기한 일이 아닐 수 없다. ㅋㅋㅋㅋ
Posted by 사무엘
