Friday, 28 December 2007

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?