Wartezeiten bei zyklischen Bedienungen an Kanten

Bei der Betrachtung von periodischen Kantenproblemen gibt es einen Planungshorizont H. In H sollen Kanten / Jobs erledigt werden. Bis zur nächsten Bedienung der Kante gibt es dann ein Zeitfenster als Abstand zu der letzten Bedienung: einen Minimalen Abstand minspan (u) und einen maximalen Abstand maxspan(u) einer Kante u. Daraus ergibt sich eine Kombination comb(u) der möglichen Bedientage.
Bei einem Planungshorizont H von einer Woche gibt es np = 7  Perioden : { 1,2,3,4,5,6,7=np}, um täglich Bedienung durch zuführen, oder bei einer 2xwöchentlichen Bedienung einer Kante kann z.B. comb(u)  = {1,4} oder {2,5} sein. Da aber an Samstagen und Sonntagen keine Bedientage sind reduzieren sich die Möglichkeiten:

• 1 mal pro Woche: {1},{2},{3},{4},{5} // Mo, ... Fr
• 2 Mal pro Woche: {1,4}, {2,5}
• 5 mal pro Woche: {1,2,3,4,5} // täglich

Periodizität an den Kanten

Periodische Kantenprobleme

An m Kanten (Straßenabschnitten) in einem gerichteten Graph G  gibt es einen bestimmten Planungshorizont H mit einer Anzahl von np Perioden.
Jeder Job oder Kante hat einen bestimmte Frquenz. Dabei ist bei den ungerichteten Kanten darauf zu achten, dass nicht nur die Kosten einmalig für beide Kanten u und v anfallen, sondern auch die Frequenz f(u) gleich ist (f(u)  = f(inv(u)). So muss eine Kante u 1<= f(u) <= np mal im Planungshorizont H bedient werden.
Die Summe aller Frequenzen ns im Planungshorituont H zerteilt das Problem in bestimmte Tagesrhytmen. Unglücklicherweise können die Bedientage nicht willkurlich gewählt werden, sondern sie sollen auch Abstandsregeln einhalten; somit sollen 2 Bedientage in der Persiode wöchentlich nicht z.B. Montag-Dienstag stattfinden, sondern dazwischen mindestens ein Bedienpausentag liegen (z.B. Montag- Donnerstag).

Strafen für schlechte Abbiegemanöver

Strafen für schlechte Abbiegemanöver

Ein Weg, um in routingfähigen Graphen unvorteilhafte Abbiegemanöver darzustellen, ist besteht darin zwischen zwei Kanten Abbiegestrafen zu hinterlegen.
Das Betrifft Linksabbiegungen bei Ampeln oder sog. U-Turns, die sich mit größeren Fahrzeugen schwer durchführen lassen.



Bei dem o.a. Beispiel sind von der eingehenden Kante u vier verschiedene, zulässige Abbiegungen zu den Kanten v1,...v4 (turn (u,v1), turn (u,v2), ...) möglich .
Abbiegestrafen würden hier wegen des U-Turns zwischen u und v1 mit der Straf-Funktion pen (u,v1) abgebildet.
Um von einer Kante u zu einer Kante v einen zulässigen Pfad µ zu bekommen, werden nur zulässige Abbigemöglichkeiten (turns) in Betracht gezogen.
In der Liste der zu bedienenden Kanten µ werden bei der Berechnung der Kosten die Kosten der Quellkante u und die Kosten der Senke v nicht mit berücksichtigt.

Verbotene Abbiegemönover wenden in einer m x m Distanzmatrix D zwischen den m Kanten berücksichtigt, so dass sich die Distanzfunktion d(u,v) die kürzeste, zulässige Entfernung zwischen den Kanten u und v berechnet. Die Distanzmatrix pro Pfad kann via Dijkstra in O( m log m) berechnet werden.

	v1	v2	v3	v4
u	U-Turn	L-Turn	0	0

Zusätzlich sind noch die Regiefahrten ins Revier und zum Depot zu berücksichtigen.

Bedienenung einer Straße

 Bedienung einer Straße

Graph zur Bedienenung einer Straße

Die Modellierung eines Gaphen der wirklichen Welt:
Nodes N und Arcs A bilden einen gerichteten Graph G = (N,A). Jede gerichtete Kante u aller m Kanten aus A kann durchfahren werden von der Quelle b(u) zur Senke e(u).
Jede Kante hat einn Bei einer Leerfahrt über die Kante u entstehen Kosten c(u). Jede Kante kann ein Andorderung (Job) haben.
Die Teilmenge der Kanten mit Anforderungen im Graphen G heissen R, die einzelne Anforderung einer Kante u aus R somit r(u).

Die gerichteten Kanten u2 (b->a)  und u3 (a->b) können oBdA wie Einbahnstraßen zusammengefasst werden. Bei jeder Duchfahrt werden die Anforderungen r1 und r2 auf beiden Seiten bedient.
Die ungerichtete Kante u1 ( a->b, b->a) bedient beide Seiten in beiden Richtungen. Der Job an dieser Straßen kann also in beiden Richtungen erledingt werden.
Deshalb gibt es zwei Kanten v1 und v2 im Graphen G mit Verweisen v1 = inv(v2) und v2 = inv(v1) zueinander. Wenn die Kante nicht "Windy" ist, so sind die Bedienkosten in beiden Richtungen gleich r(v1) = r(v2). Im Weiteren ist darauf zu achten, dass es sich bei den Kanten v1 und v2 aber nur um eine Anforderung r(u1) an der ungerichteten Kante u1 handelt, wenn inv(v1) existiert.

 (C) 2010 Volker Engels, www.softwareengel.de

Blog mit Grafik aus Google Draw

Eine Grafik einzubinden war bisher immer mit mehreren Schritten verbunden. Der Grapg-Editor von Google lässt einfache Abbildungen einfach erstellen und auch für die öffentlichkeit Referenzieren :
<img src="http://docs.google.com/drawings/pub?id=1geiSMs5zP6ZJsWLRsCCunO8mXvfWnQj6Rxa0RutXC4U&amp;w=960&amp;h=720">
Und so sieht das dann aus:

Mit flos Agent und Sony mobile SMS senden

Die Mäusetastatur ist für mich wirklich eine Strafe beim SMS-Schreiben, und ich verliere wohl den Anschluss zu der Generation Daumen, wenn da nicht  - ja wenn da nicht noch eine Möglichkeit wäre.

Der erste Versuch begann mit einem Sony G705 und eine Bluetooth-Tastatur von Logitech (steht keine Produktbeszeichnung drauf – ist auch ein Seltenes Gerät, funktioniert wunderbar mit der PS3). Das Verbinden funktioniert leider nicht, also BT-Tastatur für BT-Handy zum SMSen nicht möglich.

Aber mein PC hat auch eine BT-Verbindung, also warum nicht damit. Das Installationspaket von Sony-Ericcson wollte ich nicht installieren – versuche mein PC nicht mit unnötigem Mist vollzumüllen. Also nur mit Bordmitteln? Mobil G705 mit PC Koppeln und ein BT-Modem installieren , das sieht dann so aus.

 

 

Der serielle Adapter erscheint nach Doppelklick auf DFÜ-Netzwerk. Danach ist ein BT-COM-Port verfügbar:

Jetzt fehlt noch ein einfaches Programm, das die AT-Befehle an das Handy sendet, um Daten auszulesen und auch SMS zu senden. Nach einiger suche findet sich ein Tool, Open Source – leider in Delpi? programmiert aber funktioniert ohne Installation. Das Tool nennt sich „floAt's Mobile Agent 2.2“ und nacht nach der Aswahl des Com-Ports alles von selbst. Geräteerkennung, Historie, usw. laden, …

Nach dem Sychronisieren der Ordner mit den Textnachrichten

und die gesendeten und empfangen Nachrichten sind im PC-Kasten.

 

Jetzt noch auf "reply" klicken und wenigsten die PC-Tastatur hilft bei den SMSen.

So einfach kann's sein.

 

simple XML Serialisierer

XStream http://xstream.codehaus.org/tutorial.html (BSD license)

Der CollectionConverter unterstützt :

• java.util.ArrayList
• java.util.LinkedList
• java.util.HashSet
• java.util.Vector
• java.util.LinkedHashSet

Es gibt noch weitere Converter für häufig benztzte Java-Basis-Klassen ..
XStream ist kein Databinding-Tool (wie JAXB).

Alternativen:

• JAXB
• java.beans.XMLEncoder
  

Java Graph - Framework JUNG

Framework for the modeling, analysis, and visualization of graphs in Java

unterstützt Graphen

• gerichtet unf ungerichtet
• BFS
• Dijkstra
• Visualisierung

Basiert auf

• Commons-Collections API
  http://jakarta.apache.org/commons/collections/
• CERN Colt API (1.2.0)
  http://dsd.lbl.gov/~hoschek/colt/
  matrix operations, statistics

Doku:
http://jung.sourceforge.net JUNG Home
http://jung.sourceforge.net/presentations/JUNG_M2K.pdf
http://jung.sourceforge.net/doc/api/index.html?overview-summary.html JUNG 2.2 API

Web-Spider

Wenn Onlineangebote offline interessant sind, dann können diese heruntergeladen werden. Kandidaten für diesen Job:
- httrack (http://www.httrack.com/)
- Backstreedbrowser (http://www.spadixbd.com/backstreet/#BackStreet_Download)

Beispiele der Angewandten Graphtheorien

http://www.ics.uci.edu/~eppstein/geom.html

http://www.ics.uci.edu/~eppstein/junkyard/all.html

OWL + RDF - Server

Eine einfachste SPARQL - Abfrage aller Aussagen: select ?s ?p ?o where {?s ?p ?o}.
Alle Aussagen / Sätze sind in ein Tripel zerteilt: Subjekt - Prädikat - Objekt.

Der OpenRDF -Server Sesame lässt sich in einfachster weise auf einem Applicationserver wie Apache Tomcat installieren in dem 2 WAR-Dateien in den WebApp - Ordner bzw. den Autodeploy- Ordner kopiert werden. Sesame bietet ein API an, mit dem auf dem Server u.a. auch mit SPARQL- Abfragen abgesetzt werden können. (TODO: ob Datenmanipulations-Abfragen z.B. Insert funktionieren ist noch offen).

Der Zugriff funktioniert auch über spezielle REST- Requests. Leider bietet Sesame keine WSDL- Schnittstelle an, so dass wir eine eigene entwickeln.

http://openjena.org/ Jena – A Semantic Web Framework for Java
http://jena.sourceforge.net/ARQ/ ARQ - A SPARQL Processor for Jena
http://joseki.sourceforge.net/  Joseki A SPARQL Server for Jena
http://www.ibm.com/developerworks/xml/library/j-sparql/ IBM-Artikel:Search RDF data with SPARQL
http://www.openrdf.org/  ...home of Sesame
http://ibm-slrp.sourceforge.net/2006/11/20/boca-the-rdf-repository-component-of-the-ibm-semantic-layered-research-platform/

http://www.slideshare.net/dpalmisano/from-the-semantic-web-to-the-web-of-data-ten-years-of-linking-up

http://www.dbpedia.org
TODO: siehe "Any23"

Eclispe Project Gemini

Enterprise Modules or Project Gemini,
whose primary goal is to provide access to standard enterprise
technology implementations within a modular framework. The project will
include important Spring related OSGi reference implementations
(Blueprint Service Implementation and Web Container Integration)
contributed by SpringSource
as well as contributed code by other industry leaders in
modularization. All sub projects will be consumable as modules (or OSGi
bundles) and will provide implementations for important and popular
enterprise standards.
Gemini will be a part of the Eclipse Runtime Project and developers using Spring and OSGi are encouraged to participate and give input via the Gemini community forum.


Quelle: http://www.springsource.org/node/2178

Eclipse SOA - neue Informationen

Nachdem ich nach SOA-Komponenten in Exlispe gesucht hatte, hatte ich lange wenig gefunden. Nun gibt es eine "Eclispe SOA" Seite, in der wenigsten die Treiber der Eclipse SOA Initiative (Sopera, beao, itemis und Engineerung group) benannt sind. Der letzte Newseintrag ist vom 21.04.2010! Interessanter weise gibt es verschiedene Distributionen, u.a. eine die Sich SOA/SCA Obeo Distro nennt. Da SCA/SDO wohl in Zukunft eine Rolle spielen werden, klingt das interessant. auch Sopera bietet eine MemberDistro ihres Sofera ASF an (Swordfish) - und die Eclipse SOA Platform for Java and SOA Developers.