尽量减少车辆数量但执行相同的路线
想象一下，您有一支由各种车辆组成的车队，其中包括电动汽车。每辆车都有一个跟踪装置来记录其行程。目标是分析这些行程（一个月/一年后），如果减少机队规模，是否可以实现所有历史行程。你能给我指出一个可以做到这一点的算法、研究论文或库吗？启发式的简化也是可能的并且受到欢迎。
与典型的车辆路径问题不同，我们并不是试图找到最佳路线。路线已经给定，无法更改。重新规划未来的旅行不在本分析的范围内。不幸的是，我只找到了可以最小化行程并优化路线的算法和库。
作为一个例子，我们假设有三个位置 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 前往
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当时也闲置，但无法替代这些行程，因为它在另一个地点。
事实上，我们还需要检查电动汽车是否有足够的时间充电。
Imagine you have a fleet consisting of various vehicles, including electronic cars. Each vehicle has a tracking device to record its trips. The goal is to analyze these trips (after a month/year) whether all of the historic trips would have been possible if a fleet size was reduced. Can you point me to an algorithm, research paper, or a library that can do that? Heuristics for simplification are also possible and welcomed.
Unlike in typical vehicle routing problems, we are not trying to find the optimal route. The routes are already given, and cannot be changed. Re-Planning of future trips is not in the scope of this analysis. Unfortunately, I only found algorithms and libraries for minimizing trips that also optimize the routes.
As an example, let's assume that there are three locations A, B, and C. Each location is the home base for a set of vehicles V1, V2, …, VN from where the initial trip can be made.
A recorded trip T has a starting and destination location and timestamps for when the trip started and ended.
Let's say we are analyzing trips of just one day and the following trips are made:
7:00 - 9:00 Vehicle V1 made a trip from location A to B.
8:00 - 9:00 Vehicle V2 made a trip from location B to C.
10:00 - 11:00 Vehicle V3 made a trip from location B to C.
12:00 - 13:00 Vehicle V3 returned from location C to B.
14:00 - 15:00 Vehicle V1 returned from location B to A.
14:00 - 15:00 Vehicle V2 returned from location C to B.
15:00 - 16:00 Vehicle V4 made a trip from location C to A.
16:00 - 17:00 Vehicle V4 returned from location A to C.
In this example, vehicle V1 was idle at location B and could have replaced trips of vehicle V3. Vehicle V4 was also idle at that time but could not replace these trips because it was in another location.
In reality, we would also need to check whether electronic cars doing additional trips had enough time to recharge.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一个假设瞬时充电的算法。收集
到达和出发列表并按时间排序。
现在计算每个位置的运行总和。
跟踪每个位置获得的最小值。这是减去
开始时该位置所需的车辆数量（每个位置一辆车
位置在这里）。
充电似乎确实使这个问题变得更加困难。您可以获得有保证的
通过推迟每辆车到达的时间来高估
需要完全充电。也许这已经足够了
预测目的？
Here’s an algorithm that assumes instantaneous recharging. Gather the
list of arrivals and departures and sort them by time.
Now compute the running sums for each location.
Track the minimum value attained in each location. This is minus the
number of vehicles required in that location at the start (one in each
location here).
Charging does seem make this problem harder. You could get a guaranteed
overestimate by pushing out each vehicle arrival by the amount of time
it would have taken to fully recharge. Maybe that’s good enough for
forecasting purposes?