This one's hard, so all help really appreciated!
I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it reduces to, similar problems it reminds you of, etc.
The story goes as follows. I own an ice cream truck business with n trucks. There are m stops where I make deliveries. Each location $m_i$ has $p_i$ people waiting for me. After buying their ice cream, everyone leaves (so $p_i$ reduce to zero). $p_i$ increases over time as more people line up to wait for the ice cream trucks. Also, all the truck drivers get commission, so they are competing against each other. All trucks have to be either at a location or moving to the next at any given time.
How can I figure out where to send the trucks next in order to maximize my profit on any given day?
Things to keep in mind:
- Two trucks that stop in the same spot at similar times will only get the profit once, i.e. the people leave after one truck arrives
- The trucks take time to get from one location to another
- $p_i$ increases over time at each stop, but some stops increase faster than others, i.e. some locations are near malls (location, location, location)
I've tried reducing this to a multi-machine scheduling problem, travelling sales person problem, ILP etc., but the main issue is that the $p_i$ at every location (i.e. the distance in the TSP or the job length in the scheduling problem) is constantly changing.
Thanks in advance!