Problem N: Traveling salesman with time, rests and costs (still more on tours)

In this small example TSP, we would like to consider the following:

• Maximum time the salesman can travel before resting.
  

• Minimum rest time at each required stop along the way from one location to another.
  

• Asymmetric time and distance between any pair of locations (e.g. time from 1 to 2 is not necessarily equal to time from 2 to 1).
  

• Costs along a segment (link between two adjacent nodes in a tour) traversal must be expressible as any desired function of distance and time, and per diem expenses.
  

• Each possible tour (sequence) must start at the origin (0) and return to the origin.

We extended the previous model for generating sequences to accommodate the above requirements. This formulation can, of course, be easily changed to accommodate a combination of solution strategies such as simple branch-and-bound, to reduce computational load as follows:

• Evaluate tours sequentially and abandon pursuing a permutation when its cumulative performance measure exceeds the lowest measure recorded up to that point.
  
  
• Evaluate tours sequentially and abandon pursuing a permutation when current measure plus smallest possible additional costs to origin exceeds the lowest measure recorded up to that point.
  
  
• As n gets larger, there appears to be way(s) to dampen the typically expected growth of computational load in quick-and-dirty approaches. We will discuss it/them here at a later stage if the thought turns out to be true after some research and testing.

In the simple approach presented here, we allow surrogates to pursue all possible sequences simultaneously and stop execution when the top N surrogates get back to origin (where N can be 1 through n!, n being the number of nodes in the problem). How much memory and computing time will be required to solve a problem this way depends on the relative magnitudes of the performance measures of the sequences. The lesser the difference, the more memory and time will be required. Also, as more sequences-eliminating constraints are added to solve a problem, time and memory required to solve it will be less.

When sequences are examined using branch-and-bound, one at a time, relatively less memory is required as very few surrogates will be in the system simultaneously.

If it is not already open, click here to open a window showing the previous (Permutations) model.

Click the VSD link below to see how we extended the Permutations model to accommodate distance, time and costs in this Salesman model as follows:

• Introduced a subnet called Segment to calculate distance, time and costs of each leg in a tour.
  
  

• Introduced n[8] referencing the Segment subnet and connected a[4] to it to make surrogates go through the costing process encoded in the Segment network.
  
  

• Introduced a[9] to connect n[8] to n[3] to get the surrogates back to it for recursion.
  
  

• Set the Duration property of a[9] to current segment costs of each surrogate; this means that surrogates with lower cumulative segment costs will reach n[3] ahead of others at any given point during model execution.
  
  

• Inserted n[10] between n[3] and n[5] to reference Segment subnet again. Here, the subnet is used to calculate distance, time and costs for the last leg of the tour to get back to origin.
  
  

• Connected n[10] to n[5] with a[11] and set its Duration property equal to the costs for traversing the final leg of each tour.

The surrogate that reaches n[5] first will have traveled the minimum cost route. In the spreadsheet shown above, we can set the number of top alternatives to record. In the Results file at the link below, you can see the top 10 tours.

VSD file: Image of Visio network file describing the model.
Results: Results of this model.