# Emergency Services: How to optimize routing by measured travel time?

I would like to optimize the service areas / catchment areas for an emergency service. Therefore, I have several measurement points on the streetmap, where people have stopped the travel time from base station to these points.

All roads are classified in 6 different classes (e.g. motorway, path). Now I would like to set up a linear optimization to solve the average speed per road type. Is this linear speed optimization possible in systems like PostGIS and QGIS? Any tutorial or knowledge? Otherwise I would implement it in Mathematica, which is not optimal since all my data is already in the GIS.

Before I decided to do this, I searched for data average speed vs. road type on the net. However, there seems to be no scientifically thorough data on this topic? Maybe one on this board knows any data or report? I mean, it should be available, since all routing suppliers have those data...

@Editors: Could someone add a new tag "emergency services" and optionally tag all questions on this topic like this? I think there is a growing user base on this (advanced) topics.

-
I dont understand what exactly you are looking for. Do you want to find out the speed of a certain road type ? Why? Isn't that already implicitly given by the road type + administration boundary? Or do you want to find a place for new emergency services? – Karussell May 5 '13 at 15:56
I am looking for the average speed per road type. E.g. on a motorway with a truck ~95kmh. Since I have several paths with several road types behind each other, I can optimize the average speed on the total network by the linear optimization of the speed paramter. Why: Because for emergency services administrational boudaries are not implicitely the boundaries for max. speed. – Frank May 5 '13 at 16:00
But why do you need an optimization? What can you optimize? Dont you 'just' need an information which tells you the time from x to every other points in the emergency service boundary? – Karussell May 5 '13 at 16:04
with Dijkstra (which is a many to one algorithm) .. not really linear optimization – Karussell May 5 '13 at 16:09
Ok, so you don't need the mean weights you want to calculate them ... but I still don't get the original reason of 'why' you want this. Also I see a problem as for some road types you can drive different fast (e.g. industrial area vs. inner city), and this leads to false results for the mean values. – Karussell May 5 '13 at 16:22

The most obvious approach I can see for this problem is to first determine the legal speed limits for all roads in the area of interest. Then using the travel time measurements, see how much longer than the theoretical minimum travel time the actual times are. Could be as simple as a factor which is applied to reduce the max speed. The factor could be determined per road class.

Before I decided to do this, I searched for data average speed vs. road type on the net. However, there seems to be no scientifically thorough data on this topic? Maybe one on this board knows any data or report? I mean, it should be available, since all routing suppliers have those data...

They have some data but it's rarely clear how they got it or how reliable it is. They certainly won't give it away because it's one of they few key advantages they still hold over OSM and their other competitors.

-
Thank you for the extra tag! Well, I agree that it is likely a linear factor to multiply with. But the network (as your example of Vienna) is too large to do this manually for every measurement point. Reg. the scientific output: Yes, surely a selling proposition for commercial products. Anyway, a lot of OSM people are linked to geo sciences (as you are). I cannot imagine that the knowledge of the routing companies were not discussed priorly in university / research? – Frank May 5 '13 at 16:54
Well, TomTom/TeleAltas use speed measurements from personal navigation devices to get realistic speed estiamtes. But that's not an option for you. And before that was possible, my honest impression is that they simply guestimated the speeds based on legal speed limits, traffic volume and experience. – underdark May 5 '13 at 16:57
Of course all routing engines (including graphhopper ;)) are using this as estimation. BTW: Why is the network too large? Still I don't understand the main problem which you want to attack – Karussell May 5 '13 at 18:38
The main problem is estimating new speeds per class, based upon actual times for known routes, covering at least all classes. With 6 classes, a minimum of 6 routes are needed. With more routes, you can do a linear optimization - best fit. I am not sure how precise this will be, but it is not something you find in either PostGIS or QGIS. A mathematical optimization library is needed. But even Excel can do this, I think. – Uffe Kousgaard May 6 '13 at 8:45
@Uffe Kousgaard: yes, you understood my problem. I am on the way to Mathematica. – Frank May 6 '13 at 15:23

Ok, I obtained the speed settings per road class by a linear optimization.

1. Obtain the path length for which the travel time was measured. This can be done by pgrouting and QGIS. First route the shortest path or manually draw it, then export the path with its road classes to excel.
2. Within Excel use a Pivot table to extract the sum per road type and route.
3. Now it is a linear optimization problem to find the max. speed with respect to the measurement data. Here, as Uffe suggested the Excel solver can do this, probably. However, since I did not know how to arange the table for the solver, I chose my standard solution Mathematica
4. In Mathematica you can use

3.6/LinearProgramming[c, A, t, Method -> "Simplex", Tolerance -> .1]

where A is the matrix with the path length per road type, c is the initialization vector to be optimized and t is the vector with the experimentally obtained total drive times.

One remark: As to the simplex and interior point optimization: If you have several measurements for the same road type, the min. driving time aka max. speed is chosen and not averaged. This could be solved by preparing the linear equations first by a Gaussian algorithm or by averaging where classes are not entangled. Maybe someone else knows a more elegant way?

Furthermore, since extraction of the roads is done in postGIS/QGIS, a fine grain classification between road types inner and outer city is also possible.

Best regards,

Frank

-