I have a mathematical/computational problem that I think some of you might be able to help me with. It is a planning/scheduling problem involving states, tasks, and resources.
For simplicity, let's explain it like this:
I am a testing engineer at a car company and I am responsible for planning the upcoming testing campaign for our new hybrid (fuel + electric) car model. The goal is to plan in which order to perform a list of tests, to minimize the total number of rides needed.
The constraints are as follows:
- There is a given list of tests that need to be performed
- Each test has a given speed it needs to be performed at (different for each test)
- Each test requires a given amount of energy (from the battery) to be performed
- Each test requires a given amount of time to be performed
- There are three different speeds the car can drive at (excluding stationary)
- Changing speed requires energy and time
- When battery is empty, the ride ends
- After each ride, a new ride starts until all tests have been performed
Because of its hybrid nature, the batteries can also be recharged during the ride at the cost of fuel:
Recharging can be done at any speed and any number of times (or 0)
Recharging returns different amount of energy based on the current speed
Fuel consumption is linear to time (and a known value)
There is a given amount of fuel at the start of each ride
At each time point, the car can do one of three things:
Change speed (costs energy and fuel)
Perform a test (costs energy and fuel)
Recharge batteries (generates energy but costs fuel)
As stated, the goal is to find the optimal order of tests to minimize the number of test rides. Optimally, the solution would find more complex "paths" where the car for example performs tests at a higher speed, changes to a lower speed to recharge, and then goes back up to a higher speed again for more tests.
What way would you go about solving this? Is there a way of structuring this in terms of other, already solved, cases? Note that I am not looking for the optimal solution, but a "good enough" one.
I initially saw this as a graph problem, similar to the more famous Delivery Man Problem (DMP) and Traveling Salesman Problem (TSP). In that case, each test would be a "node" and the goal would be to find the most efficient path through all nodes. But I soon found myself struggling with these differences:
How does the recharging fit with this? Recharging can be performed any number of times, while TSP aims for every node to only be performed once.
Ideally, only the different speeds should be nodes (with fixed costs between them) and there would be a list of tests that need to be performed at each node. This is similar to DMP, but how do I handle multiple tests at the same speed?
I'm sorry for a complex and confusing description, but I'm eager to hear your thoughts. Feel free to ask for any clarification.