ORMSwareTM is a proprietary quantitative modeling and programming system developed by US Army veteran Reginald Joules at Ushar Enterprises Inc, Littleton, Colorado, USA, with keen interest in national defense problems
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).
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):
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):
The following ORMSware functions/procedures are for tracking, checking and writing travel history of a surrogate, making the implementation of the above algorithm easy:
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:
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.
Click to go to summaries of all examples