Python에서 여행 세일즈맨을위한 선형 프로그래밍 모델 정의

Question

Python 및 PuLP 라이브러리를 사용하여 선형 프로그래밍 모델을 작성하여 TSP (Traveling Salesman Problem)를 해결하는 방법은 무엇입니까? 위키

, 목적 함수와 제약

문제입니다 것은 저는 여기에 붙어 오전 내 부분적인 시도이다.

1. 코드를 정의하는 방법을 알지 못하므로 코드의 최종 제약 조건을 포함하지 않았습니다. 나는 U 변수와이 제약은 현재 모델에 대한 해결,

2. 또한 용액에 서브 사이클을 방지하기위한 것입니다 생각은 '내가 할 수있는 ... 그런 확실히 잘못 1.0 동일되고 x0_0 및 x1_1 등의 의사 결정 변수를 제공합니다 이것이 내가

   if i == j: 
        upperBound = 0 
   

있었다하더라도 그렇게

파이썬 코드

import pulp 

def get_dist(tsp): 
    with open(tsp, 'rb') as tspfile: 
     r = csv.reader(tspfile, delimiter='\t') 
     d = [row for row in r] 

    d = d[1:] # skip header row 
    locs = set([r[0] for r in d]) | set([r[1] for r in d]) 
    loc_map = {l:i for i, l in enumerate(locs)} 
    idx_map = {i:l for i, l in enumerate(locs)} 
    dist = [(loc_map[r[0]], loc_map[r[1]], r[2]) for r in d] 
    return dist, idx_map 


def dist_from_coords(dist, n): 
    points = [] 
    for i in range(n): 
     points.append([0] * n) 
    for i, j, v in dist: 
     points[i][j] = points[j][i] = float(v) 
    return points 


def find_tour(): 
    tsp_file = '/Users/test/' + 'my-waypoints-dist-dur.tsv' 
    coords, idx_map = get_dist(tsp_file) 
    n = len(idx_map) 
    dist = dist_from_coords(coords, n) 


    # Define the problem 
    m = pulp.LpProblem('TSP', pulp.LpMinimize) 


    # Create variables 
    # x[i,j] is 1 if edge i->j is on the optimal tour, and 0 otherwise 
    # Also forbid loops 
    x = {} 
    for i in range(n): 
     for j in range(n): 
      lowerBound = 0 
      upperBound = 1 

      # Forbid loops 
      if i == j: 
       upperBound = 0 
       # print i,i 

      x[i,j] = pulp.LpVariable('x' + str(i) + '_' + str(j), lowerBound, upperBound, pulp.LpBinary) 
      # x[j,i] = x[i,j] 


    # Define the objective function to minimize 
    m += pulp.lpSum([dist[i][j] * x[i,j] for i in range(n) for j in range(n)]) 


    # Add degree-2 constraint 
    for i in range(n): 
     m += pulp.lpSum([x[i,j] for j in range(n)]) == 2 


    # Solve and display results 
    status = m.solve() 
    print pulp.LpStatus[status] 
    for i in range(n): 
     for j in range(n): 
      if pulp.value(x[i,j]) >0: 
       print str(i) + '_' + str(j) + ': ' + str(pulp.value(x[i,j])) 

find_tour() 

이유 t 알아낼

내 - 중간 지점 - 거리 - dur.tsv

데이터 파일 can be found here.

결과

