1. 서 론

최근 개인과 개인 사이에 주고받던 우편물들은 감소하고 기업들이 개인들에게 발송하는 우편물들은 크게 증가하는 양상을 보이고 있다. 기존 연구에 의하면 2007년 한 해 동안 우체국을 통해 우편물을 발송하는 15개 대형 발송 기업들의 연간 총 발송 물량은 1,327만 통으로 우체국 전체에서 처리되는 연간 일반 우편 물량의 29%를 차지할 정도로 그 비중이 크다[5]. 기업들이 개인들에게 발송하는 이러한 유형의 우편물들을 본 연구에서는 상업용 다량 우편물(Commercial Bulk Mail)이라 부르며 요금 청구서, 제품홍보책자, 정기간행물 등이 이에 포함되고, 그 종류도 매우 다양하다. 이러한 상업용 다량 우편물들의 증가는 경제 활동에서 서비스 산업이 차지하는 비중이 커짐에 따라 발생되는 하나의 결과라고 생각할 수 있다. 상업용 다량 우편물들은 한 번에 발송되는 수량이 많고 우편물의 규격이 대개 동일하다는 특징을 가진다. 또한, 발송(원청)업체는 직접 우편물을 제작하여 우체국에 접수하는 대신에 <Figure 1>과 같이 발송대행업체(Mail Agency)를 통해 우편물 제작 및 접수 업무를 아웃소싱하는 것이 일반적이다. 발송대행업체는 발송(원청)업체(Mail Owner)로부터 수신자 주소, 우편물 내용, 규격 등의 정보를 제공받아 우편물을 제작하고 우편물 처리 시설에 접수(Mail Reception)시키는 업무를 대행한다. 일반적으로 하나의 발송대행업체가 여러 발송(원청)업체들의 우편물들을 제작하여 접수시키며, 하나의 발송(원청)업체는 둘 이상의 발송대행업체들에게 우편물 제작 및 접수(Reception)를 아웃소싱한다. 

<Figure 1> Production and Reception of Commercial Bulk Mail.

국내의 경우, 우편물은 <Figure 2>와 같이 접수(Reception), 발송구분(Sending Sort), 교환(Exchange), 도착구분(Delivery Sort), 배달(Delivery) 과정을 거쳐 수신자에게 전달된다. 우편물의 접수와 배달은 총괄우체국(간단히 총괄국)에서 수행되며, 발송구분과 도착구분은 집중국에서 수행되고 교환 과정은 교환센터에서 수행된다. 즉, 접수총괄국으로 접수되는 우편물들은 접수 집중국, 교환센터, 배달 집중국을 거쳐 배달총괄국으로 보내져서 배달된다. 우편물의 접수에서 배달까지 수행되는 업무들에 대한 설명은 Kim and Cha[6]와 Park et al.[4]를 참고하기 바란다. 

<Figure 2> Domestic Mail Processing Sequence.

우리나라에는 25개의 집중국(MSC : Mail Sorting Center)들과 218개의 총괄우체국(Major Post Office)들이 운영되고 있다. 전국의 25개 집중국 각각에는 2개에서 17개까지의 총괄우체국들이 할당되어 있는데, 하나의 집중국에 할당된 총괄우체국들을 해당 집중국의 관할 우체국이라 한다. 또한, 하나의 총괄우체국에는 배달 지역이 할당되어 있고, 우편물에 기재된 수신자 주소의 우편번호 6자리에 따라 우편물을 수신자에게 배달할 총괄우체국이 결정된다(다른 말로는 하나의 총괄우체국에서 배달해야 하는 수십에서 수백 개의 6자리 우편번호들이 할당되어 있다). 총괄우체국에 접수된 모든 우편물들은 해당 우체국을 관할하는 (접수)집중국으로 보내진다. (접수)집중국으로 들어온 우편물들은 배달 총괄우체국들을 관할하는 여러 (배달)집중국들로 보내지게 되는데, 이를 위해 (접수)집중국에서는 (배달)집중국 별로 우편물들을 구분하는 과정이 필요하며 이러한 구분과정을 발송구분이라 한다. 또한, (배달)집중국으로 들어온 우편물들은 (배달)집중국이 관할하는 배달 총괄우체국들로 보내지게 되는데, 이를 위해 (배달)집중국에서는 관할 배달 총괄 우체국 별로 우편물들을 구분하는 과정이 필요하며 이러한 구분과정을 도착구분이라 한다. 하나의 (접수)집중국에서 특정 (배달)집중국으로 보내는 우편물량이 많을 경우에는 (접수)집중국에서 (배달)집중국으로 우편물이 직접 보내지지만 우편물량이 적을 경우에는 여러 (접수)집중국들에서 발송구분되어 동일한 (배달)집중국으로 가야되는 우편물들을 통합하는 경우가 있는데 이 과정을 교환이라 부르며 우편물 운송 차량의 적재율을 향상시키기 위해 교환센터에서 수행된다. 배달 총괄 우체국에 도착한 우편물들은 집배원들에 의해 수신자에게 배달된다. 한 집배원이 배달하는 배달 구역이 정해져 있으며, 하나의 배달 구역에는 수십 개의 6자리 우편번호들이 할당되어 있고 수신자 주소의 우편번호 6자리가 같으면 동일한 집배원에 의해 배달된다. 참고로 우리나라의 6자리 우편번호 개수는 25,000여 개이며 서로 다른 앞 3자리는 260여 개가 존재한다. <Figure 3>은 국내의 우편물 접수와 배달 과정을 네트워크 형태로 도식화한 것이다. 단, 그림에서는 논리적인 설명을 위해 (접수)집중국과 (배달)집중국이 구분되어 있는 것으로 표현되어 있지만 하나의 집중국은 (접수)집중국과 (배달)집중국 역할을 모두 수행한다. 즉, 국내 25개 집중국 각각은 발송구분과 도착구분을 모두 수행한다. 마찬가지로 국내 218개 총괄우체국 각각은 접수와 배달 업무를 모두 수행한다. 

