尽量减少车辆数量但执行相同的路线
Minimize number of vehicles but perform the same routes
假设您有一支由各种车辆组成的车队，其中包括电动汽车。每辆车都有一个跟踪设备来记录它的行程。目标是分析这些行程（在 month/year 之后）如果减少车队规模，是否所有历史行程都是可能的。你能给我指出可以做到这一点的算法、研究论文或图书馆吗？用于简化的启发式方法也是可能的并受到欢迎。
与典型的车辆路径问题不同，我们不是要寻找最佳路径。路线已经给定，无法更改。重新规划未来的行程不在本分析范围内。不幸的是，我只找到了用于最小化行程并优化路线的算法和库。
例如，假设有三个位置 A、B 和 C。每个位置都是一组车辆 V1、V2、...、VN 的基地，可以从那里进行初始行程。
记录的行程 T 具有开始和目的地位置以及行程开始和结束时间的时间戳。
假设我们正在分析仅一天的行程，并且进行了以下行程：
7:00 - 9:00 车辆 V1 从位置 A 到 B。
8:00 - 9:00 车辆 V2 从位置 B 到 C。
10:00 - 11:00 车辆 V3 从位置 B 到 C。
12:00 - 13:00 车辆 V3 从位置 C 返回到 B。
14:00 - 15:00 车辆 V1 从位置 B 返回到 A。
14:00 - 15:00 车辆 V2 从位置 C 返回 B。
15:00 - 16:00 车辆 V4 从位置 C 到 A。
16:00 - 17:00 车辆 V4 从位置 A 返回到 C.
在这个例子中，车辆 V1 在位置 B 闲置并且可以代替车辆 V3 的行程。车辆V4当时也闲置但无法替代这些行程，因为它在另一个位置。
在现实中，我们还需要检查加班的电动汽车是否有足够的时间来充电。
这是一个假设瞬时充电的算法。收集
到达和离开列表并按时间排序。
Time
Location
Δ
0700
A
−1
0800
B
−1
0900
B
+1
0900
C
+1
1000
B
−1
1100
C
+1
1200
C
−1
1300
B
+1
1400
B
−1
1400
C
−1
1500
A
+1
1500
B
+1
1500
C
−1
1600
A
+1
1600
A
−1
1700
C
+1
现在计算每个位置的 运行 总和。
Time
A
B
C
0
0
0
0700
−1
0
0
0800
−1
−1
0
0900
−1
0
1
1000
−1
−1
1
1100
−1
−1
2
1200
−1
−1
1
1300
−1
0
1
1400
−1
−1
0
1500
0
0
−1
1600
0
0
−1
1700
0
0
0
跟踪每个位置达到的最小值。这是减去
开始时该位置所需的车辆数量（每个
位置在这里）。
充电似乎确实让这个问题变得更难了。你可以获得保证
通过按时间量推迟每辆车的到达来高估
它本来需要完全充电。也许这已经足够了
预测目的？
假设您有一支由各种车辆组成的车队，其中包括电动汽车。每辆车都有一个跟踪设备来记录它的行程。目标是分析这些行程（在 month/year 之后）如果减少车队规模，是否所有历史行程都是可能的。你能给我指出可以做到这一点的算法、研究论文或图书馆吗？用于简化的启发式方法也是可能的并受到欢迎。
与典型的车辆路径问题不同，我们不是要寻找最佳路径。路线已经给定，无法更改。重新规划未来的行程不在本分析范围内。不幸的是，我只找到了用于最小化行程并优化路线的算法和库。
例如，假设有三个位置 A、B 和 C。每个位置都是一组车辆 V1、V2、...、VN 的基地，可以从那里进行初始行程。 记录的行程 T 具有开始和目的地位置以及行程开始和结束时间的时间戳。 假设我们正在分析仅一天的行程，并且进行了以下行程：
7:00 - 9:00 车辆 V1 从位置 A 到 B。
8:00 - 9:00 车辆 V2 从位置 B 到 C。
10:00 - 11:00 车辆 V3 从位置 B 到 C。
12:00 - 13:00 车辆 V3 从位置 C 返回到 B。
14:00 - 15:00 车辆 V1 从位置 B 返回到 A。
14:00 - 15:00 车辆 V2 从位置 C 返回 B。
15:00 - 16:00 车辆 V4 从位置 C 到 A。
16:00 - 17:00 车辆 V4 从位置 A 返回到 C.
在这个例子中，车辆 V1 在位置 B 闲置并且可以代替车辆 V3 的行程。车辆V4当时也闲置但无法替代这些行程，因为它在另一个位置。
在现实中，我们还需要检查加班的电动汽车是否有足够的时间来充电。
这是一个假设瞬时充电的算法。收集 到达和离开列表并按时间排序。
| Time | Location | Δ |
|---|---|---|
| 0700 | A | −1 |
| 0800 | B | −1 |
| 0900 | B | +1 |
| 0900 | C | +1 |
| 1000 | B | −1 |
| 1100 | C | +1 |
| 1200 | C | −1 |
| 1300 | B | +1 |
| 1400 | B | −1 |
| 1400 | C | −1 |
| 1500 | A | +1 |
| 1500 | B | +1 |
| 1500 | C | −1 |
| 1600 | A | +1 |
| 1600 | A | −1 |
| 1700 | C | +1 |
现在计算每个位置的 运行 总和。
| Time | A | B | C |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0700 | −1 | 0 | 0 |
| 0800 | −1 | −1 | 0 |
| 0900 | −1 | 0 | 1 |
| 1000 | −1 | −1 | 1 |
| 1100 | −1 | −1 | 2 |
| 1200 | −1 | −1 | 1 |
| 1300 | −1 | 0 | 1 |
| 1400 | −1 | −1 | 0 |
| 1500 | 0 | 0 | −1 |
| 1600 | 0 | 0 | −1 |
| 1700 | 0 | 0 | 0 |
跟踪每个位置达到的最小值。这是减去 开始时该位置所需的车辆数量（每个 位置在这里）。
充电似乎确实让这个问题变得更难了。你可以获得保证 通过按时间量推迟每辆车的到达来高估 它本来需要完全充电。也许这已经足够了 预测目的？