[논문]항공사 비정상 운항 복구를 위한 리-타이밍 전략과 개미군집최적화 알고리즘 적용

김국화; 채준재

doi:10.11627/jkise.2017.40.2.013

항공사 비정상 운항 복구를 위한 리-타이밍 전략과 개미군집최적화 알고리즘 적용
Airline Disruption Management Using Ant Colony Optimization Algorithm with Re-timing Strategy 원문보기

Journal of Korean Society of Industrial and Systems Engineering = 한국산업경영시스템학회지, v.40 no.2, 2017년, pp.13 - 21

김국화 (한국항공대학교 항공교통물류학부) , 채준재 (한국항공대학교 항공교통물류학부)

Abstract ▼ AI-Helper

Airline schedules are highly dependent on various factors of uncertainties such as unfavorable weather conditions, mechanical problems, natural disaster, airport congestion, and strikes. If the schedules are not properly managed to cope with such disturbances, the operational cost and performance are severely affected by the delays, cancelations, and so forth. This is described as a disruption. When the disruption occurs, the airline requires the feasible recovery plan returning to the normal operations in a timely manner so as to minimize the cost and impact of disruptions. In this research, an Ant Colony Optimization (ACO) algorithm with re-timing strategy is developed to solve the recovery problem for both aircraft and passenger. The problem consists of creating new aircraft routes and passenger itineraries to produce a feasible schedule during a recovery period. The suggested algorithm is based on an existing ACO algorithm that aims to reflect all the downstream effects by considering the passenger recovery cost as a part of the objective function value. This algorithm is complemented by re-timing strategy to effectively manage the disrupted passengers by allowing delays even on some of undisrupted flights. The delays no more than 15 minutes are accepted, which does not influence on the on-time performance of the airlines. The suggested method is tested on the real data sets from 2009 ROADEF Challenge, and the computational results are compared with the existing ones on the same data sets. The method generates the solution for most of problem set in 10 minutes, and the result generated by re-timing strategy is discussed for its impact.

주제어

AI 본문요약
AI-Helper

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

문제 정의

[23]과 같이 항공기와 승객의 복구 문제에 ACO 알고리즘을 적용하고자 한다. 기존 연구와 다르게 본 연구는 ACO 알고리즘에 리-타이밍을 고려함으로써 총 비용 및 고객이 겪는 불편함을 최소화하고자 한다. 본 연구에서 리-타이밍은 비정상 운항의 영향을 받지 않은 항공편에 대해 일정 범위 내에서 지연을 허용하는 것을 의미한다.
본 연구에서는 고객과 항공기를 고려한 항공사 복구 문제를 풀기 위해 항공편 리-타이밍을 적용한 개미 군집 최적화 알고리즘을 제안하였다. 제안한 알고리즘을 2009 Roadef Challenge에서 사용되었던 문제들로 실험해 보았고, 대부분의 시나리오에서 더 좋은 값을 얻을 수 있었다.
본 연구에서는 이러한 전략이 항공사 스케줄 복구 문제에도 유용할 것이라고 판단했다. 비정상 운항 시에 환승 항공편을 놓친 승객들은 이후 다른 항공편을 제공해서 목적지에 도달할 수 있도록 해야 한다.
추가적으로 리-타이밍 전략이 스케줄 복구비용에 미치는 영향을 확인하기 위하여 해당 전략을 포함 했을 때와 하지 않았을 때의 비용 변화를 확인해 보았다. ［Figure 6］는 실험 결과 그래프로 각 시나리오 별로 목적함수의 개선율을 보여준다.

가설 설정

특히 지연의 정도가 길지 않다면 서비스 만족도에 큰영향을 미치지 않고서도 문제를 해결할 수 있을 것이다.　따라서 본 연구에서는 허용 가능 지연 시간을 항공사의 정시성(On-Time Performance) 평가에 영향을 미치지 않는 15분으로 설정했다[14, 15]. 국내 공항의 경우에는 30분을 기준으로 하고 있으나, 보다 현실적이고 국제적인 기준을 사용하였다.

제안 방법

