Mail delivery for safer roads?

Winter is here, in the Netherlands this means that we start wondering if this year it will be possible to skate the eleven-city marathon. We already had a first skate championship on natural ice, which according to the diehards in skating is a more pure experience than skating on artificial ice. Apart from wondering about the marathon, there is another issue to worry about when clearing the ice of our car windows, road safety.

Because the temperatures in the winter are around 0 °C or below the roads can become slippery because of ice or snow. Deicing is necessary otherwise accidents will happen. In fact, temporary friction enhancement through the application of salt is seen as an effective safety countermeasure. In the Netherlands, the government together with local and district authorities are responsible for the deicing of roads. Each of them covers their own roads. The government is responsible for the highways, the local and district authorities for the local roads and the road network within the cities. The deicing of roads is performed with special trucks that can be used to apply deicing salt or snow clearance. To give you an idea, in the Netherlands more than 100 depots and over 500 trucks are involved in deicing the highways alone.

Recently we performed a project to find out if integrating the deicing of highways and local roads would lead to synergies and savings for both government and the local district. The construction of routes for deicing the roads is problem that can easily be solved with the use OR. A lot of restrictions need to be taken into account although. There are several restrictions due to government regulations that state that highways to be deiced within 45 minutes. Road entries and exits need to be deiced within 90 minutes. When constructing the routes you have to take into account the various road types, like very porous or non porous asphalt, since each road type requires a different amount of deicing salt per m2. Sometimes roads are too wide to be covered by one truck, than more than one truck needs to be used. These are only a few of the restrictions that need to be taken in to account when building the deicing routes.

When you think of the problem we need to solve it looks quite similar to the traveling salesman problem. The road network that needs to be deiced consists of vertices and directed edges. The solution to the traveling salesman problem finds the shortest route thru all the vertices of the network. When constructing the deicing routes we need to visit all the directed edges in the network, not the vertices, we will probably visit those several times. The problem we need to solve is called the Chinese Postman Problem and was first described by Mei-Ko Kwan, a Chinese mathematician, in 1962. Today it is sometime called the route inspection problem. To solve it we need to find a circuit, also called an Euler circuit, through the network that only goes along each edge of the network once. If there is such a route and it ends at the same point at which it begun, then the problem is solved. Otherwise we need to adjust the network by adding artificial edges, meaning that we will travel along an edge several times to complete the Euler circuit. After the Euler circuit has been constructed for the complete network we need to split it up in order to have separate circuits that obey the restrictions on time and capacity of the trucks. The project resulted in routes with less use of equipment and depots, leading to savings in cost. So safe roads for less cost thanks to a Chinese postman.

To get an idea of the complexity of the construction of deicing routes try to solve the below example. The length of the optimal circuit is 20, but how does it run?

spORts

It is the fifth game in a best of 7 series of the national volleyball championship series. The home team is 3 games down to 2 so it must win the next two games in order to win the championship. The coach has to decide which players he will use in the game, especially which opposite hitter. His best opposite hitter has played a lot and could use some rest. The next best opposite hitter is fit and could play the next two games. The coach believes that his best opposite hitter, although not fully rested, is still better than his next best opposite hitter. Letting him play the 6th game would mean that he can’t play the last game. The opponent’s coach has chosen his next best opposite hitter, maybe saving his best player for the last game? The home team coach assesses that the opponent’s opposite hitters have about the same ability as his own opposite hitters. What should the coach decide, let his best opposite hitter play or his next best opposite hitter? Can Operations Research help in this decision?

Traditionally Operations Research has been used in sports for timetabling, like the construction of a round robin tournament schedule. Sports leagues and teams need schedules that satisfy different types of constraints. For example the three soccer teams of Rotterdam cannot play at home at the same time. Other examples are the restrictions due to the international games played by the teams, like the Champions league. Timetable construction in sports competitions is a difficult problem to which several O.R. techniques have been applied. Most of the time a Mixed Integer Problem (MIP) needs to be solved. But Operations Research can be used in other areas of sports as well.

Let’s go back to the decision the coach of the volleyball team has to make. In what way could we assist him in this decision? Should he use his best player in the 6th game and use the next best in the final game, or the other way around? Most people I talked to on this decision say to put up the best player in game 6 and use the next best player in game 7. For obvious reasons they say, because if you don’t win game 6 there won’t be a game 7. Is this the best strategy?

The decision the coach has to make is similar to the examples used by Kahneman and Tversky. They demonstrate that human intuition is notoriously bad at processing even the simplest probability problems. Here is one of their examples:

