Newbie Routing Question

[Scott Onyx Harmon]

Hello All!

I'm fairly new to the VRP, but I am trying to use this library to suggest optimizations and construct routes.  I have a list of stops with weights and lat,lon's.  I have a weight constraint on trucks.  I fed this into the vsprit engine, using a custom VRPTransportCosts class (I took the Euclidian distance one and modified it to estimate driving distance between a pair of lat, lon coordinates).  I have one depot.

The engine finds a solution, but the solution is always pretty obviously sub-optimal (just by looking at the map, I can see stops that should be swapped in routes).  I also tried to get the "costs" of the "best" solution that the engine gave and the costs seem to be much lower than the total drive distance (which makes me think I've done something wrong here).

Any direction would be appreciated.

Thanks!

[Stefan Schroeder]

Hi,

Can you post a very simple example of how you specified your problem and where you think that jsprit creates bad solutions? How do you modified Euclidean distance? Have you set cost params for your vehicles (per distance and/or time unit)? If you have lon/lat you might be better off using great circle distances or to provide you own times/distances by using a cost matrix.

Best,
Stefan

Am 23/10/15 um 17:55 schrieb Scott Onyx Harmon:

--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

[Scott Harmon]

Stefan,

Thanks, I'm sure it's just something I'm doing wrong.  Here is my modification to the Euclidean distance:

private double calculateDistance(Coordinate from, Coordinate to) {

return estimateDrivingMileage(from.getX(), from.getY(), to.getX(), to.getY()) * detourFactor;

}

private final static double estimateDrivingMileage(double x1, double y1, double x2, double y2) {

   return computeLatitudeDistance(x1, y1, x2) + computeLongitudeDistance(x1, y1, y2);

}

private final static double computeLatitudeDistance(double x1, double y1, double x2) {

final double earthRadius = 3958.75; // in miles

double dLat = Math.toRadians(x2 - x1);

   double sindLat = Math.sin(dLat / 2);

   double a = Math.pow(sindLat, 2) 

           * Math.cos(Math.toRadians(x1)) * Math.cos(Math.toRadians(x2));

   double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

   double dist = earthRadius * c;

   

   return dist;

}

private final static double computeLongitudeDistance(double x1, double y1, double y2) {

final double earthRadius = 3958.75; // in miles

   double dLng = Math.toRadians(y2 - y1);

   double sindLng = Math.sin(dLng / 2);

   double a = Math.pow(sindLng, 2)

           * Math.cos(Math.toRadians(x1));

   double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

   double dist = earthRadius * c;

   

   return dist;

}

I'm adding the vehicle type using:

final int WEIGHT_INDEX = 0;

VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(WEIGHT_INDEX, 11000);

VehicleType vehicleType = vehicleTypeBuilder.build();

Which seems to be working as each route never contains more that 11000 pounds.

The rest is basically the same as the SimpleExample.

Thanks!

--
Scott

phone: 1-800-669-9867 ext: 145   fax: 1-800-393-6699
------------------------------------------------------------------------------------
Making showers & lavatories in Kansas since 1985, and guaranteeing them FOREVER! 
------------------------------------------------------------------------------------
http://www.onyxcollection.com

--
You received this message because you are subscribed to a topic in the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/jsprit-mailing-list/KipEbXbSZXQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to jsprit-mailing-...@googlegroups.com.

[Scott Onyx Harmon]

Here is an example of the strange behavior:

[Stefan Schroeder]

Hi Scott,

Can you use this instead of your own implementation? It is also the Haversine formula. Have you tested whether the distance/time between two points is the expected distance? Which algorithm do you use? Try Jsprit.createAlgorithm(vrp).

Best,
Stefan

Am 23/10/15 um 21:26 schrieb Scott Onyx Harmon:

--

[Scott Onyx Harmon]

Thanks Stefan,

I changed to the GreatCircleCosts and got this:

Here is my code:

final int WEIGHT_INDEX = 0;

VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(WEIGHT_INDEX, 11000);

VehicleType vehicleType = vehicleTypeBuilder.build();

/*

* get a vehicle-builder and build a vehicle located at (10,10) with type "vehicleType"

*/

VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle");

final GeoPoint onyx = MapUtilities.getOnyxGeoPointInstance();

vehicleBuilder.setStartLocation(Location.newInstance(onyx.getLatitude(), onyx.getLongitude()));

vehicleBuilder.setType(vehicleType);

List<VehicleImpl> vehicles = new ArrayList<VehicleImpl>(vehicleNumber);

VehicleImpl vehicle = vehicleBuilder.build();

vehicles.add(vehicle);

Map<String, TruckStop> truckStopMap = new HashMap<String, TruckStop>();

int i = 1;

List<Service> services = new ArrayList<Service>();

for(GateStops gateStop : currentStops) {

for (TruckStop stop : gateStop.getStops()) {

truckStopMap.put(""+i, stop);

Service service = Service.Builder.newInstance(""+i)

.addSizeDimension(WEIGHT_INDEX,(int)stop.getPounds())

.setLocation(Location.newInstance(stop.getAddress().getLocation().getLatitude(), stop.getAddress().getLocation().getLongitude()))

.build();

services.add(service);

i++;

}

}

/*

* again define a builder to build the VehicleRoutingProblem

*/

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

vrpBuilder.addAllVehicles(vehicles);

vrpBuilder.addAllJobs(services);

VehicleRoutingTransportCosts transportCosts =  new GreatCircleCosts(); // VRPTransportCosts();

vrpBuilder.setRoutingCost(transportCosts);

/*

* build the problem

* by default, the problem is specified such that FleetSize is INFINITE, i.e. an infinite number of 

* the defined vehicles can be used to solve the problem

* by default, transport costs are computed as Euclidean distances

*/

VehicleRoutingProblem problem = vrpBuilder.build();

problem.getTransportCosts();

/*

* get the algorithm out-of-the-box. 

*/

Builder builder = Jsprit.Builder.newInstance(problem);

VehicleRoutingAlgorithm algorithm = builder.buildAlgorithm();

/*

* and search a solution which returns a collection of solutions (here only one solution is constructed)

*/

Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

/*

* use the static helper-method in the utility class Solutions to get the best solution (in terms of least costs)

*/

VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

On Saturday, October 24, 2015 at 3:16:37 AM UTC-5, Stefan Schröder wrote:

Hi Scott,

Can you use this instead of your own implementation? It is also the Haversine formula. Have you tested whether the distance/time between two points is the expected distance? Which algorithm do you use? Try Jsprit.createAlgorithm(vrp).

Best,
Stefan

Am 23/10/15 um 21:26 schrieb Scott Onyx Harmon:

Here is an example of the strange behavior:

On Friday, October 23, 2015 at 10:55:18 AM UTC-5, Scott Onyx Harmon wrote:

Hello All!

I'm fairly new to the VRP, but I am trying to use this library to suggest optimizations and construct routes.  I have a list of stops with weights and lat,lon's.  I have a weight constraint on trucks.  I fed this into the vsprit engine, using a custom VRPTransportCosts class (I took the Euclidian distance one and modified it to estimate driving distance between a pair of lat, lon coordinates).  I have one depot.

The engine finds a solution, but the solution is always pretty obviously sub-optimal (just by looking at the map, I can see stops that should be swapped in routes).  I also tried to get the "costs" of the "best" solution that the engine gave and the costs seem to be much lower than the total drive distance (which makes me think I've done something wrong here).

Any direction would be appreciated.

Thanks!

--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.

To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-list+unsub...@googlegroups.com.

[Stefan Schroeder]

Ok. It looks better now. But since you entitled the figure with "bad" also, I assume you are still not satisfied. What do you think is still bad?

Am 24/10/15 um 18:04 schrieb Scott Onyx Harmon:

To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.

[Scott Harmon]

Stefan,

I had some more time over the weekend to look into it, and it does appear that it is giving good results according to my mileage metric.  It just seemed counter-intuitive when I saw the routes laid out on a map.  Without actual driving distance and time, I'm afraid that I'm not going to be able to do well with the optimization.  Have you seen any good methods for estimating these things, or maybe someone using open street map data with this?

Thanks,

--
Scott

phone: 1-800-669-9867 ext: 145   fax: 1-800-393-6699
------------------------------------------------------------------------------------
Making showers & lavatories in Kansas since 1985, and guaranteeing them FOREVER! 
------------------------------------------------------------------------------------
http://www.onyxcollection.com

To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.

To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/jsprit-mailing-list/KipEbXbSZXQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to jsprit-mailing-...@googlegroups.com.

[He Huang]

Hi Scott,

For your purpose of estimating the actual driving distance and time between locations, if your number of calls is small each day, you can use Google Maps Directions API (limit is 2500 calls a day, assuming you wanna do it for free) or Google Maps Distance Matrix API (limit is here); If the number exceeds the limit, you can try GraphHopper, which is based on OSM as you asked.

Here is a post discussing "Using actual distance/time in distance matrix for 1000 deliveries" in this mailing list, which might be helpful to you.

Best regards,

He

[Scott Onyx Harmon]

Thank you!  It's looking better now using the actual distance and time.  How do I get the total time and distance for each VehicleRoute in the Solution?

Thanks,

[Stefan Schroeder]

One way is to do it like this:

FastVehicleRoutingTransportCostMatrix matrix = ....
SolutionAnalyser sa = new SolutionAnalyser(coreProblem.getVrp(), solution, new TransportDistance() {
            @Override
            public double getDistance(Location from, Location to) {
                return matrix.getDistance(from,to);
            }
        });
        System.out.println("distance: " + sa.getDistance());
        System.out.println("time: " + sa.getTransportTime());

Am 30/10/15 um 16:40 schrieb Scott Onyx Harmon:

--