초록 ▼

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

쓰레기 수거 차량 경로 문제는 일반적인 차량 경로 문제보다 고려해야 하는 제약 조건이 많아 복잡한 특징을 가진다. 본 논문에서는 차량의 필수 사용 조건, 차량 운행 방식과 같은 쓰레기 수거 산업에 특화된 제약 조건들을 반영한 차량 경로 문제의 새로운 변형을 다루었다. 문제의 도메인에 적합하도록 기존의 혼합 정수 선형계획법 (Mixed Integer Linear Programming : ...

쓰레기 수거 차량 경로 문제는 일반적인 차량 경로 문제보다 고려해야 하는 제약 조건이 많아 복잡한 특징을 가진다. 본 논문에서는 차량의 필수 사용 조건, 차량 운행 방식과 같은 쓰레기 수거 산업에 특화된 제약 조건들을 반영한 차량 경로 문제의 새로운 변형을 다루었다. 문제의 도메인에 적합하도록 기존의 혼합 정수 선형계획법 (Mixed Integer Linear Programming : MILP) 모델을 재구성하였으며, NP-Hard 문제의 특성상 문제의 규모가 커져도 풀 수 있는 하이브리드 유전자 알고리즘을 제안하였다.

쓰레기 수거 차량 경로 문제는 차량에 쓰레기를 할당하는 과정과 할당된 쓰레기들에 대한 차량의 경로를 구하는 문제로 나누어진다. 하지만 알고리즘의 해를 개선하는 과정에서 swap만으로는 한 차량에 할당된 두 개 이상의 쓰레기들을 다른 차량에 할당할 수 없기 때문에 차량 할당과 관련한 실험을 진행하였다. 실험 결과, ‘차량의 운행 거리 최소화’의 목적 하에서는 쓰레기 수거업계 특성상 최소 차량으로 운행할 경우가 가장 효율적이었다.

제안한 알고리즘의 유효성을 검증하기 위하여 소규모 문제에서는 CPLEX Solver와 성능 비교를 진행하였고, 중규모, 대규모 문제에서는 탐욕 알고리즘과 성능 비교를 진행하였다. 실험 결과, 연산 시간과 해의 품질 측면에서 성능이 많이 개선되었다.

또한 ‘차량 운행 시간의 균등 분배’를 목적 함수로 설정한 경우에는 문제의 규모가 클 때 모든 쓰레기를 수거하지 못하는 비효율적인 경로를 생성하게 되므로, 총 운행거리를 최소화하면서 차량에 쓰레기를 할당하는 기준과 확률을 부여하여 차량의 운행 시간이 어느 정도 균등 분배된 해도 구할 수 있도록 알고리즘을 개발하였다.

필수 차량 비율에 따른 운행 거리의 변화에 대한 실험을 진행하여 쓰레기 수거업체의 필수 차량 운영 방식을 제안하였다.

주제어