<p>This one's hard, so all help really appreciated!</p>

<p>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.</p>

<p>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.</p>

<p>How can I figure out where to send the trucks next in order to maximize my profit on any given day?</p>

<p>Things to keep in mind:</p>

<ul>
<li>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</li>
<li>The trucks take time to get from one location to another</li>
<li>$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)</li>
</ul>

<p>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.</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2011-12-08T21:52:36.780Z
I am not sure this problem has a finite optimum as stated. Say there existed an optimal solution. Then, since the $p_i$ seem to be monotonically increasing, a truck would do better by cycling a few more steps so that some $p_i$ increases and then going there.
Sasho Nikolov
CC BY-SA 3.0
2011-12-08T22:08:52.880Z
If you know that it is NP-complete, what was the reduction?
mhum
CC BY-SA 3.0
2011-12-08T22:17:39.303Z
You show NP-hardness by reducing an NP-hard problem to your problem, not the other way around.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-12-09T00:55:48.713Z
@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.
Jason
CC BY-SA 3.0
2011-12-09T07:17:16.133Z
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: V*V -> R, time function T: V*V -> 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?
singhsumit
CC BY-SA 3.0
2011-12-09T07:24:03.360Z
i feel you need to specify the nature of these profit functions. Do they have some properties? Also restriction like truck cannot sit idle at any vertex and other conditions to guarantee bounded maxima.
singhsumit
CC BY-SA 3.0
2011-12-12T05:11:03.123Z
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.
Yoshio Okamoto
CC BY-SA 3.0
2015-04-07T10:23:31.953Z
"so they are competing against each other" - so the truck drivers are adversaries? i.e. a truck driver tries to maximize his own profit, rather than maximize the overall profit? In that case the problem likely isn't even in NP.
Tom van der Zanden
<np-hardness><optimization><gt.game-theory><tsp><scheduling>
Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)
Jason
# Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

(Asked by: username_0 on 2011-12-08)

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!

**Tags:** np-hardness, optimization, gt.game-theory, tsp, scheduling

> **Comments:**
> **username_1**: I am not sure this problem has a finite optimum as stated. Say there existed an optimal solution. Then, since the $p_i$ seem to be monotonically increasing, a truck would do better by cycling a few more steps so that some $p_i$ increases and then going there.  
> **username_2**: If you know that it is NP-complete, what was the reduction?  
> **username_3**: You show NP-hardness by reducing an NP-hard problem to your problem, not the other way around.  
> **username_0**: @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.  
> **username_4**: 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: V*V -> R, time function T: V*V -> 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?  
> **username_4**: i feel you need to specify the nature of these profit functions. Do they have some properties? Also restriction like truck cannot sit idle at any vertex and other conditions to guarantee bounded maxima.  
> **username_5**: 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.  
> **username_6**: "so they are competing against each other" - so the truck drivers are adversaries? i.e. a truck driver tries to maximize his own profit, rather than maximize the overall profit? In that case the problem likely isn't even in NP.  

---

## 0 answers

