GraphHopper.com | Forum | GitHub | Maps | Blog

Solution not working for more than 40 shipments


#1

Hi Guys,

I am working on a solution to generate routes for given set of employees. For given list of employee with lat-lng, my solution generates routes with vehicle capacity.

I am new to VRP and found jsprit to be very useful. So I developed the solution as per my understanding and it’s working fine to some extent (I think :slight_smile:) . It generates route but not fully optimized.

It takes around 8 to 10 seconds if number of employees is till 30 but if I give large data set like 300 to 400 employees, it takes 7 to 8 minutes and sometimes it doesn’t even respond and it doesn’t give proper route also.

I am sharing my code in this thread. Can you help me if i am wrong. I asked few of my friends, they recommended me to switch to OctaPlanner. But before making any decision I just want to see if problem is scale can be solved somehow. May be we might have used wrong approch for the solution. Your insights can be a great help to me.

I am sharing the code written below. It has a method called generateRoutes which takes start location, employeeList, vehicleCapacity and fleetSize. It returns list of routes generated for employees. It internally uses buildVehicle method which returns Vehicle object as per requirement.

public ArrayList < ArrayList < String >> generateRoutes(double startLat, double startLng, Integer maxSeats, Integer maxFleetSize,
HashMap < String, HashMap < String, Object >> employees) {

//Build location object for start location.
Location pickupLocation = getLocationObj(Coordinate.newInstance(startLat, startLng));

// Build vehicle routing problem builder.
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

//Add Max Fleet size if given else keep fleet size infinite.
if (maxFleetSize == null) {
    vrpBuilder.setFleetSize(FleetSize.INFINITE);

    //Add single vehicle.
    Vehicle vehicle = buildVehicle("vehicle_0", startLat, startLng, maxSeats);
    vrpBuilder.addVehicle(vehicle);
}
else {
    vrpBuilder.setFleetSize(FleetSize.FINITE);
    //Add vehicles for given number of fleet size.
    for (int i = 0; i < maxFleetSize; i++) {
        Vehicle vehicle = buildVehicle("vehicle_" + i, startLat, startLng, maxSeats);
        vrpBuilder.addVehicle(vehicle);
    }
}

// Create Shipments for each employee and to problem object.
Iterator empIterator = employees.entrySet().iterator();
while (empIterator.hasNext()) {

    // Read current iterating employee info
    Map.Entry employeeMapObj = (Map.Entry) empIterator.next();
    String employeeCode = employeeMapObj.getKey().toString();
    HashMap employeeData = (HashMap) employeeMapObj.getValue();
    double latitude = Double.parseDouble(employeeData.get("latitude").toString());
    double longitude = Double.parseDouble(employeeData.get("longitude").toString());

    System.out.println(employeeCode + ":" + latitude + ", " + longitude);

    // Build shipment.
    Shipment shp = Shipment.Builder.newInstance(employeeCode).addSizeDimension(MAX_PASSENGERES, 1)
        .setPickupLocation(pickupLocation)
        .setDeliveryLocation(getLocationObj(Coordinate.newInstance(latitude, longitude))).build();

    // Add shipment to problem.
    vrpBuilder.addJob(shp);

}

// build the problem
VehicleRoutingProblem problem = vrpBuilder.build();


// Add any additional constraint if required using state manager.
StateManager stateManager = new StateManager(problem);
ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
// constraintManager.addConstraint(wheelchair_bus_passenger_pickup_constraint);

// Build algo for given problem.
VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem).buildAlgorithm();// .setStateAndConstraintManager(stateManager,constraintManager).buildAlgorithm();
// algorithm.setPrematureAlgorithmTermination(new
// IterationWithoutImprovementTermination(100));

// Build solution for given algo.
Collection < VehicleRoutingProblemSolution > solutionList = algorithm.searchSolutions();
VehicleRoutingProblemSolution solution = Solutions.bestOf(solutionList);

