[논문]최대 경쟁력을 갖는 최소 신설 점포위치 결정 알고리즘

이상운

doi:10.7236/jiibc.2019.19.2.203

최대 경쟁력을 갖는 최소 신설 점포위치 결정 알고리즘
Algorithm to decide Minimum New Store Positioning with Maximum Competitiveness 원문보기

The journal of the institute of internet, broadcasting and communication : JIIBC, v.19 no.2, 2019년, pp.203 - 209

초록
AI-Helper

고객 수 pop인 도시에 경쟁업체 $F_A$가 p개 점포를 운영하고 있는 경우, 신규 업체 $F_B$가 $q(1{\leq}q{\leq}p-1)$점포를 신규 개설하고자 한다. 이 경우 pop/(p+q)이상의 고객을 확보할 수 있는 q개 점포 위치를 결정해야 한다. 이 문제에 대해 Han은 포함-배제 알고리즘을 제안하였으며, $q=1,2,{\cdots},p-1$로 증가하면서 이전에 확정된 위치가 변경되는 경우를 고려하여 최대 고객 확보 상위 5개 지점을 선택하여 이들 중 최대 고객 확보 지점으로 결정하였다. 본 논문에서는 초기상태부터 탐색범위를 축소시키고, $q=1,2,{\cdots},p-1$로 증가하면서도 계속적으로 탐색 범위를 축소시키면서 q=1 한 노드에 대해서만 계속 노드를 추가하는 방법을 제안한다. 최종적으로 얻은 q 상호간에 시장을 서로 빼앗는 경우가 발생하면 보다 멀리 떨어트리는 방법으로 해를 개선하였다. 제안된 알고리즘을 11개 사례에 적용한 결과 Han 알고리즘에 비해 단순하면서도 보다 좋은 결과를 얻었다.

Abstract ▼ AI-Helper

We will be establish the new $q(1{\leq}q{\leq}p-1)$ stores of firm $F_B$ to gain pop/(p+q) over rival firm $F_A$ that has already operate with p stores in a city of population pop. Han proposes inclusion-exclusion algorithm(IEA) that searches maximal pop top 5 location and select the maximum location take account of locate variation with increasing of $q=1,2,{\cdots},p-1$. This paper reduced the orignal graph into partial graph initially and search only q=1 node continually reduced in accordance with increasing $q=1,2,{\cdots},p-1$. If the final result is shown in the case of steel customer between q, the q locations farther separate in order to improve of solution. For the eleven experimental data, this algorithm is a relative simplicity and more optimal solution than Han's IEA.

주제어

표/그림 (8)

그림 그림 1. Swain 도시 망 Fig. 1. Swain-55 network
그림 그림 2. 포함-배제 알고리즘 Fig. 2. Inclusion-exclusion algorithm(IEA)
그림 그림 3. 축소된 탐색 범위 Fig. 3. Reduced search area
표 표 1. IEA 알고리즘 수행 사례 Table 1. Result case of IEA algorithm
그림 그림 4. F_A = {5,17,31,38,41}에 대한 CA Fig. 4. CA for F_A = {5,17,31,38,41}
표 표 2. F_A(p = 5)에 대한 F_B(1 ≤ q ≤ p − 1) Table 2. F_B(1 ≤ q ≤ p − 1) about F_A(p = 5)
표 표 3. T = 0.8 × pop/(p + q)에 따른 폐쇄 점포 Table 3. Closed stores follow with T = 0.8 × pop/(p + q)
표 표 4. T = 0.7 × pop/(p+q)에 따른 조기 폐쇄 점포 Table 4. Soon closed stores follow with T = 0.7 × pop/(p+q)

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 동종업계 FA가 p개 점포를 운영하고있는 상황에서, FB가 q(1≤q≤p-1)개 점포로 p개 이하로 신규 개설하면서도 pop/(p+q)이상의 고객을 확보할 수 있는 신설 점포 위치 q개를 구하는 방법을 연구하였다.
^[1] 기존 연구는 대부분 p=q로 동일 점포수를 개설하는 경우를 연구하였으나, 본 논문은 p>q인 경우를 고려한다. 본 논문은 이 상황에서 어느 위치에 F_B의 q개의 점포를 개설하는 것이 최적인지를 결정하는 문제를 다룬다.

