Problem N: Sequencing and traveling salesman with time, rests and costs

While modeling operations management problems such as machine scheduling, vehicle routing, crew scheduling, tool path design, and numerous others, Operations Research/Management Science professionals often come across the issue of generating sequences/permutations. In general terms the issue involves systematically examining all possible ways a given set of items can be arranged/ordered/sequenced, even if all sequences may not be explicitly and exhaustively explored.

The number of possible ways n items can be ordered is n! (factorial), which explodes into huge numbers as n gets larger. For example, the number of ways groups of 2, 3, 4, 5, 6, 7 and 8 items can be ordered are 2, 6, 24, 120, 720, 5040 and 40320 respectively. Note that the issue of interest is not calculating the number of possible sequences (i.e. the factorial), but generating all possible sequences so that their potential (feasibility and performance) values and relevance can be explicitly or implicitly evaluated.

Generating sequences is an issue that arises often in solving many problems, and therefore, is something that is imbedded in many models. Our purpose in showing this example here is simply to convey the mindset involved (i.e. how one tends to think) when solving problems with the help of ORMSware. If you find thinking the ORMSware way about problems makes it easy to visualize them and model them, you will also understand how and why ORMSware serves to dramatically compress time from the point you are presented with a problem to the point you turn around with a clean running model.

Unlike other examples at this site, the first part of this problem (creating permutations) does not require looking at any raw data, or pondering operational matters or business issues. There are no assumptions to be made, and there is nothing subtle to be concerned about. In that sense this is very much a pure, clear textbook problem. Therefore, it should be easy to contemplate and jot down how to solve this problem using other tools or a modern programming language before looking at the ORMSware formulation.

After solving the permutations issue, we will extend this example to model a small Traveling Salesman problem (TSP) with cost functions and asymmetric time and distance matrices, all of which can be as complex as necessary.

To get the most out of this example, take a moment at this point to jot down how to tackle the permutations issue with the easiest tool or language (other than ORMSware) you would be inclined to use, with the following requirements in mind: 

• Users should be able to get a list of all possible ways n items can be ordered by evoking the algorithm with any value of n.
  
  
• Users should not have to add or remove any code/logic to or from the procedure containing the algorithm or change any model configuration definitions based on the size of n.
  
  
• The only limiting factors should be available memory and disk space on the users' computers.

Click Approach link above to see how one would think through this problem when the tool of choice is ORMSware.