Intelligent Problem Solving with Dr Neil Urquhart of Edinburgh Napier
Category: Blog
By Janice
22/02/2017
Company Connecting continues its focus on Edinburgh with an article from Dr Neil Urquhart of Edinburgh Napier on Intelligent Problem Solving.
Many real-world scheduling and routing problems are difficult to solve, for a long time AI techniques worked towards simply finding a feasible solution. It was enough to build a plan for scheduling a production process, organising a set of deliveries or rostering staff, producing an error free plan represented a significant challenge. In many cases such an automated plan might well not be as useful as the plan produced by an experienced supervisor who has an intimate understanding of the business process.
Let us consider the case of a mobile workforce; a number of clients located at differing addresses require a visit from a member of the workforce, that visit may be restricted to a certain time of day and may require a member of the workforce with specific qualifications. Variations of this scenario exist in many sectors ranging from the provision of social care to the scheduling of field service engineers.
For our mobile workforce problem, there will be many possible plans that will allow each client to receive a visit. Consider the very simple problem of one person having to visit 4 clients, they can visit them in any order, at any time. In this case the number of possible plans would be 12, we can easily examine each plan and pick the one that suits us best, but if we have 8 clients we have over 20,000 possible clients, with 10 clients there are almost 2 million possible plans. As soon as we have multiple employees the problem becomes more complex, with not only the ordering of visits becoming significant, but we must also take into account the allocation of visits to employees. What is significant is that the number of possible solutions to the problem increases exponentially, if the problem becomes twice as big, the number of solutions far more than doubles, computer scientists refer to such problems as NP problems. Many timetabling, scheduling, rostering and routing problems that are encountered in business are NP problems. Given the potentially huge number of solutions to an NP problem, how do we find a solution that suits our needs?
Within the possible solutions to an NP problem, we can usually discount the infeasible solutions, these are ones that break our rules – e.g. that miss out a visit or have an employee in two locations at once. Even discounting the infeasible solutions we are still likely to be left with more solutions than we can construct and evaluate – even using a powerful computing cluster – within a reasonable timescale. It quickly becomes apparent that if we wish to search for a solution with particular characteristics, e.g. low cost or environmentally friendly, then we cannot simply search through every possible solution.
An increasingly common AI technique for finding solutions to such problems is the Evolutionary Algorithm or EA. The EA takes nature as its inspiration, rather than mathematics, it seeks to find a good solution through a process of evolution. To apply an EA to a problem we need two things, firstly a way of representing a possible solution to a problem and secondly a way of evaluating the usefulness of a solution. For a simple routing problem, the representation could be a list of visits in a particular order and the evaluation function the distance that we have to travel in order cover all the visits in that order. In this case the aim of the EA is to find the ordering of the visits that results in the least distance travelled. The EA commences with a group of random solutions, known as a population, each solution is then evaluated. Having evaluated the solutions, we can then pick those the best solutions and use them to create the next generation of solutions. We create the new solutions by recombining the best solutions, so that the next generation are based upon the best of the previous. The recombination seeks to ensure that the new solutions contain some elements of each of their two predecessors. As well as recombination, we can also apply a very small random change or mutation to the new solution. The new solutions are then copied back into the population replacing the weaker solutions. The evolutionary process is repeated many times, should result in an improvement of the solutions in the population.
The EA approach has a number of distinct advantages, firstly it can find reasonably good solutions in a short period of time. In many cases it is not single best solution that is required, but simply a very good solution. For instance an Evolutionary Algorithm might find a solution to our that has a low cost reasonably quickly, whereas to find the optimal solution (that with the lowest cost) may take an unfeasible length of time.
For an example have a look at the demonstration at http://www.soc.napier.ac.uk/~40000408/gwt/ . The demonstration allows the user to locate a central depot and then add up to 20 customers who require a delivery from the depot, each customer may have a time window that specifies when the delivery must take place (e.g. between 10 and 10:20 am). Having placed up to 20 customers the user start an evolutionary algorithm to which will produce a solution. Typically the EA will examine around 5000 possible solutions and present the user with the best so far. Solutions are evaluated on the basis of distance travelled, estimated CO2 produced and the number of vehicles required. If the solution produced is not to your liking click the continue searching button to recommence the evolutionary process.
In summary Evolutionary Algorithms are an AI development that have massive potential for solving complex real-world problems. The ability to find a good solution quickly makes them a useful tool. The evaluation function within the algorithm can be written to take account of specific requirements and constraints. The range of problem solved using EAs is huge and includes logistics and delivery problems, staff scheduling and rostering, education timetabling as well as industrial process scheduling.
Website: http://www.napier.ac.uk/people/neil-urquhart
Twitter: https://twitter.com/NeilUrquhart1
Linkedin: https://www.linkedin.com/in/neil-urquhart-89aa36a
To be featured or find out more:
e-mail us on support@companyconnecting.com
call us on 0845 643 5375
"Intelligent Problem Solving with Dr Neil Urquhart of Edinburgh Napier" First published on Company Connecting February 2017
©Company Connecting