<Figure 3> Mail Delivery Network of Korea Post.

국내 우편사업자인 우정사업본부는 발송 우편 물량의 큰 비중을 차지하는 상업용 다량 우편물의 효율적인 처리를 위해 다양한 노력들을 수행하고 있다. 그 대표적인 노력이 선구분(Presort) 제도의 운영이다. 발송대행업체들에의해 제작된 상업용 다량 우편물들은 개인들이 보내는 일반 우편물의 경우와는 다르게 총괄 우체국이 아닌 (접수)집중국에 직접 접수되는 경우가 대부분이다. 이때 발송대행업체는 집중국에서 수행하는 발송구분이나 도착구분 작업을 미리 수행하여 우편물들을 접수할 수 있고, 이 경우 우편요금 일부를 할인받을 수 있다. 이와 같이 발송대행업체에 의해 미리 수행되는 발송구분이나 도착구분을 선구분이라 부른다. 우리나라에서는 3자리 선구분과 6자리 선구분에 대해 요금을 할인해 주고 있다. 여기서 3자리 선구분이란 접수되는 우편물들이 수신자 주소의 6자리 우편번호 중 앞 3자리가 동일한 우편물들 별로 구분되어있는 것을 말한다. 동일한 앞 3자리 우편번호를 가지는 우편물들은 (접수)집중국에서 동일한 (배달)집중국으로 보내지게 되는데 이로 인해 3자리로 선구분되어 접수되는 우편물들은 (접수)집중국에서 발송구분 작업이 효율적으로 수행될 수 있다. 마찬가지로 6자리 선구분은 접수되는 우편물들이 수신자 주소의 6자리 우편번호가 동일한 우편물들 별로 구분되어 있는 것을 말하며, 동일한 6자리 우편번호를 가지는 우편물들은 (배달)집중국에서 동일한 (배달)총괄우체국으로 보내지게 되는데 이로 인해 (배달)집중국에서 도착구분 작업이 효율적으로 수행될 수 있다. 따라서, 우편물 발송업체에 의해 선구분 되어 접수되는 우편물들에 대해서는 선구분 수준에 따라 우편 요금 할인이 차등적으로 적용된다. 

미국 우편사업자인 USPS(United States Postal Service)는 (주로 서비스 기업들인) 다량 우편물 발송기업들이 부가가치가 높고 지능화된 서비스들을 그들의 고객들에게 제공할 수 있도록 하기 위해서 지능형 바코드(Intelligent Barcode)를 활용하고 있다. 지능형 바코드란 우편물 처리 관련 정보와 서비스를 나타내기 위해 기존에 부착되던 여러 종류의 바코드들을 대신하여 우편물에 부착되는 하나의 유일한 바코드이다. 지능형 바코드를 통해 개별 우편물에 대한 서비스 유형을 포함한 우편물 고유 정보의 인식과 추적이 가능해지기 때문에 보다 효율적으로 다양한 형태의 지능형 서비스들을 제공할 수가 있게 된다. 기업이 판촉물, 세금 고지서, 청구서 등을 보내면 우편물이 현재 어디에 있고, 언제 배달될지에 대한 정보를 기업에게 제공하는 OneCode Confirm 서비스와 우편물이 주소 잘못으로 배달될 수 없을 때, 자동으로 주소를 정정하고 바코드를 인쇄하여 전송(Forwarding) 또는 반송(Return) 해주는 One-Code ACS 서비스가 대표적인 지능형 우편 서비스이다. 지능형 바코드는 4-state 바코드 형식으로 표현되며 USPS는 지능형 바코드가 부착된 우편물을 지능형 우편물(Intelligent Mail)이라 부르고 있다. 지능형 바코드는 통일된 하나의 바코드 사용에 따른 보다 청결한 우편물 제작, 용이한 우편물 추적에 따른 부가 업무 감소, 우편 주소 현행화 개선에 따른 미도착 우편물 감소, 반송 우편물 감소에 따른 불필요한 운송 및 배달 감소 등을 가능하게 함으로써 환경 친화적인 서비스 실현에도 크게 기여할 수 있다. 