Linda is 31 years old, single, outspoken and very bright. She majored in philosophy. As a student, she was deeply concerned with issues of discrimination and social justice, and also participated in antinuclear demonstrations. Which of the following statements is more probable?
A: Linda is a bank teller.
B: Linda is a bank teller and active in the feminist movement.
C: Linda is a bank teller and takes yoga classes.

Most respondents choose B or C. Few choose A. Yet, by the laws of probability Pr(A) ≥ Pr(A ∩ B)

In a similar way we can prove that saving the best player for the last game is the best strategy to win the series and therefore the championship. To see this, let P1 be the probability that the best player wins game 6. Then the probability of winning game 7 for the best player will be P2 = P1 + ε where ε > 0. ε is positive since the player has additional rest and the opposing players are judged to be the same. Let the probability that the next best opposite hitter wins game 6 be P3 = P1 – δ, where δ > 0. Note that this definition takes into account the assessment of the coach that his best opposite hitter is better than his next best even though he isn’t fully fit. The probability of winning game 7 (P4) with the next best player is the same as winning the 6th game, so P3=P4.

The probability of winning the championship starting with the best opposite hitter in game 6 is C1 = P1*P4. Letting the best opposite hitter play in the final game the probability of winning the championship is C2= P3*P2. Now note that C2 = P3*P2 = P3*(P1 + ε) = P3*P1 + P3*ε =P4*P1+ P4*ε. Hence C2 = C1 + P4*ε. Since P4*ε >0, the best strategy therefore would be to save the best opposite hitter for the last game. As you can see, sports can benefit from the application of Operations Research in various ways. Can you think of others?

Uganda flood response

OR to the aid again! As I stated in my last blog message every Operations Research professional should offer his or her support to initiatives of the UN or other humanitarian organizations to help improve their operations. This way more lives can be saved. Last week I got the chance to put my money where my mouth is.

By coincidence I got in touch with the UNJLC, the United Nations Joint Logistics Centre. They were asked to provide a schedule for delivering relief supplies to schools and settlements in the Amuria district of Uganda. This as part of the Uganda flood response. As you might have read in the newspaper, large parts of eastern Uganda are flooded. At this moment the situation in flood-affected parts of Uganda continues to worsen. The first priorities of the aid are to stabilize the initial food security situation, preventing disease outbreaks, ensuring capacity to respond to health emergencies and re-opening schools.

The task of the UNJLC is to help with the food supply. Tons of cereals, sugar and vegetable oil needs to be transported to schools and settlements. Because the locations cannot be reached by road, helicopters are used to deliver the relief supplies. The helicopter flies from a central point in the area to the locations of the schools and settlements. For each of the locations it is known how much of the relief supplies need to be delivered. The helicopter however has a maximum carrying capacity, which is lower than the demand of some of the schools and settlements. This means that the helicopter has to perform several flights and attend several locations more than once. For each flight it has to be decided which locations to attend and how much of the relief supplies to be delivered at the locations visited. The helicopter range wasn’t an issue in this case, so the length of the flight wasn’t a restriction. You might guess that under the pressure of many people in need no time should be lost in finding the best possible solution. Your (and mine) first reaction would be to load a helicopter and start delivering the supplies. The people at UNJLC wandered if it would be possible to construct the schedules automatically, so the best possible routes could be constructed in the least possible time. A challenge I could not resist.

There are several ways to find the optimal solution. Of course you could startup MS Excel and construct the routes by hand. This can be a very good way when the number of locations to attend is not large. Another way is to use brute force techniques like a set covering approach. In that case you generate all possible routes and use a LP model to select the best routes, assigning the amount of supplies to each of the routes in the same model. I used a Network flow model in which all the nodes in the network represent demand points except the central point (Origin) from which all flights departed. I constructed a complete network, i.e. all demand nodes in the network were connected with directed arcs. The origin was connected to all the demand points in one direction. By setting the appropriate capacity constraints on the arcs, the maximum carrying capacity was modeled. In the objective function the length of the arcs in the network was used as a proxy for cost of using the arc. A flow in the model represents a route, including the amount of relief supplies to be transported. Solving the model was easy and took only a few seconds. The optimal routes are much better than the routes used until now. They save time and money, allowing for more relief supplies to be delivered and therefore lives to be saved. OR to the Aid!

OR to the aid of children

The world is full of areas in which people and especially children suffer from war or natural hazards like the Tsunami. The United Nations and other humanitarian organizations try and help these people. Of course the aid that is provided is the best possible, but much could be improved with the help of Operations Research, enabling to save more lives and give victims a better chance to build up a new future.

