220 backtrackTSP/src/main/java/org/emergya/backtrackTSP/BackTrackingTSP.java
View file
@@ -0,0 +1,220 @@
/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/
package org.emergya.backtrackTSP;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.gofleet.openLS.tsp.TSPAlgorithm;
import org.gofleet.openLS.tsp.TSPStop;
import org.gofleet.openLS.tsp.TSPStopBag;

public class BackTrackingTSP implements TSPAlgorithm {
private static Log LOG = LogFactory.getLog(BackTrackingTSP.class);

private Boolean partialSolution = false;
private Integer seconds = 18;

private ExecutorService executor;
private ExecutorService executor2;

public BackTrackingTSP() {
}

/**
* If we cannot find a solution, do you like to get the best partial
* solution reached?
*
* @param partialSolution
*/
public BackTrackingTSP(Boolean partialSolution, Integer seconds) {
this();
if (partialSolution != null)
this.partialSolution = partialSolution;
this.seconds = seconds;
}

public List<TSPStop> order(TSPStopBag _bag) {
long time = System.currentTimeMillis();

Runtime runtime = Runtime.getRuntime();
int numthreads = runtime.availableProcessors() * 10;

executor = Executors.newFixedThreadPool(numthreads);

DistanceMatrix distances = new DistanceMatrix();

initializeMatrix(distances, _bag);

SolutionContainer solutions = new SolutionContainer(distances);

if (_bag.size() > 7) {
if (_bag.hasLast()) {
// run(executor, new AStar(_bag, distances, solutions));
run(executor, new HeuristicBacktracking(_bag, distances,
solutions));
} else {
for (TSPStop stop : _bag.getAll()) {
List<TSPStop> stops = new ArrayList<TSPStop>();
stops.addAll(_bag.getAll());
stops.remove(stop);

BacktrackStopBag bag = new BacktrackStopBag(stops,
_bag.getFirst(), stop);
// run(executor, new AStar(bag, distances, solutions));
run(executor, new HeuristicBacktracking(bag, distances,
solutions));
}
}
}
run(executor, new Backtracking(_bag, distances, solutions));

executor.shutdown();

try {
if (!executor.awaitTermination(
this.seconds - (System.currentTimeMillis() - time) / 1000,
TimeUnit.SECONDS)) {
stop();
}
} catch (InterruptedException e) {
if (!this.partialSolution) {
throw new RuntimeException(
"Timeout reached. I couldn't find a solution on a proper time. "
+ "Please, give me another chance with more time or"
+ " accept a partial solution. I won't fail you, I promise.",
e);
}
}

return getBest(solutions, distances, _bag.size());
}

private void run(final ExecutorService executor, final Runnable aStar) {
executor.execute(aStar);
}

private List<TSPStop> getBest(SolutionContainer solutions,
DistanceMatrix distances, Integer size) {

BackTrackSolution solution = solutions.getSolution();

if (solution == null)
throw new RuntimeException(
"I'm embarrased, I was unable to find a solution for you. "
+ "Please, forgive me. I am just a machine.");

return solution.getStack();

}

/**
* Initialices the distance matrix on background while tsp is running.
*
* @param distances
* @param bag
*/
private void initializeMatrix(DistanceMatrix distances, TSPStopBag bag) {

Runtime runtime = Runtime.getRuntime();
int numthreads = runtime.availableProcessors() * 3;

executor2 = Executors.newFixedThreadPool(numthreads);

List<BacktrackStop> candidates = null;
candidates = new ArrayList<BacktrackStop>();
for (TSPStop stop : bag.getAll())
candidates.add((BacktrackStop) stop);

for (BacktrackStop from : candidates) {
executor2.execute(new InitializeDistances(from, candidates,
distances));
}
executor2.shutdown();
Thread t = new Thread() {
@Override
public void run() {
try {
executor2.awaitTermination(6, TimeUnit.SECONDS);
} catch (InterruptedException e) {
LOG.error(e, e);
}
}
};
t.start();
}

@Override
public boolean stop() {
LOG.info("Shutting down backtracking");

if (executor2 != null)
executor2.shutdownNow();
if (executor != null)
executor.shutdownNow();
else
return false;

LOG.info("Backtracking shut down");

return true;
}
}

class SolutionContainer {
private BackTrackSolution solution = null;
private DistanceMatrix distances = null;

public SolutionContainer(DistanceMatrix distances) {
this.distances = distances;
}

public BackTrackSolution getSolution() {
synchronized (this) {
return this.solution;
}
}

public void add(BackTrackSolution solution) {
synchronized (this) {
if (this.solution == null)
this.solution = solution;
else {
if (this.solution.getDistance(distances) > solution
.getDistance(distances))
this.solution = solution;
}
}
}
}
63 backtrackTSP/src/main/java/org/emergya/backtrackTSP/BacktrackStop.java
View file
@@ -0,0 +1,63 @@
/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/

package org.emergya.backtrackTSP;

import org.gofleet.openLS.tsp.TSPStop;

import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.Point;

public class BacktrackStop implements TSPStop {

protected Integer id;
private Geometry position;

public Integer getId() {
return this.id;
}

public Point getPosition() {
return this.position.getCentroid();
}

public BacktrackStop(Integer id, Geometry position) {
super();
this.id = id;
this.position = position;
}

@Override
public String toString() {
return "{" + this.getId()
// + "->" + this.getPosition().toText()
+ "}";
}

}
106 backtrackTSP/src/main/java/org/emergya/backtrackTSP/BacktrackStopBag.java
View file
@@ -0,0 +1,106 @@
/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/

package org.emergya.backtrackTSP;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

import org.gofleet.openLS.tsp.TSPStop;
import org.gofleet.openLS.tsp.TSPStopBag;

public class BacktrackStopBag implements TSPStopBag {

private TSPStop first = null;
private TSPStop last = null;
private List<TSPStop> bag = Collections
.synchronizedList(new ArrayList<TSPStop>());

public TSPStop getFirst() {
return this.first;
}

public TSPStop getLast() {
return this.last;
}

public Collection<TSPStop> getAll() {
return this.bag;
}

public Boolean hasFirst() {
return getFirst() != null;
}

public Boolean hasLast() {
return getLast() != null;
}

public BacktrackStopBag(List<TSPStop> stops) {
super();
this.bag.addAll(stops);
}

public BacktrackStopBag(List<TSPStop> stops, TSPStop first, TSPStop last) {
this(stops);
this.first = first;
this.last = last;
}

public void removeStop(TSPStop stop) {
this.bag.remove(stop);
}

public void addStop(TSPStop stop) {
this.bag.add(stop);
}

public Integer size() {
Integer size = 0;
if (this.hasFirst())
size++;
if (this.hasLast())
size++;
return size + this.bag.size();
}

@Override
public String toString() {
String s = "{";

for (TSPStop stop : this.bag)
s += stop.getPosition().toText() + " ";

s += "}";

return s;
}
}
124 backtrackTSP/src/main/java/org/emergya/backtrackTSP/Backtracking.java
View file
@@ -0,0 +1,124 @@
package org.emergya.backtrackTSP;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.gofleet.openLS.tsp.TSPStop;
import org.gofleet.openLS.tsp.TSPStopBag;

class Backtracking extends Thread {
private static Log LOG = LogFactory.getLog(Backtracking.class);

private BackTrackSolution current;
private BacktrackStopBag bag;
private DistanceMatrix distances;
private SolutionContainer best;

public Backtracking(TSPStopBag _bag, DistanceMatrix distances,
SolutionContainer best) {
this.current = initializeResBag(_bag);
this.bag = getBacktrackingBag(_bag);
this.distances = distances;
this.best = best;
}

@Override
public void run() {
BackTrackSolution solution = backtrack(this.current, this.bag,
this.distances, new BackTrackSolution(new Stack<TSPStop>()));
this.best.add(solution);
}

/**
* Recursive main procedure
*
* @param current
* @param bag
* @param distances
* @param partialSolution
* @return
*/
@SuppressWarnings("unchecked")
private BackTrackSolution backtrack(BackTrackSolution current,
BacktrackStopBag bag, DistanceMatrix distances,
BackTrackSolution partialSolution) {

if (Thread.interrupted())
return partialSolution;

Collection<? super TSPStop> all = bag.getAll();
if (all.size() > 0) {
List<TSPStop> candidates = null;
candidates = new ArrayList<TSPStop>();
candidates.addAll((Collection<? extends TSPStop>) all);

// We try with all the candidates
for (TSPStop stop : candidates) {
bag.removeStop(stop);
current.push(stop);

// If we already have a solution candidate, is the current way
// worse than it? If not, just use current solution as better
if (!(partialSolution != null && current.getDistance(distances) > partialSolution
.getDistance(distances))) {

// Maybe another thread found a better solution
if (partialSolution != null
&& this.best.getSolution() != null) {
if (partialSolution.getDistance(distances) < this.best
.getSolution().getDistance(distances))
partialSolution = (BackTrackSolution) this.best
.getSolution().clone();

}
backtrack(current, bag, distances, partialSolution);
}
if (LOG.isTraceEnabled())
LOG.trace("Current: " + current);

current.pop();
bag.addStop(stop);
}
} else { // We have reached the end of the way
if (bag.hasLast()) {
current.push(bag.getLast());

if (current.getDistance(distances) < partialSolution
.getDistance(distances)) {
partialSolution.setStack(current.getStack());
}

current.pop();
} else {
if (current.getDistance(distances) < partialSolution
.getDistance(distances)) {
partialSolution.setStack(current.getStack());
}
}
}

partialSolution.getDistance(distances);
return partialSolution;
}

private BackTrackSolution initializeResBag(TSPStopBag bag) {
BackTrackSolution res = new BackTrackSolution(new Stack<TSPStop>());

if (bag.hasFirst()) {
res.push(bag.getFirst());
}
return res;
}

private BacktrackStopBag getBacktrackingBag(TSPStopBag _bag) {
List<TSPStop> all = new LinkedList<TSPStop>();
all.addAll((Collection<? extends TSPStop>) _bag.getAll());
return new BacktrackStopBag(all, _bag.getFirst(), _bag.getLast());
}

}
214 backtrackTSP/src/main/java/org/emergya/backtrackTSP/DistanceMatrix.java
View file
@@ -0,0 +1,214 @@
/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/
package org.emergya.backtrackTSP;