USPS는 상업용 다량 우편물 발송업체들에게 우편물에 지능형 바코드(Intelligent Mail Barcode)를 부착하여 지능형 바코드 라벨이 부착된 우편상자(Intelligent Mail Tray Barcode)에 담아 접수하게 하고 있다. 또한, 발송업체가 지능형 우편물을 제작하여 접수할 때 선구분을 필수적으로 수행하도록 함으로써 우편물 처리 효율을 향상시킬 수 있게 하고 있다. USPS는 발송업체들의 우편물 선구분에 대해 요금할인을 통한 보상을 해주고 있는데, 우리나라가 3자리 또는 6자리 선구분된 우편물의 총 통수에 기반하여 요금할인을 해주는 반면 USPS의 국내 우편 매뉴얼에 따르면 <Table 1>과 같이 우편상자 단위의 선구분 수준에 따라 차등화된 요금할인을 적용해 주고 있다[8]. <Table 1>에서 AADC(Automated Area Distribution Center)는 우리나라의 집중국과 같은 역할을 하는 우편물 처리시설이다. 우리나라가 선구분을 필수사항으로 하고 있지 않은 반면 USPS는 적어도 Mixed AADC 우편상자 수준으로 선구분하는 것을 우편물 접수를 위한 필수 사항으로 규정하고 있다는 점이 다른 부분이다. 

<Table 1> Presorting Conditions for Commercial Bulk Mail of USPS.

Lim[9]은 국내 우편 환경을 고려한 선구분 체계를 제안한 바 있는데, 제안된 선구분 체계에서는 현재 우리나라에서 적용중인 3자리 선구분과 6자리 선구분 방식을 보완하여 접수하고자 하는 모든 상업용 다량 우편물들을 반드시 선구분하고 우편 상자에 적재하여 접수하도록 하고 있다. Lim[9]이 제안한 선구분 체계에는 6자리 선구분, 배달국 선구분, 집중국 선구분 수준이 존재한다. 먼저, 6자리 선구분은 동일한 6자리 우편번호를 가지는 우편물들만 우편상자에 적재되는 선구분 수준으로서 선구분이 되었다고 인정받기 위해서는 적어도 일정 수량 이상의 우편물들이 각 우편 상자에 적재되어야 하는 최소요구수량 제약이 존재한다. 배달국 선구분은 동일한 배달 총괄 우체국으로 가는 우편물들만 우편상자에 담겨 있는 선구분 수준으로서 6자리 선구분과 마찬가지로 최소요구수량 제약이 존재한다. 6자리 선구분과 차이점은 하나의 배달 총괄 우체국에서 배달하는 (수백 개의) 우편번호 6자리들을 가지는 우편물들이 동일 우편상자에 담길 수 있다는 것이다. 마지막으로 집중국 선구분은 동일한 (배달)집중국으로 가는 우편물들만 우편상자에 담겨 있는 선구분 수준으로서 최소요구수량 제약이 존재하지 않으나 발송업체가 상업용 다량 우편물을 접수하기 위해서는 집중국 선구분 수준으로는 반드시 선구분하여 접수해야 한다. 배달국 선구분과의 차이점은 하나의 (배달)집중국의 모든 관할 배달 총괄 우체국들에서 배달하는 (수백에서 수천 개의) 우편번호 6자리들을 가지는 우편물들이 동일 우편상자에 담길수 있다는 것이다. 선구분에 따른 우편 요금 할인은 6자리 선구분이 가장 높고 집중국 선구분이 가장 낮다. 

본 연구에서는 우편 발송 비용을 최소화하기 위한 상업용 다량 우편물 선구분 적재 문제를 특수한 형태의 수송계획 문제로 모형화하고 휴리스틱 알고리듬들을 개발하였다. 다만, Lim[9]이 제안한 선구분 체계에 따라 미국USPS와 같이 모든 상업용 다량 우편물들은 반드시 선구분되어 우편 상자에 적재하여 접수된다고 가정하였다. 또한, 우편 요금이 발송업체 별로 청구되기 때문에 동일한 우편 상자에는 동일한 발송업체의 우편물들만 적재된다고 전제하였다. 일반적으로 다량 우편물들이 적재된 우편상자들은 우편 상자 적재용 팔렛트에 다시 적재되어 운송되기 때문에 다량 우편물 적재에 사용되는 우편 상자의 규격은 동일하다고 가정하였다. 또한, 우편물 적재에 사용되는 우편 상자의 수는 충분하다고 가정하였다. 

