Optimisation in the Real World

Optimisation exists everywhere in this world. The operation of airlines, the rostering of staff, the scheduling of sporting competitions and the layout of shelves in a supermarket are all examples of optimisation in the real world. Our lives are affected by optimisation, either by our own doing or through the products and services we use. Below you will find real world examples of optimisation in practice.

The Band Manager Problem

How does a band manager schedule locations for an international tour? A band tour manager has many things that they need to consider when organising the locations for gigs. These include: the size and availability of venues, the countries and cities to visit, maximum length of the tour.

A band manager, whether they know this or not, will need to solve an optimisation problem. In an optimisation problem, these requirements or restrictions called constraints. The restrictions of the problem tell the band manager what tour options are possible.

The band manager knows the locations for the concerts and the distance between each of the locations. The band manager may then ask the question “What is the shortest route that visits every tour location and returns the band home?”

The answer to this question come for solving the Traveling Salesman Problem. Read on for more information about this classical, and very difficult, problem.

The Traveling Salesman Problem

The travelling salesman problem is a classical optimisation problem that arises as part of many real world applications. These applications include sports scheduling, mail delivery and more fun activities such as planning tours for vacations. It is also a key component of many other problems in mathematics and optimisation.

The travelling salesman problem has been the focus of much research for 60 years. This research has developed mathematical techniques that has lead to advances in our ability to solve real-world problems.

The Grocery Delivery Problem

Online grocery shopping is very convenient for the consumer, but it makes the supermarket business much more complex. Instead of just stocking a store, a supermarket must also ensure the customer receives their goods at a specified time. These times are typically given as windows, say 8pm to 9pm. But, how does the supermarket decide the actual time that the delivery will be made to the customer?

The supermarkets are solving a problem called the Vehicle routing problem. In fact they are solving a more complex variant called the Vehicle routing problem with time windows. Scroll down to read more.

The Vehicle Routing Problem

The basic vehicle routing problem involves the design of a collection of delivery routes that ensure every customer is visited while minimising transportation costs, such as fuel. This can get more complex, such as in the case of grocery delivery, where there are additional constraints. The restrictions and conditions that the supermarket must take into account include the capacity of the vehicle, the locations that must be visited and the time windows when they can arrive.

Many methods have been developed to solve the vehicle routing problem. A very successful algorithm for solving this problem, which is still the focus of much research, is called column generation.

Read More

The Bike Sharing Problem

How are the bike sharing docking locations picked?

Many bike sharing systems around the world consist of two main components: the bikes and the stations to dock the bikes. A bike sharing system will only be useful if the docking stations are located where people want to collect bikes and where they want to drop them off. An interesting, and very commonly used optimisation problem, is the problem of determining the best locations for the docking stations.

The problem that is solved to identify the docking stations is the called the Facility location problem. This problem finds the best docking station locations that minimises the investment and achieves a minimum level of demand. There is more on this classical problem below.

Read More

The Facility Location Problem

The core of the facility location problem is to identify the locations where to open facilities in order to satisfy the demand of all customers at a minimum cost. This is typically used to identify the locations to open factories or warehouses. The costs for these problems come from the opening of the facility and the transportation of the goods to each of the customers.

The facility location problem is a classical optimisation problem that can be solved using a technique called Benders’ decomposition. Similar to the Column Generation approach, Benders’ decomposition considers only a reduced version of the problem.

Read More