Upon reading this article, the reader should understand the basics of combinatorics and how they are useful to increasing business profit. Further, the reader will be familiarized with the classic combinatorial optimization example of the Traveling Salesperson Problem (TSP), used heavily in artificial intelligence, industrial engineering, and computer science.

We live on a placid island of ignorance in the midst of black seas of infinity, and it was not meant that we should voyage far. - H.P. Lovecraft

Real World Example

In early 2016, a logistics company approached INTP to provide consulting services aimed at helping them decrease their costs, in turn increasing profit. The nature of their business was to determine the routes that a package or inventory would take from the point it left the possession of the entity sending it to its final destination. As the client identified all of the variables involved in this process, it became apparent very quickly that this would entail no trivial solution.

At the head of this process, the inventory could either be picked up at a specified location via courier or freight truck in several major cities or handed directly into a depository at even more numerous available locations. From here, the inventory would sit in the warehouse, accruing storage costs, until the transport phase was to be initiated.

The transport phase entailed either moving the inventory to the final depository, many times iterating through intermediary storage facilities, upon which a team of couriers would deliver the inventory to the final destination. Land transport occurred primarily through freight trucks, USPS (which apparently even FedEx and UPS use somewhat often as the backbone of their transportation model), and airplanes, and cross-continental transport primarily entailed the use of cargo ships and airplanes.

Let us enumerate the complexity of the problem stated above:

1. A request for delivery would enter the system. The inventory would be picked up by a courier if small enough, and by freight truck if it were too large. Either way, the magnitude of human capital was constrained in number and an effective route always needed to be determined, limiting travel distance, time, and costs.

2. The inventory would sit in a warehouse, where it might be batched with other inventory, and sent to another depository, which often would not be the final storage facility. The costs associated with storage, direct labor, and opportunity cost in not transporting ideal batch sizes needed to be minimized.

3. The actual transport mechanism was selected of various options, each with varying capital costs, time costs, and constraints involving the nature of the package itself. It would need to be determined whether the inventory gets sent directly to the final depository, if it were even possible; which depository, if so; or whether it accrues holding costs in a warehouse to be batched with other inventory going to the same destination.

4. The final phase entailed a reverse order of Step 1 above. A team of couriers or freight truck drivers would deliver the package to the final destination, requiring an optimal route and batch selection in order to minimize costs.

5. The time frame for delivery for each of the transport orders needed to be prompt, some more prompt than others.

How would one go about setting an organizational policy to minimize costs at all times? Of course, we suggested minimizing costs with some instantaneous solutions, such as digitizing the forms required to be filled out at each transport node once liability of the inventory had been ceded to the next in line, and automating this process altogether via a system of RFID tags and scanners. The latter option, however, to our knowledge, was not implemented.

Still, the bulk of cost reduction lay in setting a transport policy that continuously delivered the most optimal route for each package in terms of capital expenditure while sticking to the temporal constraints. When dealing with complex problems, one of the first steps to determining a solution is to translate the problem into a simpler one; one that is easier to wrap the mind around. This is where the TSP came to mind.

Traveling Salesperson Problem

Suppose a salesperson was required to visit every major city in the US to peddle their product. They would, of course, wish to minimize the distance they travel, saving on gas, car maintenance, and time. This problem may easily be modeled with an undirected weighted graph where the nodes represent cities and the edges represent distance.

At first glance, this appears to be a trivial problem given the power we associated with computers. Simply find each permutation in routes traveled and select the one which yields the lowest distance. I remember attempting this challenge for an algorithms assignment I took in college. As soon as I ran the program, my RAM and virtual memory would fill up entirely, pounding in the notion that such a brute force approach would not work on a standard computing node. I tried running the program a few times and checking my source code before I realized the futility of the situation. Even brute forcing on the supercomputers my school owned would be impossible. However, for smaller problem sets, finding the shortest route would be possible and quick. From what I recall, the largest amount of cities that I could process via my source code on my laptop was 19. With each additional city added, the number of permutations exhibited factorial growth, causing extreme burden on the processor and memory.

A “good enough” solution to this issue uses one of several cost-minimizing heuristics. A heuristic is a practical means of addressing a problem. It may never determine the shortest path (cost); however, it may get extremely close, all while being implemented on cheap commodity hardware. The alternative brute force method can be extremely expensive for large enough problem sets, and even impossible for many business requirements with our current hardware capabilities.

For example, there exists a heuristic called the nearest neighbor. It is a greedy algorithm, meaning it is myopic in its iterative decisions on which node to visit next. For example, it will always suggest the next closest not-visited city to the salesperson. This algorithm often does not yield a solution within 20% of the optimal value. However, it is a good introduction into combinatorial heuristics.

Another heuristic, the ant colony algorithm, mimics the behavior of ants to arrive at a solution. This is an artificial intelligence approach, in particular, swarm intelligence, where a set of agents with relatively low processing power and memory will work together as a team to accomplish amazing feats. Whenever ants in search of food come across some obstacle, say a rock, some will travel to the left and some will travel to the right. During this process, they will lay down a pheromone trail which evaporates at a set rate. The shorter path will hold higher concentrations of pheromones, as the shorter time it takes to find the food and bring it back to the colony will be traveled more times by an ant. Unlike the nearest neighbor algorithm, the ant algorithm yields solutions that are very near to the optimal route.

There are hundreds, if not thousands, of other heuristics that may be applied to provide some solution that will suffice. The important thing to take away, however, is that for large problem sets, there is a sacrifice in finding the absolute shortest route so that a solution may actually be determined with cost-effective computing resources.

Conclusion

Although we cannot disclose the solution we provide to our client, we do reveal a particular way of viewing combinatorial problems related to business optimization. The complexity of the problem described in the first section was translated into a TSP-style problem from which we determined the most appropriate heuristic to cut costs for our client. As our client previously used an algorithm similar to the nearest neighbor, we had significant room for improvement in cost-reduction via our recommendation, and we yielded over a 10% decrease in variable costs.

It is relatively easy to see how the initial and final delivery stages involving the couriers could be transposed into a standard TSP problem, except one involving several agents, as the problem statement is almost the same as that of the TSP. The intermediate steps were a bit trickier, however, we used a similar paradigm to increase efficiency.

Many business problems may be thought of in terms of the TSP. Any time there exists a variety of options for inputs and how to handle them prior to their release into the outputs market, yielding an immense magnitude of permutations, the TSP should come to mind. The initial investment in building such a system is often paid off in a relatively short time frame and the continuous costs with such a system are lower than prior operating costs and/or opportunity cost.