用Python定义旅行商的线性规划模型

概述使用 Python和PuLP库,我们如何创建线性编程模型来解决旅行商问题(TSP)？ 从维基百科,目标函数和约束是 问题：这是我被困的部分尝试. >我没有在代码中包含最终约束,因为我不知道如何定义它.我相信这个与u变量的约束是为了防止解决方案中的子循环 >此外,求解当前模型会给出决策变量,如x0_0和x1_1等于1.0,这绝对是错误的…我无法弄清楚为什么即使我有 if i == j: 使用 Python和PulP库,我们如何创建线性编程模型来解决旅行商问题(TSP)？

从维基百科,目标函数和约束是

问题：这是我被困的部分尝试.

>我没有在代码中包含最终约束,因为我不知道如何定义它.我相信这个与u变量的约束是为了防止解决方案中的子循环
>此外,求解当前模型会给出决策变量,如x0_0和x1_1等于1.0,这绝对是错误的…我无法弄清楚为什么即使我有

if i == j:        upperBound = 0

Python代码

import pulpdef 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_mapdef 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 pointsdef 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()

我的航点 – 距离 – dur.tsv

数据文件can be found here.

结果

0_0: 1.00_5: 1.01_1: 1.01_15: 1.02_2: 1.02_39: 1.03_3: 1.03_26: 1.04_4: 1.04_42: 1.05_5: 1.05_33: 1.06_6: 1.06_31: 1.07_7: 1.07_38: 1.08_8: 1.08_24: 1.09_9: 1.09_26: 1.010_4: 1.010_10: 1.011_11: 1.011_12: 1.012_11: 1.012_12: 1.013_13: 1.013_17: 1.014_14: 1.014_18: 1.015_1: 1.015_15: 1.016_3: 1.016_16: 1.017_13: 1.017_17: 1.018_14: 1.018_18: 1.019_19: 1.019_20: 1.020_4: 1.020_20: 1.021_21: 1.021_25: 1.022_22: 1.022_27: 1.023_21: 1.023_23: 1.024_8: 1.024_24: 1.025_21: 1.025_25: 1.026_26: 1.026_43: 1.027_27: 1.027_38: 1.028_28: 1.028_47: 1.029_29: 1.029_31: 1.030_30: 1.030_34: 1.031_29: 1.031_31: 1.032_25: 1.032_32: 1.033_28: 1.033_33: 1.034_30: 1.034_34: 1.035_35: 1.035_42: 1.036_36: 1.036_47: 1.037_36: 1.037_37: 1.038_27: 1.038_38: 1.039_39: 1.039_44: 1.040_40: 1.040_43: 1.041_41: 1.041_45: 1.042_4: 1.042_42: 1.043_26: 1.043_43: 1.044_39: 1.044_44: 1.045_15: 1.045_45: 1.046_40: 1.046_46: 1.047_28: 1.047_47: 1.0...

更新的代码

import csvimport pulpdef get_dist(tsp):    with open(tsp,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] 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()

解决方法 最后一个约束不是单个约束.您应该为满足该条件的每对索引i,j添加一个约束：

for i in range(n-1):    for j in range(i+1,n):        m += pulp.lpSum([ u[i] - u[j] + n*x[i,j]]) <= n-1

但是,您首先必须将u_i变量声明为整数,并将cat =’Integer’参数传递给LpVariable：

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

总结

以上是内存溢出为你收集整理的用Python定义旅行商的线性规划模型全部内容，希望文章能够帮你解决用Python定义旅行商的线性规划模型所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。