0_0: 1.0 
0_5: 1.0 
1_1: 1.0 
1_15: 1.0 
2_2: 1.0 
2_39: 1.0 
3_3: 1.0 
3_26: 1.0 
4_4: 1.0 
4_42: 1.0 
5_5: 1.0 
5_33: 1.0 
6_6: 1.0 
6_31: 1.0 
7_7: 1.0 
7_38: 1.0 
8_8: 1.0 
8_24: 1.0 
9_9: 1.0 
9_26: 1.0 
10_4: 1.0 
10_10: 1.0 
11_11: 1.0 
11_12: 1.0 
12_11: 1.0 
12_12: 1.0 
13_13: 1.0 
13_17: 1.0 
14_14: 1.0 
14_18: 1.0 
15_1: 1.0 
15_15: 1.0 
16_3: 1.0 
16_16: 1.0 
17_13: 1.0 
17_17: 1.0 
18_14: 1.0 
18_18: 1.0 
19_19: 1.0 
19_20: 1.0 
20_4: 1.0 
20_20: 1.0 
21_21: 1.0 
21_25: 1.0 
22_22: 1.0 
22_27: 1.0 
23_21: 1.0 
23_23: 1.0 
24_8: 1.0 
24_24: 1.0 
25_21: 1.0 
25_25: 1.0 
26_26: 1.0 
26_43: 1.0 
27_27: 1.0 
27_38: 1.0 
28_28: 1.0 
28_47: 1.0 
29_29: 1.0 
29_31: 1.0 
30_30: 1.0 
30_34: 1.0 
31_29: 1.0 
31_31: 1.0 
32_25: 1.0 
32_32: 1.0 
33_28: 1.0 
33_33: 1.0 
34_30: 1.0 
34_34: 1.0 
35_35: 1.0 
35_42: 1.0 
36_36: 1.0 
36_47: 1.0 
37_36: 1.0 
37_37: 1.0 
38_27: 1.0 
38_38: 1.0 
39_39: 1.0 
39_44: 1.0 
40_40: 1.0 
40_43: 1.0 
41_41: 1.0 
41_45: 1.0 
42_4: 1.0 
42_42: 1.0 
43_26: 1.0 
43_43: 1.0 
44_39: 1.0 
44_44: 1.0 
45_15: 1.0 
45_45: 1.0 
46_40: 1.0 
46_46: 1.0 
47_28: 1.0 
47_47: 1.0 



... 

---

업데이트 코드 마지막으로 제약하지 하나의 제약 조건 입니다

import csv 
import pulp 


def get_dist(tsp): 
    with open(tsp, 'rb') as tspfile: 
     r = csv.reader(tspfile, delimiter='\t') 
     d = [row for row in r] 

    d = d[1:] # skip header row 
    locs = set([r[0] for r in d]) | set([r[1] for r in d]) 
    loc_map = {l:i for i, l in enumerate(locs)} 
    idx_map = {i:l for i, l in enumerate(locs)} 
    dist = [(loc_map[r[0]], loc_map[r[1]], r[2]) for r in d] 
    return dist, idx_map 


def dist_from_coords(dist, n): 
    points = [] 
    for i in range(n): 
     points.append([0] * n) 
    for i, j, v in dist: 
     points[i][j] = points[j][i] = float(v) 
    return points 


def find_tour(): 
    tsp_file = '/Users/test/' + 'my-waypoints-dist-dur.tsv' 
    coords, idx_map = get_dist(tsp_file) 
    n = len(idx_map) 
    dist = dist_from_coords(coords, n) 


    # Define the problem 
    m = pulp.LpProblem('TSP', pulp.LpMinimize) 


    # Create variables 
    # x[i,j] is 1 if edge i->j is on the optimal tour, and 0 otherwise 
    # Also forbid loops 
    x = {} 
    for i in range(n+1): 
     for j in range(n+1): 
      lowerBound = 0 
      upperBound = 1 

      # Forbid loops 
      if i == j: 
       upperBound = 0 
       # print i,i 

      # Create the decision variable and First constraint 
      x[i,j] = pulp.LpVariable('x' + str(i) + '_' + str(j), lowerBound, upperBound, pulp.LpBinary) 
      # x[j,i] = x[i,j] 


    # Define the objective function to minimize 
    m += pulp.lpSum([dist[i][j] * x[i,j] for i in range(1,n+1) for j in range(1,n+1)]) 


    # Add degree-2 constraint (3rd and 4th) 
    for i in range(1,n+1): 
     m += pulp.lpSum([x[i,j] for j in range(1,n+1)]) == 2 


    # Add the last (5th) constraint (prevents subtours) 
    u = [] 
    for i in range(1, n+1): 
     u.append(pulp.LpVariable('u_' + str(i), cat='Integer')) 
    for i in range(1, n-1): 
     for j in range(i+1, n+1): 
      m += pulp.lpSum([ u[i] - u[j] + n*x[i,j]]) <= n-1 


    # status = m.solve() 
    # print pulp.LpStatus[status] 
    # for i in range(n): 
    # for j in range(n): 
    #  if pulp.value(x[i,j]) >0: 
    #   print str(i) + '_' + str(j) + ': ' + str(pulp.value(x[i,j])) 

find_tour() 

Answer 1

. 당신은 그 조건을 만족하는 인덱스 i, j의 각 쌍에 대해 하나 개의 제약 조건을 추가해야합니다 :

u = [] 
for i in range(n): 
    u.append(pulp.LpVariable('u_' + str(i), cat='Integer'))