트럭-트레일러 경로문제 해법을 위한 알고리즘

Abstract

육상운송의 효율화를 위해 최근에 국내외에서 트럭-트레일러 차량을 도입하여 운영하고 있다. 세계적인 종합물류전문회사와 국내 유통기업은 트럭-트레일러를 도입해 적재량과 배송 시간 그리고 탄소배출량을 줄였다. 트럭-트레일러를 운영하기 위해서는 하드웨어적인 트럭, 트레일러와 소프트웨어적인 경로운영에 관한 계획이 무엇보다 중요하다. 그러나 현실에서는 트럭-트레일러 경로에 관한 소프트웨어 개발과 이에 관한 연구는 미비한 편이다. 트럭-트레일러 경로문제는 기존 차량 경로문제에서 확장되고 변형된 형태로 문제사이즈가 커짐에 따라 해결이 어려운 NP-hard 문제에 속한다. 기존연구에서는 트럭-트레일러 경로문제를 정의하였지만 수리 최적화 모델을 제시하지 않았다. 그리고 주어진 예제 문제를 해결하기 위해 2단계 방법, 타부서치, 시뮬레이티드 어닐링 방법을 사용하여 해를 도출하고 개선하였다. 이러한 문제를 해결하기 위해 트럭-트레일러 경로문제에 적합한 수리 최적화 모델을 수립하고 프리미엄 솔버를 사용하여 작은 사이즈 문제를 해결할 수 있도록 한다. 또한, 문제 사이즈가 커짐에 따라 시간이 오래 걸리고 풀리지 않는 문제사이즈가 발생하면 이를 해결하기 위해 메타휴리스틱 방법의 하나인 하이브리드 유전자 알고리즘을 개발하여 다양한 사이즈의 문제를 원활히 해결할 수 있도록 한다.