hxtk / road-trip-router Goto Github PK

View Code? Open in Web Editor NEW

1.0 1.0 0.0 75 KB

Find a (nearly) optimal path among several destinations for your next road trip.

License: MIT License

Python 9.03% Java 90.97%

optimization road-trip tsp-solver

road-trip-router's People

Contributors

Stargazers

Watchers

road-trip-router's Issues

Test for lexicographic permutation generator causes ConcurrentModificationException

me.psanders.utils.LexicographicPermuterTest.getsSecondPermutation consistently throws a ConcurrentModificationException when run through Bazel.

Find an alternative to Google Maps Services distance matrix.

We generate O(n²) requests to the API at the beginning of our algorithm for Issue #1, and at the free rate for Google Maps Services this takes substantially more time than the genetic optimization.

With only a handful of destinations, the limit for requests per day becomes a limiting factor for those with free subscriptions. That renders this project nearly unusable to people who do not already have enterprise subscriptions.

Remove calls to System.exit

As referenced in #10, calls to System.exit make the code harder to follow because it can exit in multiple places. Instead, we will print the error messages and then return null values until we get back up to main to exit.

Prints errors to terminal that could be ignored

$ RoutePlanner --key "any non-empty string, including a valid key"
SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.

Graph generator

Accept a list of locations and use the Google Maps Services DistanceMatrix API to convert them into a list of distances.

Refactor DistanceMatrixFactory to Builder design pattern

This would allow us to use several smaller methods that had a lesser cognitive overhead, e.g.:

new DistanceMatrixFactory().withPlaces(places).withFlags(flags).withContext(context).build();

Note, this would require rewriting all use cases. Those include the use in ShortRouteFinder and the Unit Test for this class.

Break up me.psanders.ShortRouteFinder into testable components

Factory for matrix should take flags, a list of places, and a DistanceMatrixApiRequest object, modify that object based on the flags, and return a MatrixGraph<String, Long>
- Mock DistanceMatrixApiRequest that fails to connect to the internet, i.e., throws ConnectException
- Pass in a bad GeoApiContext, e.g., null, no API key, etc.
- Mock that fails because the API key has exceeded its quota
- Mock that works as expected

Print usage if arguments are invalid

So far, we only require --key -k.

Output is resolved locations instead of given locations

This can be confusing to users because the locations they provide may not appear recognizably on the output list.

Test case for Brute Force Optimization Strategy

This should include a couple of TSPs that have been solved by hand and test their results against that of the BruteForceOptimizationStrategy.

Accept file input on the --file flag

Given list.txt containing a newline-delimited list of places, the following command should work should work as if the locations in file were passed as arguments and the file flag were absent.

$ RoutePlanner --file list.txt --key "..."

Exit gracefully on exception.

Print a user-friendly message and exit with error status instead of a stack trace and crash.

Usage message should explicitly prompt for a list of at least two places.

See: https://commons.apache.org/proper/commons-cli/javadocs/api-release/org/apache/commons/cli/HelpFormatter.html

Invalid output for the following arguments.

$ bazel-bin/RoutePlanner --key $(cat api.key) "Columbia, SC" "Riley Moore Falls Trail, Westminster, SC" "Raven Cliff Falls, SC" "Carrick Falls, SC" "Twin Falls, Water Falls Road, Sunset, SC" "Cherry Hill Campground, SC" "Blue Hill Falls, Rich Mountain Road, Mountain Rest, SC" "Brasstown Falls, SC" --scenic        
We couldn't resolve the leg between "Columbia, SC, USA" and "", so we're trying to route around it.
We couldn't resolve the leg between "Riley Moore Falls Trail, Westminster, SC 29693, USA" and "", so we're trying to route around it.
We couldn't resolve the leg between "Raven Cliff Falls, South Carolina 29635, USA" and "", so we're trying to route around it.
We couldn't resolve the leg between "388 Table Rock State Park Rd, Pickens, SC 29671, USA" and "", so we're trying to route around it.
We couldn't resolve the leg between "Twin Falls, Water Falls Rd, Sunset, SC 29685, USA" and "", so we're trying to route around it.
We couldn't resolve the leg between "CHERRY HILL CAMPGROUND, SC-107, Walhalla, SC 29691, USA" and "", so we're trying to route around it.
We couldn't resolve the leg between "" and "Columbia, SC, USA", so we're trying to route around it.
We couldn't resolve the leg between "" and "Riley Moore Falls Trail, Westminster, SC 29693, USA", so we're trying to route around it.
We couldn't resolve the leg between "" and "Raven Cliff Falls, South Carolina 29635, USA", so we're trying to route around it.
We couldn't resolve the leg between "" and "388 Table Rock State Park Rd, Pickens, SC 29671, USA", so we're trying to route around it.
We couldn't resolve the leg between "" and "Twin Falls, Water Falls Rd, Sunset, SC 29685, USA", so we're trying to route around it.
We couldn't resolve the leg between "" and "CHERRY HILL CAMPGROUND, SC-107, Walhalla, SC 29691, USA", so we're trying to route around it.
We couldn't resolve the leg between "" and "Creek, Westminster, SC 29693, United States", so we're trying to route around it.
We couldn't resolve the leg between "Creek, Westminster, SC 29693, United States" and "", so we're trying to route around it.
CHERRY HILL CAMPGROUND, SC-107, Walhalla, SC 29691, USA ->
Twin Falls, Water Falls Rd, Sunset, SC 29685, USA ->
388 Table Rock State Park Rd, Pickens, SC 29671, USA ->
Raven Cliff Falls, South Carolina 29635, USA ->
Columbia, SC, USA ->
 ->
Creek, Westminster, SC 29693, United States ->
Riley Moore Falls Trail, Westminster, SC 29693, USA ->
CHERRY HILL CAMPGROUND, SC-107, Walhalla, SC 29691, USA
Total distance: -5731137678988703mi

`--fast` flag incorrectly causes cost to be printed in time rather than distance.

Fix suggestion:

After the best route is found, use the hash table to convert it back to a distance route and return that if it was found as a time route.

Wrapper class for DistanceMatrixApiRequest

It is impossible to mock DistanceMatrixApiRequiest appropriately to serve Issue #10 due to heavy use of final methods. We must provide a thin wrapper class around it that is more easily mocked.

hxtk / road-trip-router Goto Github PK

road-trip-router's People

Contributors

Stargazers

Watchers

road-trip-router's Issues

Recommend Projects

Recommend Topics

Recommend Org