A special case of the travelling salsman (he gets the week-ends off)

Question

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.

Answer 1

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).