[논문]혼합 정수 선형 계획법을 이용한 수송 계획 모델 설계

박용국; 이민구; 정경권; 원영진

doi:10.5573/ieie.2016.53.11.166

혼합 정수 선형 계획법을 이용한 수송 계획 모델 설계
Design of Mixed Integer Linear Programming Model for Transportation Planning 원문보기

Journal of the Institute of Electronics and Information Engineers = 전자공학회논문지, v.53 no.11 = no.468, 2016년, pp.166 - 174

박용국 (전자부품연구원) , 이민구 (전자부품연구원) , 정경권 (동신대학교 에너지IoT 전공) , 원영진 (부천대학교 전자과)

초록
AI-Helper

본 논문에서는 스포츠 이벤트에서 선수단 수송 계획을 위한 혼합 정수 선형 계획법 모델을 제안하였다. 선수단 수송 계획은 선수단을 다수의 숙소에서 경기장까지 최소의 비용과 빠른 시간 계획을 찾는 것이다. 운행 회수를 의사결정 변수로 하고, 전체 수송비용은 최소가 되어야 하는 목적함수가 된다. 제안한 방법은 혼합 정수 선형 계획법을 이용하여 전역 최적점을 찾을 수 있는 장점이 있다. 제안한 방식의 유용성을 확인하기 위해서 시뮬레이션을 수행하고 스포츠 이벤트 관리 서비스 플랫폼(SEMSP)에서 수송 계획을 구축하였다.

Abstract ▼ AI-Helper

In this paper, we developed a mixed-integer linear programming model for transportation planning of athletes in sports events. The transportation planning of athletes involves finding the lowest-cost and fastest-time plan for distributing athletes from multiple accommodation to stadium. The decision variables associate with the number of driving events, and the total transportation cost is the objective function that needs to be minimized. The proposed method uses mixed integer linear programming to solve transportation problem, thus the global optimality is guaranteed. In order to verify the effectiveness of proposed method, we performed simulation and built the sports event management service platform (SEMSP) for transportation planning.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 스포츠 이벤트 준비 단계에서 선수단 수송을 최적화하는 방식을 제안하였다. 제안한 방식은 혼합 정수 계획법을 이용하여 선수단 규모와 배정된 숙소, 가용 운송수단 등의 정보로부터 선수단 수송 배차 스케줄을 최적화 하였다.
본 논문에서는 스포츠 이벤트의 참여 선수나 관계자, 진행요원 등의 인력 수송 최적화를 위한 혼합 정수 계획법을 이용한 수송 계획 방법을 제안한다. 스포츠 이벤트 참여자를 호텔에서 경기장과 같은 이벤트 장소까지 수송하기 위해서 수송비용이 최소가 되도록 목적함수를 설정하고 수송 자원이 참여자가 대기하는 특정 위치와 이벤트 장소사이를 운행하는 횟수를 의사결정 변수로 하여 탐색한다.
스포츠와 같은 이벤트에서 최적 수송 스케줄링 시스템을 위해서는 선수단 숙소 관련(숙소이름 및 위치, 숙소별 각국 선단 숙박 인원, 개별 숙소와 개별 경기장 사이의 거리 등), 경기장 관련(경기장이름 및 위치, 경기시작 시간, 경기 시작 전 도착 요구 시간 등), 수송자원관련(차량 종류 및 운행 대수, 평균 연비 및 연료비용, 기타 운행경비 등) 정보들이 요구된다. 이러한 정보들을 바탕으로 선수단 숙소에서 개별 경기장까지 비용이최소화되는 최적 수송 스케줄을 도출한다.

제안 방법

