1

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

  1. 一名乘客只能乘坐一辆车

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

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

我遇到的问题是添加第一个约束。我一直在关注http://uswaretech.com/blog/2009/03/constraint-programming-in-python/上的教程，并且我使用了与他们解决幻方问题类似的风格：乘客的分配to a car 存储为元组（司机，乘客），这些元组存储在列表中。驾驶员和乘客的实际详细信息存储在包含他们的 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。

4

1 回答 1

4

您的变量具有以下形式(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)，它会引发错误，因为它不知道该变量（我假设您的示例只有两个驱动程序）。

于 2011-02-13T17:11:05.397 回答