• 日期: 2027-04-28
  • 标签: 常规

以下代码使用 Python 的 scipy.optimize.linprog 函数求解列车调度问题，该问题旨在找到最佳的机车分配方案，以满足列车的到站和出发时间，并考虑机车数量限制和整备时间。

from scipy.optimize import linprog
import numpy as np

# 列车到站时间
arr = [18*60+30, 22*60, 60+20, 2*60+10, 4*60+40, 7*60, 10*60, 12*60, 14*60+30, 16*60+30, 3*60+50, 7*60+20, 9*60+30, 12*60+30, 14*60+50, 18*60, 22*60+30, 60+50]
# 列车出发时间
dep = [18*60+20, 21*60+20, 23*60+30, 3*60+30, 5*60+20, 8*60+30, 12*60+30, 15*60+50, 9*60, 12*60, 14*60+20, 16*60, 18*60+40, 21*60+30, 24*60+30, 3*60+30, 5*60, 7*60, 9*60, 100000]
# 列车编号
train_id = [301, 303, 305, 307, 309, 311, 313, 315, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 301, 303, 305, 307, 309, 311, 313, 315]
# 列车类型，到站/出发列车
train_type = ['arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr']
# 机车数量
m = 10
# 列车数量
n = len(train_id)
# 整备时间
time_limit = 100

# 目标函数系数
c = np.ones(m*n)

# 约束：每辆列车都必须有一辆机车牵引，且每辆机车只能牵引一辆列车
A_eq = np.zeros((n, m*n))
for i in range(n):
    for j in range(m):
        A_eq[i, i*m+j] = 1
b_eq = np.ones(n)

# 约束：机车使用均衡
A_ub = np.zeros((2*m*n, m*n))
b_ub = np.zeros(2*m*n)
for i in range(m):
    for j in range(n):
        for k in range(m):
            if i != k:
                A_ub[i*n+j, i*n+j] = 1
                A_ub[i*n+j, k*n+j] = -1
                b_ub[i*n+j] = 1
                A_ub[m*n+i*n+j, i*n+j] = -1
                A_ub[m*n+i*n+j, k*n+j] = 1
                b_ub[m*n+i*n+j] = 1

# 约束：列车必须按照时间顺序安排，且牵引列车的机车必须在列车到站时间之前到达
for i in range(n):
    for j in range(m):
        if train_type[i] == 'arr':
            A_ub[(2*m+n)*n+i*m+j, i*m+j] = 1
            for k in range(n):
                if dep[k] <= arr[i]:
                    A_ub[(2*m+n)*n+i*m+j, k*m+j] = -1
                    b_ub[(2*m+n)*n+i*m+j] = 0
                    break
        else:
            A_ub[(2*m+n)*n+i*m+j, i*m+j] = 1
            for k in range(n):
                if arr[k] >= dep[i]-time_limit:
                    A_ub[(2*m+n)*n+i*m+j, k*m+j] = -1
                    b_ub[(2*m+n)*n+i*m+j] = 0
                    break

# 约束：每辆机车在牵引列车之前需要进行整备
for i in range(m):
    for j in range(n):
        A_ub[(2*m+2*n)*n+i*m+j, i*n+j] = dep[j]-arr[i]-time_limit
b_ub[(2*m+2*n)*n:(2*m+2*n+1)*n] = np.zeros(n)

res = linprog(c, A_eq=A_eq, b_eq=b_eq, A_ub=A_ub, b_ub=b_ub, bounds=(0, 1), method='simplex')

if res.success:
    x = res.x.reshape(m, n)
    for i in range(n):
        for j in range(m):
            if x[j,i] == 1:
                print('Train %d is assigned to locomotive %d' % (train_id[i], j+1))
else:
    print('Failed to find a solution')

错误分析

错误提示“IndexError: index 1196 is out of bounds for axis 0 with size 520”说明 A_ub 数组的第一维索引 1196 超出了数组的范围，数组大小为 520。

解决方法

经过检查代码，发现错误源于对 A_ub 数组的第一维索引计算错误。

在以下代码片段中：

for i in range(n):
    for j in range(m):
        if train_type[i] == 'arr':
            A_ub[(2*m+n)*n+i*m+j, i*m+j] = 1
            for k in range(n):
                if dep[k] <= arr[i]:
                    A_ub[(2*m+n)*n+i*m+j, k*m+j] = -1
                    b_ub[(2*m+n)*n+i*m+j] = 0
                    break