As an example of what can be achieved with the use of Operations research I would like to address a project that was set up by the World Food Program (WFP) of the UN. The UN World Food Program is the world’s largest humanitarian food aid organization. It provides food to about 90 million people in around 80 countries. These people depend on the aid that is provided by the WFP, since no other source for food is available to them. Additional to this aid, the WFP also uses supports 800 million malnourished people in the world with special food aid projects.

One of those special food aid projects is the food distribution to schools in Liberia. The project’s aim was to improve the food distribution to children. With the use of Operations Research the WFP distribution network in Liberia was optimized resulting in better locations for the depots from which the food was distributed. Also the distribution of the food to the 1,600 schools in Liberia was optimized, ensuring that 250,000 children receive their food. Initially the routing and scheduling was performed by hand. TNT (which takes part in WFP) together with ORTEC (the company I work for), changed that by automating the scheduling process with the use of state of the art routing software. The scheduling became less time consuming, also the dynamics of the scheduling process could be supported better. As you may guess the road network in Liberia is not that sophisticated. Due to the rain season and mines, not all the roads could be used at all times, even bridges may have collapsed. This introduces a lot of dynamics which is hard to incorporate when every thing is done by hand. Also we improved the distribution network by relocating the depots. The achieved improvements saved al lot of money that can now be used to maintain or further improve the aid that is provided to the children of Liberia.

To my opinion Operations Research professionals should offer more support to the initiatives of the UN and other humanitarian organizations to improve the effectiveness of these operations. This will result in more lives saved and a better future for all victims of humanitarian disasters, especially children.

Complicating Simplifications

Recently the court of The Hague gave a judgement on the remuneration of resident on call working of the firemen in the Netherlands. Direct cause of the judgement is that the firemen will work less hours a week with no reduction in salary, a loss of productivity of about 11%. The judgement was caused by an attempt of the Dutch government to simplify the rules in the working time directive. These adjustments were necessary because the rules were becoming to complex, also the Dutch working time directive did not follow the agreed working time directive on the European level and the Jaeger as well as the SiMAP judgement. Both judgements state that the hours spend during a resident on call duty should be valued as normal working hours.

From April 1st of 2007 on the simplified working time directive (s-WTD) came into force in the Netherlands. In this new law many rules were simplified or skipped, also some additions were made. The s-WTD sets rules to protect the safety, health and wellbeing of any employee. It contains, for example, rules on the maximum number of hours that employee can work during a shift, a week or consecutive number of weeks. Also it sets rules on the length of a rest period after a shift and after a number of consecutive shifts. The simplifications lead to an increase of possible deployments of employees of about 20%. The question is however if the employers understand the rules well enough to take advantage of the increase in deployment possibilities.

