Optimisation in Car-Sharing Systems

For many people the costs of owning, running and maintaining a car are simply too big to justify having one. Having to pay hundreds, if not thousands of pounds to cover insurance, road tax and fuel costs for only a few short journeys a week to work or to the shops doesn’t make financial sense. One alternative to this that has proven popular is ‘car-sharing‘ or ‘car-clubs‘. These schemes allow members to access vehicles owned by the company by reserving them in advance so they can use them for the short trips they might make in a day. This could be anything from picking up the kids from school, popping down to the shops or going out for a few hours at the weekend.

There are several other benefits to using a car-sharing schemes in addition to any potential financial savings. By using a single vehicle to do several different people’s short trips means that less cars are on the road in total reducing traffic congestion and vehicle emissions. Even something as simple as being able to guarantee a parking space when you reach your destination can be attractive, particularly in busy inner cities.

See more…

Optimal Search Problems

One active area of research within STOR-i is the problem of how to optimally search for something or someone. This is a problem of practical importance with it being used for many real world applications. Bomb disposal squads need to search for unexploded ordinance, search parties want to look for survivors of disasters and the police want to find people on the run from the law.

Like most things the best way to build intuition to a problem is to start by constructing smaller toy models of the system. We can represent the places where an object might be hidden as arcs in a network which are connected to each other with nodes. This type of structure is deliberately similar to that of a road system, the arcs represent streets and the nodes are the street corners. The object that we want to find will be hidden along one of the streets and the job of those searching is to find it as quickly as possible.


Example Network for Optimal Searches

See More…

Emergency Planning with OR

One recent talk that stood out to me was given by Marc Goerigk and talked about how operational research can be used to help improve evacuation planning for emergencies. For example unexploded WWII era bombs, Lancaster floods or terrorist incidents.

The ideas I will talk about are to do with using an optimisation approach to give a good lower bound on the evacuation time. Simulation techniques on the other hand are more useful for finding an upper bound on the evacuation time.

A clever thing to do when we are trying to model real world places is to try and represent the place in a network. Essentially we can take a map and represent it in a graph network using nodes and arcs. Arcs generally represent paths or roads and nodes the intersection of these paths and roads. This allows us to simplify tricky features such as curved roads into nice straight lines.


Transforming a map of my flat into a network diagram

See More…


Routing Electric Vehicles

Electric cars seem to be the way of the future, they are cheaper to run and better for the environment. However there has always been one thing holding them back in many people’s eyes: actually finding somewhere to recharge and the length of time needed to recharge.

Many companies continue to try and reduce the time needed to fully recharge a car battery, with a new generation of fast charging stations being able to recharge significantly a battery in around 30 mins. However one approach suggested by some companies is to simply swap batteries depleted with fresh ones at stations.


One interesting talk given at that the recent STOR-i conference was presented by Pitu Mirchandani from Arizona State University in the United States. His work has been directed towards electric cars and the somewhat unique problems that crop up for the battery exchange models in particular.

He defined a new problem as the ‘Electric Vehicle Shortest Walk Problem’. Note that it is shortest walk rather than shortest path, as it takes into account the fact that vehicles will often need to take detours in order to recharge or swap batteries. This mean that the problem he had to deal with couldn’t be solved with traditional shortest path algorithms such as Dijkstra’s algorithm and he had to develop a new approach.

The two main things that need to be minimised are:

  1. The total distance detoured from the optimal route (the route with no stops)
  2. The total number of stops (to exchange batteries)

He went on to discuss further his ideas of other interesting problems that can be studied such as where to locate the battery exchange stations and how large they should be. This meant that he was able to propose a system that could decide where every car in the network should stop off on its journey to swap batteries. The point of doing this was that he found the overall total journey time of all the cars in the system was minimised. In particular it was substantially below the case when every driver made their own decision about where and when they chose to stop. So whilst drivers would lose their independence, all road users would benefit.

I should probably conclude by saying that nothing is the world of research is guaranteed. In fact it turns out that the man behind Tesla, Elon Musk, has since changed his mind on battery exchange technology following an unsuccessful pilot. He suggested that people just prefer being able to recharge their car! This appears to be for several reasons, not least of which that recharging at their solar powered superchargers is free and using a battery exchange station costs the same as a fresh tank of petrol!