<p>Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints. </p>

<ol>
<li>Salesman can go to a different city only on weekends, all weekdays of a week he will sell in the same city</li>
<li>The salesman has limited fuel, so he can visit only cities which are in 300(or any other constant) mile radius</li>
<li>Every time a salesman travels to a different city he gets new prices for each city for his inventory based on demand and supply in each city. For simplicity, you can assume you have prices for each city for each week are pre-decided. i.e. you have Nx52 matrix where <em>N</em> is the number of cities. The more the price the more will be the profit.</li>
</ol>

<p>To simplify further we can assume a Graph(<em>G</em>) will contain <em>N</em> nodes and each node will point to all cities within a 300-mile radius. </p>



<pre><code>class GraphNode:
    def __init__(self, locID, prices, close_locations)
        self.locID = locID
        self.prices = prices #List of prices in 52 weeks
        self.close_locations = close_locations #List of locations in 300 mile radius
</code></pre>

<p>How to approach this problem. I could not find any resources to get started to solve this. 
Here is a similar kind of question but this is as far I could find a similarity:
<a href="https://stackoverflow.com/questions/24396976/what-is-the-name-for-this-special-case-of-the-travelling-salesman-involving-dyna">https://stackoverflow.com/questions/24396976/what-is-the-name-for-this-special-case-of-the-travelling-salesman-involving-dyna</a></p>

CC BY-SA 4.0
2019-12-22T08:44:13.213Z
Are you interested in actually solving the problem or the computational complexity of it? The phrasing of the problem sounds like this question could be better suited for operations research stackexchange.
Laakeri
CC BY-SA 4.0
2019-12-22T09:40:55.100Z
@Laakeri: The problem clearly is NP-complete, as it contains the static TSP as a special case (where every week all distances remain the same).
Gamow
CC BY-SA 4.0
2019-12-22T18:35:29.857Z
Is there still on a constraint that every city must be visited? If not, dynamic programming should work here.
Yonatan N
CC BY-SA 4.0
2019-12-22T20:17:16.117Z
@YonatanN: Dynamic programming only works if you assume the prices in any city don't depend on whether he has visited the city before.
Peter Shor 
CC BY-SA 4.0
2019-12-25T17:03:40.287Z
No! Your target is to maximize profit, so it is not needed to visit every city. But every time you plan to visit a new city you get a new set of prices, that are independent of cities you previously visited.
puneet
CC BY-SA 4.0
2020-01-06T20:27:58.237Z
@puneet: Can you visit a city twice? And if you do so, do the prices in the city at time $t$ go down if you visited the city before, or are they independent of the sequence of cities you have visited? If they're independent, dynamic programming probably works. Otherwise, you probably have an NP-complete problem.
Peter Shor 
<graph-theory><graph-algorithms><dynamic-programming>
How to approach the "traveling salesman problem" with cost changing every time salesman reaches a new city
puneet
# How to approach the "traveling salesman problem" with cost changing every time salesman reaches a new city

(Asked by: username_0 on 2019-12-22)

Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints. 

Salesman can go to a different city only on weekends, all weekdays of a week he will sell in the same city
The salesman has limited fuel, so he can visit only cities which are in 300(or any other constant) mile radius
Every time a salesman travels to a different city he gets new prices for each city for his inventory based on demand and supply in each city. For simplicity, you can assume you have prices for each city for each week are pre-decided. i.e. you have Nx52 matrix where N is the number of cities. The more the price the more will be the profit.

To simplify further we can assume a Graph(G) will contain N nodes and each node will point to all cities within a 300-mile radius. 
class GraphNode:
    def __init__(self, locID, prices, close_locations)
        self.locID = locID
        self.prices = prices #List of prices in 52 weeks
        self.close_locations = close_locations #List of locations in 300 mile radius

How to approach this problem. I could not find any resources to get started to solve this. 
Here is a similar kind of question but this is as far I could find a similarity:
https://stackoverflow.com/questions/24396976/what-is-the-name-for-this-special-case-of-the-travelling-salesman-involving-dyna

**Tags:** graph-theory, graph-algorithms, dynamic-programming

> **Comments:**
> **username_1**: Are you interested in actually solving the problem or the computational complexity of it? The phrasing of the problem sounds like this question could be better suited for operations research stackexchange.  
> **username_2**: @username_1: The problem clearly is NP-complete, as it contains the static TSP as a special case (where every week all distances remain the same).  
> **username_3**: Is there still on a constraint that every city must be visited? If not, dynamic programming should work here.  
> **username_4**: @YonatanN: Dynamic programming only works if you assume the prices in any city don't depend on whether he has visited the city before.  
> **username_0**: No! Your target is to maximize profit, so it is not needed to visit every city. But every time you plan to visit a new city you get a new set of prices, that are independent of cities you previously visited.  
> **username_4**: @username_0: Can you visit a city twice? And if you do so, do the prices in the city at time $t$ go down if you visited the city before, or are they independent of the sequence of cities you have visited? If they're independent, dynamic programming probably works. Otherwise, you probably have an NP-complete problem.  

---

## 0 answers

