CODEWITHSUNDEEP
pythonpython-3.xpython-2.7
Anis Boudieb
Anis Boudieb

Reputation: 85

An assignment problem of flights into slots with a constraint?

I have problem with allocating slots to flights arriving at an airport (assignment problem).

I have the following information:

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

(which means intervals for example slot 1 : "4:45" to "4:59")

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

(How many flights we can assign to 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]`

I have calculated:

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

(it means which slot each flight belongs)`

So, I need to allocate each flight to slot under the constraint of capacity. For example, slot 1 (4:45) cannot take more than one flight, slot 2 (5:00) cannot take more than two flights..etc.

I have managed to allocate slots to each flights under the constraint that I just explained above using this code:

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]

My problem is I want to add another constraint that implement a priority scheme to a flight that has more than 10 hours of flight (Duration_flights > 1000).

I was thinking I could start with the exemptions and assign them first using their indices as:

exempted_flights_indices = [2, 4, 6]

In this case my result would be:

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

How to add the duration constraint in my code please?

Upvotes: 1

Views: 149

Answers (1)

MarianD
MarianD

Reputation: 14181

This is not a solution for your question, but this is a way to make your code more clear (for applying your other constrains, too).

Use dictionaries, not (calculated) indices - creating them is very easy:

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))

(I changed your capitalized names to all lowercase letters - see PEP 8 - Function and Variable Names.)

So you will obtain dictionaries

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

and

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}

Also, instead of times expressed as strings it is better to use the built-in module datetime — you will be then able to compare times:

import datetime

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

Upvotes: 1

Related Questions