API tools faq
paste
Guest User

Untitled

a guest
Mar 18th, 2018
133
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.20 KB | None | 0 0
raw download clone embed print report
  1. package com.example.aziza.tourguide.TSP;
  2.  
  3. import android.os.StrictMode;
  4. import android.util.Log;
  5.  
  6. import com.example.aziza.tourguide.Attraction;
  7. import com.example.aziza.tourguide.DBHelper;
  8.  
  9. import org.osmdroid.bonuspack.routing.GraphHopperRoadManager;
  10. import org.osmdroid.bonuspack.routing.RoadManager;
  11. import org.osmdroid.util.GeoPoint;
  12. import org.w3c.dom.Attr;
  13.  
  14. import java.sql.Time;
  15. import java.text.DateFormat;
  16. import java.text.ParseException;
  17. import java.text.SimpleDateFormat;
  18. import java.util.ArrayList;
  19. import java.util.Collections;
  20. import java.util.Date;
  21. import java.util.HashMap;
  22. import java.util.List;
  23. import java.util.Random;
  24. import java.util.concurrent.ThreadLocalRandom;
  25. import java.util.concurrent.TimeUnit;
  26.  
  27. /**
  28. * Created by aziza on 2018-03-01.
  29. */
  30.  
  31. public class TSP{
  32. GeoPoint startPoint;
  33. Date currentTime = null;
  34. Date endTime;
  35. RoadManager roadManager;
  36. ArrayList<GeoPoint> bestRoute = new ArrayList<GeoPoint>();
  37. ArrayList<GeoPoint> visitedPlaces = new ArrayList<GeoPoint>();
  38. ArrayList<Attraction> passedAttractions = new ArrayList<Attraction>();
  39. public HashMap<Double, ArrayList<GeoPoint>> possibleRoutes = new HashMap<Double, ArrayList<GeoPoint>>();
  40. public ArrayList<Double> distanceKeys = new ArrayList<Double>();
  41. double fastest = Double.MAX_VALUE;
  42. DBHelper mydb;
  43.  
  44.  
  45. public ArrayList<GeoPoint> findBestRoute(RoadManager roadManager, ArrayList<Attraction> attractions, Attraction start, DBHelper mydb) {
  46. this.mydb = mydb;
  47. passedAttractions = attractions;
  48. this.roadManager = roadManager;
  49. ArrayList<GeoPoint> waypoints = new ArrayList<GeoPoint>();
  50. for (int i = 0; i < attractions.size(); i++) {
  51. GeoPoint point = new GeoPoint(attractions.get(i).latitude, attractions.get(i).longitude);
  52. waypoints.add(point);
  53. }
  54. startPoint = new GeoPoint(start.latitude, start.longitude);
  55. waypoints.remove(startPoint);
  56. ArrayList<ArrayList<GeoPoint>> permutations = listPermutations(waypoints);
  57. for (ArrayList<GeoPoint> al : permutations) {
  58. al.add(0, startPoint);
  59. double roadLength = roadManager.getRoad(al).mDuration;
  60. // double roadLength = ThreadLocalRandom.current().nextInt(0, 10 + 1);
  61. possibleRoutes.put(roadLength, al);
  62. distanceKeys.add(roadLength);
  63. if (roadLength<fastest) {
  64. fastest = roadLength;
  65. }
  66. }
  67. Collections.sort(distanceKeys);
  68. return possibleRoutes.get(fastest);
  69. }
  70.  
  71. /* TODO: run that first and tell them if they don't have enough time to visit all attractions
  72. that is even best case path
  73. Offer to reconsider points or time, alternatively build a path
  74. */
  75. public boolean enoughTime() {
  76. long minutesAvailable = mydb.timeDifference(mydb.parseTime(mydb.currentTimeTo), mydb.parseTime(mydb.currentTimeFrom), TimeUnit.MINUTES);
  77. double totalTime = TimeUnit.MINUTES.convert((long)fastest, TimeUnit.MILLISECONDS);;
  78. for (GeoPoint g : possibleRoutes.get(fastest)) {
  79. totalTime += Attraction.getAttractionByGeo(passedAttractions, g).time_to_spend;
  80. }
  81. if (minutesAvailable > totalTime) {
  82. return true;
  83. }
  84.  
  85. return false;
  86. }
  87.  
  88. /* TODO: implementation of route/time algorithm
  89. * grab fastest route and check if opening hours correlate with time available
  90. * if something is closing soon go to the closest one with least walking time ...
  91. * ### keep track of visited places ?
  92. * ### have some sorta table of distance n opening hours correlation?
  93. *
  94. * /* attraction start time should be before current time and
  95. * attraction end time should be after currentTime + travelling time + time at the place
  96. * * trip end time should be after current time
  97. * * rework it to be more specific, i.e. if we can make it to the place and
  98. * * spend at least 20 minutes there give an alert
  99. *
  100. * ######### Brain-storming ########
  101. * Best-case: the fastest tour fits in all criterions, keep running for loop updating current time, output it back
  102. * Average-case: one attraction is not open at the time of visit, so go the the other one
  103. * Example: 3 points, so possible routes are abc, acb, optimal is abc, going from a to b and b is not open yet but c is,
  104. * so go to c first, shift b down the priority queque.
  105. * Have a subarray of a different permutation array, if it contains all the points we visited before, i.e "a", then grab it and do its points
  106. * repeat for the next
  107. * do the same for close hours
  108. *
  109. *
  110. * */
  111. public void timeRouteAlgorithm() {
  112. // currentTime = mydb.parseTime(mydb.currentTimeFrom);
  113. // endTime = mydb.parseTime(mydb.currentTimeTo);
  114. ArrayList<GeoPoint> fastestRoute = possibleRoutes.get(fastest);
  115. int keepKeyIndex = 0;
  116. /*for testing purposes */
  117. SimpleDateFormat inFormat = new SimpleDateFormat("hh:mmaa");
  118. try {
  119. currentTime = inFormat.parse("02:00pm");
  120. endTime = inFormat.parse("5:01pm");
  121.  
  122. } catch (Exception e) {
  123. e.printStackTrace();
  124. }
  125.  
  126. fastestRoute = new ArrayList<GeoPoint>();
  127. fastestRoute.add(new GeoPoint(1.0, 1.0));
  128. fastestRoute.add(new GeoPoint(2.0, 2.0));
  129. fastestRoute.add(new GeoPoint(3.0, 3.0));
  130. // fastestRoute.add(new GeoPoint(4.0, 3.0));
  131.  
  132. /* create permutation list for test purposes */
  133. ArrayList<GeoPoint> visitedPlaces = new ArrayList<GeoPoint>();
  134. ArrayList<GeoPoint> arrayToCopy = new ArrayList<GeoPoint>();
  135. arrayToCopy.addAll(fastestRoute);
  136. arrayToCopy.remove(arrayToCopy.get(0));
  137. ArrayList<ArrayList<GeoPoint>> allPermutations = listPermutations(arrayToCopy);
  138. distanceKeys.add(2.0);
  139. distanceKeys.add(3.0);
  140. allPermutations.get(0).add(0, (new GeoPoint(1.0, 1.0)));
  141. allPermutations.get(1).add(0, (new GeoPoint(1.0, 1.0)));
  142. possibleRoutes.put(2.0, allPermutations.get(0));
  143. possibleRoutes.put(3.0, allPermutations.get(1));
  144.  
  145. for (int i=0;i< fastestRoute.size();i++) {
  146.  
  147. Date attStartTime = null;
  148. try {
  149. if (i == 0) {
  150. attStartTime = inFormat.parse("01:30pm");
  151. }
  152. if (i == 1) {
  153. attStartTime = inFormat.parse("03:00pm");
  154. }
  155.  
  156. } catch (Exception e) {
  157. e.printStackTrace();
  158. }
  159.  
  160. long differenceSeconds = currentTime.getTime() - attStartTime.getTime();
  161. long differenceMinutes = TimeUnit.MINUTES.convert(differenceSeconds, TimeUnit.MILLISECONDS);
  162.  
  163. if (differenceMinutes > 0) {
  164. long summedTime = 0;
  165. System.out.println("The place is already open at the time of our visit");
  166. /*Make sure the place won't close on us */
  167.  
  168. if (i > 0) {
  169. /*Caclucate walking time from previous spot to current */
  170. summedTime += 15;
  171. }
  172. Date attEndTime = null;
  173. try {
  174. attEndTime = inFormat.parse("03:25pm");
  175. } catch (Exception e) {
  176. e.printStackTrace();
  177. }
  178. /* i* 10 is the time we are gonna spend at the place */
  179. summedTime += TimeUnit.MINUTES.convert(currentTime.getTime(), TimeUnit.MILLISECONDS) + (i * 10 + 5);
  180. long makeBeforeOver = TimeUnit.MINUTES.convert(attEndTime.getTime(), TimeUnit.MILLISECONDS) - summedTime;
  181. if (makeBeforeOver > 0) {
  182. System.out.println("The place is open for the whole duration of the trip ");
  183.  
  184. /* now check that we have enought time to finish the visit */
  185. long haveEnoughTime = TimeUnit.MINUTES.convert(endTime.getTime(), TimeUnit.MILLISECONDS) - summedTime;
  186. if (haveEnoughTime > 0) {
  187. System.out.println("We have enough time to finish visiting this place");
  188. /*update current time */
  189. currentTime = new Date(TimeUnit.MILLISECONDS.convert(summedTime, TimeUnit.MINUTES));
  190. visitedPlaces.add(fastestRoute.get(i));
  191. }
  192. /* tbh that should be a different case all together but keep it just in case */
  193. else {
  194. System.out.println("Unfortunately, we do not have enough time to finish visiting the place ");
  195. }
  196. } else {
  197. System.out.println("The place will close before we can finish our visit");
  198. }
  199. } else {
  200. System.out.println("The place is not yet open at the time of our visit");
  201. /* so check if we can go to a different place on the list */
  202. for (int d = 1; d < distanceKeys.size(); i++) {
  203. System.out.println("Visitied places size is " + visitedPlaces.size());
  204. List<GeoPoint> sublistOfPoints = possibleRoutes.get(distanceKeys.get(d)).subList(0, (visitedPlaces.size()));
  205. // for (GeoPoint g : sublistOfPoints) {
  206. // System.out.println(g);
  207. // }
  208. // for (GeoPoint a : visitedPlaces) {
  209. // System.out.println(a);
  210. // }
  211. if (sublistOfPoints.containsAll(visitedPlaces)) {
  212. // System.out.println("Second point in a sublist is " + possibleRoutes.get(distanceKeys.get(d)).get(1));
  213. attStartTime = null;
  214. List<GeoPoint> sublistToKeepGoing = possibleRoutes.get(distanceKeys.get(d)).subList(visitedPlaces.size(), possibleRoutes.get(distanceKeys.get(d)).size()-1);
  215. for (int q=0;q<sublistToKeepGoing.size();i++) {
  216. try {
  217. attStartTime = inFormat.parse("01:40pm");
  218.  
  219. } catch (Exception e) {
  220. e.printStackTrace();
  221. }
  222. differenceSeconds = currentTime.getTime() - attStartTime.getTime();
  223. differenceMinutes = TimeUnit.MINUTES.convert(differenceSeconds, TimeUnit.MILLISECONDS);
  224.  
  225. if (differenceMinutes > 0) {
  226. System.out.println("Keep doing your thing");
  227. }
  228. }
  229. }
  230. }
  231. }
  232. }
  233. // for (int i=0;i< fastestRoute.size();i++) {
  234. // Date attStartTime = mydb.parseTime(Attraction.getAttractionByGeo(passedAttractions, fastestRoute.get(i)).from_time_week);
  235. // long calcDifference = mydb.timeDifference(currentTime, attStartTime, TimeUnit.MINUTES);
  236. // if (calcDifference > 0) {
  237. // long summedTime = 0;
  238. // if (i>1) {
  239. // ArrayList<GeoPoint> distancebetweenTwo = new ArrayList<GeoPoint>();
  240. // distancebetweenTwo.add(fastestRoute.get(i));
  241. // distancebetweenTwo.add(fastestRoute.get(i-1));
  242. // summedTime += TimeUnit.MINUTES.convert((long) roadManager.getRoad(distancebetweenTwo).mDuration, TimeUnit.MILLISECONDS);
  243. // }
  244. // Date attEndTime = mydb.parseTime(Attraction.getAttractionByGeo(passedAttractions, fastestRoute.get(i)).to_time_week);
  245. // summedTime += TimeUnit.MINUTES.convert(currentTime.getTime(), TimeUnit.MILLISECONDS) + Attraction.getAttractionByGeo(passedAttractions, fastestRoute.get(i)).time_to_spend;
  246. // long makeBeforeOver = TimeUnit.MINUTES.convert(attEndTime.getTime(), TimeUnit.MILLISECONDS) - summedTime;
  247. // /*attraction won't close before we get there and spend time in there */
  248. // if (makeBeforeOver > 0) {
  249. // // Log.i("TSP", "We know tour is doable");
  250. // System.out.println("Tour is doable");
  251. // }
  252. // }
  253. }
  254.  
  255. public void recursiveTRAlgorithm(List<GeoPoint> points) {
  256. boolean b = false;
  257. for (GeoPoint g : points) {
  258. if (true) {
  259.  
  260. }
  261. else {
  262. for (int i = 1; i < distanceKeys.size(); i++) {
  263. recursiveTRAlgorithm(sublistToKeepGoing);
  264. }
  265. }
  266. }
  267.  
  268. }
  269.  
  270. /*Used for test purposes only */
  271. public void setUp() {
  272. ArrayList<GeoPoint> fastestRoute = new ArrayList<GeoPoint>();
  273. fastestRoute.add(new GeoPoint(1.0, 1.0));
  274. fastestRoute.add(new GeoPoint(2.0, 2.0));
  275. fastestRoute.add(new GeoPoint(3.0, 3.0));
  276.  
  277. /* create permutation list for test purposes */
  278. ArrayList<GeoPoint> visitedPlaces = new ArrayList<GeoPoint>();
  279. ArrayList<GeoPoint> arrayToCopy = new ArrayList<GeoPoint>();
  280. arrayToCopy.addAll(fastestRoute);
  281. arrayToCopy.remove(arrayToCopy.get(0));
  282. ArrayList<ArrayList<GeoPoint>> allPermutations = listPermutations(arrayToCopy);
  283. distanceKeys.add(2.0);
  284. distanceKeys.add(3.0);
  285. allPermutations.get(0).add(0, (new GeoPoint(1.0, 1.0)));
  286. allPermutations.get(1).add(0, (new GeoPoint(1.0, 1.0)));
  287. possibleRoutes.put(2.0, allPermutations.get(0));
  288. possibleRoutes.put(3.0, allPermutations.get(1));
  289.  
  290. }
  291.  
  292. public ArrayList<ArrayList<GeoPoint>> listPermutations(ArrayList<GeoPoint> list) {
  293.  
  294. if (list.size() == 0) {
  295. ArrayList<ArrayList<GeoPoint>> result = new ArrayList<ArrayList<GeoPoint>>();
  296. result.add(new ArrayList<GeoPoint>());
  297. return result;
  298. }
  299.  
  300. ArrayList<ArrayList<GeoPoint>> returnMe = new ArrayList<ArrayList<GeoPoint>>();
  301.  
  302. GeoPoint firstElement = list.remove(0);
  303.  
  304. ArrayList<ArrayList<GeoPoint>> recursiveReturn = listPermutations(list);
  305. for (List<GeoPoint> li : recursiveReturn) {
  306. for (int index = 0; index <= li.size(); index++) {
  307. ArrayList<GeoPoint> temp = new ArrayList<GeoPoint>(li);
  308. temp.add(index, firstElement);
  309. returnMe.add(temp);
  310. }
  311. }
  312. return returnMe;
  313. }
  314.  
  315. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!