为了扩展我的评论，这里有一个简单的方法来处理这个问题。
首先，我们生成“往返行程”，即从枢纽到另一个机场并返回的可行行程（“可行”行程是在第一段完成后离开远程机场的行程）。对于给定的出境航班，我们选择返回最快的航班。请注意，它不一定是“第一个返回的航班”，因为对于给定的路线，持续时间可能会有所不同：例如，你可能有一个去JFK的航班，在上午10点着陆，然后有两个回程航班，一个在10：30起飞，在下午1点到家，第二个在10：35起飞，但在下午12：50更早到达。
第二，我们选择最长的可行往返序列，也就是说，在下一个往返开始之前，必须完成一个往返，这个序列贪婪地选择返回时间的第一个往返，然后选择在那个时间之后离开的第二个往返，再一次选择最快返回的往返，以此类推。
在这两个步骤中，贪婪方法保证我们找到全局最优：
1.在第一步中，为给定的第一段“X”选择比我们所选择的（第一个返回的）更晚返回的往返没有优势。
1.在第二步中，选择下一个比我们选择的更晚返回的往返没有任何优势（同样，第一个返回）。

假飞行数据生成器

为了进行实验，我们编写了一个伪飞行数据的随机生成器，唯一的要求是ARRV_TIME > DPTR_TIME，我们不关心如何合理地安排城市，使距离满足三角不等式，或者飞行时间与距离大致一致。

def gen_random_flights(n, m, t0='2020-01-01', hub='hub'):
    # random airport flight data:
    #   random made-up destinations, random durations
    #   (one-way duration can be totally diff. than return flight)
    # n: number of "other" airports
    # m: number of flights
    airports = pd.unique(
        np.random.randint(65, 65+26, 2*n * 3, dtype=np.uint32).view(f'U3')
    )[:n]  # other airports
    t0 = pd.Timestamp(t0)
    starts = np.random.uniform(size=m + 1).cumsum()
    starts = (pd.to_timedelta(starts / starts[-1], 'day')[:-1] + t0).round('min')

    dur = pd.to_timedelta(pd.Series(np.random.randint(30, 4*60, size=m)), 'min')
    is_dept = np.random.choice([False, True], size=m)
    other_airport = np.random.choice(airports, m)

    flight_num = pd.unique(np.random.randint(0, 10000, 2*m))[:m]
    flight_airline = np.random.choice(['UA', 'AS', 'NZ', 'AC', 'AA', 'VA', 'LH'], m)
    flight_num = [f'{name}{i}' for name, i in zip(flight_airline, flight_num)]

    df = pd.DataFrame({
        'flight': flight_num,
        'DPTR_TIME': starts,
        'ARRV_TIME': starts + dur,
        'ORIG': np.where(is_dept, hub, other_airport),
        'DEST': np.where(is_dept, other_airport, hub),
    })
    return df

例如：

np.random.seed(163)  # chosen for more interesting data
df = gen_random_flights(2, 10)
>>> df
   flight           DPTR_TIME           ARRV_TIME ORIG DEST
0  NZ1149 2020-01-01 02:48:00 2020-01-01 03:37:00  hub  BOH
1    UA70 2020-01-01 04:51:00 2020-01-01 08:04:00  BOH  hub
2  LH3995 2020-01-01 05:27:00 2020-01-01 08:05:00  hub  BOH
3  AS7420 2020-01-01 07:04:00 2020-01-01 10:29:00  hub  BOH
4  UA2777 2020-01-01 08:18:00 2020-01-01 08:50:00  hub  PCH
5  VA3028 2020-01-01 09:09:00 2020-01-01 10:22:00  PCH  hub
6  AA1217 2020-01-01 12:12:00 2020-01-01 13:00:00  hub  BOH
7  AA8825 2020-01-01 15:02:00 2020-01-01 16:39:00  BOH  hub
8  LH9857 2020-01-01 17:36:00 2020-01-01 20:01:00  PCH  hub
9  LH5359 2020-01-01 20:53:00 2020-01-01 23:40:00  hub  PCH