본 논문의 구성은 다음과 같다. 제 2장과 제 3장에서는 상업용 다량 우편물 선구분 적재 문제의 수리 모형과 본 연구에서 개발한 휴리스틱 알고리듬들을 설명하였다. 제 4장에서는 개발한 휴리스틱 알고리듬들의 성능을 평가하기위해 수행한 계산 실험을 결과를 제시하였으며 제 5장에서는 추후 연구 과제를 포함한 연구의 결과들을 정리하였다. 

2. 상업용 다량 우편물 선구분 적재를 위한 수리모형

먼저, 본 연구에서 개발한 수리 모형의 이해를 돕기 위해 상업용 다량 우편물 선구분 우편상자 적재 문제에서 전제하고 있는 사항들을 정리하면 다음과 같다.

(1) 각 우편상자들은 6자리 선구분, 배달국 선구분, 집중국 선구분 중 하나로 선구분 수준이 미리 정해져 있다. 또한, 가용한 우편상자 수에 대한 제한이없는 경우이므로 선구분 수준 별 우편상자가 충분히 있다고 가정하고 모형을 개발하였다.
(2) 6자리 선구분 우편상자와 배달국 선구분 상자로 인정받기 위해서는 최소요구수량 이상의 우편물들이 동일한 우편상자에 적재되어야 한다. 따라서, 6자리 선구분 우편상자와 배달국 선구분 우편상자에 대해서는 정해진 최소요구수량이 적용된다. 다만, 집중국 선구분 상자에는 최소요구수량 제한이 없으므로 최소요구수량도 적용되지 않는다.
(3) 6자리 선구분 우편상자에는 동일한 6자리 우편번호를 가지는 우편물들만 적재가 가능하며, 배달국 선구분 우편상자에는 동일한 배달국에서 배달되는 우편번호를 가지는 우편물들만 적재가 가능하고 집중국 선구분 우편상자는 동일한 집중국의 관할 총괄 우체국들에서 배달되는 우편번호를 가지는 우편물들이 적재가 가능하다. 따라서, 하나의 우편물은 해당 우편물의 6자리 우편번호와 동일한 우편번호가 할당된 6자리 선구분 우편상자 또는 해당 6자리 우편번호의 우편물을 배달하는 배달국 선구분 우편상자 또는 해당 배달국을 관할하는 집중국 선구분 우편상자 중 하나에 적재될 수 있다. 

상업용 다량 우편물들을 선구분 우편상자들에 적재하는 문제인 LBLP(Letter-Box Loading Problem)를 모형화 하는데 사용되는 기호들을 정의하면 다음과 같다. 

파라메터
l 6자리 우편번호에 대한 인덱스
m 선구분 우편상자들에 대한 인덱스
p 배달국에 대한 인덱스
W 하나의 선구분 우편상자에 적재할 수 있는 상업용 다량 우편물의 최대 통 수
D_m 선구분 우편 상자 m에 담겨야 하는 최소 요구 우편물 통 수
N_I 6자리 우편번호가 l인 상업용 다량 우편물 통 수
Φ_I 6자리 우편번호가 l인 상업용 다량 우편물을 적재할 수 있는 선구분 우편상자들의 집합
F_Im 6자리 우편번호가 l인 상업용 다량 우편물 한통을 선구분 우편상자 m에 적재할 때 선구분 할인율이 적용된 통 당 우편요금

결정변수
χ_Im 선구분 우편상자 m에 적재하는 6자리 우편번호가 l인 상업용 다량 우편물의 통 수
ym 선구분 우편상자 m이 다량 우편물 적재에 사용되면 1, 아니면 0을 가지는 이진정수변수

앞서 정의한 기호들과 전제사항들을 가지고 상업용 다량 우편물들을 선구분 우편상자들에 적재하는 문제인 LBLP는 다음과 같은 선형정수모형으로 모델링될 수 있다. 단, 하나의 선구분 우편상자에는 동일한 발송원청업체의 우편물들만 적재될 수 있기 때문에 LBLP는 발송원청업체 별로 문제가 정의된다.
 