이는 처음에 스케줄 계획 단계에서 보강 스케줄(robust schedule)을 구성하기 위하여 제안된 방법으로 고객 지연 시간은 물론이고 이로 인해 항공사가 지불하는 보상비용 또한 감소시킨 바 있다[13]. 개선된 알고리즘은 2009 ROADEF Challenge 데이터를 사용해 기존의 해와의 비교를 통해 성능을 테스트한다. 결과적으로 해당 알고리즘의 성능이 기존보다 개선되었음을 확인했다.

대상 데이터

본 연구에서는 리-타이밍 전략을 적용한 개미 군집 최적화 알고리즘의 성능 평가를 위해 2009 Roadef challenge에서 사용했던 데이터로 실험을 진행했으며, Python을 통해 실험을 수행했다. 2009 Roadef Challenge의 결과 값과의 비교를 위해 최대 연산 시간은 10분으로 대회와 동일하게 설정했다.

이론/모형

본 연구에서는 Zegordi et al.[23]과 같이 항공기와 승객의 복구 문제에 ACO 알고리즘을 적용하고자 한다. 기존 연구와 다르게 본 연구는 ACO 알고리즘에 리-타이밍을 고려함으로써 총 비용 및 고객이 겪는 불편함을 최소화하고자 한다.

성능/효과

결과적으로 본 연구에서는 대부분의 시나리오에서 기존의 값들보다 좋은 해를 찾을 수 있었으나 비정상 운항의 정도가 매우 컸던 A05와 A10 시나리오에 대해서는 값이 개선되지 못했다. 다른 시나리오들과 달리 두 시나리오에 대해서 나은 해를 찾지 못한 이유는 리-타이밍 전략에 대한 유연성이 크게 감소했기 때문으로 판단된다.
개선된 알고리즘은 2009 ROADEF Challenge 데이터를 사용해 기존의 해와의 비교를 통해 성능을 테스트한다. 결과적으로 해당 알고리즘의 성능이 기존보다 개선되었음을 확인했다.
특성이 서로 다른 10개의 문제에서 연산 시간을 10 분으로 제한했고, 결과적으로 8개에 대해서는 기존 해보다 더 나은 값을 찾았으며 나머지 2개의 시나리오에서도 평균보다 좋은 값을 구할 수 있었다. 또한 리-타이밍 전략을 포함한 경우와 아닌 경우에 대한 추가 실험을 통해리-타이밍 전략이 비용 감소에 영향을 미친다는 점을 알수 있었다.
표의 상단부터 차례대로 항공편 개수, 항공기 대수, 공항 개수, 고객 여정개수와 문제가 발생한 항공편, 항공기, 공항 개수, 그리고 스케줄 복구 기간에 대한 특성 값을 의미한다. 모든 시나리오에서 고려되는 항공편, 항공기, 공항의 수를 보면 각각 608개, 85대, 35개로 동일하지만, 고객 여정 개수와 비정상 운항의 원인 및 그 정도, 그리고 복구 기간에는 상호간 차이가 있다.
각 시나리오 별 리-타이밍의 효과 또한 이와 일치하는 결과를 보여준다. 비정상 운항의 영향을　미치는 범위가 다른 시나리오에 비해 컸던 두 시나리오에서 리-타이밍의 효과가 상대적으로 작은 것을 확인했다.
본 연구는 다양한 방면으로 추가 연구가 진행되어야 한다. 실험 결과에 따르면 복구 전략에 따라서 발생 비용에 차이가 크게 발생한 것을 확인했다. 복구 전략에 따른 비용 변화는 기존 연구를 통해서도 밝혀진 바 있다[5, 6, 11].
시나리오 별로 다르긴 하지만 최대 약 2%까지 목적 함수 값을 감소시킬 수 있었다. 전반적으로 발생한 문제의 범위가 크지 않을 때에 효과가 더 좋았으며, 예상대로 시나리오 A05와 A10에서는 다른 시나리오 보다 그 정도가 덜 미치고 있었다.
본 연구에서는 고객과 항공기를 고려한 항공사 복구 문제를 풀기 위해 항공편 리-타이밍을 적용한 개미 군집 최적화 알고리즘을 제안하였다. 제안한 알고리즘을 2009 Roadef Challenge에서 사용되었던 문제들로 실험해 보았고, 대부분의 시나리오에서 더 좋은 값을 얻을 수 있었다. 특성이 서로 다른 10개의 문제에서 연산 시간을 10 분으로 제한했고, 결과적으로 8개에 대해서는 기존 해보다 더 나은 값을 찾았으며 나머지 2개의 시나리오에서도 평균보다 좋은 값을 구할 수 있었다.
제안한 알고리즘을 2009 Roadef Challenge에서 사용되었던 문제들로 실험해 보았고, 대부분의 시나리오에서 더 좋은 값을 얻을 수 있었다. 특성이 서로 다른 10개의 문제에서 연산 시간을 10 분으로 제한했고, 결과적으로 8개에 대해서는 기존 해보다 더 나은 값을 찾았으며 나머지 2개의 시나리오에서도 평균보다 좋은 값을 구할 수 있었다. 또한 리-타이밍 전략을 포함한 경우와 아닌 경우에 대한 추가 실험을 통해리-타이밍 전략이 비용 감소에 영향을 미친다는 점을 알수 있었다.

