To main content

The optimal result

The optimal result

Published 15 October 2014
We don’t just want the best. We want the very best.

The Norwegian Central Securities Depository (VPS) in Biskop Gunnerus gate in Oslo is buzzing. It’s not a buzz of voices, but comes from a machine in the corner – and a backup close by. It’s the sound of problems being solved.

rep_optimering_buss

Bus drivers often have inflexible shift arrangements and unpractical plans. SINTEF created a new arrangement for the Nordic bus company Nobina whereby the drivers themselves can specify their wishes.
Photo: Nobina

Click to open

The Norwegian Central Securities Depository is part of the Oslo Stock Exchange. Every hour, hundreds of purchase and sales orders tick in: Dealer A buys sixty shares from foreign dealer B who buys twenty shares from C and thirty shares from investor D. Then D buys fifty shares from C, and so on. In the course of a day a large number of transactions accumulates, and three days after a deal is sealed, settlement takes place.

This is when the securities change hands and the challenges arise. Some dealers have been slow to record sales with their brokers before settlement takes place. Others don’t have a good enough overview of all their transactions. The result may be that a dealer sells more shares than they have available. In such a case, which of the recorded transactions shall be completed?

How can VPS ensure that sales are as high as possible when some of the transactions have to be annulled? This is a question of optimization – the art of maximizing a figure, such as profit, or in other cases minimizing figures, such as transportation distances and energy consumption.

“On days with high turnover we may be involved in optimizing sales with a value of around a hundred billion kroner,” says Oddvar Kloster, a research scientist working on optimization in SINTEF. “We don’t reduce the number of transactions which cannot be completed, but we make their effect as small as possible. This is called achieving a high degree of settlement. We supplied the computer software to VPS several years ago, and it has functioned well.”

Increased use of optimization models

“Working with optimization problems is about describing the structure of a problem mathematically. Hence, many adjustments are often necessary depending on the result one wants,” explains Tomas Nordlander, who is in charge of the optimization group at SINTEF.

Nordlander explains that the most common method used to handle complex problems manually is to divide them up into a large number of smaller problems.

Efficiency in the health service

When SINTEF’s research scientists were awarded the assignment for the health services, they realized how many complex fields and natural applications for optimization technology were present here.

The treatment of a single patient includes a range of activities. These are defined in a so-called “treatment process” from the moment a patient is admitted until he or she is discharged. Treatment involves activities in many different departments. It is also the case that the human resources in a hospital, such as doctors, nurses and ward staff, are involved in the treatment of many patients.

“A good deal of what takes place is connected with some form of planning,” Atle Riise explains, “Just imagine all the treatment which has to be planned, in addition to all the emergency responses and patient transport within the hospital.”

The goal is always to make use of the resources efficiently while providing the highest possible treatment quality.

All these interrelationships demand an integrated approach. Last autumn saw the start of an innovation project entitled “Verktøy for helhetlig aktivitetsplanlegging I sykehus” (tools for integrated activity planning in hospitals), the AKTIV project. The participants in the project are health trusts, research scientists and DIP ASA, the largest supplier to Norwegian hospitals of systems for electronic patient journals.

Health projects with optimization

The AKTIV project, developing tools for integrated activity planning in hospitals. An innovation project supported by the Research Council of Norway. 2012-2016. Objective: To improve efficiency and treatment quality in hospitals by means of better planning of day-to-day activities. Project partners: DIPS ASA, SINTEF IKT, the Vestre Viken health authority and the University Hospital in Northern Norway.

HOSPITAL (Health Care Optimization Software for Planning). 2007-2012. Developing optimization methods for planning in the health service. Participants: Gatsoft AS, DIPS ASA and SINTEF.

MEDICAL WHITEBOARD. 2011-2013. Developing an interactive software solution for dynamic, detailed planning of surgical operations. Participants: Vivit AS, The Alloy, Hospital Organiser and SINTEF.

Together they plan to develop optimization tools to help planners.

Electronic planning board

At a hospital, the planning of operations for the following day often takes place in meetings attended by the surgeons involved and the resource coordinators.

“This is a dynamic planning situation in which it is difficult to keep a full overview of the best possible plan,” says Riise. “There was a pressing need to produce an overview in real time: what will happen if we move that operation?”

The objective of Hospital Medical White-board, an international healthcare project in which SINTEF participates, is to develop an electronic planning board. When the participants discuss various modifications of the plan layout, any consequences of those changes must be calculated immediately. The people in the room will then see the consequences straight away. The board thus becomes a tool making it possible to find solutions rapidly in a situation which is both too dynamic and too complex for a single person to be able to manage properly.

Shifts for nurses

Drawing up shift plans is not an easy task. One reason is that the planners must observe Norwegian law and a complex set of regulations which have to be complied with. Shift work also creates conflicts for employees because unfavourable working hours can easily affect the quality of their private life. It is not at all easy to get everything to fit together when all employees have their own wishes as regards shifts and leisure time.

