1

我正在使用python-constraint库来解决 CSP 问题,以便为机场的每个航班预留舱位。我需要将Bays:('A1', 'A2', 'B1', 'B2', 'C1')分配给Flight :('MI428', 'UL867', 'QR664', 'TK730', 'UL303')变量集的地方。

将值分配给第二组时几乎没有约束。这是我的代码

from constraint import *

problem = Problem()

flight_names = ['MI428', 'UL867', 'QR664', 'TK730', 'UL303']

bays_list = ['A1', 'A2', 'B1', 'B2', 'C1']

problem.addVariables(flight_names, bays_list)

bay_compat = {'MI428':['A1', 'A2', 'B1'], 'UL867':['B1', 'B2'], 'QR664':['A2', 'B1', 'B2'] , 'TK730':['C1', 'A1'], 'UL303':['B2', 'C1']}

for flight in flight_names:
    problem.addConstraint(lambda fl: fl in bay_compat[flight], [flight])

solutions = problem.getSolutions()

print (solutions)

上面的代码工作正常。我想要添加另一个约束,其中每个航班都与特定时间段相关联,称为到达和离开时间之间的时间段。

为此,我创建了另一个列表,如下所示:

time_constraints = {'MI428':(1,3) , 'UL867':(2,7), 'QR664':(3,9), 'TK730':(15,16), 'UL303':(16,17)}

注意:例如,这里的 (1,3) 表示 1.00 am 到 3.00 am

我需要分配舱位,以便同时没有两个航班获得相同的舱位。所以我问如何使用python-constraintaddConstraint()中的方法添加该约束?

4

1 回答 1

0

First you have to add variables that define the time at which flights depart:

flight_names = ['MI428', 'UL867', 'QR664', 'TK730', 'UL303']
flight_times = ['T-' + name for name in flight_names]
bays_list = ['A1', 'A2', 'B1', 'B2', 'C1']

times = range(20)   # or how many times you have

problem.addVariables(flight_names, bays_list)
problem.addVariables(flight_times, times)

Then you have to impose the constraint that each flight must be assigned with a certain time following time_constraints:

time_constraints = {'T-MI428':(1,3) , 'T-UL867':(2,7), 'T-QR664':(3,9), 'T-TK730':(15,16), 'T-UL303':(16,17)}

for flight_time in flight_times:
    start, end = time_constraints[flight_time]
    problem.addConstraint(lambda fl: fl in range(start, end+1), [flight_time])

Now you have to add the "you cannot have two flights at the same bay at the same time" constraints. To do this you need to generate every possible pair of flights:

for flight_one, time_one in zip(flight_names, flight_times):
    for flight_two, time_two in zip(flight_names, flight_times):
        if flight_one == flight_two:
            continue
        problem.addConstraint(
            lambda fl_one, t_one, fl_two, t_two: fl_one != fl_two or t_one != t_two, 
            [flight_one, time_one, flight_two, time_two]
        )

The constraint is satisfied if either the bay used is different or the time used is different.


I'm unable to test the code above, however this should give you a good starting point.

于 2018-10-17T12:54:43.930 回答