후속연구

또한 본 연구에서는 승무원 스케줄을 고려하지 않았고, 결과적으로 동일 기종 간의 교체만 허용했다. 따라서 승무원 스케줄을 고려한다면 더욱 현실적인 연구가 될 것이다.
특히 비정상 운항의 정도가 심한 시나리오에서는 방법론에 따라서 목적 함수 값의 차이가 최대 10배까지 발생했다. 따라서 어떠한 시나리오에서도 항상 안정적인 값을 도출할 수 있도록 추가적인 연구가 행해질 수 있을 것이다. 또한 본 연구에서는 승무원 스케줄을 고려하지 않았고, 결과적으로 동일 기종 간의 교체만 허용했다.
본 연구는 다양한 방면으로 추가 연구가 진행되어야 한다. 실험 결과에 따르면 복구 전략에 따라서 발생 비용에 차이가 크게 발생한 것을 확인했다.

질의응답

핵심어	질문	논문에서 추출한 답변
	비정상 운항이란 무엇인가?	비정상 운항(disruption)이란 기상이변, 조종사 파업, 갑작스런 항공기 고장과 같이 예기치 못한 사건들로 인하여 운항 스케줄을 계획대로 운영할 수 없는 상태를 말한다[8]. 항공사는 네트워크 특성 상 발생한 문제가 네트워크를 통해 전파되는 파급효과(downstream effect)가 매우 크다[19].
	스케줄 복구를 위해 항공사가 사용하는 방법은 무엇인가?	스케줄 복구를 위해 항공사가 사용하는 방법은 항공편 취소, 항공기 경로 재설정 혹은 대체 항공기 사용, 조종사 재할당 및 대체 조종 인력(reserve crews) 사용, 그리고 승객 재할당 등이 있다. 이때 스케줄 복구의 목적은 발생한 비정상 운항 및 이로인한 네트워크 파급효과를 최소화하는, 실행 가능한 복구 스케줄을 찾는 것이다.
	항공기 교체는 무엇에 효과적인가?	항공기 교체는 서로 다른 두 항공기의 경로를 서로 바꾸는 것이다. Talluri[18]에 따르면 해당 방법은 총 항공편 지연 시간을 줄이는데 효과적이라고 알려져 있다. 고객 재할당은 가능한 최소 지연 시간 내에 그들의 목적지에 도달할 수 있도록 다른 항공편에 재할당하는 방법이다.

참고문헌 (23)

Abdelghany, A., Ekollu, G., Narasimhan, R., and Abdelghany, K., A Proactive Crew Recovery Decision Support Tool for Commercial Airlines during Irregular Operations, Ann. Oper. Res., 2004, Vol. 127, No. 1-4, pp. 309-331.

상세보기
Aloulou, M.A., Haouari, M., and Mansour, F.Z., Robust aircraft routing and flight retiming, Electron. Notes Discret. Math., 2010, Vol. 36, No. C, pp. 367-374.

상세보기
Ball, M., Barnhart, C., Nemhauser, G., and Odoni, A., Chapter 1 Air Transportation : Irregular Operations and Control, Handbooks in Operations Research and Management Science, 2007, Vol. 14, No. C, pp. 1-67.
Bratu, S. and Barnhart, C., Flight operations recovery : New approaches considering passenger recovery, J. Sched., 2006, Vol. 9, No. 3, pp. 279-298.