구현 흐름은 그림 7과 같다. 네이티브 Java 데이터형을 MATLAB 함수로 전달하고 MATLAB 데이터형으로 변환하여 정수 선형 계획법을 실행하고, 오브젝트 형태로 출력되는 결과를 Web 상에서 표출한다.
본 논문에서 제안한 방법은 목적함수의 구성에 있어서 의사결정 변수가 선형 조합으로 적용되어야 하는 단점이 있다. 이러한 방식으로는 다수의 숙소에서 다수의 경기장으로 선수단을 수송하는 문제에 대해 적용이 어렵기 때문에 유전자알고리즘과 같은 최적화 방법을 도입하여 진행할 예정이다.
그림 1은 수송 용량이 큰 차량이 계속 선택되는 결과로 효율적인 수송을 위해서 전체 수송 완료 시간을 제한할 필요가 있다. 본 논문에서는 식(7)과 같이 호텔과 경기장 사이의 전체 이동 거리와 평균 차량 속도를 이용하여 구한 평균 소요 시간을 구하고 선수단 전체수송 인원과 전체 차량 용량을 이용해 구한 대수적인 이동 횟수를 통해 여유있는 전체 수송 완료 시간을 구한다.
본 논문에서는 의사결정 변수에 고정비용 변수를 추가하고 제약조건을 통해 ‘1’로 고정시켜서 목적함수가 의사결정 변수의 선형 조합 조건을 만족하도록 하였다.
본 논문에서는 스포츠 이벤트의 참여 선수나 관계자, 진행요원 등의 인력 수송 최적화를 위한 혼합 정수 계획법을 이용한 수송 계획 방법을 제안한다. 스포츠 이벤트 참여자를 호텔에서 경기장과 같은 이벤트 장소까지 수송하기 위해서 수송비용이 최소가 되도록 목적함수를 설정하고 수송 자원이 참여자가 대기하는 특정 위치와 이벤트 장소사이를 운행하는 횟수를 의사결정 변수로 하여 탐색한다. 스포츠 이벤트를 대상으로 숙소에서 경기장까지의 선수단 수송에 대해서 수송비용이 최소가 되는 운행 스케줄과 시간 제약이 발생했을 경우 수송 자원을 추가하여 수송 스케줄을 구성하고, 스포츠 이벤트 관리 서비스 플랫폼(SEMSP)의 스포츠 이벤트 준비 기능으로 구현한다.
스포츠 이벤트 참여자를 호텔에서 경기장과 같은 이벤트 장소까지 수송하기 위해서 수송비용이 최소가 되도록 목적함수를 설정하고 수송 자원이 참여자가 대기하는 특정 위치와 이벤트 장소사이를 운행하는 횟수를 의사결정 변수로 하여 탐색한다. 스포츠 이벤트를 대상으로 숙소에서 경기장까지의 선수단 수송에 대해서 수송비용이 최소가 되는 운행 스케줄과 시간 제약이 발생했을 경우 수송 자원을 추가하여 수송 스케줄을 구성하고, 스포츠 이벤트 관리 서비스 플랫폼(SEMSP)의 스포츠 이벤트 준비 기능으로 구현한다.
시간 최적화에서는 전체 수송 시간 제약을 좀 더 엄격하게 설정하였을 때 정수 선형 계획법으로 최적 결과를 탐색하지 못한다면, 입력한 차량 자원에서 수송 용량이 큰 차량에서 작은 차량 순으로 추가하여 다시 탐색을 진행하도록 구성하였다.
시뮬레이션에서는 표 2와 같이 호텔 5곳에 투숙한 선수단을 경기장까지 수송하는 예제를 표 3의 차량 자원을 이용할 때 수송비용이 최적이 되는 운행 횟수를 탐색하였다. 수송 목적지인 경기장은 1곳으로 하며, 차량은 경기장에서 출발하여 호텔에서 선수단을 태우고 다시 경기장으로 이동하여 선수단을 하차 시킨다.
전자정부에서 채택하고 있는 Spring Framework 기반으로 Bean Container와 IoC Container만을 차용하여 사용함으로써 향후 Spring의 업그레이드(전자정부 프레임워크 업그레이드)시 영향을 최소화 하였고, 톰캣 WAS를 사용하였다^[10].
전체 수송 시간 제약을 2시간으로 설정했을 때의 시간 최적 수송 스케줄링 시뮬레이션을 수행하였다. 수송시간 제약을 맞추기 위해서 추가된 차량은 총 7대 이고, 스케줄링 결과는 그림 4와 같다.
본 논문에서는 스포츠 이벤트 준비 단계에서 선수단 수송을 최적화하는 방식을 제안하였다. 제안한 방식은 혼합 정수 계획법을 이용하여 선수단 규모와 배정된 숙소, 가용 운송수단 등의 정보로부터 선수단 수송 배차 스케줄을 최적화 하였다. 수송비용이 최소가 되는 운행 스케줄과 시간 제약이 발생했을 경우 수송 자원을 추가하여 수송 스케줄을 구성하고, 스포츠 이벤트 관리 서비스 플랫폼(SEMSP)의 스포츠 이벤트 준비 기능으로 구현하여 유용성을 확인하였다.
차량 추가 과정에서 7대가 추가 되었을 때에 정수 선형 계획법에서 최적 결과를 출력하였고, 차량 수송 용량이 적은 차량을 다시 대입해서 최적 결과를 출력하는지 확인하게 된다. 최적 결과를 출력한다면 각 차량 추가에 대해서 소요되는 비용을 저장한 후 비용이 최소인 차량을 선택하는 방식이다.
목적함수는 선수단 수송에 있어서 비용이 최소가 되는 운행 회수를 찾는 것으로 식(3)과 같다. 호텔과 경기장까지 왕복 거리(2D_j)의 운행비용과 차량 대여비, 기사 인건비의 고정비로 구성되며 의사결정 변수에 고정비용 변수를 추가하여 선형 조합 조건을 만족하도록 하였다.

