March 25, 2013, by Graham Kendall
What is Operations Research?
In this What is? series, we invite experienced researchers to write about their area of research, but in more general terms than they might normally do.
As this is the first one, I thought I would go first, just to show willing.
If you would like to contribute, then please let me know (Graham.Kendall@nottingham.edu.my) and we can discuss how best to go about it.
Anybody wishing to contact the author of this article should go to about the author.
What is Operations Research (OR)?
The terms Operations Research (American term) and Operational Research (European term) are used interchangeably. The discipline is also referred to as:
- Management Science (most often used in a Business Management sense)
- Decision Science (less frequently used, but is used most often when statistics are involved)
- Analytics (a relatively new term but is increasingly used)
Operations Research has close links with Mathematics and Computer Science. It draws on many areas to solve the various problems that it is presented with. Included in these are
- Optimization (drawing on mathematical programming and and areas such as Linear Programming)
- Modelling
- Simulation
- Heuristics
- Meta-heuristics
- Hyper-heuristics
- Evolutionary Computation
- Game Theory
- Statistics
A Traveling Salesman Problem solution for USA (Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook)
The essence of Operations Research is to provide (ideally) optimal, or near optimal solutions to complex decision problems. Probably, the most well known problem (at least in the scientific arena) is the Traveling Salesman Problem (TSP) which can be described as follows:
“A salesman has to visit a number of cities. He can choose which one he starts at, but he must complete his tour at the same city. He must visit every other city exactly once. The aim is to minimize the distance traveled.”
Whilst being very easy to describe, the TSP gets very difficult to solve (at least in polynomial time) due to the fact that the number of possible tours grows exponentially with the number of cities (the actual number of tours is n!/2 (we divide by two as a tour in one direction is the same as a tour in the opposite direction)).
Historical Details
Like many things, especially in Computer Science, many of its origins can be traced back to the second world war, necessity being the mother of invention, although some would argue that OR’s roots can be traced back beyond this point. Given the subject, you’d expect that many people would have documented the history of the subject and, indeed, this is the case. I have provided below some sources which the interested reader might want to follow.
- [1] Gass S.I. and Assad A.A. An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163
- [2] Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013
- [3] Gass, S. I., A.A. Assad. History of operations research. J. Geunes, ed. INFORMS TutORials in Operations Research, Vol. 8. INFORMS, Hanover, MD, pp. 1–14 (this is also available from here)
Why is OR so hard?
The type of combinatorial explosion we see in problems such as the TSP often underpins the problems that we face in OR. In fact, the problems where is is easy to verify (i.e. in polynomial time) if a solution is correct but to find the optimal solution cannot be done (we suspect) in polynomial time is often at the heart of the problems we are trying to solve in OR.
These problems are NP-Complete. That is, we can easily verify a solution is correct (given a TSP solution, we can easily add up the distances to verify that the solution we have been given is correct) but we do not know of a polynomial time algorithm that is guaranteed to return an optimal solution. Indeed, proving P=NP (or not) is one of the Millenium Problems and if you are able to do it, you will receive a prize of $1M USD.
There are some common problems that you will often come across in OR. We have already mentioned the TSP.
The Vehicle Routing Problem!
The Vehicle Routing Problem (VRP) is another classic OR problem. As the name suggests, this problem is about scheduling deliveries for vehicles. The classic version is the Capacitated Vehicle Routing Problem (where we minimize total distance traveled, but have to respect vehicle capacities) but there are many variants, such as VRPTW (Vehicle Routing with Time Windows), where deliveries have to be made at certain times. In fact, VRP and TSP are very closely related.
Another classic problem is graph coloring. That is, given a graph with various connections between the nodes you have to try and color the nodes, using as few colors as possible, such that no nodes which are connected have the same color. This problem has an obvious application is coloring maps but you might be surprised to know that it underpins many (many, many) other problems. As an example, university examination timetabling (i.e. scheduling the exams for our students) can be modeled (and solved) as a graph coloring problem. There are almost an infinite number of problems that can be modeled as a graph coloring problem.
Second to the TSP (and this is debatable, it might be first), with respect to the number of papers written, machine/job shop scheduling problem. This problem, in its simplest form, looks at scheduling factories.
Given a number of machines, and a number of processes that have to be gone through to produce a product, what is the best way to utilize the machine(s) to maximize the throughput?
Graph Colouring Problem
Like the graph coloring problem, Job Shop Scheduling (JSP) and Flow Shop Scheduling (FSP) can be used to represent many other problems, that are about as far away from the factory floor as you can imagine (how about having telescope(s) in space and trying to schedule their usage for various scientists).
Methodologies
If we could prove that P=NP (which most people think unlikely) then we would be able to find the optimal solution to many of the important problems in OR. That is, we would have a polynomial time algorithm that would give us an optimal solution in a reasonable time. Of course, it might still take a long time but this better than an exponential time algorithm that might take millions of years to return the optimal solution, even on the fastest computers. In fact, there are many problems (or many problems of sufficient size) where we would have only considered a small number of the possible solutions even if we started the algorithm when the dinosaurs were roaming the earth.
However, there are sophisticated algorithms (such as linear programming) that are increasingly able to solve moderately sized problems to optimality.
When these fail (or we find it difficult to model the problem in sufficient detail to use a mathematical programming approach) we tend to use either heuristics, meta-heuristics, hyper-heuristics or evolutionary computation.
The definition of these is not formal (in that, we could argue where they blur at the edges) but:
- Heuristics tend to be one pass algorithms and are quite quick.
- Meta-heuristics are based on phenomena seen in the real world. Things like tabu search (based on memory) and simulated annealing (based on the way we cool metal).
- Hyper-heuristics are a development of meta-heuristics (although their roots, strangely, can be traced back to before the term meta-heuristics was coined). They are based on the idea of exploring the heuristic space, rather than searching the solution space directly.
- Evolutionary Computation are algorithms that are based on Darwin’s principles of natural evolution (survival of the fittest) where we have a population of solutions which compete against each other for survival. Common algorithms in this domain include genetic algorithms, genetic programming, honey-bee mating algorithms and particle swam optimisation.
Where do we publish?
If you are looking for journals that you might want to consider publishing in then Thomas Reuters, Web of Knowledge, Journal Citation Reports has a specific category for Operations Research & Management Science. For the 2011 journal rankings, this category contained 77 journals. Of course, not all of them will be suitable for a given piece of research but these 77 journals all most (if not all) areas of Operations Research.
Want to know more?
There are too many resources to list here, and a serch on a bibliographic search engine such as Science Direct is likley to throw up more references than you would imagine.
But, youtube has a god set of videos where you can Learn About OR.
A couple of videos that caught my eye are OR in Sport and OR in Transport
About the author
Graham Kendall is a Professor of Computer Science who works in the Automated Scheduling, Optimisation and Planning Research Group (ASAP). He is a Fellow of the OR Society, as well as an Associate Editor of the Journal of Operational Research Society (in addition to several other journals). He has published widely in Operations Research, as well as other areas. Hi spublications can be seen here.
He has over 30 years experience in OR, both in industry and academia.
Graham is currently based on the University of Nottingham’s Malaysia Campus (UNMC) where he is the Vice-Provost of Research and Knowledge Transfer.
Contact details:
References
[1] Gass S.I. and Assad A.A. (Author) An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163
[2] Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013
[3] Gass, S. I., A.A. Assad. History of operations research. J. Geunes, ed. INFORMS TutORials in Operations Research, Vol. 8. INFORMS, Hanover, MD, pp. 1–14 (this is also available from here)
No comments yet, fill out a comment to be the first
Leave a Reply