상세보기
Castro, A. J. M. and Oliveira, E., Airline Operations Control : A New Concept for Operations Recovery, Airline Industry : Operations and Safety, 2011.
Chen, X., Chen, X., and Zhang, X., Crew scheduling models in airline disruption management, in 2010 IEEE 17th International conference, 2010, pp. 1032-1037.
Clarke, M.D.D., Irregular airline operations : a review of the state-of-the-practice in airline operations control centers, J. Air Transp. Manag., 1998, Vol. 4, No. 2, pp. 67-76.

상세보기
Clausen, J., Larsen, A., Larsen, J., and Rezanova, N.J., Disruption management in the airline industry-Concepts, models and methods, Comput. Oper. Res., 2010, Vol.37, No. 5, pp. 809-821.

상세보기
Dorigo, M. and Di Caro, G., Ant colony optimization : a new meta-heuristic, Proc. 1999 Congr. Evol. Comput. (Cat. No. 99TH8406), 1999, Vol. 2, pp. 1470-1477.
Jafari, N. and Zegordi, S.H., Simultaneous recovery model for aircraft and passengers, in Journal of the Franklin Institute, 2011, Vol. 348, No. 7, pp. 1638-1655.

상세보기
Jarrah, A.I., Yu, G., Krishnamurthy, N., and Rakshit, A., A Decision Support Framework for Airline Flight Cancellations and Delays, Transp. Sci., 1993, Vol. 27, No. 3, pp. 266-280.

상세보기
Kohl, N., Larsen, A., Larsen, J., Ross, A., and Tiourine, S., Airline disruption management-Perspectives, experiences and outlook, J. Air Transp. Manag., 2007, Vol. 13, No. 3, pp. 149-162.

상세보기
Lan, S., Clarke, J.P., and Barnhart, C., Planning for Robust Airline Operations : Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions, Transp. Sci., 2006, Vol. 40, No. 1, pp. 15-28.

상세보기
Ministry of Land, Infrastructure, and Transport., Reduced inconveniences for airline passenger due to flight delays, 2016, [Online] : Available: https://www.molit.go.kr/USR/NEWS/m_71/dtl.jsp?id95078299.
Niehues, A., Berlin, S., Hansson, T., Hauser, R., Mostajo, M., and Richter, J., Punctuality : How Airlines Can Improve On-Time Performance, Booz Allen Hamilt., 2001.
Petersen, J.D., Solveling, G., Clarke, J.P., Johnson, E.L., and Shebalov, S., An Optimization Approach to Airline Integrated Recovery, Transp. Sci., 2012, Vol. 46, No. 4, pp. 482-500.

상세보기
Stojkovic, G., Soumis, F., Desrosiers, J., and Solomon, M.M., An optimization model for a real-time flight scheduling problem, Transp. Res. Part A Policy Pract., 2002, Vol. 36, No. 9, pp. 779-788.

상세보기
Talluri, K.T., Swapping Applications in a Daily Airline Fleet Assignment, Transp. Sci., 1996, Vol. 30, No. 3, pp. 237-248.

상세보기
Teodorvic, D., Airline Operations Research, Gordon and Breach Science Publishers, 1988.
Yan, S. and Lin, C.G., Airline Scheduling for the Temporary Closure of Airports, Transp. Sci., 1997, Vol. 31, No. 1, pp. 72-82.

상세보기
Yan, S. and Yang, D.H., A decision support framework for handling schedule perturbation, Transp. Res. Part B Methodol., 1996, Vol. 30, No. 6, pp. 405-419.

상세보기
Yun, H.K., Lee, J.J., and Lee, J.C., A Study on Development of the Aircraft Scheduling System Using ILOG, J. Soc. Korea Ind. Syst. Eng., 2001, Vol. 24, No. 62, pp. 89-102.
Zegordi, S.H. and Jafari, N., Solving the Airline Recovery Problem By Using Ant Colony Optimization, Int. J. Ind. Eng. Prod. Res., 2010, Vol. 21, No. 3, pp. 121-128.

저자의 다른 논문 :

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

연합인증