외판원 순회 문제 (TSP)
Traveling Salesman Problem(TSP, 외판원 순회 문제)은 물류 분야에서 널리 쓰이는 고전 문제입니다. TSP에서는 외판원이 도시 목록과 각 도시 쌍 사이의 거리를 알고 있다고 가정합니다. 목표는 출발 도시에서 시작해 모든 도시를 한 번씩 방문한 뒤, 다시 출발 도시로 돌아오는 경로 중 최단 경로를 찾는 것입니다. 이 문제는 계산적으로 매우 어렵지만, Miller-Tucker-Zemlin(MTZ)은 정수 선형계획법으로 풀 수 있음을 보였습니다. 이번 연습에서는 아래 이미지에 보이는 15개 도시의 소규모 데이터셋에 대해 TSP의 목적함수와 일부 제약식을 정의해 보겠습니다. 또한 리스트 컴프리헨션과 함께 LpVariable.dicts를 사용하는 방법을 연습하겠습니다.
세 개의 Python 변수 n, cities, dist가 미리 준비되어 있습니다 \(^{1}\). n은 도시의 개수, cities는 번호가 매겨진 도시 목록, dist는 각 도시 간 쌍별 거리가 들어 있는 pandas DataFrame입니다. 콘솔에서 살펴보셔도 됩니다. 또한 모델도 이미 초기화되어 있습니다.
\(^{1}\) 데이터셋 출처: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
이 연습은 강의의 일부입니다
Python으로 배우는 공급망 분석
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____],
cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____],
lowBound=0, upBound=(n-1), cat=____)