pgrouting Dijksta Travelling Salesman Problem (TSP) with OpenStreetmap
I recently had to educate myself about Route Optimization due to an upcoming project. One of the interesting features was to solve the so-called “Travelling Salesman Problem“: To find the correct ordering of places to visit when driving on a road in order to minimize the number of km to drive (so cost=length of route in this case).
I wanted to do the Optimazation on freely available data, therefore I choose OpenStreetMap as a data source. I then tried to find out which program is suited best to do such kind of optimization under Linux. I first stumbled upon OsmSharp and took the pain of all the Mono compilation woes, but soon learned, that it does not suit well for the imposed task, because it has to load all data before doing optimization and so it doesn’t work well in a timely manner, if you for example want to do an optimization for a lot of points within Austria.
So I learned about pgrouting which seems to be a PostgreSQL database designed specially for Geospatial processing. There is a simple guide on how to import OSM data to pgrouting. libgaul isn’t needed anymore, as the TSP extention dependency on it was removed in version 2.0.
I found out, that there are simple TSP-Solutions in pgrouting using the pgr_tsp function, however, they only do euclidean distance checking and that wasn’t what I wanted (even tough the help for the function mentions that euclidean distance should be sufficient in most cases – for me, it wasn’t good enough). I wanted to find the correct order of points using the given road network. In order to do this, you have to take all your points you want to visit and then calculate the distance between all of them forming a distance matrix. As the way between all points is the same in both directions, you end up calculating n²/2-n ways (where n is the number of points to visit). Then you have to do a TSP-calculation over that matrix and as a result, you get the correct order.
To calculate the fastest route between 2 points, you can use the pgr_kdijkstraCost SQL function of pgrouting (as the name implies, it’s using the Dijkstra algorithm).
I am an absolute newbie on PostgreSQL, therefore my solution may not be the cleanest, but here is how I solved this problem:
1) Install my pgrouting Dijkstra functions, which basically offer you 2 functions:
pgr_tspDijkstra - Does a TSP optimization using Dijkstra distances pgr_tspDijkstraLen - Does the same, but implies that cost = length of route
2) My functions are designed so that you have to create a table containing all the points that you want to visit on your route. So create this table:
create table my_route (id serial, lat double precision, lon double precision, node integer);
3) Now you most probably have the points you want to visit as Longitude/Latitude points, so just insert your points into that table:
insert into my_route(lat,lon) values (48.30609, 14.28642); ...
4) Now you have to calculate the correct nodes for all the points you entered, because pgrouting is only accepting node-IDs. This can be done with the folowing statement:
update my_route g set node=(
SELECT source FROM (
SELECT source, distance(the_geom,
GeometryFromText('POINT('||g.lon||' '||g.lat||')', 4326)) AS dist
FROM ways
WHERE the_geom && setsrid(
('BOX3D('||g.lon-0.1||' '||g.lat-0.1||','||g.lon+0.1||' '||g.lat+0.1||')'
)::box3d, 4326)
order by dist LIMIT 1
) as foo
);
5) Now that you have all the nodes in your table, it’s time to do the real calculation. If length is the only cost of a route for you, simply use the pgr_tspDijkstraLen function. You have to find out the node ID of the starting node from your my_route table and pass it to the function, so that it knows where to start. The syntax for the function is:
function pgr_tspDijkstraLen(thetbl text, start_id integer, end_id integer default (-1))
thetbl - Name of your table that contains all the nodes to visit
start_id - Node ID of the starting point
end_id - Node ID of the last point to visit. If not given, it's a round trip
ending at the starting point.
Therefore it’s as simple as i.e.
select * from pgr_tspDijkstraLen('my_route', 189064);
As a result, you get a table with the folowing columns:
seq | id1 | id2 | cost -----+-----+--------+------------------ 0 | 2 | 64186 | 11.1983268959869 ...
seq - row sequence number in the resulting table. id1 - internal index into the distance matrix id2 - id of the node cost - cost to traverse from the current node to the next node.
So theoretically, you can use the following statement to get your lon/lat points ordered:
select id,lon,lat from pgr_tspDijkstraLen('my_route', 189064
) dj, my_route rt where dj.id2=rt.node;
Now there may be the case that you have your own slightly trickier definition of the cost, not just the length of the route. In this case, you can use the pgr_tspDijkstra function.
Its syntax is:
function pgr_tspDijkstra(thetbl text, sql text, start_id integer, end_id integer default (-1)) thetbl - Name of your table that contains all the nodes to visit sql - SQL statement that returns a pgr_costResult to do TSP optimization on start_id - Node ID of the starting point end_id - Node ID of the last point to visit. If not given, it's a round trip ending at the starting point.
So basically, it’s just the same as the pgr_tspDijkstraLen function, but hsa the additional parameter sql, which lets you define your own costresult to do TSP optimization on. For an example on how to use this, just have a look at what pgr_tspDijkstraLen returns:
return query SELECT * FROM pgr_tspDijkstra(thetbl,
'SELECT gid AS id, source::integer, target::integer,
length::double precision AS cost FROM ways',
start_id, end_id);
I hope that this function is useful to anybody and feedback is appreciated.
svchost.exe using 100% CPU because of Windows Update (wuauclt) in XP
Recently I had a Windows XP machine where CPU usage stayed at 100% for approx. 10-15 Minutes after startup. So I used process analyzer to check which thread was using the CPU and (as usual) it turned out to be Windows Update.
It seems that some recent Windows XP updates broke the system once again (after already having issues with an update ruining DOS high memory last year). The solution to the problem is to install the updates KB2879017 and KB2870699 manually. After installing these and a reboot, CPU usage of svchost.exe went back to normal.
Edit: Here is an explanation from Microsoft why this is happening.
“Speichern unter” Dialog hängt
Hatte heute wieder einen Fall, dass eine Shell-Extension auf einem Rechner Probleme machte und den Speicher unter Dialog zum Hängen brachte (besonders ärgerlich in MS Office, da will man speichern….)
Hier die Lösung:
http://superuser.com/questions/378296/windows-7-save-dialog-hang-any-solutions
War genau wie dort angegeben. Verursacher war die Erweiterung “Share-to-Web” von HP. Mit ShellExView von nirSoft deaktiviert und er hängt nun nicht mehr.
Doodle Alternative
Nachdem Doodle für mich mittlerweile unbrauchbar geworden ist, da es
1) Mit allen etwas älteren Browser-Versionen nicht mehr funktioniert und die mobile Version quasi nicht verwendbar ist
2) Es mit HTTP-Proxies überhaupt nicht funktioniert
war ich auf der Suche nach einem brauchbaren Ersatz.
Und hier ist das Ergebnis meiner Recherche: Dudle!
Windows XP von IDE-Festplatte auf SATA-Festplatte migrieren
Unlängst hatte ich die Problemstellung, ein Windows XP von einem alten Rechner mit IDE-Festplatte auf einen neuen Rechner mit SATA-Festplatte zu migrieren. Ansich keine große Sache, man kopiert mittels Diskimager (wie z.B. dem kostenlosen Macrium Reflect) ein Image der alten Platte auf die neue Platte, indem man diese z.B. mittels eine USB-Adapters an den alten Rechner anhängt und stellt anschließend im BIOS den SATA-Mode der SATA-Platte im neune Rechner von AHCI auf IDE. So weit, so gut, das bekannte Procedere…
Das Problem hierbei war nur, dass die Kopie von Windows XP nur Treiber für den im alten Zielgerät verwendeten IDE-Treiber installiert hatte und damit mit dem SATA IDE-Modus am neuen Rechner nicht zurechtkam, was im bekannten STOP 0x7B (INACCESSIBLE_BOOT_DEVICE) endet.
Nun gibt es in der Microsoft Knowledge Base ja den Artikel KB314082, welcher die Vorgehensweise in so einem Fall erklärt. Das Problem ist nur, dass der Artikel dort davon ausgeht, dass man den gleichen Festplattentyp (sprich: IDE) von einem Gerät zum Anderen überträgt, also dass es damit quasi möglich ist, von der kopierten Platte im alten System zu Booten und Anpassungen am dort laufenden System durhczuführen. In diesem Fall war dies allerdings nicht möglich, da ich ja auf eine SATA-Platte kopiert hatte, von welcher ich im alten System nicht booten konnte. Die Lösung des Problems ist dennoch relativ trivial.
Man hängt die kopierte Platte z.B. mittels eines USB-Adapterkabels an ein beliebiges Windows-System an (in unserme Fall einfach an den laten Rechner, wo wir die Platte ja auch schon zum Kopieren hängen hatten) und führt folgende Schritte analog zur Anleitung des KB-Artikels aus:
- Extrahieren Sie aus der Datei “%SystemRoot%\Driver Cache\I386\Driver.cab” die Dateien “Atapi.sys”, “Intelide.sys”, “Pciide.sys” und “Pciidex.sys”, oder kopieren Sie diese Dateien in den Ordner “%SystemRoot%\System32\Drivers” der Zielplatte.
- Öffnen Sie den Registrierungseditor (Start/Ausführen/regedit) , gehen Sie auf den Schlüssel HKEY_LOCAL_MACHINE und gehen Sie im Menü Datei auf “Struktur laden…” und öffnen Sie die Datei %SystemRoot%\System32\config\SYSTEM der Zielplatte. Benennen Sie den Einhängpunkt für die Struktur z.B. dest
Damit ist die Registry der kopireten Windows-Installation unter HKEY_LOCAL_MACHINE\dest eingehängt. - Laden Sie die mergeide.reg vom Knowledgebase-Artikel in einem Texteditor und ändern Sie mittels Suchen & Ersetzen (CRTL+H) den String
\SYSTEM\CurrentControlSet
in
\dest\ControlSet001
Damit wird die .reg Datei angewiesen, nicht in die Registry des aktuellen Systems zu schreiben, sondern in die eingehängte Struktur des Zielsystems.
- Doppelklicken Sie auf die .reg Datei, um sie mit der Registrierung zusammenzuführen.
- Markieren Sie den HKEY_LOCAL_MACHINE\dest Zweig, wo Sie die Remote-Registrierung eingehängt haben und gehen Sie auf Datei/Struktur entfernen… um die Remote-Registrierung wieder zu entladen.
- Hängen Sie nun die Zielplatte aus und geben Sie diese in den neuen Rechner und schon sollte dieser wie gewohnt von der Festplatte booten.
Mithilfe dieses einfachen Procederes sollte es möglich sein, Windows XP auch problemlos von IDE auf SATA-Platten umzukopieren.
Replicate directory timestamps
Yesterday I copied a huge amount of data from one harddrive to another. The timestamps of the files were preserverd correctly, but the timestamps of the directories were changed to the date of the copying. I know that there are utilities that may preserve the timestamps, like presumably robocopy, but I didn’t want to copy all files again as this took half a day.
So I wrote a little utility that replicates the directory Timestamps from one directory to the other. If you are in the same situation as me, you may want to give it a try, get it here.
VMWare 9 – PC Speaker bug
Unter VMware 9 funktioniert aufgrund eines Bugs der PC Speaker nicht mehr, von einem Upgrade wird daher abgeraten, bis der Fehler beseitigt wurde, was bis Dato leider noch nicht der Fall ist.
IBM Access Connections findet kein WLAN mehr
Hatte unlängst den Fall, dass IBM Access Connections auf einem Thinkpad kein WLAN mehr gefunden hat. Stellte man die WLAN-Steuerung von Access Connections auf Windows um, fand Windows die Netze aber problemlos.
Des Rätsels Lösung war, dass sich in Windows-Verzeichnis eine veraltete ssleay32.dll von OpenSSL befunden hat, was scheinbar dazu geführt hat, dass Access connections keine Verbindung mehr mit dem Interface des WLAN Treibers herstellen konnte. Habe die Datei dann gelöscht und durch eine neuere aus einem der IBM-Verzeichnisse ersetzt, neu gestartet und siehe da, es funktioniert wieder.
Windows XP benötigt Minuten lang nach dem Boot-screen, bevor der Desktop kommt
Heute hatte ich einen Windows XP Rechner mit einem sehr merkwürdigen Problem:
Nach dem Windows XP Bootscreen mit dem Ladebalken wurde der Bildschirm schwarz, was ja noch normal ist, aber danach kam Minutenlang nichts, bevor endlich der Desktop erschien (ca. 7 Minuten Wartezeit).
Ich habe mich dann mit dem Process Monitor von Sysinternals auf die Lauer gelegt und den Bootvorgang protokolliert. Ergebnis war, dass der Ladevorgang normal verlief, bis schließlich “DeviceUsageNotification” auf C: angezeigt wurde, dann Minutenlang nichts und erst dann ging es wieder weiter. Hilft einem also auch nicht wirklich, aber das Ganze hat scheinbar schon jemand Anderer versucht und über dessen Fehlerbeschreibung in einem Russischen Forum bin ich dann auf die Lösung des Problems gestoßen:
Was ihm wie mir aufgefallen ist, ist, dass in der Ereignisanzeige unter “System” die Zeitstempel vertauscht waren, also (normalerweise ist das neueste Ereignis ganz oben):
22:06:46 Service Control Manager 22:02:18 Tcpip 22:02:10 HECI 22:05:50 eventlog
Das HECI hat mich ohnehin schon etwas stutzig gemacht, das gehört scheinbar zu den Intel Management Engine Komponenten, aber ob es die Ursache für die Probleme ist konnte ich zu diesem Zeitpunkt natürlich noch nicht sagen. Im Forum war dann der Tip zu lesen, dass man die Größe des Registry-Zweigs “default” überprüfen sollte (wie wir wissen lagert die Registry ja in windows\system32\config), und die Datei war in der Tat etwas aufgebläht (88 MB). In weiterer Folge hatte der Benutzer dann auch den problematischen Zweig identifiziert:
HKEY_USERS\.DEFAULT\Software\Microsoft\Windows\CurrentVersion\Internet Settings\Digest\Hosts
Mein Verusch, diesen Zweig im Registry Editor zu öffnen erwies sich tatsächlich als Minutenlanges Geduldspiel. Schuld daran scheint die “Intel Management Engine” zu sein, die den Zweig permanent vollmüllt.
Und tatsächlich, ein Entfernen des Treibers brachte Abhilfe. Also, Lösung:
1) Systemsteuerung/Software -> Intel Management Engine deinstallieren
2) reg del "HKEY_USERS\.DEFAULT\Software\Microsoft\Windows\CurrentVersion\Internet Settings\Digest\Hosts"
Näheres kann man hier nachlesen.
Repairing boot loader of damaged Sony Vaio Recovery partition
Today I got a Sony Vaio notebook where the user tried to reinstall the Operating System, but not, as supposed via the Vaio Recovery (by hitting F10 on boot and booting to the recovery console), but by installing the OS himself. He failed with installing Windows XP because of some drivers which were not available for download, so he tried to install Windows Vista which was overkill for the poor machine.
The interesing thing about the machine in the state I got it, was, that the Recovery Partition actually wasn’t hidden, but visible and the Bootloader for Vista (and previously XP) was installed to that partition so that the original loader for the Recovery partition got overwritten. Additionally, no recovery DVDs were available. So to install the proper XP Image, which was still on the (now visible) recovery partition, I needed to make the recovery partition bootable again so that it doesn’t boot into the OS which I wanted to reinstall, but into the recovery console when F10 on boot gets pressed. I finally found out how it works:
There is a directory MININT on the partition which contains a minimal version of Windows XP used as a base for the recovery program. This is loaded by the SETUPLDR.BIN boot loader (as opposed to the default NTLDR bootloader), which starts NT in in MININT directory and then uses texsetup.inf there for further processing (in this case: Launching the Recovery application). Therefore I ha to replace the Windows Vista Bootloader with the XP Bootloader and make it load the SETUPLDR. I accomplished this by ensuring that the recovery partition is visible, booting to the Windows XP Recovery console, selecting C:\MININT as installation and then using the well known restore-Commands:
FIXBOOT FIXMBR copy minint\setupldr.bin ntdlr
exit, and the machine rebooted straight into the Recovery system where I managed to restore the original System image. More information about the SETUPLDR can be found in appendix C in this article.
System programmer