4

Suppose the salesman had to go back home for the week-end. and suppose the time spent in each city wasn't constant. does any one know of any particular work done to address this version of the problem?

What I mean is each city will have a cost attached to it which states how long he needs to stay in that city (as low as 1 hour and as high as four days) each city of course has a location so distances from each point and to each point can be calculated. the salesman will be making several trips to visit all the cities. each Trip is 5 days long (starts on Monday and finish on Friday). So the objective is to design the trips so that he may visit all cities once (except for home city which he'll be coming back to at the end of every week) in the shortest time possible.

user2681358
  • 99
  • 1
  • 1
  • 8
  • true he has to visit all cities but how would you choose the group of cities that compromise a trip. in a way that optimizes the total time needed. the usual TS solution isn't necessarily optimal in this case because you keep going back to the starting position – user2681358 Feb 23 '14 at 11:21
  • I suspect that, if the time needed to visit a single city is bounded from below, this is strictly easier to optimize than the standard TSP. It may even be optimally solvable in polynomial time. – Ilmari Karonen Feb 23 '14 at 11:23
  • it would look that way, we are essentially solving TSP for a smaller set (each trip). Choosing the trips remains the most time consuming task. an upper bound for the number of cities for each trip can easily be computed. but this seems to me like a very general representation of the TSP so I assumed some work may have already been done on optimizing it. – user2681358 Feb 23 '14 at 11:36
  • First I would have to know the speed of movement from each city to each other city and calculate the time to do so. Then the graph becomes a DiGraph with two edges between each city. Then add the time spent in the city to the cost of the edge. Still, this can only be solved exactly if the number of cities is sufficiently small. – Marichyasana Feb 23 '14 at 12:45
  • 1
    Researchers call this a "vehicle routing problem". – David Eisenstat Feb 23 '14 at 22:45
  • "Vehicle routing problem" that fits perfectly thanks @DavidEisenstat – user2681358 Feb 24 '14 at 06:12

1 Answers1

2

That's just Vehicle Routing with Time Windows:

  • Each "Vehicle" represents 1 work week of the "Salesman"
  • The "Depot" is the "Salesman's Home City"
  • Each "Customer's service duration" is each "City's staying time"
  • Each "Customer's startTime and dueTime" are ignored as City's have no opening or closing time
  • The goal is the same: visit as many Customers (=Cities) in the available time for each Vehicle (=trip).
Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120