Problem N: Sequencing and traveling salesman with time, rests and costs (the tour continues!)

The ORMSware paradigm involves formulating problems in terms of entities traversing hierarchical logical networks.

In ORMSware's NMOD component, entities are analogical customers and their surrogates traversing analogical service networks. So, it will be no surprise that we have formulated this sequences generating problem in terms of surrogates traversing a logical network.

Click the figure at left to open a separate window showing how we mapped out a logical network of sequences for 4 items to figure out a formulation strategy. Keep in mind that this is not the final ORMSware formulation. This is just part of the thought process involved in getting to the final formulation.

If you want to preview the final algorithm right now without reading through the development process involved, click the links above the Traveling salesman section towards the bottom of this page. You can also go directly to the traveling salesman problem by clicking the TSP link towards the bottom of this page. 

After clicking the figure at left and opening a separate window showing the tree, switch back to this window.

Dashed lines originating out of the two nodes in the middle left serve to indicate that the paths out of those nodes have patterns similar to the exhaustive paths in the top and bottom halves of the diagram. Tracking each path from the Start node, you can see that we can articulate exhaustively every possible ordering sequence of n items for any value of n by mapping out a tree this way.

Notice that while we are formulating this problem as sequences of places which surrogates visit along each path, we are representing each stop as a logical place rather than a physical place. That is why there are many nodes with the same label, whereas in a physically-oriented network there can only be one node representing a given place in that network (as explained further in Note below).

Note (not a good idea!) If this problem were mapped out in a physically-oriented network, it would have looked something like the diagram at left. Though NMOD is only a subset of ORMSware's discrete event simulator component, this diagram and the one above illustrate the difference between virtually all well-known simulators and ORMSware simulator. ORMSware uses a task/activity/process-centric paradigm, while others use location/resource-centric paradigms. To some, the difference may seem subtle, and the diagram at left may seem more efficient than the one above. But, as you will see shortly, the impact is significant in terms of model formulation/implementation ease, speed, and clarity. The power is in the perspective.

Let us switch to the Sequences window now and study the diagram more closely. Notice that we cannot use the mapping process used there to generate sequences if we are to meet the requirement of producing sequences by simply supplying the value of n, without physically altering the model or code. For example, we cannot ask the user to add 5! - 4! = 96 nodes to the model if n = 5 rather than 4; we have to generate 5! sequences simply by knowing n = 5.

Once one has acquired an ORMSware mindset, there is a natural tendency to always to think of problems in terms of network traversals. In the case of this problem, the thought process will most likely be as follows (it may be helpful to check the Sequences diagram while reading the bullets below):

• I know that once I pick an item while generating a sequence, I cannot choose that item again. But, I have the choice of picking any of the items I have not yet chosen to proceed with producing a sequence.
  
  
• When I first start out, I have the choice of n items. If there are 4 items, for example, I will be able to choose 1, 2, 3 or 4. I will consider each item to be a node in a logical network. So, from the node for starting the process, I will have 4 successor nodes. Since I need to enumerate all possible sequences, I will send surrogates to all four nodes.
  
  
• Now, if I go to any of the successor nodes of the Start node, I will have chosen one of the available 4 items. So, from that node, I have to send surrogates to the 3 items available to be chosen. So, that means that when a surrogate is at any given node, I have to know where it already has been to be able to decide the remaining items/nodes to which I want to send surrogates. That is easy to do, since I can take care of all that with the HasBeenAt functions and procedures supplied by ORMSware.
  
  
• I also have to record the path each surrogate travels so that when there are no more successors to a given node, I can list the path which that surrogate took (i.e. the sequence) to get to that final node. That is also easy to do, since I can use the TravelNotes procedures supplied by ORMSwsare.
  
  
• When there are no more surrogates in the Events queue, I know that I have exhausted all possible sequences.

After mapping out a tree as above, the analyst would want to extract the essence of the process to be able to handle the mapping logically and automatically for any given value of n, without having to physically construct different trees for different values of n. That means an iterative or recursive process that will enable surrogates to logically visit all of the n items that have not been visited. Doing this for every surrogate that comes out of the Events queue, all possible sequences can be identified and recorded.

The following 4 steps do just that (it may be helpful to check the Sequences diagram while examining steps below):

1. Look at the travel history of the surrogate arriving at a given node (item) to decide all of the items/nodes to which surrogates should be sent from that node. Notice that only one surrogate will come into a node, since no node has more than one arc leading into it. Send surrogates to all items/nodes that have not been visited.
   
   
2. When a surrogate is on its way to an item not yet visited, record the target item/node in the surrogate's travel history. If the surrogate has already visited all items, record the total path of the surrogate (i.e. a sequence).
   
   
3. Take the next surrogate in the Events queue to send more surrogates to items that surrogate has not visited; if there are no more surrogates in the Events queue, all possible sequences have been found and the mapping process (i.e. finding all sequences) is complete.

The following ORMSware functions/procedures are for tracking, checking and writing travel history of a surrogate, making the implementation of the above algorithm easy:

• InitHasBeenAt: Every surrogate has an allocatable binary array property that indicates whether or not the surrogate has been to a given node in a network. InitHasBeenAt procedure allocates required memory and initializes a surrogate's logHasBeenAt binary array property value, relative to each node, to No.
  
  

• HasBeenAt: Binary function that checks/retrieves the logHasBeenAt array property of a surrogate to see if it has already been to a given node.
  
  

• SetHasBeenAt: Sets the logHasBeenAt property value(s) of a surrogate to Yes/No value supplied by the calling routine.
  
  

• TravelNotes: Appends a string to an expandable chain of strings attached to each surrogate. If you have checked out example Problem 1, you have seen how this works.
  
  

• ShowTravelNotes: Writes the chain of notes created by TravelNotes to any file specified by the analyst.

The final ORMSware formulation for generating all possible sequences of n items can now be easily understood by reviewing files and diagrams at the links below:

VSD file: Image of Visio network file describing the model.
Results: Results of this model (for n=5).

If you have read about the Duration property of ORMSware network objects as well as conceptual clock, either in the Primer or the Hands-on Tutorial, you may have already noticed how this algorithm can be extended to accommodate performance functions for travel between any pair of items.

Even if we use Duration properties to express the cost dimension rather than the time dimension as usual, we can use user-defined surrogate properties to track distance traveled and time consumed. While doing that, we can also incorporate factors such as repair times, rest times, etc. into the model, too, and roll them into total traversal costs.

When the surrogate traveling the optimal path reaches its origin, we can stop searching for the optimal tour and drain other surrogates pursuing other paths from the Events queue. How many surrogates will be in the system at that point and how much memory will be in use will depend upon the cost matrix and cost functions in the model.

Click the link above to see the formulation of a TSP model for minimizing total costs with due consideration of traversal time required with intermediate rest stops.