가설 설정

[1]은 정확한 해를 다항시간으로 구하는 알고리즘이 알려져 있지 않다는 가정하에 Ant System+Tabu Search의 하이브리드형 메타휴리스틱 기법을 적용하여 해를 구하고자 하였다. Han^[2]은 다항 시간으로 해를 구하는 규칙을 찾고자 하였다.
다음으로, 각 점포는 확보한 고객 수가 요구 한계 수준(demand threshold level, T) 이상을 충족시켜야만 점포 운영비용을 제외하고 이득을 남길 수 있어 점포를 계속 운영할 수 있으며, 그렇지 못하면 점포를 운영하면 할수록 매출급감에 따른 계속적인 적자로 인해 점포는 폐업한다(문을 닫는다)고 가정한다. 이 경우 Serra et al.
,p-1로 증가시키면서 해를 구하는 포함-배제 알고리즘(inclusion-exclusion algorithm, IEA)이다. 이 알고리즘은 가장 인접한 노드 점포로 고객이 찾아간다는 가정 하에, 그림 1의 n=55개 노드들 중 q는 p와 동일한 노드에 위치하면 보다 많은 고객을 확보할 수 없다고 가정하고, n-p=55-5=50개 노드를 대상으로 p=5개 노드가 존재하는 상황에서 각 노드의 점유율(확보 고객 수)을 구하여 q위치를 구하는 방법이다. 단, q가 증가할수록, 기존에 선정된 위치가 변동이 될 수도 있고 안될 수도 있기 때문에 상위 5개 위치를 대상으로 해를 구하여 가장 많이 확보한 위치를 결정하는 방법을 채택하였다.

제안 방법

이 알고리즘은 가장 인접한 노드 점포로 고객이 찾아간다는 가정 하에, 그림 1의 n=55개 노드들 중 q는 p와 동일한 노드에 위치하면 보다 많은 고객을 확보할 수 없다고 가정하고, n-p=55-5=50개 노드를 대상으로 p=5개 노드가 존재하는 상황에서 각 노드의 점유율(확보 고객 수)을 구하여 q위치를 구하는 방법이다. 단, q가 증가할수록, 기존에 선정된 위치가 변동이 될 수도 있고 안될 수도 있기 때문에 상위 5개 위치를 대상으로 해를 구하여 가장 많이 확보한 위치를 결정하는 방법을 채택하였다.
본 논문에서 제안된 알고리즘으로 1≤q≤p-1을 구하여 q개 신규 점포 개설 비용 대비 pop×q/(p+q)또는T=0.7×pop/(p+q)에 따른 이득을 적용하여 적절한 q개 점포를 결정할 수 있을 것이다.
본 논문에서는 n-p개 노드를 대상으로 하지 않고, q의 후보위치가 될 수 있는 보다 적은 노드를 추출하여 탐색 범위를 축소시킨다. 이 축소된 그래프에 대해 Han^[2]의 5개 위치에 대한 다중 경로 탐색(multiple path search)이 아닌 단일 경로 탐색(single path search)법을 제안하여 Han^[2] 알고리즘에 비해 보다 단순하면서도 보다 최적해를 찾는 방법을 제안한다.
본 논문에서는 주어진 대상 도시의 노드들 n개 중에서 pop/(p+q)이상의 고객을 확보할 수 없는 후보 위치가 되지 못하는 노드들을 최소신장트리를 구하여 제외시켜 탐색 대상을 축소하였다. 축소된 그래프의 노드들 n′를 대상으로 F_A의 p개 점포가 존재하는 경우 n′╲p개 노드들 중에서 F_B의 첫 번째 위치(q=1)로 최대 고객 확보지점을 선정하였다.
본 장에서는 FB의 q(1≤q≤p-1)개 점포 위치를 결정하기 위해 주어진 도시의 노드 n=55개 전체를 대상으로 하지 않고, 사전준비 단계에서 이를 축소하는 기법을 적용한다.
본 장에서는 표 2의 11개 데이터인 F_A(p=5)인 경우 F_B를 CA로 구하고, Han^[2]의 IEA와 결과를 비교하였다. 여기서 마지막 2개 데이터인 {6,8,13,16,31}과{4,21,22,36,38}은 p=q에 대한 Lee et al.
이 문제에 대해 기존의 방법은 다항시간으로 해를 구하는 규칙을 찾지 못해 메타휴리스틱 기법을 적용하거나 정확한 위치를 선정하지 못해 최대 고객 확보 위치 상위 5개 지점 각각을 기준으로 찾는 방법을 제안하였다. 그러나 이 알고리즘은 최적 해를 찾지 못하는 단점을 갖고 있어 완벽한 알고리즘이라고 할 수 없다.
본 논문에서는 n-p개 노드를 대상으로 하지 않고, q의 후보위치가 될 수 있는 보다 적은 노드를 추출하여 탐색 범위를 축소시킨다. 이 축소된 그래프에 대해 Han^[2]의 5개 위치에 대한 다중 경로 탐색(multiple path search)이 아닌 단일 경로 탐색(single path search)법을 제안하여 Han^[2] 알고리즘에 비해 보다 단순하면서도 보다 최적해를 찾는 방법을 제안한다. 2장에서는 Han^[2] 알고리즘의 문제점을 고찰한다.
Han^[2]은 다항 시간으로 해를 구하는 규칙을 찾고자 하였다. 이를 위해 q=1,2,...,p-1로 증가시키면서 해를 구하는 구성법(constructive method)을 제안하였다. 이 문제는 q가 증가할수록 선택된 위치들과의 근접 거리로 인해 F_A의 경쟁업체 고객을 빼앗기 보다는 F_B업체 자신의 고객을 빼앗은 경우가 발생하여 기존에 확정된 위치가 변경되는 문제점을 갖고 있다.

