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.
CodePudding user response：
Here’s an algorithm that assumes instantaneous recharging. Gather the list of arrivals and departures and sort them by time.
| 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 |
Now compute the running sums for each location.
| 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 |
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?