1

私は、ドライバーと乗客のリストとその場所を受け取り、次の制約に従って、ドライバーに割り当てられた乗客の数を最大化するドライバーへの乗客の割り当てのリストを返す関数を作成しています。

  1. 乗客は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() メソッドの実行中に、最初のタプルの最大値が 1 であっても (2,0) を検索しようとするようです (データ セットには 2 つのドライバーしかありません)。ExactSumConstraint ではなく MaxSumConstraint を使用していることを除けば、エラーが発生するほどコードがどのように異なるのかわかりません。

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)

したがって、ソルバーが変数ごとに制約をグループ化しようとして、 variable の制約になると、(2, 0)この変数がわからないためエラーがスローされます (例にはドライバーが 2 つしかないと仮定します)。

于 2011-02-13T17:11:05.397 に答える