성능/효과

식 (1)에 의거 결국에는 폐쇄되는 점포를 구한 결과는 표 3에 제시되어 있다. 11개 F_A위치에 따른 q=1,2,3,4 44개 데이터에 대해, 모든 경우에 T이하가 되는 점포들이 폐쇄되는 현상을 발견할 수 있었으며, 이 경우 F_B의 일부 데이터인 9개에 대해 특정 점포가 고객을 확보하지 못하고 있음을 알 수 있다. 이들 점포는 F_A 점포가 폐쇄될 때까지 적자를 내지만 계속 운영한다면 F_A 점포 폐쇄 이후에는 흑자로 반전시킬 수 있음을 알 수 있다.
p=4에서 7개 노드들 중에서 {1} 노드가 추가되었으며, 이로 인해 {9} 노드의 확보 고객수가 감소되었다. 따라서 {9}와 교환 가능한 노드가 있는지 여부를 검증하기 위해, {9}의 N_G(9)={10,6,42}에 대해 추가확보 고객 수를 계산한 결과 344, -25와 -202.5를 나타내{9}를 이동시킬 수 있는 노드가 존재하지 않아 {9,32,49,1}로 최종 확정되었다.
제안된 알고리즘을 11개 F_A 위치에 대해 적용한 결과 Han^[2]의 IEA에 비해 보다 좋은 결과를 얻었다.
표 2의 44개 경우 수를 분석한 결과, F_A={6,8,13,16,31}, F_B(q=1)을 제외한 43개 데이터에 대해 F_B점포들은 pop/(p+q)이상의 고객을 확보하는 결과를 얻었다. 또한, q=p 대신 q=p-1개 점포만을 개설하고도 시장을 과반수(50%) 이상 확보한 경우는 11개 중 6개로 나타나 굳이 1개 점포를 추가로 개설하지 않고도 효과를 극대화시킬 수 있음을 알 수 있다.

후속연구

