Some Classical Applications of Operations Research
When applied to tackle real life problems, mathematics becomes more beautiful and fascinating. This is the case of operations research, a subfield of applied mathematics, where problems are formulated mathematically before being solved. Over the previous years, this subfield flourished in a parallel to the development of computational power. Nowadays, many organizations are using operations research to design their operational, tactical, and even strategic decisions. If successful, it leads to significant cost reduction and/or profit increase. The problems tackled usually involve assignment, scheduling, routing, pairing, partitioning, as well as other tasks within a specific time and/or space framework.
In this article, I want to go through some of the popular applications I have seen in my lab where operations research has been quite successful. It may be considered a foretaste for curious mindsets. Problems that will be briefly presented are the vehicle routing problem (VRP), the airline planning problem (APP), the bus driver scheduling problem (BDSP), the locomotive assignment problem (LAP), and the shift scheduling problem (SSP). The cutting stock problem, also well known, was already presented in one of my previous articles.
The Vehicle Routing Problem
The VRP with time windows consists of designing a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicles that serve a set of customers with known demands. The customers must be assigned exactly once to vehicles such that the vehicle capacities are not exceeded. It can be generalized into the VRP with time windows (VRPTW) where, in addition the the previous conditions, the service at a customer must begin within the time window defined by the earliest time and the latest time when the customer permits the start of service. This topic was and is still heavily studied in research and has been applied to many real life problems. From the definition, we can easily infer that for any organization that operates a fleet of vehicles and serves specific customers, VRP can support in optimally, or near-optimally, managing the fleet while reducing cost and increasing profits. A simple model is presented below.
In my lab, many are working on the VRP topic with its variants. It is tackled either heuristically or exactly using advanced operations research techniques such as Dantzig-Wolfe and Benders decompositions. Furthermore, given the large number of variables, compared to the number of constraints, column generation, already presented in one of my previous articles, is involved in order to make resolution efficient and effective.
The Airline Planning Problem
The APP is one of the most challenging problems in the field of operations research. It consists of many subproblems that are solved either sequentially or simultaneously based on the optimization framework used as presented in the figure below. The subproblems are flight scheduling, fleet assignment, aircraft routing, and crew scheduling. In the first one, we determine a set of flights with a specific departure and arrival times with the goal of maximizing the expected profit. In the second one, we select the type of aircraft to assign to each scheduled flight so as to maximize the profit, on the basis of the different capacities and the number of available aircraft. In the third one, we assign individual aircraft to flights while satisfying maintenance requirements. In the last one, we determine crew schedules that cover all the scheduled flights and satisfy the constraints, which is usually done in two steps: pairing problem and assignment problem. In crew pairing, we generate a set of pairings given the scheduled flights such that the cost of the pairings is minimized and all the flights are covered exactly once while in the crew assignment, we build monthly schedules for each crew member given the set of pairings such that every pairing is covered exactly once.
With the increasing demand in the airline industry, the airline planning problem became more and more complex. Hence, tackling it manually may not lead to efficient management of cost and generation of profit. Here, operations research, with the computational power of today’s computers, became the best candidate to solve this problem and lead to significant time gain, cost reduction, and profit increase. Nowadays, almost all airlines, if not all of them, rely on operations research to manage their operations.
The Bus Driver Scheduling Problem
The bus driver scheduling problem consists of covering every part of the bus
schedule by bus drivers at minimum cost. It can be school-bus, urban-bus, or any other context. The bus schedule defines the vehicle blocks, each vehicle block, or simply block, being a bus trip starting at the depot and going back to the depot. Along such a block, there are relief points where there can be a change of driver. The portion of a block which falls between two consecutive relief points, and which is thus always served by a single driver, is a task. A piece of work consists of several consecutive tasks in a block to be performed by a single driver. The internal regulations of a bus company, and the collective agreement between the drivers’ union and the transit operators define all of the details relevant to duty (workday) and schedule feasibility. A duty consists of one or more pieces of work executed by the same driver. In cases where a duty is composed of more than one piece of work, breaks or unworked periods are inserted between the pieces. The feasibility of a duty depends both on the length of the pieces of work and on the length of the breaks. It is also restricted by constraints such as limits on the number of pieces of work in a duty, the total worked time, the paid time, or the total spread. The collective agreement may also classify the duties into types and define constraints on the global manpower schedule.
In operations research, this problem is usually tackled using optimized networks, i.e. with the least possible number of arcs and nodes, and can be solved more efficiently compared to the manual resolution. Using Dantzig-Wolfe decomposition combined with column generation solution approach, very high quality schedules which do not require any manual adjustments are produced.
The Locomotive Assignment Problem
One of the many problems faced by rail transportation companies is to optimize the utilization of the available stock of locomotives. The equipment assignment plan specifies the composition of the train consist that will be used on each scheduled train, and indicates which trains will be covered by the same units of equipment. Railways usually use locomotives of different types that are combined to form train consists. A train consist is a group of compatible units of equipment that travel along some part of the physical rail network. The objective of the LAP is to assign a fleet of locomotives to a set of trains while satisfying a rich set of operational and budget constraints and optimizing one or more crucial objectives.
In many papers, the computational experiments performed show that even for different instances, Benders decomposition, which can be seen as the dual of Dantzig-Wolfe decomposition, is faster than solving the problem manually. The superiority of this method is even greater on larger instances. In particular, as the number of locomotives types increases, one should gain even more by decomposing the problem. Hence, the utility of operations research compared to the manual resolution.
The Shift Scheduling Problem
Shift scheduling arises in many areas such as retail, health, postal services, transportation and industrial production. The personnel scheduling process can vary from one area to another but the goal, generally, remains the same. It consists of constructing the work schedule of a set of employees over a given time horizon to satisfy the demand in employees induced by a set of tasks or jobs. The computed schedule must respect various working, union and legislative constraints, and must be optimal with respect to one or several selection criteria such as the employee salaries, the quality of the work provided or the employee preferences. Finding such a schedule is a very delicate exercise which is better performed using an optimization software. In practice, personnel scheduling is subject to a great deal of uncertainty. Indeed, employees may be late, absent or the observed demand may also differ from the expected demand for certain periods of the horizon.
Similarly to problems presented above, the SSP is also heavily studied in literature and has many applications in real life. Both heuristics and exact methods are used to solve it for complex contexts. Beyond the deterministic case, it can also be resolved rapidly in real time, starting from the deterministic optimal or near-optimal solution, to deal with unexpected of perturbations, which shows the advantage of using operations research.
“True optimization is the revolutionary contribution of modern research to decision processes.” — George Dantzig
With George Dantzig quote, I conclude the presentation of some of the classical applications of operations research. The interaction between mathematics, computer science, and real life problems has a unique and fascinating beauty that tastes spicy when the whole process is completed successfully, i.e. from the mathematical formulation of the real problem until the implementation of the optimized solution.
It is fascinating ! Isn’t it? I am looking forward to hear your ideas :-).
