건설업은 우리나라에서 산업재해로 인한 사망자가 가장 많은 산업으로 더욱 체계적인 관리의 필요하다. 그러나 건설현장을 관리하는 인원은 공사현장의 수에 비해 턱 없이 부족하다. 이러한 상황을 고려하여 본 연구에서는 건설현장을 소수의 인원이 효율적, 경제적을 관리할 수 있는 루트를 한달 단위로 생성하여 현실에 적용할 수 있는 방법론을 제시한다. 본 연구는 VRP 문제를 기반으로 하며 실제 건설현장 위치 데이터와 기간 데이터를 활용하여 문제를 정의하고 해결했다. 기존 VRP 문제와 다르게 방문 가능 날짜를 추가적으로 고려하여 한 달 단위의 차량 경로를 Nearest Neighbor Search, Tabu Search, Large Neighbor Search 세 가지 휴리스틱을 활용하여 문제를 다뤘다. Cplex가 30분 내에 도출한 가장 좋은 해와 비교했을때 평균적으로 5% 개선된 해를 도출하였고, 노드가 많은 경우(90개)에는 Cplex에서는 가능해를 구하지 못했지만 휴리스틱을 활용했을때 1초 이내에 해를 구할 수 있었다. 총 3단계의 프로세스를 거치며 초기의 경로보다 시간과 거리가 감소하였고, 한달마다 업데이트 되는 건설현장 관리 루트를 도출했다는 점에서 큰 의의가 있다.
Large Neighbor Search의 모든 구현 과정은 페어 프로그래밍으로 이루어졌고,
삭제는 랜덤, 복구는 Nearest로 이루어지게 구현하였다.
해당 repo는 Cplex를 활용한 모델 구현과 그를 개선하기 위한 LNS 구현에 대한 부분으로 이루어졌다.