이 경우 계속 적자를 나타내는 점포는 44개 데이터 중에서 3개로 감소하였다. 그러나 이 경우에도 추가적으로 F_A가 폐쇄될 점포가 반드시 존재하여, F_A가 추가로 폐쇄될 때까지만 견디면 생존이 가능할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	FA의 p개 점포가 운영되고 있는 상황에서 최대 고객 확보 위치를 어떻게 결정하는가?	Step 1. FA의 p개 점포가 운영되고 있는 상황에서, 최대 고객 확보 위치를 q=1의 첫 번째 노드로 결정한다.
	탐색 대상이 축소 되는 경우는 어떤 떄인가?	본 논문에서는 주어진 대상 도시의 노드들 n개 중에서 pop이상의 고객을 확보할 수 없는 후보 위치가 되지 못하는 노드들을 최소신장트리를 구하여 제외시켜 탐색 대상을 축소하였다. 축소된 그래프의 노드들 n′를대상으로 FA의 p개 점포가 존재하는 경우 n′╲p개 노드들 중에서 FB의 첫 번째 위치(q=1)로 최대 고객 확보지점을 선정하였다.
	정확한 해를 다항시간으로 구하는 알고리즘이 알려져 있지 않다는 가정하에 Ant System+Tabu Search의 하이브리드형 메타휴리스틱 기법을 적용하여 해를 구하고자 하는 문제는 무엇인가?	[1] 기존 연구는 대부분 p=q로 동일 점포수를 개설하는 경우를 연구하였으나, 본 논문은 p>q인 경우를 고려한다. 본 논문은 이 상황에서 어느 위치에 FB의 q개의 점포를 개설하는 것이 최적인지를 결정하는 문제를 다룬다.

참고문헌 (8)

R. Colome, H. R. Lourenco, and D. Serra, "A New Chance-Constrained Maximum Capture Location Problem", Annals of Operations Research, Vol. 122, No. 1-4, pp. 121-139, Sep. 2003, doi:10.2139/ssrn.394940
T. Y. Han, "A Study of the Decision on the Minimum Number and Location of Sporting Goods Department for Securing the Largest Market Share", Journal of the Korean Society of Sports Science, Vol. 24, No. 1, pp. 557-570, Feb. 2015, uci: G704-001369. 2015.24.1.079
D. Serra and C. ReVelle, "Market Capture by Two Competitors: The Pre-Emptive Location Problem", Economics Working Paper 39, Dept. of Economics and Business, Universitat Pompeu Fabra, 1993.
S. B. Choi, B. G. Kim, and T. Y. Han, "Sports Shop Location Strategy to Maximize the Market Share Using Divide-and-Conquer Strategy," Journal of the Korean Society of Sports Science, Vol. 23, No. 2, pp. 309-320, Apr. 2014, uci: G704-001369.2014.23.2.018
S. U. Lee, Y. S. Lee, S. B. Choi, and T. Y. Han, "Location Strategy of Sports Outlets to Maximize the Market Share," Journal of the Institute of Internet, Broadcasting and Communication, Vol. 13, No. 3, pp. 93-101, Jun. 2013, doi:10.7236/ JIIBC.2013.13.3.93
S. U. Lee, "New Store Positioning Algorithm to ensure Competitive Advantage in Monopoly Market," Journal of the Institute of Internet, Broadcasting and Communication, Vol. 18, No. 5, pp. 251-257, Oct. 2018, doi:10.7236/JIIBC.2018. 18.5.251
S. U. Lee, "Decision Algorithm for Survival New Establishment Stores Location in Monopoly Market," Journal of the Institute of Internet, Broadcasting and Communication, Vol. 18, No. 6, pp. 213-220, Dec. 2018, doi:10.7236/ JIIBC.2018.18.6.213
D. Serra, C. ReVelle, and K. Rosing, "Surviving in a Competitive Spatial Market: The Threshold Capture Model", Journal of Regional Science, Vol. 39, No. 4, pp. 637-650, Dec. 2002, doi:10.1111/0022-4146.00153

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증