식 (1)은 선구분 우편상자들에 담기는 상업용 다량 우편물들의 총 우편 요금 최소화를 목적함수로 한다는 것을 의미한다. 여기서, 우편상자가 어떤 선구분 수준인가에 따라 해당 우편상자에 담긴 우편물들의 선구분에 따른 할인된 요금이 정해진다. 식 (2)는 상업용 다량 우편물들은 모두 선구분 우편상자에 담겨야 함을 나타내는 제약식이다. x식 (3)은 선구분 우편상자가 우편물 적재에 사용되면 적재시킬 수 있는 최대 수량을 넘어서지 말아야 함을 나타내는 제약식이다. 식 (4)는 선구분 우편상자에 우편물이 적재될 때 선구분 수준에 따라 반드시 적재해야 하는 최소 요구 수량 이상은 적재해야 함을 나타내는 제약식이다. 식 (5)와 식 (6)은 결정 변수를 나타낸다. 다만, 배달 우체국 별로 배달해야 하는 6자리 우편번호들이 겹치지 않게 구분되어 정해져 있고 집중국 별로 관할하는 배달 우체국들도 겹치지 않게 구분되어 정해져있기 때문에 상업용 다량 우편물들을 선구분 우편상자들에 적재하는 문제인 LBLP는 집중국 별로 분리하여 문제를 해결할 수 있다. 

3. 상업용 다량 우편물 선구분 적재 알고리듬

3.1 선구분 적재 문제의 특성

LBLP는 수요지가 6자리 우편번호가 되며 공급지는 선구분 우편상자가 되는 최소요구수량 제약이 있는 수송계획 문제의 특수한 형태이다. 여기서 공급지는 3가지 유형(6자리 선구분 우편상자, 배달국 선구분 우편상자, 집중국 선구분 우편상자)이 존재하며 각 유형 별 공급지의 수는 제한이 없고 동일 공급지 유형에 대해서는 동일한 수송 비용이 발생하고 공급지 유형에 따라 수송 비용이 차등적으로 발생한다. 수송계획문제는 오랜 기간 다양한 형태로 연구가 되어왔지만 최소요구수량 제약이 있는 수송계획문제(Transportation Problem with Minimum Quantity Commitment : TP with MQC)는 Lim et al.[1]의 연구에서 처음으로 소개되었으며 NP-hard 문제로 증명된 바 있어 최적해를 구하는 것이 매우 어렵다. 비록 Lim et al.[3]의 연구에서 언급된 바와 같이 최소요구수량 제약이 있는 수송계획문제는 다양한 분야에서 응용이 가능하지만 현재까지는 관련 연구가 많은 편이 아니다. 더욱이 본 연구에서 다루는 상업용 다량 우편물 적재 문제에 대해서는 관련 연구가 전무한 실정이다. Lim et al.[3]은 국제 화물 수송에서 발생되는 문제를 MQC 제약이 있는 수송계획문제로 모델링하였고 선형계획 완화를 이용한 휴리스틱과 Greedy 유형의 휴리스틱을 개발한 바 있다. 또한, Lim et al.[3]은 다른 연구에서 동일한 문제에 대한 라그랑지안 완화 기법을 이용한 해법을 제시한 바 있다. 한편, Lim and Xu[2]는 서비스 제공업체의 업무 부하 균등화를 위해서 MQC 제약식을 활용하였다. MQC제약식은 공급 계약 문제들에도 적용된 바가 있으며 대표적인 연구에는 Bassok and Anupindi[10]와 Chen and Krass[7]의 연구가 있다. Bassok and Anupindi[10]의 연구에서는 가격할인과 MQC 제약하에서의 최적 구매정책에 대한 연구를 수행하였고, Chen and Krass[7]에서는 수요가 일정하지 않고 MQC 제약이 있을 때의 공급 계약에 대한 연구를 수행하였다. 본 연구에서는 현실에서 적용 가능한 상업용 다량 우편물 선구분 적재 휴리스틱 알고리듬을 개발하였다. Lim et al.[3]의 연구에서 언급된 바와같이 최소요구수량 제약이 있는 수송계획문제는 다양한 분야에서 응용이 가능하지만, 본 연구에서 다루는 상업용 다량 우편물 적재 문제에는 아직까지 적용된 사례가 없으며 해당 연구도 전무한 실정이다. 

<Figure 4> Commercial Bulk Mail-Presorted Mail Tray Loading Relationship.

<Figure 4>는 상업용 다량 우편물들과 선구분 우편상자들 간의 적재 관계를 보여주고 있다. 그림에서 동서울 집중국의 관할 배달 총괄국인 광화문우체국, 서대문우체국, 동대문우체국에서 배달되는 상업용 다량 우편물들을 6자리 우편번호에 따라 6자리 선구분, 배달국 선구분, 집중국 선구분 우편상자에 적재할 수 있음을 보여주고 있다. 그림에서 볼 수 있듯이 광화문우체국에서 배달되는 110-100이라는 우편번호를 가지는 우편물들은(110-100) 6자리 선구분 우편상자, (광화문우체국) 배달국 선구분 우편상자 또는 (동서울 집중국) 집중국 선구분 우편상자에 담길 수 있다. 광화문우체국에서 배달되는 다른 6자리 우편번호들을 가지는 우편물들에 대해서도 동일한 방식으로 선구분 우편상자 적재 관계가 성립된다. 또한, 서대문우체국과 동대문우체국에 대해서도 광화문우체국의 경우와 동일한 방식의 선구분 우편상자 적재가 가능하다. 