机场代码和航班号当然是随机的。

往返

如上所述，这里的算法简单地为任何出港航班选择第一个可行的返航航班 * 通过到达时间 *。

def make_roundtrips(df, hub='hub'):
    is_outb = df['ORIG'] == hub
    is_back = df['DEST'] == hub

    a = df.loc[is_outb]
    b = df.loc[is_back]

    z = a.merge(
        b, left_on='DEST', right_on='ORIG',
        suffixes=['', '_ret']
    ).query('ARRV_TIME < DPTR_TIME_ret').sort_values('ARRV_TIME_ret')
    z = z.groupby('DPTR_TIME', sort=False).first().reset_index()
    
    return z[[
        'flight', 'DPTR_TIME', 'ARRV_TIME', 'DEST',
        'flight_ret', 'DPTR_TIME_ret', 'ARRV_TIME_ret',
    ]]

我们上面的假数据示例：

z = make_roundtrips(df)
>>> z
   flight           DPTR_TIME           ARRV_TIME DEST flight_ret       DPTR_TIME_ret       ARRV_TIME_ret
0  NZ1149 2020-01-01 02:48:00 2020-01-01 03:37:00  BOH       UA70 2020-01-01 04:51:00 2020-01-01 08:04:00
1  UA2777 2020-01-01 08:18:00 2020-01-01 08:50:00  PCH     VA3028 2020-01-01 09:09:00 2020-01-01 10:22:00
2  LH3995 2020-01-01 05:27:00 2020-01-01 08:05:00  BOH     AA8825 2020-01-01 15:02:00 2020-01-01 16:39:00
3  AS7420 2020-01-01 07:04:00 2020-01-01 10:29:00  BOH     AA8825 2020-01-01 15:02:00 2020-01-01 16:39:00
4  AA1217 2020-01-01 12:12:00 2020-01-01 13:00:00  BOH     AA8825 2020-01-01 15:02:00 2020-01-01 16:39:00

选择往返行程的最长序列

既然我们已经缩小了有趣的往返范围，我们可以通过返回（到达）时间贪婪地选择第一个往返，然后选择下一个往返，等等。

def select_roundtrips(z):
    t = z['DPTR_TIME'].min() - pd.Timedelta(1)
    z = z.sort_values('ARRV_TIME_ret')  # just to make sure
    ix = []
    while True:
        cond = z['DPTR_TIME'] > t
        if not cond.any():
            break
        i = z.loc[cond].index[0]
        ix.append(i)
        t = z.loc[i, 'ARRV_TIME_ret']
    return z.loc[ix]

继续我们上面的假例子：

>>> select_roundtrips(z)
   flight           DPTR_TIME           ARRV_TIME DEST flight_ret       DPTR_TIME_ret       ARRV_TIME_ret
0  NZ1149 2020-01-01 02:48:00 2020-01-01 03:37:00  BOH       UA70 2020-01-01 04:51:00 2020-01-01 08:04:00
1  UA2777 2020-01-01 08:18:00 2020-01-01 08:50:00  PCH     VA3028 2020-01-01 09:09:00 2020-01-01 10:22:00
4  AA1217 2020-01-01 12:12:00 2020-01-01 13:00:00  BOH     AA8825 2020-01-01 15:02:00 2020-01-01 16:39:00

速度

在更现实的数据大小上性能如何？交叉连接不是很昂贵吗？
这个连接的大小实际上是O（p^2），其中p是枢纽机场和给定机场之间的最大航班数，实际上，即使是忙碌的机场，这个值也很小。
对于伪数据，该方法表现得相当好。

df = gen_random_flights(50, 2500)
%timeit select_roundtrips(make_roundtrips(df))
26.1 ms ± 197 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)