Branch and bound techniques; solving the stagecoach problem by computer. Steven Peacock.
There is a classic problem that is described in many management science and operations research textbooks called the stagecoach problem. The gist of the problem is that a man has to cross the country on a stagecoach. The insurance rates are different for each leg of the journey depending on the dangers that exist in that particular part of the country. A total of 18 stages connect in a network that can get him across the country (Figure 1). The man wants to take the route that will cost him the least.
The same type problem exists today in the planning of projects in business and industry. With the Critical Path Method (CPM), managers examine projects to determine the maximum time it will take to complete all phases of the project.
The normal method for solving these problems by hand is to work your way through the network that connects the important events in the life of a project calculating the minimum and maximum time it may take to get to each node. The purpose of the following program is to get the computer to find the longest or shortest path through the network. The Algorithm
It is quite simple to find the shortest path. Let the computer follow the first path that it finds all the way through the network. This then becomes the shortest path. Next backtrack to the node before the end and examine any other paths that may lead from it. If at any time the current time value exceeds that of the shortest path, we know that particular path cannot be the solution, so we back up again and repeat the process. Each time the computer makes it to the last node without exceeding the minimum time, it has found a shorter path. We then save the shortest path and time. When we run out of nodes to which we can backtrack, we know we are through.
This is fine for the shortest path, but with the longest path, we can't check to see if an alternative route is longer because any path will always be shorter than the longest path until the end is reached. To handle this, the program adds all the individual times together to get a total. All of the individual times are then subtracted from that total. This makes the longer paths have smaller values and the shorter paths have a larger value. Using these new values the computer can solve for the shortest path and then restore the original time values and compute the value of the longest path. Storage of the Network
The real challenge in programming a solution to this problem is how to represent the network structure in Basic. Initially I had thought of using a three- or four- dimensional array. This was a cumbersome process and was discarded early one morning when I was struck with the idea of using strings.
The network is stored in a string array, each element of which represents one node. The first character of that element is the node represented by that element. To speed up search time, the nodes are arranged in the array according to their ACSII code minus 64. The characters following the first one are the modes that are pointed to by the first character.
The paths that connect the nodes are stored in an array individually for time look up purposes. Each element of this array has a two-character value that corresponds with a path in the network. In a corresponding numerical array, the times between the nodes in the string array are stored. The Program
The initialization of the following program for the TRS-80 Model III is divided into three routines. The first ascertains the number of paths and nodes in the network and whether you want to minimize or maximize the network. The second initialization routine gets all of the nodes that are pointed to by each individual node. The last of the initialization routines gets the times between the nodes. If the user decides to maximize, a fourth routine is called to reverse the numbers so that minimization will solve the problem.
The program then sets up to begin solution of the network. The current time is set to zero along with the shortest path string (TT and SP$). The node index and the node pointer (NI% and NP%) are set to 1 and 2 respectively. These values are then pushed on to a stack for later recall. Using these values, the computer then enters the routine that looks up the time value for the path that they indicate. The value is added to the current time and then compared with the minimum time.
If the current time is less than the minimum time, the path is added to the shortest path string and the computer advances to the node indicated by the node pointer (NP%). The computer examines the ASCII value of the node to see if it is the last node. If it is, a shorter path than the existing one has been found and must be saved. If it is not the last node, the node index is set to this node and the node pointer is reset to 2. This gives the computer the first path available from the new node. The computer than returns to the Find Time and Get Line Routine from which it came.
If the current time is greater than the minimum time or the end of the path has been reached and saved, the computer goes to the Check Other Branches Routine. It first checks to see if the stack is completely empty. If it is, the computer knows that it has examined all possible paths. If not, the computer pops the stack of the last node pointer and node index used. The time for that path is then looked up and subtracted from the current time and that path is removed from the shortest path. The node pointer is then incremented to provide the next node that the node index can be combined with to produce a path.
When the node pointer value is greater than the length of the string that corresponds with the node index, there are no more paths to be examined from this node and this routine is entered again. If there are more paths from this node, control is returned to the Set Up Next Line routine at the point where the node index and node pointer values are pushed onto the stack.
when the stack is empty, the computer turns control over to the All Through routine. If this was a maximization problem, the computer restores the original times into the time array and looks up the times from the minimum path string (MP$) to calculate the time needed to traverse the network. The result of the program execution is then printed.