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 
) . 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;
}