import java.io.IOException;
import java.text.ParseException;
import java.util.HashMap;
import java.util.Locale;
import java.util.Map;

import javax.xml.bind.JAXBElement;
import javax.xml.bind.JAXBException;
import javax.xml.namespace.QName;

import net.opengis.gml.v_3_1_1.DirectPositionType;
import net.opengis.gml.v_3_1_1.PointType;
import net.opengis.xls.v_1_2_0.AbstractLocationType;
import net.opengis.xls.v_1_2_0.DetermineRouteRequestType;
import net.opengis.xls.v_1_2_0.DetermineRouteResponseType;
import net.opengis.xls.v_1_2_0.PositionType;
import net.opengis.xls.v_1_2_0.RoutePlanType;
import net.opengis.xls.v_1_2_0.WayPointListType;
import net.opengis.xls.v_1_2_0.WayPointType;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.emergya.osrm.OSRM;
import org.gofleet.openLS.tsp.TSPStop;

import com.vividsolutions.jts.geom.Point;

public class DistanceMatrix {

private Map<Key, Double> distances = new HashMap<Key, Double>();
private static Log LOG = LogFactory.getLog(DistanceMatrix.class);

private OSRM osrm;
private org.gofleet.configuration.Configuration configuration;

public DistanceMatrix() {
this.osrm = new OSRM();
}

public DistanceMatrix(OSRM osrm,
org.gofleet.configuration.Configuration configuration) {
super();
this.osrm = osrm;
this.configuration = configuration;
}

public Double distance(BacktrackStop from, BacktrackStop to)
throws InterruptedException {
Key k = new Key(from.id, to.id);
Double d = null;
synchronized (distances) {
d = distances.get(k);
}
if (d != null) {
return d;
} else {
if (LOG.isDebugEnabled())
LOG.debug("DistanceMatrix.distance(" + k + ")");
return calculateDistance(from, to, k);
}
}

private Double calculateDistance(TSPStop from, TSPStop to, Key k)
throws InterruptedException {
String host_port = "localhost:5000";
String http = "http";
if (configuration != null) {
if (configuration.get("OSRM_SSL", "off").equals("on"))
http = "https";
host_port = configuration.get("OSRM_HOST", "localhost:5000");
}
DetermineRouteRequestType param = new DetermineRouteRequestType();

if (param.getRoutePlan() == null)
param.setRoutePlan(new RoutePlanType());

if (param.getRoutePlan().getWayPointList() == null)
param.getRoutePlan().setWayPointList(new WayPointListType());

WayPointListType waypointList = param.getRoutePlan().getWayPointList();

WayPointType start = getWayPoint(from.getPosition());
WayPointType end = getWayPoint(to.getPosition());

waypointList.setStartPoint(start);
waypointList.setEndPoint(end);

try {
DetermineRouteResponseType res = (DetermineRouteResponseType) osrm
.routePlan(param, host_port, http, Locale.ROOT);
double cost = res.getRouteSummary().getTotalDistance().getValue()
.doubleValue();
synchronized (distances) {
distances.put(k, cost);
}
return cost;
} catch (IOException e) {
LOG.error("Error extracting distance from " + from + " to " + to);
return Double.MAX_VALUE;
} catch (ParseException e) {
LOG.error("Error extracting distance from " + from + " to " + to);
return Double.MAX_VALUE;
} catch (JAXBException e) {
LOG.error("Error extracting distance from " + from + " to " + to);
return Double.MAX_VALUE;
}
}

@SuppressWarnings("restriction")
private WayPointType getWayPoint(Point position) {
WayPointType point = new WayPointType();
point.setStop(Boolean.TRUE);

PositionType postype = new PositionType();
PointType pointtype = new PointType();
DirectPositionType directPosition = new DirectPositionType();

directPosition.setSrsName("EPSG:" + position.getSRID());
directPosition.getValue().add(position.getX());
directPosition.getValue().add(position.getY());

pointtype.setPos(directPosition);
postype.setPoint(pointtype);
JAXBElement<? extends AbstractLocationType> value = new JAXBElement<PositionType>(
new QName("http://www.opengis.net/gml", "pos", "gml"),
PositionType.class, postype);
point.setLocation(value);

return point;
}

}

class Key {

protected Key(Integer from, Integer to) {
super();
this.from = from;
this.to = to;
}

private Integer from;
private Integer to;

public Integer getFrom() {
return from;
}

public void setFrom(Integer from) {
this.from = from;
}

public Integer getTo() {
return to;
}

public void setTo(Integer to) {
this.to = to;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((from == null) ? 0 : from.hashCode());
result = prime * result + ((to == null) ? 0 : to.hashCode());
return result;
}

@Override
public boolean equals(Object obj) {
if (!(obj instanceof Key))
return false;
Key other = (Key) obj;
return other.getFrom().equals(this.from)
&& other.getTo().equals(this.to);
}

@Override
public String toString() {
return "{ K<" + this.getFrom() + "->" + this.getTo() + ">}";
}

}
183 backtrackTSP/src/main/java/org/emergya/backtrackTSP/HeuristicBacktracking.java
View file
@@ -0,0 +1,183 @@
package org.emergya.backtrackTSP;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.gofleet.openLS.tsp.TSPStop;
import org.gofleet.openLS.tsp.TSPStopBag;

import com.vividsolutions.jts.geom.Point;

/**
* Like Backtracking but a simple heuristic which order the candidates to try
*
* @author marias
*
*/
class HeuristicBacktracking extends Thread {
private static Log LOG = LogFactory.getLog(HeuristicBacktracking.class);

private BackTrackSolution current;
private BacktrackStopBag bag;
private DistanceMatrix distances;
private SolutionContainer best;

public HeuristicBacktracking(TSPStopBag _bag, DistanceMatrix distances,
SolutionContainer best) {
this.current = initializeResBag(_bag);
this.bag = getBacktrackingBag(_bag);
this.distances = distances;
this.best = best;
}

@Override
public void run() {
BackTrackSolution solution = heuristicBacktracking(this.current,
this.bag, this.distances, new BackTrackSolution(
new Stack<TSPStop>()));
best.add(solution);
}

private BackTrackSolution heuristicBacktracking(BackTrackSolution current,
BacktrackStopBag bag, DistanceMatrix distances,
BackTrackSolution partialSolution) {

if (Thread.interrupted())
return partialSolution;

Collection<? super TSPStop> all = bag.getAll();
if (all.size() > 0) {

List<BacktrackStop> candidates = null;
candidates = new ArrayList<BacktrackStop>();
for (Object s : all)
candidates.add((BacktrackStop) s);

BacktrackStop from = null;
if (current.getStack().size() > 0)
from = (BacktrackStop) current.getStack().peek();
BacktrackStop end = (BacktrackStop) bag.getLast();
HeuristicComparator heuristicComparator = new HeuristicComparator(
distances, from, end);
Collections.sort(candidates, heuristicComparator);

for (TSPStop next : candidates) {
bag.removeStop(next);
current.push(next);

// If we already have a solution candidate, is the current way
// worse than it? If not, just use current solution as better
if (!(partialSolution != null && current.getDistance(distances) > partialSolution
.getDistance(distances))) {
heuristicBacktracking(current, bag, distances,
partialSolution);
}
if (LOG.isTraceEnabled())
LOG.trace("Current: " + current);

current.pop();
bag.addStop(next);
}

} else {
current.push(bag.getLast());

// Maybe another thread found a better solution
partialSolution = checkIfBetterAnotherThread(distances,
partialSolution);

if (current.getDistance(distances) < partialSolution
.getDistance(distances)) {
partialSolution.setStack(current.getStack());
this.best.add(partialSolution);
}

current.pop();
}

partialSolution.getDistance(distances);
return partialSolution;
}

private BackTrackSolution checkIfBetterAnotherThread(
DistanceMatrix distances, BackTrackSolution partialSolution) {

// Maybe another thread found a better solution
if (partialSolution != null && this.best.getSolution() != null) {
if (partialSolution.getDistance(distances) < this.best
.getSolution().getDistance(distances))
partialSolution = (BackTrackSolution) this.best.getSolution()
.clone();

}
return partialSolution;
}

private BackTrackSolution initializeResBag(TSPStopBag bag) {
BackTrackSolution res = new BackTrackSolution(new Stack<TSPStop>());

if (bag.hasFirst()) {
res.push(bag.getFirst());
}
return res;
}

private BacktrackStopBag getBacktrackingBag(TSPStopBag _bag) {
List<TSPStop> all = new LinkedList<TSPStop>();
all.addAll((Collection<? extends TSPStop>) _bag.getAll());
return new BacktrackStopBag(all, _bag.getFirst(), _bag.getLast());
}

}

class HeuristicComparator implements Comparator<BacktrackStop> {
private static Log LOG = LogFactory.getLog(HeuristicComparator.class);
private BacktrackStop end = null;
private DistanceMatrix distances = null;
private BacktrackStop from = null;

protected HeuristicComparator(DistanceMatrix distances, BacktrackStop from,
BacktrackStop end) {
this.end = end;
this.distances = distances;
this.from = from;
}

public int compare(BacktrackStop o1, BacktrackStop o2) {
if (from != null) {
Double dist1 = Double.MAX_VALUE;
Double dist2 = Double.MAX_VALUE;
try {
dist1 = (distances.distance(from, o1) + heuristic(o1, end));

} catch (InterruptedException e) {
LOG.info("distance interrupted");
}
try {
dist2 = (distances.distance(from, o2) + heuristic(o2, end));
} catch (InterruptedException e) {
LOG.info("distance interrupted");
}
return dist1.compareTo(dist2);
} else {
Double dist1 = heuristic(o1, end);
Double dist2 = heuristic(o2, end);
return dist1.compareTo(dist2);
}
}

private Double heuristic(BacktrackStop from, BacktrackStop to) {
Point a = from.getPosition();
Point b = to.getPosition();

return a.distance(b);
}

}
38 backtrackTSP/src/main/java/org/emergya/backtrackTSP/InitializeDistances.java
View file
@@ -0,0 +1,38 @@
package org.emergya.backtrackTSP;

