一个有约束的航班入槽分配问题？

Question

我在为到达机场的航班分配航班时遇到问题（分配问题）

我有以下资料：

time_slots = ['4:45' , '5:00', '5:15', '5:30', '5:45', '6:00']  

（这意味着间隔，例如插槽1：“4:45”到“4:59”）

Capacity_each_slot = [1, 2, 1, 1, 2, 3] 

（我们可以为每个时段分配多少航班）

flights_arrivals = ['4:47', '5:02', '5:10', '5:12', '5:14', '5:33', '5:48', '5:50', '5:58']
Duration_flights = [500, 400, 1200, 350, 1000, 350, 1000, 250, 300]`

我计算过：

Indices_for_arrivals = [0, 1, 1, 1, 1, 3, 4, 4, 4] 

（这意味着每个航班属于哪个时段）`

因此，我需要在容量限制下将每个航班分配到插槽。例如，插槽1（4:45）不能乘坐多个航班，插槽2（5:00）不能乘坐多个航班……等等

在我刚才使用以下代码解释的约束条件下，我成功地为每个航班分配了机位：

def ration_by_schedule(flight_times, capacity, T):
    num_sched_flights = [0 for i in range(T)] # list to keep track of number of flights scheduled in each interval
    new_flight_schedule = [] # list to store new flight times 
    for t in flight_times:
        for s in range(t, T):
             if num_sched_flights[s] < capacity[s]:
                new_flight_schedule.append(s)
                num_sched_flights[s] += 1
                break
        else:
            raise RuntimeError ("Not enough capacity to schedule all flights")
    return new_flight_schedule

schedule = ration_by_schedule(Indices_for_arrivals, Capacity_each_slot, 9)
print(schedule)

Output : [0, 1, 1, 2, 3, 3, 4, 4, 4]

我的问题是，我想添加另一个约束条件，对飞行时间超过10小时（持续时间>1000）的航班实施优先级方案

我想我可以从豁免开始，首先使用它们的指数分配它们：

exempted_flights_indices = [2, 4, 6]

在这种情况下，我的结果是：

new_flight = [0 , 2, 1, 3, 1, 3, 4, 4, 4]

如何在我的代码中添加持续时间约束

Answer 1

这不是问题的解决方案，但这是一种使代码更清晰的方法（用于应用其他约束）

使用字典，而不是（计算）索引-创建它们非常简单：

time_slots = ['4:45', '5:00', '5:15', '5:30', '5:45', '6:00']  
capacity_each_slot = [1, 2, 1, 1, 2, 3] 

capacities = dict(zip(time_slots, capacity_each_slot))

flights_arrivals = ['4:47', '5:02', '5:10', '5:12', '5:14', '5:33', '5:48', '5:50', '5:58']
duration_flights = [500, 400, 1200, 350, 1000, 350, 1000, 250, 300]

durations = dict(zip(flights_arrivals, duration_flights))

（我将您的大写姓名改为所有小写字母-请参见PEP 8 - Function and Variable Names。）

所以你会得到字典

capacities = {'4:45': 1, '5:00': 2, '5:15': 1, '5:30': 1, '5:45': 2, '6:00': 3}

及

durations = {'4:47': 500,
             '5:02': 400,
             '5:10': 1200,
             '5:12': 350,
             '5:14': 1000,
             '5:33': 350,
             '5:48': 1000,
             '5:50': 250,
             '5:58': 300}

此外，最好使用内置模块datetime，而不是用字符串表示时间，这样您就可以比较时间：

import datetime

slot0 = datetime.time(4, 45)              # 4:45
slot1 = datetime.time(5)                  # 5:00   (or datetime.time(5, 0))
...
time_slots = (slot0, slot1, ...)