3.2 선구분 적재 계획 알고리듬

본 연구에서는 선구분에 의한 요금 할인이 높은 순서대로 선구분이 되도록 하면서 우편물들이 최대 적재 수량만큼 가득 적재된 우편상자의 개수가 많아지도록 하는 알고리듬을 개발하였다. 앞서 언급한 바와 같이 배달 우체국 별로 배달해야 하는 6자리 우편번호들이 겹치지 않게 구분되어 정해져 있고 집중국 별로 관할하는 배달 우체국들도 겹치지 않게 구분되어 정해져 있기 때문에 상업용 다량 우편물들을 선구분 우편상자들에 적재하는 문제인 LBLP는 집중국 별로 분리하여 문제를 해결할 수 있다. 따라서 선구분 적재 계획 알고리듬은 각 집중국에 대해 적용하여 해를 구하면 된다. 

6자리 우편 번호가 l인 다량 우편물을 6자리 선구분 우편 상자 각각에 적재 가능한 최대 수량만큼 적재할 때 6자리 선구분 상자의 최소 필요 개수 이다. 여기서⌈α⌉는 α보다 크거나 같은 최소 정수를 의미한다. 최대 적재 선구분 알고리듬(Full Load Presort; FLP)
(Phase 1. 6자리 선구분)
Step 1 : 각각의 6자리 우편번호 l에 대해 μ_l 을 구한다. 만일 이 정수이면 Step 2로 가고, 그렇지 않으면 Step 3으로 간다.
Step 2 : 이 정수이면 μ_l개의 선구분 우편상자에 W개씩의 6자리 우편번호가 l인 다량 우편물들을 담는다. 여기서, 6자리 선구분 우편상자에 담기지 않고 남는 6자리 우편번호가 l인 우편물의 수량은 0이 된다.
Step 3 : 이 정수가 아니면 (  ― 1 )개의 6자리 선구분 우편상자에 W개씩의 6자리 우편번호가 l인 다량 우편물들을 담는다. ( μ_l ― 1 )개의 6자리 선구분 우편상자에 담기지 않고 남은 다량 우편물들의 개수가 6자리 선구분에 대한 최소요구수량보다 크거나 같으면 하나의 6자리 선구분 상자에 남은 우편물들을 모두 적재한다. 이때 6자리 선구분 우편상자에 담기지 않고 남는 6자리 우편번호가 l인 우편물의 수량은 0이 된다. 만일 남은 다량 우편물들의 개수가 6자리 선구분에 대한 최소요구수량보다 적으면 남은 우편물들을 대상으로 Phase 2를 수행한다. 이때에는 6자리 선구분 우편상자에 담기지 않고 남는 6자리 우편번호가 l인 우편물의 수량  가 된다.

(Phase 2. 배달국 선구분)
 Step 4 : 각각의 배달국 p에 대해 ε_{ρ =}를 계산한다. 여기서 Ω_ρ 는 배달국 p에 할당된 6자리 우편번호들의 집합이다. 만일  이 정수이면 Step 5로 가고 정수가 아니면 Step 6으로 간다.
Step 5 :  이 정수이면 ε_ρ 개의 선구분 우편상자에 W개씩의 l∈Ω_ρ인 다량 우편물들을 담는다. 여기서, 배달국 선구분 우편상자에 담기지 않고 남는 우편물의 수량은 0이 된다.
Step 6 :  이 정수가 아니면 ( ε_ρ ― 1 )개의 배달국 선구분 우편상자에는 W개씩의 l∈Ω_ρ인 다량 우편물들을 담는다. ( ε_ρ ― 1 )개의 배달국 선구분 우편상자에 담기지 않고 남은 다량 우편물들의 개수가 배달국 선구분에 대한 최소요구수량보다 크거나 같으면 하나의 배달국 선구분 상자에 남은 우편물들을 모두 적재한다. 이때 배달국 선구분 우편상자에 담기지 않고 남는 우편물의 수량은 0이 된다. 만일 남은 다량 우편물들의 개수가 배달국 선구분에 대한 최소 요구수량보다 적으면 남은 우편물들을 대상으로 Phase 3을 수행한다. 여기서 배달국 선구분 우편상자에 담기지 않고 남는 다량 우편물은  가 된다.

(Phase 3. 집중국 선구분)
Step 7 : = ⌈ ⌉를 계산하고 가 정수이면 개의 집중국 선구분 우편상자에 W개씩의 배달국 선구분 우편상자에 담기지 않은 다량 우편물들을 담는다. 만일  가 정수가 아니면 (  ― 1 )개의 집중국 선구분 우편상자에는 W개씩의 배달국 선구분 우편상자에 담기지 않은 다량 우편물들을 담고 한 개의 집중국 선구분 상자에는 담기지 않고 남은 다량 우편물들을 담는다.

