# Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

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.

• is your problem like this?? : Given a graph $G=(V,E)$, and set $W$ of trucks which can start at arbitary nodes, cost function c: VV -> R, time function T: VV -> R and profit function p: V*t -> R, give the order of nodes that needs to be visited such that profit is maximized. Note that once a vertex v is visited, it's profit becomes 0 for any subsequent visit? Dec 9, 2011 at 7:17