Research scientists at SINTEF are currently supplying an “optimization core” to Gatsoft AS, a software developer in Skien. This has been incorporated into the company’s software, a product which is used to plan shifts for nursing staff. The partners are currently working on a new version of the planning tool which will also take personal wishes into account.

Countless combinations

So, we know that optimization is about mathematics and algorithms, and making complex situations easier to visualize, but how do the researchers tackle this?

“I usually bring out my “jelly baby” example,” Tomas Nordlander says, with a smile. “Imagine that these three jelly babies are to be operated on: red, blue and green. There is only one operating theatre and one surgeon, so it all has to happen in a certain order. With three jelly babies there are six different combinations for the order in which the operations can be done. So, perhaps you think that if we double the number of jelly babies, there are twice as many solutions?”

“Well …?”

“No. In fact, if we double the number of patients to six, the number of possible combinations is not doubled, but is 120 times as many – in other words 720!”

“And the realistic number of patients is perhaps rather more than six?”

“Exactly, but many people find it difficult to understand that the number of combinations explodes.”

People decide

Nordlander tells us about a meeting with healthcare personnel in which he demonstrated the jelly baby example and the number of combinations resulting from 48 individuals. The department manager pointed out that a capable operation planner would immediately be able to see many combinations which would not be possible, and hence find good solutions.

“Unfortunately I had to put her right by pointing out that even if one managed to discard 99 per cent of the possible solutions, it would take longer than the lifetime of the universe to inspect the remaining combinations. That’s why we need to use computers. Then she suddenly went quiet,” says Nordlander.

“So, what do the computers do?”

“There are a number of different methods. Sometimes Solution A is tried first, and then the next solution is displayed: Is this better than Solution A? Then the next solution is tried, and all the time the best solutions are being moved forward. Many people are afraid that the computer will be making the decisions, but in practice it is always people who decide. Optimization is intended to present the optimal solution or a couple of good alternatives, and then the planners can decide which solution they want to settle on.”

The optimal journey

What do you do when you are going to travel to an unfamiliar destination, or want to drive to a street address in a town you don’t know? You go online, use Google, and get a map and a route description. This is simple, specific and easy to understand.

rep_opt_stor

Operation planning
How many different combinations are there for operating on 3, 6, 12 or 24 patients? And how long will it take to evaluate all of them? The
illustration shows the possible combinations presented by three patients. The table shows how rapidly the number of combinations increases according to the number of patients.
Ill: Knut Gangåssæter

Click to open

“Surely we don’t need any kind of optimization here?”

“Well, that depends,” Dag Kjenstad smiles, “The big players like Google and Ruter (the public transport authority for Oslo and Akershus) are good, and they also use optimization, but we are now adding new possibilities.”

“Such as?”

“Looking at all possible means of transport.”

The research scientist explains: “Suppose John wants to travel from A to B. There are many ways to do this. Which means of transport need to be used for each part of the journey? What if John lives in Lommedalen, for example, and wants to get to the centre of Oslo. The most practical solution may be to drive down to Sandvika, get a train to the city centre and jump on a city bike to reach the final destination.”

“Is that realistic? Aren’t we too lazy to do this?”

“We believe it will be more likely once people are having the options put before them and can make the “right choice”. We have different points of view and different needs, depending on whether we are students, pensioners or businessmen. Some people have environmental preferences. Others need to take their finances into account.”

Scientists envisage a competitively neutral national travel planner for public transport, similar to the Norwegian online services yr.no (weather information) and ut.no (outdoor activities). Road and route information provided by the bus and rail operators must be incorporated into the tool, and all the available real-

time information must also be used as input to the calculations. The idea is that several providers will be able to use a central search engine to market their different services.

Satisfied bus drivers

The shift arrangements for Swedish drivers in the Nordic bus company Nobina were not optimal, either with regard to the requirements of the trade union or of the law. The drivers felt that the plans were inflexible and not very practical for employees. At the same time there is considerable demand for good drivers, and the company made it clear that they wanted to attract new employees.

Trouble-free air travel

Recognize this? The plane has touched down on the runway. People jump up from their seats, turn on mobile phones and try to get hold of their hand baggage. Then they stand there waiting impatiently, sweating, with their heads squeezed in at an angle under the baggage holders, with people pushing them from all directions. And they are all thinking, “How is this possible? Can it be THAT difficult to get a plane positioned correctly and open the door?”

Organizing air traffic also involves isolated planning processes, personnel who have to be in place and coordination of activities. The flight controllers in the tower must ensure that taxiways and gates are free. Somebody has to be given instructions to bring the gangway to the plane. While the aircraft is on the ground, other teams have to clean it, refuel it and handle the baggage.

“Finance, health services, trains, buses, aircraft and private travel: is there any area of society where you are not involved?

“Lots, but you haven’t mentioned sport!”

“Sport?”

“Yes, we’ve been working for years on series and tournament planning in sports. But if you write that, please point out to sports fans that it’s no good contacting us to ask for special match fixtures,” says Tomas Nordlander with a smile.

Åse Dragland