4. 계산 실험

본 연구에서 제안한 알고리듬의 성과를 평가하기 위해 국내 발송업체들의 상업용 다량 우편물 발송 통계를 기초로 다양한 문제들을 생성하고 해를 구해 보았다. 제안한 알고리듬을 C언어로 프로그래밍 하였고 2.66GHz의 클럭스피드를 가지는 인텔 코어 2 프로세서가 장착된 PC에서 계산 실험을 수행하였다. 문제 생성에 필요한 데이터는 다음과 같이 방법으로 결정하였다. 여기서 D(a, b)는 구간[a, b]에서의 이산균일분포 (discrete uniform distribution)를 표시하며 N(μ, σ2)은 평균이 μ이고 표준편차가 σ인 정규 분포를 표시한다. 

1) 집중국의 수는 25개로 하였고 배달 우체국의 수는 200개로 설정하였다. 하나의 배달 우체국에 할당된 6자리 우편번호의 수는 DU(100, 150)로 생성하였다. 하나의 배달 우체국은 하나의 집중국에만 할당되며 하나의 6자리 우편번호 또한 하나의 배달 우체국에만 할당된다.
2) 3가지 유형의 발송업체를 고려하였다.
유형 1. 대규모 발송 고객(연간 평균 1억 통 발송)
유형 2. 중규모 발송 고객(연간 평균 5천만 통 발송)
유형 3. 소규모 발송 고객(연간 평균 2천만 통 발송)
3) 3가지 유형의 발송 빈도를 고려하였다.
유형 1. 1주에 1회 발송(연간 52회 발송)
유형 2. 2주에 1회 발송(연간 26회 발송)
유형 3. 4주에 1회 발송(연간 13회 발송)
4) 1회 발송 물량은 으로 생성하였다. 는 연간 발송 물량을 발송 횟수로 나눈 평균 1회 발송 물량이다. ρ는 1회 발송 물량 간의 차이 정도를 나타내는 계수로서 ρ = 1.0인 경우와 ρ = 2.0인 경우를 고려하였다. ρ = 2.0인 경우가 1회 발송 물량 간 차이가 큼을 의미한다.
5) 각 6자리 우편 번호 별 발송 물량은 으로 생성하였다. 여기서 는 평균 1회 발송 물량을 우편번호의 수로 나눈 우편번호 별 평균 발송 물량이다. δ는 각 우편 번호 별 발송 물량 간의 차이 정도를 나타내는 계수로서 δ = 1.0인 경우와 δ = 2.0인 경우를 고려하였다. δ = 2.0인 경우가 각 우편 번호간 발송 물량 차이가 큼을 의미한다.
6) 선구분 수준에 따른 우편 요금 할인은 6자리 선구분의 경우 정상 요금의 10% 할인, 배달국 선구분의 경우에는 정상 요금의 7% 할인, 집중국 선구분의 경우에는 5% 할인을 적용하였다.
7) 우편 상자의 최대적재 가능 통 수는 200통인 경우와 300통인 경우를 고려하였다. 최소요구수량은 최대적재 가능 통 수의 75%로 설정하였다. 

<Table 2>에서 볼 수 있듯이 발송 규모가 큰 기업이 선구분에 의한 더 많은 비용 감소 효과를 볼 수 있다. 또한, 소규모의 우편 상자를 사용하는 것이 비용감소에 더 효과적이라는 것을 알 수 있다. 발송 빈도를 가능한 줄이는 것도 더 많은 비용 감소 효과를 얻는데 도움이 된다. 1회 발송물량 간 차이가 큰 경우가 그렇지 않은 경우 보다 더 많은 비용 감소 효과를 얻을 수 있을 것으로 나타났으며 1회 발송 물량을 구성하는 우편물들의 우편 번호 별 발송 물량 편차가 클수록 더 많은 비용 감소 효과를 얻을 수 있다. 

