iRB-Lab/py-ga-VRPTW

해결하는 문제

이 프로젝트는 시간 창이 있는 차량 경로 문제(VRPTW)를 해결하기 위한 파이썬 구현을 제공합니다. 각 고객을 특정 시간 창 내에 방문하고 차량의 용량 제한을 초과하지 않도록 하면서, 차량 풀의 최적 경로를 찾는 것을 목표로 합니다.

작동 방식

이 프로젝트는 유전 알고리즘(GA)을 사용하여 가능한 경로 해를 진화시킵니다. 경로는 고객의 순서열로 구성된 '개체'(염색체)로 표현됩니다. 프로세스는 다음과 같습니다:

• 디코딩: 차량 용량과 시간 제약에 따라 고객 순서열을 실제 하위 경로로 변환합니다.
• 평가: 운송 비용, 차량 가동 비용, 너무 일찍 도착한 경우(대기 비용) 또는 너무 늦게 도착한 경우(지연 비용)에 대한 벌점을 기반으로 해의 적합도를 계산합니다.
• 선택: 루렛 휠 선택을 사용하여 다음 세대에 사용할 개체를 선택합니다.
• 교차: 부분 일치 교차(PMX)를 적용하여 두 부모 해의 특성을 결합합니다.
• 변이: 경로의 랜덤한 세그먼트를 역순으로 바꾸는 역전 연산을 사용하여 유전적 다양성을 유지합니다.

대상 사용자

물류 공학, 운영 연구에 관심이 있거나, 유전 알고리즘과 조합 최적화 문제에의 응용을 공부하는 학생들에게 적합합니다.

주요 기능

• 벤치마크 지원: 솔로몬의 VRPTW 벤치마크 문제(랜덤, 클러스터, 혼합형)를 지원합니다.
• 유연한 데이터 입력: 텍스트 및 JSON 형식의 문제 인스턴스를 지원하며, 서로 변환하는 유틸리티도 제공합니다.
• 사용자 정의 인스턴스: 사용자가 자신의 맞춤형 루트 데이터를 정의하고 알고리즘을 실행할 수 있습니다.
• 세부적인 GA 구현: 선택, 교차, 변이, 적합도 평가 등의 핵심 GA 구성 요소를 명확하게 구현합니다.