title: Minimize number of vehicles but perform the same routes
body: <p>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.</p>
  <p>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.</p>
  <p>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:</p>
  <p>7:00 - 9:00 Vehicle V1 made a trip from location A to B.</p>
  <p>8:00 - 9:00 Vehicle V2 made a trip from location B to C.</p>
  <p>10:00 - 11:00 Vehicle V3 made a trip from location B to C.</p>
  <p>12:00 - 13:00 Vehicle V3 returned from location C to B.</p>
  <p>14:00 - 15:00 Vehicle V1 returned from location B to A.</p>
  <p>14:00 - 15:00 Vehicle V2 returned from location C to B.</p>
  <p>15:00 - 16:00 Vehicle V4 made a trip from location C to A.</p>
  <p>16:00 - 17:00 Vehicle V4 returned from location A to C.</p>
  <p>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.</p>
  <p>In reality, we would also need to check whether electronic cars doing additional trips had enough time to recharge.</p>