2
$\begingroup$

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.

  1. Salesman can go to a different city only on weekends, all weekdays of a week he will sell in the same city
  2. The salesman has limited fuel, so he can visit only cities which are in 300(or any other constant) mile radius
  3. 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

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$ – Laakeri Dec 22 '19 at 8:44
  • $\begingroup$ @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). $\endgroup$ – Gamow Dec 22 '19 at 9:40
  • $\begingroup$ Is there still on a constraint that every city must be visited? If not, dynamic programming should work here. $\endgroup$ – Yonatan N Dec 22 '19 at 18:35
  • 1
    $\begingroup$ @YonatanN: Dynamic programming only works if you assume the prices in any city don't depend on whether he has visited the city before. $\endgroup$ – Peter Shor Dec 22 '19 at 20:17
  • $\begingroup$ 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. $\endgroup$ – puneet Dec 25 '19 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.