대상 데이터

본 논문에서 구성한 제약 조건은 수송인원 제약과 전체 수송 완료 시간 제약, 고정비용 변수 제약으로 구성된다. 인원 제약은 수송에 참여하는 차량의 수송 용량의 총 합이 호텔에 투숙하는 선수단 인원 이상이여야 한다.
제안한 시스템의 유용성을 확인하기 위하여 2015 서울컵 국제핸드볼대회에 적용하였다. 서울컵은 여자대표팀의 1988 서울올림픽 제패를 기념해 2년에 한 번씩 열리고 있으며 직전대회까지는 여자부 경기만 열리다 2016 리우올림픽 아시아지역예선을 앞두고 2015 서울컵 국제핸드볼대회로 명칭을 정하고 남자부까지 함께 개최되었다.
서울컵은 여자대표팀의 1988 서울올림픽 제패를 기념해 2년에 한 번씩 열리고 있으며 직전대회까지는 여자부 경기만 열리다 2016 리우올림픽 아시아지역예선을 앞두고 2015 서울컵 국제핸드볼대회로 명칭을 정하고 남자부까지 함께 개최되었다. 참가 팀은 대한민국 남녀 선수팀과 이집트 남자 대표팀과 프랑스 여자 클럽팀 이시 파리(Issy Paris)로 표 7의 숙소가 배정되었다.

데이터처리

제안한 평가 방식의 유용성을 확인하기 위해서 MATLAB Optimization Toolbox를 이용하여 시뮬레이션을 수행하였다^[9]. 정수 선형 계획법은 Toolbox의 혼합 정수 선형계획법 함수(intlinprog)를 이용하였으며, 모든 의사결정 변수를 정수로 하여 탐색하였다.

이론/모형

. 정수 선형 계획법은 Toolbox의 혼합 정수 선형계획법 함수(intlinprog)를 이용하였으며, 모든 의사결정 변수를 정수로 하여 탐색하였다.

성능/효과

제안한 비용 최적화 기반 수송 스케줄링의 결과는 그림 9와 같고 전체 수송 시간 제약을 1시간 30분으로 설정했을 때의 시간 최적화 기반 수송 스케줄링의 결과는 그림 10과 같다. 2대의 차량이 추가되어 정해진 시간 이내에 수송이 완료됨을 확인할 수 있다.
제안한 방식은 혼합 정수 계획법을 이용하여 선수단 규모와 배정된 숙소, 가용 운송수단 등의 정보로부터 선수단 수송 배차 스케줄을 최적화 하였다. 수송비용이 최소가 되는 운행 스케줄과 시간 제약이 발생했을 경우 수송 자원을 추가하여 수송 스케줄을 구성하고, 스포츠 이벤트 관리 서비스 플랫폼(SEMSP)의 스포츠 이벤트 준비 기능으로 구현하여 유용성을 확인하였다.
최적 결과를 출력한다면 각 차량 추가에 대해서 소요되는 비용을 저장한 후 비용이 최소인 차량을 선택하는 방식이다. 시뮬레이션에서 마지막 차량은 3대 모두 최적 결과로 탐색되었으며 17인승(약374만원), 27인승(약383만원6), 44인승(약378만원)의 비용에서 제안한 알고리즘은 최소 비용인 17인승을 선택하게 되었다.

후속연구