SolutionPrinter.print(problem, solution, SolutionPrinter.Print.VERBOSE);

// Read Routes
ArrayList < ArrayList < String >> result = new ArrayList<ArrayList<String>>();
List < VehicleRoute > rawRoutes = new ArrayList<VehicleRoute>(solution.getRoutes());
Collections.sort(rawRoutes, new com.graphhopper.jsprit.core.util.VehicleIndexComparator());
for (VehicleRoute route : rawRoutes) {

    System.out.println("--------------------------------------------");

    ArrayList < String > routeItems = new ArrayList<String>();

    // Iterate and print activities
    TourActivity prevAct = route.getStart();
    for (TourActivity act : route.getActivities()) {

        if (act.getName().equals("deliverShipment")) {
            String employeeCode = ((TourActivity.JobActivity) act).getJob().getId();
            System.out.println(act.getName() + " -> " + employeeCode);
            routeItems.add(employeeCode);
        }
    }

    if (routeItems.size() > 0) {
        result.add(routeItems);
    }
}

return result;

}

private Vehicle buildVehicle(String vehicleInstanceId, double startLat, double startLng, int maxSeats) {

// Build Start Location Object
Location startLocation = getLocationObj(Coordinate.newInstance(startLat, startLng));

// Build vehicle type
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicle")
    .addCapacityDimension(MAX_PASSENGERES, maxSeats);
VehicleType vehicleType = vehicleTypeBuilder.build();

// Build Vehicle Builder
Builder vehicleBuilder = VehicleImpl.Builder.newInstance(vehicleInstanceId);
vehicleBuilder.setStartLocation(startLocation);
vehicleBuilder.setReturnToDepot(false);
vehicleBuilder.setType(vehicleType);

// Build vehicle
VehicleImpl vehicle = vehicleBuilder.build();
return vehicle;

}


#2

Thanks for your post. Would you mind to provide us with the 40 shipment example. It would be great, if it were in jsprit’s xml format so that we can just read it. I do not have any experience with OptaPlanner, but I assume it can solve these kind of problems also, and I would not exclude that it can solve certain types of problems better than jsprit does. I just dont know. Therefore, I am very much interested in how one can solve it with OptaPlanner. Thus, if you try to model and solve this in OptaPlanner, it would be great you share the results :D.

BTW: It is always hard to judge the quality of a solver in general. What I did - when it comes to pickup and delivery - is that I solved the benchmarking problems from LiLim and it showed that the solutions are quite reasonable, i.e. not that far away from the best known results. Therefore, it would be great you illustrated why jsprit does not solve your problems reasonably. In this way we can try to make it better.


#3

Hi Stefan,
Unfortunately I couldn’t prepare the json file since I couldn’t clearly understood the structure of it.
But I have attached json array of locations in which, each array element contains employee_code, address_lat and address_lng. I have also attached solution generated by my solution which is 2d array containing routes generated.

employee_roaster.json (20.0 KB)

solution.json (23.7 KB)

These locations are of mumbai city.

Start location for all is given below:
lat: 19.119677
lng: 72.905081

There are total 165 employees in this json list.
I tried on myside, it took around 7 minutes to generate solution and cpu utilization went 85%.
I used 50 threads to algorithm(using Jsprit.Parameter.THREADS property).
My solution was hosted on EC2(m4.xlarge) with following hardware configuration:
Ram: 8GB
vCpu: 2
Clock Speed: Up to 3.0 GHZ
Processor: Intel Xeon family

I am okay with cpu utilization, and if needed, I can upgrade hardware as well. But only problem is time. My client can not wait for 7 minutes. I need to give response within 10 to 20 seconds max.


#4

hi ravipatel

We are also facing a similar problem you described above. Jsprit is taking more than 8 minutes for 400 shipments with only 200 iterations for generating routes. Please share if you have found any solution. I will be really grateful.
Thanks in advance.