在 python-constraint 中添加约束时出现 KeyError

Question

我正在制作一个函数，该函数接收司机和乘客及其位置的列表，并向司机返回乘客分配列表，以最大限度地增加分配给司机的乘客数量，但须遵守以下约束：

1. 乘客只能乘坐一辆车

2. 每节车厢分配的乘客数量不能超过该车厢规定的座位数

3. 每个司机接载所有乘客的行程距离不能超过某个任意常数

我遇到的问题是添加第一个约束。我一直在关注 http://uswaretech.com/blog 上的教程/2009/03/constraint-programming-in-python/ 和我使用了类似的风格来解决他们的幻方问题：将乘客分配给汽车存储为元组（司机，乘客）并且这些元组存储在列表中。驾驶员和乘客的实际详细信息存储在包含他们的 ID、纬度和经度以及每个驾驶员的汽车中有多少个座位的类中。这是我用来构建问题的代码，从文件中提取了测试数据：

self.problem = Problem()
drivers = range(len(self.drivers))
passengers = range(len(self.passengers))
p = [(driver, passenger) for driver in drivers for passenger in passengers]
driver_set = [zip([e1]*len(passengers), passengers) for e1 in drivers]
passenger_set = [zip([e1]*len(drivers), drivers) for e1 in passengers]
self.problem.addVariables(p, [0,1])
for passenger in passenger_set:
    self.problem.addConstraint(MaxSumConstraint(1), passenger)
print self.problem.getSolutions()

以交互方式运行此代码后，我发现我可以在添加约束之前运行 getSolutions() ，但是在运行时出现以下错误整个事情：

Traceback (most recent call last):
  File "allocation.py", line 84, in <module>
    obj1.buildProblem("testdata.txt")
  File "allocation.py", line 81, in buildProblem
    self.problem.getSolutions()
  File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 233, in getSolutions
    domains, constraints, vconstraints = self._getArgs()
  File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 275, in _getArgs
    vconstraints[variable].append((constraint, variables))
KeyError: (2, 0)

似乎在 getSolutions() 方法中的某个时候，它尝试查找 (2,0)，即使第一个元组的最大值是 1（我的数据集中只有 2 个驱动程序）。我运行了教程中的代码，它工作得很好，除了我使用 MaxSumConstraint 而不是 ExactSumConstraint 之外，我只是不确定我的代码有何不同足以导致错误。

Answer 1

您的变量的形式为（driver，passenger）：

p = [(driver, passenger) for driver in drivers for passenger in passengers]
self.problem.addVariables(p, [0,1])

但是，您提供给addConstraint（）的变量的形式为（passenger，driver） >：

passenger_set = [zip([e1]*len(drivers), drivers) for e1 in passengers]
for passenger in passenger_set:
    self.problem.addConstraint(MaxSumConstraint(1), passenger)

因此，当求解器尝试按变量对约束进行分组，并遇到变量 (2, 0) 的约束时，它会抛出错误，因为它不知道该变量（我假设您的示例只有两个驱动程序）。