5 5 5 Operations Research in Practice (Part 2): Generic Problems

# Operations Research in Practice (Part 2): Generic Problems

by | July 21, 2022

In “Operations Research in Practice (Part 1): Identifying Problems”, we discussed the first step of OR in practice. Once the problem is successfully identified and structured, an operations researcher will move forward to the second task: converting the problem into a well-known generic OR problem. This is another interesting and important step in the process of solving problems with OR.

During the development of OR as a science and discipline, mathematicians figured that most business problems could be mathematically represented by a number of generic formulations of problems. They gave these problems names and proposed methods to solve them. Operations researchers usually spend their time mostly converting a business problem into one of these generic problems. Recall that some of the generic OR problems mentioned in “Better Decision-Making with Operations Research” are

• Travelling Salesman Problem
• Shortest Path Problem
• Set Covering Problem
• Knapsack Problem
• Assignment Problem

Take traveling salesman problem (TSP) as an example. The question of TSP is “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. The application of TSP ranges from logistics, planning, scheduling, and manufacturing, to DNA sequencing. In these cases, “city” can represent customer, station, or DNA fragment, and “distance” can represent travel time or cost, production time or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources and time windows are incorporated.

Source: https://physics.aps.org/

Another generic OR problem is the set covering problem which asks “Given a collection of elements, what is the minimum number of sets that incorporate (cover) all of these elements?”. Variations of set covering problem with significant applications include

• optimal location problem which maximizes the coverage of some public facilities placed at different locations, e.g placing fire stations to serve the populations of some city
• optimal route selection problem which selects the optimal routes to place certain resources such that the coverage is maximized, e.g. selecting the optimal bus routes to place pothole detectors
• airline crew scheduling problem which, given a collection of flights to be covered, searches for the optimal assignment of employees to flights.

Some business problems are not easy to convert into a generic problem due to their complexity and high level of interaction between variables. However, once we get into this stage, solving the problem becomes easier assuming we have some standard procedures in mind. We’ll discuss the next step of OR in practice, which is formulating the generic problem into a mathematical model, in the next article. In the meantime, contact us to explore our service related to Operations Research and get further information by sending an email to [email protected].

—

Reference:

More Insight for you