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!

  • 3
    $\begingroup$ If you know that it is NP-complete, what was the reduction? $\endgroup$
    – mhum
    Dec 8, 2011 at 22:08
  • 6
    $\begingroup$ You show NP-hardness by reducing an NP-hard problem to your problem, not the other way around. $\endgroup$ Dec 8, 2011 at 22:17
  • 2
    $\begingroup$ @Kaveh - I'm a PhD student at MIT in computer science and this is adjacent work to our final course project. I think this question is research-level. In fact, one of my teammates want to evolve this into his PhD thesis. $\endgroup$
    – Jason
    Dec 9, 2011 at 0:55
  • 1
    $\begingroup$ 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? $\endgroup$
    – singhsumit
    Dec 9, 2011 at 7:17
  • 2
    $\begingroup$ As a problem in theoretical computer science, the description looks too vague. It's not clear what is to be maximized (or minimized), what is a constraint, what is given as input, when a decision should be made, how other trucks come into play, and so on. Since it's said "I know it's NP-complete," the reduction may clarify the problem, I hope. $\endgroup$ Dec 12, 2011 at 5:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.