유전 알고리즘을 이용한 다유종 단일 송유관 스케줄링

Abstract

이 논문에서는 다유종 단일 송유관 문제에 대한 메타 휴리스틱 해법을 유전알고리즘에 기반하여 개발하였다. 다유종 단일 송유관 시스템은 다양한 종류의 기름을 운반하기 위해서 설계된 파이프, 저장시설, 펌프, 밸브 등으로 구성된 시스템이다. 수송되는 다양한 종류의 기름들은 단일근원지인 하나의 정제소에서 단일경로상의 복수개의 저유소로 하나의 송유관을 통해 운반된다. 이 논문에서는 단일근원지로부터 하나의 송유관을 통해 복수개의 목적지로 복수개의 기름을 적절한 시기에 적절한 양만큼 보내는 송유관 스케줄을 생성한다. 송유관 스케줄은 각 저유소의 기름들이 너무 많아서 넘치거나 부족해서 바닥나는 경우가 발생하지 않게 적정재고수준을 만족시키고 제품보호 차원에서 특정유종끼리는 인접할 수 없는 점과 최소 송유량 제약 등 여러 현실적인 제약들을 고려한다. 송유관 스케줄의 목적은 송유관 내부에서 다른 종류의 기름이 인접함으로써 기름이 섞이면서 발생하는 경계유 비용과 단일 송유관을 통해 복수개의 저유소로 운반함에 따라 수송 중 저유를 위해 정지하였다가 다시 움직이게 되는 재시작 용량을 최소화하는 것이다. 실험결과는 개발된 유전알고리즘이 실제 사용되는 휴리스틱 방법보다 더 좋은 결과를 보여준다.