Optimizing school inspectors’ routes
During Autumn 2021 Gispo was one of the companies co-operating with University of Turku in organizing a “Get to know worklife” type of course for future applied mathematicians and statisticians. The idea of the course was that each of the involved companies present one problem they have faced, but have not yet been able to solve (typically because of limited time resources). However, the company has to offer guidance to the students throughout the course so the company has to have on idea on how to solve the problem. The students, in turn, will act as “borrowed employees” and start to investigate the presented real life problem with the help of co-operation company’s contact person. Each student group of 2-4 persons will have an assigned professor in the team too, just to make sure that each team has enough “academic muscle” to survive the challenge.
Problem definition
We at Gispo wanted to utilize this change for emerging the team into the problem UNESCO International Institute for Educational Planning (IIEP) had presented for us in one of our previous collaboration projects. In other words, we wanted to figure out which would be the most optimal way to arrange school inspections. In practice, we have a bunch of school inspectors living at certain locations and a much greater number of schools whose actions need to be inspected. We at Gispo utilized PostGIS and pgrouting for transforming the actual road network of the study area into routable graph. Since mathematical optimization and GIS data do not really speak the same language, we also created files containing the lengths of each road with its start and end node id. For each graph node we stored the information about their location. We also attached each of the studied schools / school inspectors’ home points into the closest road network node id.
In order to say that we have a solution for the school inspection problem, only one universal requirement has to be met: each school has to get inspected once and only once. But if we look at the problem from a perspective of single school inspector, more requirements emerge:
- The school inspector has to know which schools he should inspect
- The school inspector has to know which of the schools allocated to him he should inspect during the same work day
- Note that a number of work days school inspectors can use for school inspections is limited.
- The school inspector has to know the order he should visit each school planned to be inspected during one work day
- In this project, we assumed that
- the length of a work day is 8 hours
- it takes an hour to complete the school inspection
- The school inspector has to know which routes to take when driving from the first school planned to be inspected during one work day to the second one etc. until he reaches the last school planned to be inspected during that particular work day
In addition to these, each of the school inspector & work day specific school inspection routes should begin and end at the particular school inspector’s home address. In other words, we do not allow overnight trips.
If we wish to talk about the optimal solution, we need to have some way to measure the goodness of each solution. It is not enough to find just some solution which satisfies all the requirements listed above.
The objective: to minimize the distance driven by school inspectors in order to visit & inspect all the schools in the study area.
The roadmap to the solution
Who solves the problem?
- Allocation problem (for the interested: the idea is to create an initial solution and iteratively improve it with the help of nearest neighbor algorithm and simulated annealing): Python program developed specifically for this purpose
- Route optimisation problem (for the interested, the more accurate type of the problem is Time-Window Multi-Depot Vehicle Routing Problem): GAMS
Note that GAMS system creates optimization problems from your models and data, and retrieves results for analysis and processing, but it does not solve the optimization problem. Instead, it uses solvers that have been connected to GAMS and are included in the GAMS system.
It is important to recognize that other, open-source, options for solving phase 2 exist, e.g. NEOS Server or Google OR-Tools. The students chose to use GAMS system mainly because they had a licence for it (offered by the University).
How to understand the solution?
It is not trivial to understand the solution of the route optimization problem. This follows from the fact that we need to convert our demands (requirements) and wishes (objective) into the language of math; in this case into a GAMS-model. No need to go further into the process of creating it. The necessary part is to understand that the construction of the GAMS-model representing the school inspection problem has been automated in this project, and it can be done via executing one command. Likewise, the process of converting the integer solution GAMS produces into standard GIS format has been automatized. As a result, we get out a bunch of GeoJSON files. Each of these files represents a route planned for the particular school inspector to be driven during one of his work days.
The solution for the case study
Image 3: GIF animation visualizing the optimal inspection routes of school inspector 4 for each work day. Animation produced by Gispo Ltd.
Conclusions
Note that the solution power of the developed model, and the tools for solving it, does not limit to this more or less hypothetical case study of inspecting the schools in the subarea of Finland. The same kind of solution can be produced anywhere in the world as long as we have access to the real road network of the study area (e.g. via OpenStreetMap) and we know the locations of the school inspectors and schools to be inspected.
Neither does the solution power limit only for cases where the length of a work day is 8 hours or it takes an hour to inspect a school. All of these things are parametrized and they can get any value necessary. Parameterization can be easily also extended (e.g. if we cannot say that each school inspector has 100 work days to use for school inspection but rather the number of work days available depends heavily on the school inspector).
To wrap up; theoretical models and algorithms may, in some cases, be just what we need in order to solve complex, real-world geospatial problems!
See it for yourself!
All the data used and codes produced in this project (programs for graph analysis, allocation of schools, writing of GAMS model and converting integer solution of the TWMD-VRP onto GIS format), along with the obtained results, can be found in the project’s open gitlab repository.
The team:
Pauliina Mäkinen (Gispo’s representative), Olli Tuhkanen, Jenni Leinonen, Katariina Rantanen and Marko M. Mäkelä (Professor, Applied mathematics)