There is one rule in particular that has drawn my attention. I my opinion it is impossible to take that rule into account when construction a roster, without consulting an Operations research specialist or using an advanced planning system, since it requires you to solve the well know multiple knapsack problem. In normal English the rule states that when an employee performs one or more resident on call duties, each period of 7 times 24 hours must contain at least 90 hours of compensatory rest. So far this is simple, we can easily add up all the rest periods an see if it matches the requested 90 hours. There are additional restrictions however on how the compensatory rest period is divided up over the 168 hours period. These restrictions state that there should be at least one period of 24 hours compensatory rest, four of at least 11 hours, one of at least 10 hours and finally one of at least 8 hours. 7 rest periods in total. This still is simple to verify, however these periods of compensatory rest can be joined together. Because of this last condition we have a multiple knapsack problem to solve, which is NP-Hard. (see http://en.wikipedia.org/wiki/Knapsack_problem) I wonder if this crossed the minds of the clerks when writing the new laws. To see the analogy let each period of rest be equal to a knapsack, the capacity of the knapsack is equal to the length of the rest period. Now we have to find out how the 7 rest periods of various sizes can be fitted into the knapsacks. If we succeed, the roster is valid; if not then we need to change it.

To experience what kind of puzzle a planner has to solve, I will give you an example. Assume that an employee has 3 rest periods. The lengths of the periods are 32 hours, 31 hours and 28 hours. I invite you to react and tell me of it is possible to solve this puzzle.

Blood sample logistics

The diagnostic centre of a hospital asked me to analyze their blood sample collection process from a logistic point of view. They had a feeling that the performance of the collection process could be improved. They asked to verify this and also to provide a set of possibilities to improve the collection process.

The main activity of the diagnostic centre is to take blood samples from patients, analyze them and report the results back to the physician or patient. Sometimes they advise the patient with respect to the medicine they take, for example in the case of diabetes. Some of the patients come to the hospital to have a blood sample taken. Many of the blood samples however are taken at service locations of the diagnostic centre in the area around the location of the hospital. In this case there are about 30 different service locations where a patient can go, to have their blood sample taken.

The employees of the diagnostic center work at the service locations and take the blood samples from the service location to a laboratory to have them analyzed. As an extra service the employees also visits patients at home to take a blood sample. Currently the employees visit the patient at home before and after they work at the service location. This takes careful planning because patients at the service location must not be kept waiting. As you may guess an important condition in the collection process is to have the blood at the laboratory in time. Blood can not be kept indefinitely; it must be delivered on time to the laboratory, otherwise no analyses can be performed.

As you can see this is a rather complex logistic process. Many questions arise, such as

• Are there enough locations available for the patients to go to, or should the number be changed?
• What should be the opening times and the geographic position of each of these locations?
• Should all the blood samples be taken directly to the laboratory, or should they be collected first at specific places in the network. In other words should hubs be used?
• Should from an employees point of view the samples taken at the patient’s home be combined with the blood samples taken on the service locations of the diagnostic centre?

This is where Operations Research comes in. We analyzed the blood sample logistics with a model that we developed to analyze and optimize supply chains. With this model we can answer questions like where facilities should be situated, how large they should be and which customers should they serve. With this model we found that introducing a few hubs where blood samples are collected from the service locations before taking them to the laboratory saves about 25% of travel time of the employees. This saves time but also the distance traveled, which reduces the costs for the diagnostic center. This time saved can be used to take more blood samples boosting the workforce effectiveness as well.

OR in the OR

De Franz Edelman Award wordt elk jaar toegekend aan ‘outstanding examples of Operations Research (OR) – based projects’, die grote veranderingen bewerkstelligen in de samenleving, industrieën en het bedrijfsleven. Deze prestigieuze prijs voor het best wereldwijd toegepaste Operations Research project kan worden gezien als de ‘Superbowl’ in toegepaste O.R. Dit jaar waren onder andere Hewlett Packard, Daimler Chrysler, The Memorial Sloan-Kettering Cancer Centre en Coca Cola genomineerd.

ORTEC, het bedrijf waar ik voor werk, was dit jaar bij een van de genomineerde projecten betrokken. Coca-Cola Enterprises is genomineerd, omdat het bedrijf haar distributienetwerk wist te optimaliseren met rit- en routeplanningsoplossing Shortrec van ORTEC. Het systeem dat in 2004 werd geïmplementeerd heeft Coca-Cola Enterprises een besparing van 45 miljoen dollar per jaar opgeleverd.

De award werd uiteindelijke gewonnen door een zeer innovatief project van OR in het Memorial Sloan-Kettering Cancer Centre. De kern van de toepassing is het vinden van de beste positie voor het inbrengen van radioactieve "zaadjes" in de prostaat. Een soort locatie vraagstuk dus. Veelal wordt dit vraagstuk in het platte vlak opgelost, het feit dat het nu in 3 dimensies plaatsvindt en dat het real time (met de patient op tafel) wordt opgelost maakt het uniek. Kijk voor meer informate over dit project op http://www.lionhrtpub.com/orms/orms-6-07/fredelman.html. De toepassing heeft er toe geleid dat een kostenbesparing van 450 miljoen dollar per jaar kan worden bereikt, maar belangrijker is dat de levensverwachting van de behandelde patiënten vergroot wordt en dat de succeskans van de behandeling enorm is gestegen. Kortom "OR in the OR"

Wat is OR?

In de Operations Research (OR) worden geavanceerde analytische methoden gebruikt om betere beslissingen te nemen. Operations Research is geen standaardoplossing die meegeleverd wordt met de volgende versie van het operating system van je computer. Het vraagt specialisten met kennis en ervaring om er praktisch bruikbare resultaten mee te behalen. OR is niet alleen theoretisch, de kracht zit hem in de praktische oplossingen die het kan beiden.

OR is in Engeland ontstaan vlak voor het uitbreken van de Tweede Wereldoorlog. De behoefte aan een structurele en praktische benadering van tactische en strategisch militaire vraagstukken leidde tot de initiatie van OR. Het doel van het toenmalige onderzoek was het vinden van de meest effectieve manier om beperkte militaire middelen aan te wenden. Dat hebben ze bereikt door gebruikt te maken van kwantitatieve technieken. De doelstellingen van OR zijn ten opzichte van het toenmalige onderzoek niet veranderd, behalve dan dat het zich niet beperkt tot militaire toepassingen. Vele sectoren plukken nu de vruchten van de mogelijkheden die OR kan bieden. Op deze blog wil ik je daar voorbeelden van laten zien en je laten meekijken in de OR praktijk, OR at Work dus.