import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public class InitializeDistances extends Thread {
private static Log LOG = LogFactory.getLog(InitializeDistances.class);

private BacktrackStop from;
private List<BacktrackStop> to;
private DistanceMatrix distance;

public InitializeDistances(BacktrackStop from, List<BacktrackStop> to,
DistanceMatrix distance) {
super();
this.from = from;
this.to = to;
this.distance = distance;
}

public void run() {
for (BacktrackStop i : to) {
if (Thread.interrupted())
return;

if (i != from)
try {
distance.distance(from, i);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
LOG.trace("Done with " + from.getId());
}

}
211 backtrackTSP/src/test/java/org/emergya/backtrackTSP/BackTrackingTSPTest.java
View file
@@ -0,0 +1,211 @@
/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/
package org.emergya.backtrackTSP;

import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import org.gofleet.openLS.tsp.TSPStop;
import org.junit.Test;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;

public class BackTrackingTSPTest {

private GeometryFactory gf = new GeometryFactory();

@Test
public void simpleTest() {
BackTrackingTSP backtracking = new BackTrackingTSP();
List<TSPStop> stops = new LinkedList<TSPStop>();

stops.add(new BacktrackStop(1, gf.createPoint(new Coordinate(
-3.7091297753d, 40.40085892d))));
stops.add(new BacktrackStop(2, gf.createPoint(new Coordinate(
-3.7234753d, 40.401237892d))));
stops.add(new BacktrackStop(3, gf.createPoint(new Coordinate(
-3.724762553d, 40.40543562d))));
stops.add(new BacktrackStop(4, gf.createPoint(new Coordinate(
-3.7578463d, 40.40462346252d))));
stops.add(new BacktrackStop(5, gf.createPoint(new Coordinate(
-3.726525635453d, 40.422222456252d))));
stops.add(new BacktrackStop(6, gf.createPoint(new Coordinate(
-3.722566553d, 40.425624492d))));
stops.add(new BacktrackStop(7, gf.createPoint(new Coordinate(
-3.7223562453d, 40.40434567456692d))));
stops.add(new BacktrackStop(9, gf.createPoint(new Coordinate(
-3.722362543d, 40.40262352d))));
stops.add(new BacktrackStop(10, gf.createPoint(new Coordinate(
-3.724567456753d, 40.402345234592d))));

BacktrackStopBag bag = new BacktrackStopBag(stops);

long time = System.currentTimeMillis();
final List<TSPStop> order = backtracking.order(bag);
System.out.println(System.currentTimeMillis() - time + "ms");
assertNotNull(order);
System.out.println(order);
}

@Test
public void firstLastTest() {
BackTrackingTSP backtracking = new BackTrackingTSP();
List<TSPStop> stops = new LinkedList<TSPStop>();

stops.add(new BacktrackStop(1, gf.createPoint(new Coordinate(
-3.7091297753d, 40.40085892d))));
stops.add(new BacktrackStop(2, gf.createPoint(new Coordinate(
-3.7234753d, 40.401237892d))));
stops.add(new BacktrackStop(3, gf.createPoint(new Coordinate(
-3.724762553d, 40.40543562d))));
stops.add(new BacktrackStop(5, gf.createPoint(new Coordinate(
-3.726525635453d, 40.422222456252d))));
stops.add(new BacktrackStop(6, gf.createPoint(new Coordinate(
-3.722566553d, 40.425624492d))));
stops.add(new BacktrackStop(7, gf.createPoint(new Coordinate(
-3.7223562453d, 40.40434567456692d))));
stops.add(new BacktrackStop(8, gf.createPoint(new Coordinate(
-3.722362543d, 40.40262352d))));

BacktrackStopBag bag = new BacktrackStopBag(stops, new BacktrackStop(9,
gf.createPoint(new Coordinate(-3.724567456753d,
40.402345234592d))), new BacktrackStop(4,
gf.createPoint(new Coordinate(-3.7578463d, 40.40462346252d))));

long time = System.currentTimeMillis();
final List<TSPStop> order = backtracking.order(bag);
System.out.println(System.currentTimeMillis() - time + "ms");
assertNotNull(order);
System.out.println(order);
}

@Test
public void performance() {

Random r = new Random();
Double x = -4.6d;
Double y = 37.5d;

int max = 4;
int numparadas = 20;

long totaltime = 0;

for (int k = 3; k < numparadas; k++) {

for (int i = 0; i < max; i++) {

BackTrackingTSP backtracking = new BackTrackingTSP();
List<TSPStop> stops = new LinkedList<TSPStop>();

for (int j = 0; j < k; j++)
stops.add(new BacktrackStop(j, gf
.createPoint(new Coordinate(x
+ (r.nextFloat() * ((r.nextBoolean()) ? -1
: 1)), y
+ (r.nextFloat() * ((r.nextBoolean()) ? -1
: 1))))));

BacktrackStopBag bag = new BacktrackStopBag(stops);

long time = System.currentTimeMillis();
final List<TSPStop> order = backtracking.order(bag);
totaltime += System.currentTimeMillis() - time;
assertNotNull(order);
assertTrue(order.size() == k);
// System.out.println(order);
}
System.out.println("Time for " + k + " stops: " + (totaltime / max)
+ "ms");
}
}

@Test
public void performanceWithLast() {

Random r = new Random();
Double x = -4.6d;
Double y = 37.5d;

int max = 4;
int numparadas = 20;

for (int k = 3; k < numparadas; k++) {

long totaltime = 0;

for (int i = 0; i < max; i++) {

BackTrackingTSP backtracking = new BackTrackingTSP();
List<TSPStop> stops = new LinkedList<TSPStop>();

for (int j = 0; j < k - 2; j++)
stops.add(new BacktrackStop(j, gf
.createPoint(new Coordinate(x
+ (r.nextFloat() * ((r.nextBoolean()) ? -1
: 1)), y
+ (r.nextFloat() * ((r.nextBoolean()) ? -1
: 1))))));

BacktrackStopBag bag = new BacktrackStopBag(stops,
new BacktrackStop(k - 1,
gf.createPoint(new Coordinate(
x
+ (r.nextFloat() * ((r
.nextBoolean()) ? -1
: 1)), y
+ (r.nextFloat() * ((r
.nextBoolean()) ? -1
: 1))))),
new BacktrackStop(k,
gf.createPoint(new Coordinate(
x
+ (r.nextFloat() * ((r
.nextBoolean()) ? -1
: 1)), y
+ (r.nextFloat() * ((r
.nextBoolean()) ? -1
: 1))))));

long time = System.currentTimeMillis();
final List<TSPStop> order = backtracking.order(bag);
totaltime += System.currentTimeMillis() - time;
assertNotNull(order);
assertTrue(order.size() == k);
}
System.out.println("Time for " + k + " stops: " + (totaltime / max)
+ "ms");
}
}
}
6 configuration/pom.xml
View file
@@ -38,6 +38,12 @@
<version>1.7</version>
</dependency>


<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.10</version>
</dependency>
<!-- Context (Spring) -->
<dependency>
<groupId>org.springframework</groupId>
34 configuration/src/main/java/org/gofleet/configuration/Configuration.java
View file
@@ -7,7 +7,10 @@
import javax.naming.NamingException;

import org.apache.commons.configuration.AbstractConfiguration;
import org.apache.commons.configuration.CompositeConfiguration;
import org.apache.commons.configuration.DatabaseConfiguration;
import org.apache.commons.configuration.JNDIConfiguration;
import org.apache.commons.configuration.PropertiesConfiguration;
import org.apache.commons.logging.LogFactory;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Repository;
@@ -28,36 +31,51 @@
*/
public class Configuration {

private static AbstractConfiguration configuration = null;
private static CompositeConfiguration configuration = null;
private static org.apache.commons.logging.Log log = LogFactory
.getLog(Configuration.class);

@Autowired
private org.apache.commons.dbcp.BasicDataSource dataSource;

private AbstractConfiguration getConfiguration() {
protected AbstractConfiguration getConfiguration() {
if (configuration == null) {

configuration = new CompositeConfiguration();

try {
configuration = new DatabaseConfiguration(dataSource,
"configuration", "key", "value");
if (dataSource != null
&& dataSource.isAccessToUnderlyingConnectionAllowed()
&& !dataSource.isClosed())
configuration.addConfiguration(new DatabaseConfiguration(
dataSource, "configuration", "key", "value"));
} catch (Throwable t) {
log.error("Error loading database configuration", t);
}
try {
configuration.addConfiguration(new JNDIConfiguration(
new InitialContext()));
} catch (Throwable t) {
log.error("Error loading jndi configuration", t);
}

try {
final PropertiesConfiguration configurator = new PropertiesConfiguration();
InitialContext icontext = new InitialContext();
Context context = (Context) icontext.lookup("java:comp/env");
NamingEnumeration<NameClassPair> propiedadesJDNI = context
.list("");
while (propiedadesJDNI.hasMoreElements()) {
NameClassPair propiety = propiedadesJDNI.nextElement();
configuration.addProperty(propiety.getName(),
configurator.addProperty(propiety.getName(),
context.lookup(propiety.getName()));
log.trace("Configuring '" + propiety.getName() + "' as '"
+ context.lookup(propiety.getName().toString())
+ "'");
log.trace("Configuring '"
+ propiety.getName()
+ "' as '"
+ configurator.getString(propiety.getName()
.toString()) + "'");
}
configuration.addConfiguration(configurator);

} catch (NamingException e) {
log.error("Error loading configuration from context: " + e, e);
96 osrm-connector/pom.xml
View file
@@ -0,0 +1,96 @@
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.emergya</groupId>
<artifactId>osrm-connector</artifactId>
<version>0.1.0</version>
<name>osrm-connector</name>
<description>Connector to OSRM routing</description>


<distributionManagement>
<repository>
<id>gofleet</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet</url>
</repository>
<snapshotRepository>
<id>gofleet-snap</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet-snapshots</url>
</snapshotRepository>
</distributionManagement>


<build>
<plugins>
<plugin>

<!-- Maven compiler plugin -->
<artifactId>maven-compiler-plugin</artifactId>
<configuration>
<source>1.6</source>
<target>1.6</target>
<optimize>true</optimize>
</configuration>
</plugin>
</plugins>
</build>

<dependencies>
<dependency>
<groupId>org.geotools</groupId>
<artifactId>gt-opengis</artifactId>
<version>${geotools.version}</version>
</dependency>
<dependency>
<groupId>org.geotools</groupId>
<artifactId>gt-epsg-hsql</artifactId>
<version>${geotools.version}</version>
</dependency>
<dependency>
<groupId>org.geotools</groupId>
<artifactId>gt-api</artifactId>
<version>${geotools.version}</version>
</dependency>

<!-- Internacionalization -->
<dependency>
<groupId>org.gofleet</groupId>
<artifactId>internacionalization</artifactId>
<version>1.1.0</version>
</dependency>

<!-- Log -->
<dependency>
<groupId>commons-logging</groupId>
<artifactId>commons-logging</artifactId>
<version>1.1.1</version>
</dependency>

<!-- JSON parser -->
<dependency>
<groupId>org.codehaus.jackson</groupId>
<artifactId>jackson-core-lgpl</artifactId>
<version>1.9.4</version>
</dependency>

<!-- OpenLS classes -->
<dependency>
<groupId>org.jvnet.ogc</groupId>
<artifactId>ols-v_1_2_0-schema</artifactId>
<version>1.0.3</version>
</dependency>

<!-- Http connection to OSRM -->
<dependency>
<groupId>org.apache.httpcomponents</groupId>
<artifactId>httpclient</artifactId>
<version>4.1.3</version>
</dependency>

</dependencies>

<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<geotools.version>8.0-M4</geotools.version>
</properties>
</project>
154 osrm-connector/src/main/java/org/emergya/osrm/GeoUtil.java
View file
@@ -0,0 +1,154 @@
package org.emergya.osrm;

import java.util.LinkedList;
import java.util.List;

import net.opengis.gml.v_3_1_1.AbstractRingPropertyType;
import net.opengis.gml.v_3_1_1.CoordType;
import net.opengis.gml.v_3_1_1.DirectPositionType;
import net.opengis.gml.v_3_1_1.LinearRingType;
import net.opengis.gml.v_3_1_1.PointType;
import net.opengis.gml.v_3_1_1.PolygonType;
import net.opengis.xls.v_1_2_0.PositionType;
import net.opengis.xls.v_1_2_0.WayPointType;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.geotools.geometry.jts.JTS;
import org.geotools.referencing.CRS;
import org.opengis.referencing.crs.CoordinateReferenceSystem;
import org.opengis.referencing.operation.MathTransform;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LinearRing;

/*
* Copyright (C) 2011, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.es">María Arias</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This software is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/
public class GeoUtil {
static Log LOG = LogFactory.getLog(GeoUtil.class);
static GeometryFactory geomFact = new GeometryFactory();

@SuppressWarnings("restriction")
public static com.vividsolutions.jts.geom.Point getPoint(
WayPointType startPoint, CoordinateReferenceSystem targetCRS) {

// TODO what if we don't receive coordinates?
PositionType ptype = (PositionType) startPoint.getLocation().getValue();
PointType pointType = ptype.getPoint();
DirectPositionType ctype = pointType.getPos();

CoordinateReferenceSystem sourceCRS = getSRS(startPoint);

LOG.trace(sourceCRS.toWKT());
LOG.trace("(" + ctype.getValue().get(0) + ", "
+ ctype.getValue().get(1) + ")");

com.vividsolutions.jts.geom.Point p = geomFact
.createPoint(new Coordinate(ctype.getValue().get(0), ctype
.getValue().get(1)));

LOG.debug(p);
if (targetCRS != null && !sourceCRS.equals(targetCRS)) {
try {
MathTransform transform = CRS.findMathTransform(sourceCRS,
targetCRS);
p = JTS.transform(p, transform).getCentroid();

p = geomFact.createPoint(new Coordinate(p.getY(), p.getX()));

LOG.info(p);
} catch (Throwable t) {
LOG.error("Error converting coordinates", t);
}
}

return p;
}

public static CoordinateReferenceSystem getSRS(WayPointType point) {
// TODO what if we don't receive coordinates?
PositionType ptype = (PositionType) point.getLocation().getValue();
PointType pointType = ptype.getPoint();
try {
return CRS.decode(pointType.getSrsName());
} catch (Throwable e) {
LOG.trace(e, e);
try {
return CRS.decode("EPSG:4326");
} catch (Throwable t) {
LOG.trace(t);
return null;
}
}
}

public static com.vividsolutions.jts.geom.Geometry getGeometry(
PositionType position) {

Geometry g = null;

if (position.getPoint() != null) {
if (position.getPoint().getCoord() != null
&& position.getPoint().getCoord().getX() != null) {
g = geomFact.createPoint(new Coordinate(position.getPoint()
.getCoord().getX().doubleValue(), position.getPoint()
.getCoord().getY().doubleValue()));
} else if (position.getPoint().getPos() != null
&& position.getPoint().getPos().getValue() != null
&& position.getPoint().getPos().getValue().size() == 2) {
g = geomFact.createPoint(new Coordinate(position.getPoint()
.getPos().getValue().get(0), position.getPoint()
.getPos().getValue().get(1)));
}
} else if (position.getPolygon() != null) {
PolygonType polygon = position.getPolygon();

List<LinearRing> interiorRings = new LinkedList<LinearRing>();
polygon.getInterior();
// TODO
LinearRing[] holes = interiorRings.toArray(new LinearRing[] {});

List<Coordinate> coordinateList = new LinkedList<Coordinate>();
AbstractRingPropertyType exterior = polygon.getExterior()
.getValue();
LinearRingType ring = (LinearRingType) exterior.getRing()
.getValue();
for (CoordType coord : ring.getCoord()) {
coordinateList.add(new Coordinate(coord.getX().doubleValue(),
coord.getY().doubleValue()));
}
Coordinate[] coordinates = coordinateList
.toArray(new Coordinate[] {});
LinearRing shell = geomFact.createLinearRing(coordinates);
g = geomFact.createPolygon(shell, holes);
}
return g;
}
}
239 ...rg/gofleet/openLS/util/OSRMConnector.java → .../src/main/java/org/emergya/osrm/OSRM.java
View file
@@ -25,15 +25,17 @@
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/
package org.gofleet.openLS.util;
package org.emergya.osrm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.net.URL;
import java.net.UnknownHostException;
import java.text.ParseException;
import java.util.List;
import java.util.Locale;

import javax.ws.rs.core.MediaType;
import javax.xml.bind.JAXBElement;
import javax.xml.bind.JAXBException;
import javax.xml.datatype.DatatypeFactory;
@@ -57,7 +59,12 @@

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.apache.http.HttpResponse;
import org.apache.http.client.HttpClient;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.impl.client.DefaultHttpClient;
import org.codehaus.jackson.JsonFactory;
import org.codehaus.jackson.JsonParseException;
import org.codehaus.jackson.JsonParser;
import org.codehaus.jackson.JsonToken;
import org.geotools.geometry.jts.JTS;
@@ -75,31 +82,40 @@
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.io.ParseException;

/**
* @author marias
*
*/
@SuppressWarnings("restriction")
@Repository
public class OSRMConnector {
public class OSRM {

protected static final String EPSG_4326 = "EPSG:4326";
private static Log LOG = LogFactory.getLog(OSRMConnector.class);
private static Log LOG = LogFactory.getLog(OSRM.class);
private GeometryFactory gf = new GeometryFactory();
private DatatypeFactory dataTypeFactory = new com.sun.org.apache.xerces.internal.jaxp.datatype.DatatypeFactoryImpl();

@Autowired
private I18n i18n;

/**
* @param i18n the i18n to set
* @param i18n
* the i18n to set
*/
public void setI18n(I18n i18n) {
this.i18n = i18n;
}

public OSRMConnector() {
public OSRM() {
}

/**
* To use outside spring context
*/
public OSRM(I18n i18n) {
this();
setI18n(i18n);
}

/**
@@ -153,24 +169,22 @@ public AbstractResponseParametersType routePlan(
WayPointListType wayPointList = param.getRoutePlan()
.getWayPointList();

String url = http + "://" + host_port + "/viaroute";
String url = "/viaroute";

CoordinateReferenceSystem sourceCRS = CRS.decode(EPSG_4326);
CoordinateReferenceSystem targetCRS = GeoUtil.getSRS(wayPointList
.getStartPoint());

Point point = GeoUtil.getPoint(wayPointList.getStartPoint(),
sourceCRS);
url += "&start=" + point.getY() + "," + point.getX();
point = GeoUtil.getPoint(wayPointList.getEndPoint(), sourceCRS);
url += "&dest=" + point.getY() + "," + point.getX();
com.vividsolutions.jts.geom.Point point = GeoUtil.getPoint(
wayPointList.getStartPoint(), sourceCRS);
url += "?loc=" + point.getY() + "," + point.getX();

for (WayPointType wayPoint : wayPointList.getViaPoint()) {
point = GeoUtil.getPoint(wayPoint, sourceCRS);
url += "&via=" + point.getY() + "," + point.getX();
url += "&loc=" + point.getY() + "," + point.getX();
}

url += "&output=json&instructions=true";
point = GeoUtil.getPoint(wayPointList.getEndPoint(), sourceCRS);
url += "&loc=" + point.getY() + "," + point.getX();

LOG.debug(url);

@@ -179,70 +193,28 @@ public AbstractResponseParametersType routePlan(
lst.setSrsName(targetCRS.getName().getCode());

JsonFactory f = new JsonFactory();
JsonParser jp = f.createJsonParser(new URL(url));
JsonParser jp = f.createJsonParser(getOSRMStream(host_port, url));
jp.nextToken();
while (jp.nextToken() != JsonToken.END_OBJECT
&& jp.getCurrentToken() != null) {
String fieldname = jp.getCurrentName();
if (fieldname == null)
;
else if (fieldname.equals("route_summary")) {
if (jp.nextToken() == JsonToken.START_OBJECT
&& jp.getCurrentToken() != null) {
while (jp.nextToken() != JsonToken.END_OBJECT
&& jp.getCurrentToken() != null) {
if (jp.getCurrentName().equals("total_time")) {
jp.nextToken();
Duration duration = dataTypeFactory
.newDuration(true, 0, 0, 0, 0,
jp.getIntValue(), 0);
routeSummary.setTotalTime(duration);
} else if (jp.getCurrentName().equals(
"total_distance")) {
jp.nextToken();
DistanceType duration = new DistanceType();
duration.setUom(DistanceUnitType.M);
duration.setValue(new BigDecimal(jp.getText()));
routeSummary.setTotalDistance(duration);
}
}
}
else if (jp.getCurrentName().equals("total_distance")) {
DistanceType duration = new DistanceType();
duration.setUom(DistanceUnitType.M);
duration.setValue(new BigDecimal(jp.getText()));
routeSummary.setTotalDistance(duration);
} else if (jp.getCurrentName().equals("total_time")) {
Duration duration = dataTypeFactory.newDuration(true, 0, 0,
0, 0, 0, jp.getIntValue());
routeSummary.setTotalTime(duration);
} else if (jp.getCurrentName().equals("route_geometry")) {
String geometry = jp.getText();
decodeRouteGeometry(geometry,
lst.getPosOrPointPropertyOrPointRep(), targetCRS,
sourceCRS);
decodeRouteGeometry(lst.getPosOrPointPropertyOrPointRep(),
targetCRS, sourceCRS, jp);
} else if (jp.getCurrentName().equals("route_instructions")) {
while (jp.nextToken() == JsonToken.START_ARRAY
&& jp.getCurrentToken() != null) {
RouteInstructionType e = new RouteInstructionType();
jp.nextToken();
String instruction = i18n.getString(locale,
jp.getText());
jp.nextToken();
if (jp.getText().length() > 0)
instruction += " " + i18n.getString(locale, "on")
+ " " + jp.getText();
e.setInstruction(instruction);
jp.nextToken();

DistanceType distance = new DistanceType();
distance.setUom(DistanceUnitType.M);
distance.setValue(new BigDecimal(jp.getText()));
e.setDistance(distance);

jp.nextToken();

Duration duration = dataTypeFactory.newDuration(true,
0, 0, 0, 0, jp.getIntValue(), 0);
routeSummary.setTotalTime(duration);
e.setDuration(duration);

while (jp.nextToken() != JsonToken.END_ARRAY
&& jp.getCurrentToken() != null)
;
routeInstructionsList.getRouteInstruction().add(e);
}
processInstructions(locale, routeSummary,
routeInstructionsList, jp);
}
jp.nextToken();
}
@@ -252,64 +224,121 @@ else if (fieldname.equals("route_summary")) {
res.setRouteGeometry(routeGeometry);
res.setRouteHandle(routeHandle);

if (param.getRouteInstructionsRequest() != null)
if (param.getRouteInstructionsRequest() != null) {
res.setRouteInstructionsList(routeInstructionsList);
res.getRouteInstructionsList().setFormat(MediaType.TEXT_PLAIN);
res.getRouteInstructionsList().setLang(locale.getLanguage());
res.getRouteInstructionsList().setFormat("text/plain");
res.getRouteInstructionsList().setLang(locale.getLanguage());
}
res.setRouteSummary(routeSummary);
} catch (Throwable t) {
LOG.error("Error generating route response: " + t, t);
t.printStackTrace();
}

return res;
}

private List<JAXBElement<?>> decodeRouteGeometry(String encoded,
List<JAXBElement<?>> list, CoordinateReferenceSystem targetCRS,
CoordinateReferenceSystem sourceCRS)
private BufferedReader getOSRMStream(String host_port, String url)
throws UnknownHostException, IOException {

DefaultHttpClient httpclient = new DefaultHttpClient();
HttpGet httpget = new HttpGet("http://" + host_port + url);

HttpResponse response = httpclient.execute(httpget);

BufferedReader in = new BufferedReader(new InputStreamReader(response
.getEntity().getContent()));
return in;
}

/**
* @param locale
* @param routeSummary
* @param routeInstructionsList
* @param jp
* @throws IOException
* @throws JsonParseException
*/
public void processInstructions(Locale locale,
RouteSummaryType routeSummary,
RouteInstructionsListType routeInstructionsList, JsonParser jp)
throws IOException, JsonParseException {
while (jp.nextToken() == JsonToken.START_ARRAY
&& jp.getCurrentToken() != null) {
RouteInstructionType e = new RouteInstructionType();
jp.nextToken();
String instruction = jp.getText();
if (i18n != null)
instruction = i18n.getString(locale, jp.getText());
jp.nextToken();
if (jp.getText().length() > 0) {
if (i18n == null)
instruction += " on " + jp.getText();
else
instruction += " " + i18n.getString(locale, "on") + " "
+ jp.getText();
}
e.setInstruction(instruction);
jp.nextToken();

DistanceType distance = new DistanceType();
distance.setUom(DistanceUnitType.M);
distance.setValue(new BigDecimal(jp.getText()));
e.setDistance(distance);

jp.nextToken();

Duration duration = dataTypeFactory.newDuration(true, 0, 0, 0, 0,
0, jp.getIntValue());
e.setDuration(duration);

while (jp.nextToken() != JsonToken.END_ARRAY
&& jp.getCurrentToken() != null);
routeInstructionsList.getRouteInstruction().add(e);
}
}

private List<JAXBElement<?>> decodeRouteGeometry(List<JAXBElement<?>> list,
CoordinateReferenceSystem targetCRS,
CoordinateReferenceSystem sourceCRS, JsonParser jp)
throws NoSuchAuthorityCodeException, FactoryException,
MismatchedDimensionException, TransformException {
MismatchedDimensionException, TransformException,
JsonParseException, IOException {

MathTransform transform = null;

double precision = 5;
precision = Math.pow(10, -precision);
int len = encoded.length(), index = 0, lat = 0, lng = 0;
while (index < len) {
int b, shift = 0, result = 0;
do {
b = encoded.charAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
int dlat = (((result & 1) != 0) ? ~(result >> 1) : (result >> 1));
lat += dlat;
shift = 0;
result = 0;
do {
b = encoded.charAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
int dlng = (((result & 1) != 0) ? ~(result >> 1) : (result >> 1));
lng += dlng;

Coordinate coord = new Coordinate(lng * precision, lat * precision);
LOG.trace(targetCRS.toWKT());
LOG.trace(sourceCRS.toWKT());
jp.nextToken();

while (jp.nextToken() == JsonToken.START_ARRAY
&& jp.getCurrentToken() != null) {
jp.nextToken();
Double lat = jp.getDoubleValue();
jp.nextToken();
Double lon = jp.getDoubleValue();
jp.nextToken();

Coordinate coord = new Coordinate(lat, lon);
Point sourceGeometry = gf.createPoint(coord);
LOG.trace(sourceGeometry);
if (sourceCRS != targetCRS) {
if (transform == null)
transform = CRS.findMathTransform(sourceCRS, targetCRS);
sourceGeometry = JTS.transform(sourceGeometry, transform)
.getCentroid();
LOG.trace(sourceGeometry);
}
DirectPositionListType e = new DirectPositionListType();
e.getValue().add(coord.x);
e.getValue().add(coord.y);
e.getValue().add(sourceGeometry.getY());
e.getValue().add(sourceGeometry.getX());

JAXBElement<DirectPositionListType> elem = new JAXBElement<DirectPositionListType>(
new QName("http://www.opengis.net/gml", "pos", "gml"),
DirectPositionListType.class, e);

list.add(elem);

}

return list;
46 pom.xml
View file
@@ -4,22 +4,23 @@
<groupId>org.gofleet</groupId>
<artifactId>openLS</artifactId>
<packaging>war</packaging>
<version>1.2.0-SNAPSHOT</version>
<version>1.2.0</version>
<name>OpenLS</name>
<url>http://www.gofleet.org</url>


<distributionManagement>
<snapshotRepository>
<repository>
<id>gofleet</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet</url>
</snapshotRepository>
<repository>
<id>gofleet-snap</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet_releases</url>
</repository>
<snapshotRepository>
<id>gofleet-snap</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet-snapshots</url>
</snapshotRepository>
</distributionManagement>




<build>
<finalName>openLS</finalName>
@@ -124,11 +125,6 @@
</exclusion>
</exclusions>
</dependency>
<dependency>
<groupId>javax.xml</groupId>
<artifactId>jaxb-api</artifactId>
<version>2.1</version>
</dependency>

<!-- test dependencies -->
<dependency>
@@ -259,7 +255,7 @@
<dependency>
<groupId>com.sun.jersey.contribs</groupId>
<artifactId>jersey-spring</artifactId>
<version>1.11</version>
<version>1.12-b01</version>
<exclusions>
<exclusion>
<artifactId>spring-core</artifactId>
@@ -305,6 +301,26 @@
<version>1.1.0</version>
</dependency>


<!-- OSRM-Connector -->
<dependency>
<groupId>org.emergya</groupId>
<artifactId>osrm-connector</artifactId>
<version>0.1.0</version>
</dependency>

<!-- JaxB -->
<dependency>
<groupId>com.sun.xml.bind</groupId>
<artifactId>jaxb-impl</artifactId>
<version>2.2.1</version>
</dependency>
<dependency>
<groupId>javax.xml.bind</groupId>
<artifactId>jaxb-api</artifactId>
<version>2.1</version>
</dependency>

</dependencies>

<repositories>
161 src/main/importers/NavTeq2OSM.py
View file
@@ -76,8 +76,8 @@ def getNode(point, id_nodes):
def writeWay(file, attrs, nodes, tags):

if nodes is None:
if attrs.has_key('id'):
print "Way without nodes: " + str(attrs['id'])
# if attrs.has_key('id'):
# print "Way without nodes: " + str(attrs['id'])
return

#Write way to file
@@ -143,7 +143,7 @@ def printRelation(file, rid, source, target, via={}, tags={}, attrs={}):

writeToFile(file," </relation>\n")

def processStreets(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress, relations_file, relations_file_):
def process(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress, relations_file):

ways = {}
nodes = {}
@@ -161,6 +161,7 @@ def processStreets(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress
record = zlevels.shapeRecord(i)

link_id = record.record[0]

level = record.record[3]

#Nodes array saves nodes_id by coordinates and level
@@ -189,27 +190,50 @@ def processStreets(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress

#write node definition to file

nodes = None
link_id = None
node_key = None
record = None
node_cont = None
node_id = None
cont = zlevels.numRecords
zlevels = None
last_node_id = None
last_level = None
last_link_id = None

t2 = processRDMS(rdms, cleanCDMS(cdms, [3, 7, 8, 21]), relations_file, ways)
t2 = processRDMS(rdms, cleanCDMS(cdms, [3, 7, 8, 21]), relations_file[0], ways)
rdms = rdms.close()
rdms = None
t7 = processVials(shpfile, progress, ways, ways_file, nodes, cleanCDMS(cdms, [2]), cont)
cdms.close()
cdms = None

max = float(len(shpfile))

t3 = processRDMS_divider(relations_file[1], ways, shpfile.name, nodes_file.name, progress, 0, round(max/4), 1)
t4 = processRDMS_divider(relations_file[2], ways, shpfile.name, nodes_file.name, progress, round(max/4) + 1, 2 * round(max/4), 2)
t5 = processRDMS_divider(relations_file[3], ways, shpfile.name, nodes_file.name, progress, 2 * round(max/4) + 1, 3 * round(max/4), 3)
t6 = processRDMS_divider(relations_file[4], ways, shpfile.name, nodes_file.name, progress, 3 * round(max/4) + 1, max, 4)

t3 = processRDMS_divider(relations_file_, ways, shpfile.name, nodes_file.name)
shpfile = None

t2.join()
t3.join()
t4.join()
t5.join()
t6.join()
t7.join()

cdms = cleanCDMS(cdms, [2])
cont = zlevels.numRecords
zlevels = None
@run_async
def processVials(shpfile, progress, ways, ways_file, nodes, cdms, cont):

#Walking through all ways (vials)
for i in range(0, len(shpfile)):
try:
progress.update(cont + i)
except:
print "Couldn't update progressbar"
traceback.print_exc()
pass
try:
shpRecord = shpfile[i]
except:
@@ -291,8 +315,8 @@ def processStreets(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress
if ways.has_key(way_id):
nodes = ways[way_id]
ways[way_id] = None
else:
print("Error: way (" + str(way_id) + ") without nodes!! i=" + str(i))
# else:
# print("Error: way (" + str(way_id) + ") without nodes!! i=" + str(i))

#Commented because it takes too long
tags = getWayTags(cdms, way_id, tags)
@@ -305,8 +329,6 @@ def processStreets(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress
shpfile = None
ways = None
cdms = None
t2.join()
t3.join()

#Instead of having to search through all the data, we just save in memory
#the data we will be using.
@@ -356,22 +378,30 @@ def processRDMS(rdms, cdms, file, ways = {}):


@run_async
def processRDMS_divider(relations_file_, ways, streetsname, nodes_file_name):
def processRDMS_divider(relations_file_, ways, streetsname, nodes_file_name, progress, min=0, max=1000, res_id=1):

res_id = 1
res_id = res_id * 1000000

nodes_file = open(nodes_file_name, "r")
streets = dbf.Dbf(streetsname, "r")
while nodes_file: #Walking through all ways (vials)
for i in range(0, len(streets)):
for i in range(int(min), int(max)):
try:
progress.update(cont + i)
except:
pass
try:
street_ = streets[i]
except:
print "Malformed Street [" + str(i) +"]"
pass
try:
#print "id " + str(street_[0])
divider = street_[31]
if divider == 'A' or divider == '1' or divider == '2':
#print "has divider"
way_id = street_[0]
if not ways.has_key(way_id):
continue
street = ways[way_id]
node_a = street[0]
node_b = street[len(ways[way_id]) - 1]
@@ -380,30 +410,31 @@ def processRDMS_divider(relations_file_, ways, streetsname, nodes_file_name):
continue
try:
way = ways[k]

#We search for the angle of the intersections
#If it is a left turn, it is forbidden
if way[0] == node_a \
and angle(searchLatLon(nodes_file, street[1]), \
searchLatLon(nodes_file, node_a), \
searchLatLon(nodes_file, way[1])) > 0:
searchLatLon(nodes_file, way[1])) < 0:
printRelation(relations_file_, res_id, k, way_id, {node_a: 'node'}, {'type': 'restriction', 'type': 'no_right_turn'})
res_id = res_id + 1
elif way[len(way) - 1] == node_a \
and angle(searchLatLon(nodes_file, street[1]), \
searchLatLon(nodes_file, node_b), \
searchLatLon(nodes_file, way[len(way) - 2])) > 0:
searchLatLon(nodes_file, way[len(way) - 2])) < 0:
printRelation(relations_file_, res_id, k, way_id, {node_b: 'node'}, {'type': 'restriction', 'type': 'no_right_turn'})
res_id = res_id + 1
elif way[0] == node_b \
and angle(searchLatLon(nodes_file, street[len(street) - 2]), \
searchLatLon(nodes_file, node_a), \
searchLatLon(nodes_file, way[1])) > 0:
searchLatLon(nodes_file, way[1])) < 0:
printRelation(relations_file_, res_id, k, way_id, {node_a: 'node'}, {'type': 'restriction', 'type': 'no_right_turn'})
res_id = res_id + 1
elif way[len(way) - 1] == node_b \
and angle(searchLatLon(nodes_file, street[len(street) - 2]), \
searchLatLon(nodes_file, node_b), \
searchLatLon(nodes_file, way[len(way) - 2])) > 0:
searchLatLon(nodes_file, way[len(way) - 2])) < 0:
printRelation(relations_file_, res_id, k, way_id, {node_b: 'node'}, {'type': 'restriction', 'type': 'no_right_turn'})
res_id = res_id + 1
except AttributeError as ae:
@@ -416,14 +447,14 @@ def processRDMS_divider(relations_file_, ways, streetsname, nodes_file_name):
traceback.print_exc()
except:
print "Error processing divider:"
traceback.print_exc
traceback.print_exc()
streets.close()


def searchLatLon(nodes_file, node_id):
nodes_file.seek(0)
while 1:
lines = nodes_file.readlines(400)
lines = nodes_file.readlines(100)
if not lines:
break
for node in lines:
@@ -592,18 +623,21 @@ def main(argv):
nodes_file = codecs.open(nodes_file_.name, "r+w", "utf-8")
ways_file_ = tempfile.NamedTemporaryFile()
ways_file = codecs.open(ways_file_.name, "r+w", "utf-8")
relations_file_ = tempfile.NamedTemporaryFile()
relations_file = codecs.open(relations_file_.name, "r+w", "utf-8")
relations_file2_ = tempfile.NamedTemporaryFile()
relations_file2 = codecs.open(relations_file2_.name, "r+w", "utf-8")

relations_file = []
relations_file.append(tempfile.NamedTemporaryFile())
relations_file.append(tempfile.NamedTemporaryFile())
relations_file.append(tempfile.NamedTemporaryFile())
relations_file.append(tempfile.NamedTemporaryFile())
relations_file.append(tempfile.NamedTemporaryFile())

widgets = ['Importing data from NavTeq Shapes: ', progressbar.Bar(marker=progressbar.AnimatedMarker()),
' ', progressbar.ETA()]
maxval = len(shpfile) + zlevels.numRecords
maxval = 2 * len(shpfile) + zlevels.numRecords
progress = progressbar.ProgressBar(widgets=widgets, maxval=maxval).start()
progress.update(0)

processStreets(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress, relations_file, relations_file2)
process(zlevels, rdms, cdms, shpfile, nodes_file, ways_file, progress, relations_file)

if not progress is None:
progress.finish()
@@ -635,13 +669,16 @@ def main(argv):
nodes_file.flush()
nodes_file.seek(0)
while 1:
lines = nodes_file.readlines(1000)
lines = nodes_file.readlines(200)
if not lines:
break
else:
for line in lines:
output_file.write(line)
progress.update(progress.currval + 1)
try:
progress.update(progress.currval + 1)
except:
pass
if random.random() > 0.8 :
output_file.flush()
nodes_file.close()
@@ -650,49 +687,39 @@ def main(argv):
ways_file.flush()
ways_file.seek(0)
while 1:
lines = ways_file.readlines(500)
lines = ways_file.readlines(200)
if not lines:
break
else:
for line in lines:
output_file.write(line)
progress.update(progress.currval + 1)
try:
progress.update(progress.currval + 1)
except:
pass
if random.random() > 0.8 :
output_file.flush()
ways_file.close()
ways_file_.close()

relations_file.flush()
relations_file.seek(0)
while 1:
lines = relations_file.readlines(500)
if not lines:
break
else:
for line in lines:
output_file.write(line)
progress.update(progress.currval + 1)
if random.random() > 0.8 :
output_file.flush()
relations_file.close()
relations_file_.close()

relations_file2.flush()
relations_file2.seek(0)
while 1:
lines = relations_file2.readlines(500)
if not lines:
break
else:
for line in lines:
output_file.write(line)
progress.update(progress.currval + 1)
if random.random() > 0.8 :
output_file.flush()
output_file.flush()
relations_file2.close()
relations_file2_.close()


for rfile in relations_file:
rfile.flush()
rfile.seek(0)
while 1:
lines = rfile.readlines(200)
if not lines:
break
else:
for line in lines:
output_file.write(line)
try:
progress.update(progress.currval + 1)
except:
pass
if random.random() > 0.8 :
output_file.flush()
rfile.close()

output_file.write(' </osm>')
output_file.write('\n')
output_file.flush()
420 src/main/java/net/opengis/xls/v_1_2_0/XLSType.java
View file

Large diffs are not rendered by default.

8 src/main/java/net/opengis/xls/v_1_2_0/package-info.java
View file
@@ -0,0 +1,8 @@
@XmlSchema(namespace = "http://www.opengis.net/xls", elementFormDefault = XmlNsForm.QUALIFIED, xmlns = {
@javax.xml.bind.annotation.XmlNs(prefix = "xls", namespaceURI = "http://www.opengis.net/xls"),
@javax.xml.bind.annotation.XmlNs(prefix = "xs", namespaceURI = "http://www.w3.org/2001/XMLSchema") })
package net.opengis.xls.v_1_2_0;

import javax.xml.bind.annotation.XmlNsForm;
import javax.xml.bind.annotation.XmlSchema;

139 src/main/java/org/gofleet/openLS/OpenLS.java
View file
@@ -33,10 +33,10 @@

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.emergya.osrm.OSRM;
import org.gofleet.openLS.ddbb.GeoCoding;
import org.gofleet.openLS.ddbb.Routing;
import org.gofleet.openLS.util.MoNaVConnector;
import org.gofleet.openLS.util.OSRMConnector;
import org.gofleet.openLS.util.Utils;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.Scope;
@@ -81,7 +81,7 @@ public class OpenLS {
private Routing routingController;

@Resource
private OSRMConnector osrmConnector;
private OSRM osrmConnector;

@Resource
private GeoCoding geoCodingController;
@@ -105,7 +105,7 @@ public void setConfiguration(
this.configuration = configuration;
}

private MoNaVConnector monavConnector = new MoNaVConnector();
private MoNaVConnector monavConnector = new MoNaVConnector();

/**
* Stupid test to see if the Server is alive.
@@ -126,76 +126,82 @@ public String test() {
* @return
*/
@POST
@Produces(MediaType.TEXT_XML)
@Produces(MediaType.APPLICATION_XML)
@Consumes({ MediaType.APPLICATION_XML, MediaType.TEXT_XML,
MediaType.APPLICATION_ATOM_XML })
public JAXBElement<XLSType> openLS(JAXBElement<XLSType> jaxbelement) {
final XLSType parameter = jaxbelement.getValue();
LOG.trace("openLS(" + parameter + ")");
Locale localetmp = Locale.ROOT;

if (parameter.getLang() != null && !parameter.getLang().isEmpty()) {
LOG.trace("Language detected: " + parameter.getLang());
localetmp = new Locale(parameter.getLang());
}
final Locale locale = localetmp;
localetmp = null;
final List<List<AbstractResponseParametersType>> resultado = new LinkedList<List<AbstractResponseParametersType>>();

ExecutorService executor = Executors.newFixedThreadPool(3);

for (JAXBElement<? extends AbstractBodyType> jaxbbody : parameter
.getBody()) {

AbstractBodyType body = jaxbbody.getValue();

if (body instanceof RequestType) {

final AbstractRequestParametersType request = ((RequestType) body)
.getRequestParameters().getValue();

FutureTask<List<AbstractResponseParametersType>> thread = new FutureTask<List<AbstractResponseParametersType>>(
new Callable<List<AbstractResponseParametersType>>() {

public List<AbstractResponseParametersType> call()
throws Exception {
List<AbstractResponseParametersType> response = null;

try {
if (request instanceof DetermineRouteRequestType)
response = routePlan(
(DetermineRouteRequestType) request,
locale);
else if (request instanceof ReverseGeocodeRequestType)
response = reverseGeocoding((ReverseGeocodeRequestType) request);
else if (request instanceof GeocodeRequestType)
response = geocoding((GeocodeRequestType) request);
else if (request instanceof DirectoryRequestType)
response = directory((DirectoryRequestType) request);
public XLSType openLS(JAXBElement<XLSType> jaxbelement) {
try {
final XLSType parameter = jaxbelement.getValue();
LOG.trace("openLS(" + parameter + ")");
Locale localetmp = Locale.ROOT;

synchronized (resultado) {
resultado.add(response);
if (parameter.getLang() != null && !parameter.getLang().isEmpty()) {
LOG.trace("Language detected: " + parameter.getLang());
localetmp = new Locale(parameter.getLang());
}
final Locale locale = localetmp;
localetmp = null;
final List<List<AbstractResponseParametersType>> resultado = new LinkedList<List<AbstractResponseParametersType>>();

ExecutorService executor = Executors.newFixedThreadPool(3);

for (JAXBElement<? extends AbstractBodyType> jaxbbody : parameter
.getBody()) {

AbstractBodyType body = jaxbbody.getValue();

if (body instanceof RequestType) {

final AbstractRequestParametersType request = ((RequestType) body)
.getRequestParameters().getValue();

FutureTask<List<AbstractResponseParametersType>> thread = new FutureTask<List<AbstractResponseParametersType>>(
new Callable<List<AbstractResponseParametersType>>() {

public List<AbstractResponseParametersType> call()
throws Exception {
List<AbstractResponseParametersType> response = null;

try {
if (request instanceof DetermineRouteRequestType)
response = routePlan(
(DetermineRouteRequestType) request,
locale);
else if (request instanceof ReverseGeocodeRequestType)
response = reverseGeocoding((ReverseGeocodeRequestType) request);
else if (request instanceof GeocodeRequestType)
response = geocoding((GeocodeRequestType) request);
else if (request instanceof DirectoryRequestType)
response = directory((DirectoryRequestType) request);

synchronized (resultado) {
resultado.add(response);
}
} catch (Throwable e) {
LOG.error("Error answering request", e);
throw new RuntimeException(e);
}
} catch (Throwable e) {
LOG.error(e, e);
throw new RuntimeException(e);
return response;
}
return response;
}
});
executor.execute(thread);
});
executor.execute(thread);
}
}
}

executor.shutdown();
executor.shutdown();

try {
executor.awaitTermination(10, TimeUnit.SECONDS);
} catch (InterruptedException e) {
LOG.error(e, e);
try {
executor.awaitTermination(10, TimeUnit.SECONDS);
} catch (InterruptedException e) {
LOG.error(e, e);
}
return Utils.envelop(resultado, locale).getValue();
} catch (Throwable t) {
LOG.error("Unexpected error. Help!", t);

return null;
}

return Utils.envelop(resultado, locale);
}

/**
@@ -215,10 +221,11 @@ protected List<AbstractResponseParametersType> routePlan(
String conn = configuration.get("RoutingConnector", "default");
if (conn.equals("PGROUTING"))
arpt = routingController.routePlan(param);
else if (conn.equals("MONAV"))
else if (conn.equals("MONAV")) {
if (monavConnector == null)
monavConnector = new MoNaVConnector();
arpt = monavConnector.routePlan(param);
else {

} else {
String host_port = configuration.get("OSRM_HOST",
"localhost:5000");
String http = "http";
12 src/main/java/org/gofleet/openLS/util/GeoUtil.java
View file
@@ -25,11 +25,8 @@
import org.geotools.geometry.jts.JTS;
import org.geotools.referencing.CRS;
import org.gofleet.openLS.ddbb.dao.GeoCodingDAO;
import org.opengis.geometry.MismatchedDimensionException;
import org.opengis.referencing.FactoryException;
import org.opengis.referencing.crs.CoordinateReferenceSystem;
import org.opengis.referencing.operation.MathTransform;
import org.opengis.referencing.operation.TransformException;
import org.postgis.PGgeometry;
import org.postgis.Point;
import org.postgresql.jdbc4.Jdbc4Array;
@@ -219,15 +216,24 @@ public static com.vividsolutions.jts.geom.Point getPoint(

CoordinateReferenceSystem sourceCRS = getSRS(startPoint);

LOG.trace(sourceCRS.toWKT());
LOG.trace("(" + ctype.getValue().get(0) + ", "
+ ctype.getValue().get(1) + ")");

com.vividsolutions.jts.geom.Point p = geomFact
.createPoint(new Coordinate(ctype.getValue().get(0), ctype
.getValue().get(1)));

LOG.info(p);
if (targetCRS != null && !sourceCRS.equals(targetCRS)) {
try {
MathTransform transform = CRS.findMathTransform(sourceCRS,
targetCRS);
p = JTS.transform(p, transform).getCentroid();

p = geomFact.createPoint(new Coordinate(p.getY(), p.getX()));

LOG.info(p);
} catch (Throwable t) {
LOG.error("Error converting coordinates", t);
}
4 src/main/java/org/gofleet/openLS/util/MoNaVConnector.java
View file
@@ -84,8 +84,8 @@ public MoNaVConnector() {
.createUnmarshaller();
context = JAXBContext.newInstance("org.jvnet.ogc.gml.v_3_1_1.jts");
marshaller = context.createMarshaller();
} catch (JAXBException e) {
LOG.error(e, e);
} catch (Throwable e) {
LOG.error("Unable to load MoNaV connector" , e);
}
}

2 src/main/resources/applicationContext.xml
View file
@@ -104,7 +104,7 @@
</bean>


<bean id="osrmConnector" class="org.gofleet.openLS.util.OSRMConnector">
<bean id="osrmConnector" class="org.emergya.osrm.OSRM">
<property name="i18n" ref="i18n" />
</bean>

2 src/main/resources/jdbc.properties
View file
@@ -1,5 +1,5 @@
jdbc.driverClassName=org.postgis.DriverWrapper
jdbc.url=jdbc\:postgresql_postGIS\://localhost\:5433/gofleetls
jdbc.url=jdbc\:postgresql_postGIS\://localhost\:5432/gofleetls
jdbc.username=gofleetls
jdbc.password=gofleetls
jdbc.hibernate.dialect=org.gofleet.openLS.ddbb.dialect.GoFleetDialect
1 src/main/resources/log4j.properties
View file
@@ -28,6 +28,7 @@ log4j.logger.de=FATAL
log4j.logger.httpclient=FATAL
log4j.logger.com=FATAL
log4j.logger.org.gofleet=DEBUG
log4j.logger.org.apache.commons.configuration=ERROR

# CONSOLE is set to be a ConsoleAppender using a PatternLayout.
log4j.appender.CONSOLE=org.apache.log4j.ConsoleAppender
4 src/main/webapp/WEB-INF/web.xml
View file
@@ -19,7 +19,7 @@


<servlet>
<servlet-name>Jersey REST Service</servlet-name>
<servlet-name>GoFleetLS</servlet-name>
<servlet-class>com.sun.jersey.spi.spring.container.servlet.SpringServlet</servlet-class>
<init-param>
<param-name>com.sun.jersey.config.property.packages</param-name>
@@ -28,7 +28,7 @@
<load-on-startup>1</load-on-startup>
</servlet>
<servlet-mapping>
<servlet-name>Jersey REST Service</servlet-name>
<servlet-name>GoFleetLS</servlet-name>
<url-pattern>/*</url-pattern>
</servlet-mapping>
</web-app>
4 src/test/java/org/gofleet/openls/GeoCodingTest.java
View file
@@ -74,7 +74,7 @@ public void testReverseGeocoding() throws FileNotFoundException,
JAXBException, XMLStreamException, FactoryConfigurationError,
SAXException {
XLSType xls = openLS.openLS(Utils.convertFile2XLSType(
"/reverseGeocoding.xml", XLSType.class)).getValue();
"/reverseGeocoding.xml", XLSType.class));

assertNotNull("The response is null", xls);

@@ -130,7 +130,7 @@ public void testReverseGeocoding() throws FileNotFoundException,
public void testGeocoding() throws FileNotFoundException, JAXBException,
XMLStreamException, FactoryConfigurationError, SAXException {
XLSType object = openLS.openLS(Utils.convertFile2XLSType(
"/geocodingRequest.xml", XLSType.class)).getValue();
"/geocodingRequest.xml", XLSType.class));

XLSType xls = (XLSType) object;

41 src/test/java/org/gofleet/openls/RoutingServiceTests.java
View file
@@ -13,23 +13,32 @@
import javax.xml.stream.XMLStreamException;

import net.opengis.gml.v_3_1_1.DirectPositionListType;
import net.opengis.gml.v_3_1_1.DirectPositionType;
import net.opengis.xls.v_1_2_0.AbstractBodyType;
import net.opengis.xls.v_1_2_0.AbstractResponseParametersType;
import net.opengis.xls.v_1_2_0.DetermineRouteResponseType;
import net.opengis.xls.v_1_2_0.ResponseType;
import net.opengis.xls.v_1_2_0.RouteGeometryType;
import net.opengis.xls.v_1_2_0.XLSType;

import org.geotools.geometry.jts.JTS;
import org.geotools.referencing.CRS;
import org.gofleet.openLS.OpenLS;
import org.gofleet.openLS.util.Utils;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.opengis.geometry.MismatchedDimensionException;
import org.opengis.referencing.FactoryException;
import org.opengis.referencing.crs.CoordinateReferenceSystem;
import org.opengis.referencing.operation.TransformException;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.test.context.ContextConfiguration;
import org.springframework.test.context.junit4.SpringJUnit4ClassRunner;
import org.xml.sax.SAXException;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.Point;

@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(locations = { "classpath:applicationContext.xml" })
public class RoutingServiceTests {
@@ -42,7 +51,7 @@ public void testSimpleRoute() throws FileNotFoundException, JAXBException,
XMLStreamException, FactoryConfigurationError, SAXException {
JAXBElement<XLSType> convertFile2XLSType = Utils.convertFile2XLSType(
"/determineRouteRequest.xml", XLSType.class);
XLSType object = openLS.openLS(convertFile2XLSType).getValue();
XLSType object = openLS.openLS(convertFile2XLSType);

assertNotNull("Empty response", object);

@@ -120,6 +129,32 @@ public void testSRSRouted() throws FileNotFoundException, JAXBException,
XMLStreamException, FactoryConfigurationError, SAXException {
JAXBElement<XLSType> convertFile2XLSType = Utils.convertFile2XLSType(
"/determineRouteRequestSRS.xml", XLSType.class);
assertNotNull(openLS.openLS(convertFile2XLSType).getValue());
assertNotNull(openLS.openLS(convertFile2XLSType));
}

@Test
public void testSRS() throws FileNotFoundException, JAXBException,
XMLStreamException, FactoryConfigurationError, SAXException,
MismatchedDimensionException, TransformException, FactoryException {

GeometryFactory gf = new GeometryFactory();

CoordinateReferenceSystem sourceCRS = CRS.decode("EPSG:4326");
CoordinateReferenceSystem targetCRS = CRS.decode("EPSG:23030");
CRS.findMathTransform(sourceCRS, targetCRS);

Double y = -3.7091297753788;
Double x = 40.400858925754;

Point p = gf.createPoint(new Coordinate(x, y));
System.out.println(p);

p = JTS.transform(p, CRS.findMathTransform(sourceCRS, targetCRS))
.getCentroid();
System.out.println(p);
p = JTS.transform(p, CRS.findMathTransform(targetCRS, sourceCRS))
.getCentroid();

System.out.println(p);
}
}
62 src/test/resources/determineRouteRequestSRS.xml
View file
@@ -1,38 +1,34 @@
<?xml version="1.0" encoding="UTF-8"?>
<xls:XLS xmlns:xls="http://www.opengis.net/xls"
xsi:schemaLocation="http://www.opengis.net/xls http://schemas.opengis.net/ols/1.2.0/ADT.xsd http://schemas.opengis.net/ols/1.2.0/LocationUtilityService.xsd http://schemas.opengis.net/ols/1.2.0/RouteService.xsd"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<xls:RequestHeader />
<xls:Request methodName="RouteRequest">
<xls:DetermineRouteRequest>
<xls:RoutePlan>
<xls:RoutePreference>Fastest</xls:RoutePreference>
<xls:WayPointList>

<XLS version="1.1" xmlns="http://www.opengis.net/xls" xmlns:gml="http://www.opengis.net/gml"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.opengis.net/xls">
<RequestHeader />
<Request methodName="RouteRequest" version="1.1" requestID="rte1">
<DetermineRouteRequest>
<RoutePlan>
<RoutePreference>Fastest</RoutePreference>
<WayPointList>
<StartPoint>
<Position>
<gml:Point srsName="EPSG:4258">
<gml:pos>-5.917055 37.394202</gml:pos>
<xls:StartPoint>
<xls:Position>
<gml:Point srsName="EPSG:23030" xmlns:gml="http://www.opengis.net/gml">
<gml:pos>444227 4474647.25</gml:pos>
</gml:Point>
</Position>
</StartPoint>
</xls:Position>
</xls:StartPoint>

<EndPoint>
<Position>
<gml:Point srsName="EPSG:4258">
<gml:pos>-5.9172345 37.386752</gml:pos>
<xls:EndPoint>
<xls:Position>
<gml:Point srsName="EPSG:23030" xmlns:gml="http://www.opengis.net/gml">
<gml:pos>443984 4474719.25</gml:pos>
</gml:Point>
</Position>
</EndPoint>
</WayPointList>
</RoutePlan>
<RouteInstructionsRequest format="text/plain"
provideGeometry="false" />
<RouteGeometryRequest />
<RouteMapRequest>
<Output format="png8" height="400" width="400" />
</RouteMapRequest>
</DetermineRouteRequest>
</Request>
</xls:Position>
</xls:EndPoint>

</XLS>
</xls:WayPointList>
</xls:RoutePlan>
<xls:RouteInstructionsRequest />
<xls:RouteGeometryRequest />
<xls:RouteMapRequest />
</xls:DetermineRouteRequest>
</xls:Request>
</xls:XLS>
50 tsp/pom.xml
View file
@@ -0,0 +1,50 @@
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.emergya</groupId>
<artifactId>tsp</artifactId>
<version>0.1.1</version>
<name>tsp</name>
<description>TSP interfaces and utilities.</description>


<distributionManagement>
<repository>
<id>gofleet</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet</url>
</repository>
<snapshotRepository>
<id>gofleet-snap</id>
<url>http://nexus.emergya.es/nexus/content/repositories/gofleet-snapshots</url>
</snapshotRepository>
</distributionManagement>


<build>
<plugins>
<plugin>

<!-- Maven compiler plugin -->
<artifactId>maven-compiler-plugin</artifactId>
<configuration>
<source>1.6</source>
<target>1.6</target>
<optimize>true</optimize>
</configuration>
</plugin>
</plugins>
</build>

<dependencies>
<dependency>
<groupId>org.geotools</groupId>
<artifactId>gt-api</artifactId>
<version>${geotools.version}</version>
</dependency>
</dependencies>

<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<geotools.version>8.0-M4</geotools.version>
</properties>
</project>
59 tsp/src/main/java/org/gofleet/openLS/tsp/TSPAlgorithm.java
View file
@@ -0,0 +1,59 @@

/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/

package org.gofleet.openLS.tsp;

import java.util.List;

public interface TSPAlgorithm {

/**
* Returns the optimum TSP of the bag.
*
* The list contains all the stops of the bag.
*
* If {@link TSPStopBag#hasLast()}, {@link TSPStopBag#getLast()} is the last
* {@link TSPStop} of the list.
*
* If {@link TSPStopBag#hasFirst()}, {@link TSPStopBag#getFirst()} is the
* first {@link TSPStop} of the list.
*
* @param bag
* @return
*/
List<TSPStop> order(TSPStopBag bag);

/**
* Cancels the execution of the ordering. Useful for expensive algorithms.
* @return
*/
boolean stop();

}
48 tsp/src/main/java/org/gofleet/openLS/tsp/TSPStop.java
View file
@@ -0,0 +1,48 @@

/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/

package org.gofleet.openLS.tsp;

import com.vividsolutions.jts.geom.Point;

public interface TSPStop {

/**
* Returns the unique id (on this bag) for this stop.
* @return
*/
Integer getId();

/**
* Returns the position of this stop.
* @return
*/
Point getPosition();
}
83 tsp/src/main/java/org/gofleet/openLS/tsp/TSPStopBag.java
View file
@@ -0,0 +1,83 @@

/**
* Copyright (C) 2012, Emergya (http://www.emergya.es)
*
* @author <a href="mailto:marias@emergya.com">María Arias de Reyna</a>
*
* This file is part of GoFleet
*
* This software is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This software is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*
* As a special exception, if you link this library with other files to
* produce an executable, this library does not by itself cause the
* resulting executable to be covered by the GNU General Public License.
* This exception does not however invalidate any other reasons why the
* executable file might be covered by the GNU General Public License.
*/
package org.gofleet.openLS.tsp;

import java.util.Collection;

public interface TSPStopBag {
/**
* If {@link #hasFirst()} returns true, returns the stop which has to be
* first
*
* Otherwise, returns null.
*
* @return
*/
TSPStop getFirst();

/**
* If {@link #hasLast()} returns true, returns the stop which has to be last
*
* Otherwise, returns null.
*
* @return
*/
TSPStop getLast();

/**
* Returns, unordered, all the stops.
*
* @return
*/
Collection<TSPStop> getAll();

/**
* Returns if this bag has a stop which must be the first stop
*
* @return
*/
Boolean hasFirst();

/**
* Returns if this bag has a stop which must be the last stop
*
* @return
*/
Boolean hasLast();

/**
* Returns the number of stops the solution has to have (which means, the
* total number of stops of this bag).
*
* @return
*/
Integer size();

}