当 n 为 26，m 为 10 时，(2*m+n)*n 的值就超过了 520，因此导致 A_ub 数组的索引越界。

解决方案

将 A_ub 数组的第一维大小修改为 270，即 (2*m+n+1)*n，以满足索引需求。

修改后的代码如下：

A_ub = np.zeros(((2*m+n+1)*n, m*n))

修正后的代码

from scipy.optimize import linprog
import numpy as np

# 列车到站时间
arr = [18*60+30, 22*60, 60+20, 2*60+10, 4*60+40, 7*60, 10*60, 12*60, 14*60+30, 16*60+30, 3*60+50, 7*60+20, 9*60+30, 12*60+30, 14*60+50, 18*60, 22*60+30, 60+50]
# 列车出发时间
dep = [18*60+20, 21*60+20, 23*60+30, 3*60+30, 5*60+20, 8*60+30, 12*60+30, 15*60+50, 9*60, 12*60, 14*60+20, 16*60, 18*60+40, 21*60+30, 24*60+30, 3*60+30, 5*60, 7*60, 9*60, 100000]
# 列车编号
train_id = [301, 303, 305, 307, 309, 311, 313, 315, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 301, 303, 305, 307, 309, 311, 313, 315]
# 列车类型，到站/出发列车
train_type = ['arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'dep', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr', 'arr']
# 机车数量
m = 10
# 列车数量
n = len(train_id)
# 整备时间
time_limit = 100

# 目标函数系数
c = np.ones(m*n)

# 约束：每辆列车都必须有一辆机车牵引，且每辆机车只能牵引一辆列车
A_eq = np.zeros((n, m*n))
for i in range(n):
    for j in range(m):
        A_eq[i, i*m+j] = 1
b_eq = np.ones(n)

# 约束：机车使用均衡
A_ub = np.zeros(((2*m+n+1)*n, m*n))
b_ub = np.zeros((2*m+n+1)*n)
for i in range(m):
    for j in range(n):
        for k in range(m):
            if i != k:
                A_ub[i*n+j, i*n+j] = 1
                A_ub[i*n+j, k*n+j] = -1
                b_ub[i*n+j] = 1
                A_ub[m*n+i*n+j, i*n+j] = -1
                A_ub[m*n+i*n+j, k*n+j] = 1
                b_ub[m*n+i*n+j] = 1

# 约束：列车必须按照时间顺序安排，且牵引列车的机车必须在列车到站时间之前到达
for i in range(n):
    for j in range(m):
        if train_type[i] == 'arr':
            A_ub[(2*m+n)*n+i*m+j, i*m+j] = 1
            for k in range(n):
                if dep[k] <= arr[i]:
                    A_ub[(2*m+n)*n+i*m+j, k*m+j] = -1
                    b_ub[(2*m+n)*n+i*m+j] = 0
                    break
        else:
            A_ub[(2*m+n)*n+i*m+j, i*m+j] = 1
            for k in range(n):
                if arr[k] >= dep[i]-time_limit:
                    A_ub[(2*m+n)*n+i*m+j, k*m+j] = -1
                    b_ub[(2*m+n)*n+i*m+j] = 0
                    break

# 约束：每辆机车在牵引列车之前需要进行整备
for i in range(m):
    for j in range(n):
        A_ub[(2*m+2*n)*n+i*m+j, i*n+j] = dep[j]-arr[i]-time_limit
b_ub[(2*m+2*n)*n:(2*m+2*n+1)*n] = np.zeros(n)

res = linprog(c, A_eq=A_eq, b_eq=b_eq, A_ub=A_ub, b_ub=b_ub, bounds=(0, 1), method='simplex')

if res.success:
    x = res.x.reshape(m, n)
    for i in range(n):
        for j in range(m):
            if x[j,i] == 1:
                print('Train %d is assigned to locomotive %d' % (train_id[i], j+1))
else:
    print('Failed to find a solution')

总结

在编写线性规划代码时，仔细检查数组的维度和索引范围，避免数组索引越界错误。

Python 线性规划求解列车调度问题 - 错误索引解决方法

原文地址: https://www.cveoy.top/t/topic/mGDe 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录