3가지 유형의 발송업체, 2가지 유형의 1회 발송 물량, 2가지 유형의 6자리 우편번호 별 발송 물량의 모든 12가지 조합에 대해서 5문제씩을 생성하였다. 총 60문제 각각을 3가지의 유형의 발송 빈도와 2가지 유형의 우편 상자 최대 적재 가능 통 수에 대한 6가지 조합 별로 해를 구하였다. 이렇게 함으로써 발송업체 유형에 따라 생성된 연간 발송 물량을 발송 빈도에 따라 나누어 발송하는 경우를 비교할 수 있게 된다. 또한, 1회 발송 시 사용하는 우편 상자의 최대 적재가능 수량에 따른 비용 감소 효과의 차이도 알 수 있다. 선구분에 따른 연간 우편 비용 감소 효과에 대한 계산 실험의 결과가 <Table 2>에 주어져 있다. 여기서 비용 감소 효과는 선구분에 의한 우편 요금 할인이 적용되지 않을 때의 정상 요금에 의한 연간 총 우편 비용과 선구분에 의해 절감된 연간 총 우편 비용으로 산정한 비용 감소 비율이다. 즉, {(정상 요금 적용 시의 연간 총 우편 비용-선구분에 의한 우편 요금 할인이 적용 되었을 때의 연간 총 우편 비용)/(정상 요금 적용 시의 연간 총 우편 비용)}×100(%)이다. 

본 연구에서 제안한 휴리스틱이 어느 정도의 성과를 주는지 알아보기 위해 상용 최적화 소프트웨어인 Xpress- MP와 결과 값을 비교하였다. Xpress-MP의 계산시간 제한을 30분으로 두고 해를 구한 것과 본 연구에서 제안한 방법으로 구한 해를 비교하였다. 단, 본 연구에서 제안한 휴리스틱의 성능을 상용 최적화 소프트웨어와 비교 하는 것이 목적이므로 실험 조건을 단순화하여 계산 실험을 수행하였다. 우편 상자 최대 적재가능 통 수는 앞의 실험 결과에서 가장 좋은 비용 감소 효과를 나타낸 200통으로 지정하였다. 또한, 발송 빈도와 1회 발송 물량 및 우편번호 별 물량에 대한 편차는 고려하지 않았다. 이와 더불어 앞서 언급한 바와같이 배달 우체국 별로 배달해야 하는 6자리 우편번호들이 겹치지 않게 구분되어 정해져 있고 집중국 별로 관할하는 배달 우체국들도 겹치지 않게 구분되어 정해져 있으므로 상업용 다량 우편물들을 선구분 우편상자들에 적재하는 문제인 LBLP는 집중국 별로 분리하여 문제를 해결할 수 있기 때문에 집중국이 하나이며 배달 우체국의 수는 5개인 경우에 대해 총 10문제를 생성하여 비교를 수행하였다. 통당정상 우편 요금은 100원으로 설정하였고, 선구분 수준에 따른 우편 요금 할인은 6자리 선구분의 경우 정상 요금의 10% 할인, 배달국 선구분의 경우에는 정상 요금의 7% 할인, 집중국 선구분의 경우에는 5% 할인을 적용하였다. 

<Table 2> Mail Fee Reduction Effect thanks to Presorting.

<Table 3>은 실험결과를 보여주는데, *표시는 상용 소프트웨어가 최적해를 찾은 경우를 나타낸다. <Table 3>에서 보는 바와 같이 본 연구에서 제안한 휴리스틱은 상용 소프트웨어가 발견한 해에 근접한 수준의 매우 우수한 해를 매우 빠른 시간 안에 찾아준다. 선구분되는 우편물의 통 수가 수백만 통을 넘는 현실적인 문제에 대해서는 상용 소프트웨어로 해를 구하는 것이 용이하지 않기때문에 본 연구에서 제안한 휴리스틱의 활용 가능성은 크다고 할 수 있겠다. 

<Table 3> Performance Evaluation of FLP Algorithm.

5. 결론 및 추후 연구

본 연구에서는 상업용 다량 우편물의 선구분 적재를 위한 수리 모형을 개발하고 현실에서 사용 가능한 휴리스틱 알고리듬을 제안하였다. 제안한 알고리듬을 계산 실험을 통해 평가하였으며 선구분 적재에 따른 비용 감소 효과가 발송 업체의 규모, 발송 빈도, 우편 상자의 크기, 발송 물량의 편차 등에 의해 영향을 받음을 확인하였다. 본 연구에서 개발한 선구분 적재 모형은 최소요구수량 제약이 있는 수송계획 문제로 알려져 있으며 일반적인 경우에서는 NP-hard로 증명되어 있다. 그러나 본 연구에서 다루는 문제가 동일한 수준에서 선구분된 우편물은 어떤 우편상자에 적재되는지에 상관없이 동일한 우편요금이 발생하고 현실적으로 우편상자의 수에 대한 제한을 고려하지 않아도 된다는 독특한 특성을 가지기 때문에 이를 고려한 보다 효과적인 해법 개발도 가능하리라 생각한다. 또한, 우편물이 적재된 우편상자들은 팔렛트라 불리는 용기에 재적재되어 운송되기 때문에 우편 상자-팔렛트 적재 문제에 대한 연구도 필요하리라 판단된다. 

Acknowledgement

This study has been partially supported by a Research Fund of Yeungnam University, Korea. 

36-1-02 임승길 김재곤 신용호8-16.pdf641.8KB