제안한 수송 최적화 방법은 보유한 차량 모두를 대입했을 때 결과를 탐색하지 못했다면 수송 용량이 큰 차량을 임의로 추가하고, 다시 수송 용량이 큰 차량에서 최적 결과가 도출되면 수송 용량이 작은 순서로 다시 차량을 대입하고, 최적 결과를 도출한다. 도출된 결과에서 전체 수송비용이 최소가 되는 차량으로 최종 선택한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	선형 계획법이란 무엇인가?	선형 계획법(Linear Programming)은 주어진 선형 조건들을 만족시키면서 선형 목적 함수를 최적화하는 문제이다. 선형 계획법은 운용 과학, 미시 경제학, 네트워크 경로 최적화 등 많은 분야에서 사용되고 있으며, 선형 계획법의 특수한 경우인 네트워크 흐름과 같은 문제들에 대해서는 여러 특화된 알고리즘들이 연구되어 왔다.
	선수단 수송 계획이란?	본 논문에서는 스포츠 이벤트에서 선수단 수송 계획을 위한 혼합 정수 선형 계획법 모델을 제안하였다. 선수단 수송 계획은 선수단을 다수의 숙소에서 경기장까지 최소의 비용과 빠른 시간 계획을 찾는 것이다. 운행 회수를 의사결정 변수로 하고, 전체 수송비용은 최소가 되어야 하는 목적함수가 된다.
	스포츠 분야에서도 사전 시뮬레이션 방법이 필수적인 이유는 무엇인가?	다양한 국내외 스포츠 이벤트 개최 시 주최측에서 참여자의 수송과 관련한 사전 계획들을 준비하는 과정은 존재하나 대부분의 경우 주최측 담당자의 관리에 의존하여왔으며 IT기술을 적용한 수송 최적화를 위한 시뮬레이션기반 사전 계획 방법의 적용은 전무한 상황이다. 특별히 대형 이벤트인 스포츠 분야에서도 수송과 관련하여 사전 계획들을 준비하지만 사전 계획들의 오류와 현장에서의 잦은 운영 실수로 다양한 문제를 야기해왔다. 이러한 문제를 사전에 방지하고 스포츠 이벤트 개최 시 참여자의 원활한 수송을 지원하기 위해서는 수송최적화를 위한 사전 시뮬레이션 방법이 필수적이다[2].

참고문헌 (10)

Yong Kuk Park, Min Goo Lee, Kyung Kwon Jung, "Transportation Scheduling System based on Cost Optimization," Proceeding of 2016 IEIE Summer Conference, pp. 2016-2017, 2016.
Heather J. Gibson, Kyriaki Kaplanidou, Sung Jin Kang, "Small-scale event sport tourism: A case study in sustainable tourism," Sport Management Review, Volume 15, Issue 2, pp. 160-170, May 2012.

상세보기
Eva Kassens, Transportation planning for mega events : a model of urban change, Thesis (Ph. D.), Massachusetts Institute of Technology, 2009.
Alan Sultan, Linear Programming: An Introduction With Applications, CreateSpace Independent Publishing Platform, July 12, 2011.
Renata Mansini, Wlodzimierz Ogryczak, M. Grazia Speranza, Linear and Mixed Integer Programming for Portfolio Optimization, Springer; 2015 edition (June 10, 2015)
Jae-Han Jeon and Chong-S Rim, "A Minimum Crosstalk Wire Spacing Method by Linear Programming," Journal of the Institute of Electronics Engineers of Korea, v.40, SD, no.11 no.317, pp. 62-72, 2003.
Ki-Bog Kim, and Chi-Ho Lin, "A New ILP Scheduling Algorithm that Consider Delay Constraint," Proceeding of 2005 IEEK Fall Conference, pp. 1213-1216, 2005 Nov. 26, 2005.
Minje Jun and Eui-Young Chung, "On-Chip Crossbar Network Topology Synthesis using Mixed Integer Linear Programming," Journal of the Institute of Electronics Engineers of Korea, vol. 50 no.1, pp. 166-173, 2013.
Matlab Optimization Toolbox
Yong Kuk Park, Min Goo Lee, Kyung Kwon Jung, and Young-Jin Won, "Implementation of Fuzzy Comprehensive Evaluation System for Multi-level Decision Making," Journal of the Institute of Electronics and Information Engineers, vol. 52, no. 7, pp. 169-177, 2015.

원문보기 상세보기

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증