A Bike Sharing System (BSS) is a set of stations with a specific quantity of bicycles parked in them.
The people take and park bikes continuously in different stations and, some times, that produces empty/full stations.
This is a problem because it is necessary to have available space to park a new bicycles and obviously are necessary to have available bicycles to be able to take them.
To solve this problem it necesary perform a reallocation of the bikes.Thus, there are multiple stations with a common comodity (bicycles) and some trucks to perform the reallocation,
each one with an specific load. The objective is obtain the best route/s for each truck to perform the reallocation, taking in account that the demand in each station could be positive or negative (a pickup or a delivery)
and its size could be different. A practical example:
10 stations. Demand of each one: (-1,0,0,-1,+1,+2,-2,-2,0,0)
2 trucks. (Max size 3 bicycles)
Note: As the comodity is the same I can take any bike in the route and drop in any other station. Only I take bikes from depot if (delivers size > pickupSize).
I want to calculate the best route/s for perform the reallocation. I currently use HardConstraint to implement the maximum capacity of the truck and also having enough bikes to perform a delivery.
As JSPRIT in Deliveries and Pickups load size at the depot, we have to change the size and use a StateUpdater to track the size in each route.
@stefan Any help, other approach suggestions or anything with this is welcomed.
Thanks so much for your support and thank you so much to @jie31best!!!
Here the code until now:
public class BikeSharingProblemExample {
private static final Logger logger = LoggerFactory.getLogger(VehicleRoutingAlgorithm.class);
static final int BIKES_DIMENSION_INDEX = 0;
static final long SEED = 200; // For reproducible examples
static Random r = new Random(SEED);
private static Set<Coordinate> uniqueCoordinates = new HashSet<>();
public static void main(String[] args) {
VehicleType type = VehicleTypeImpl.Builder.newInstance("type")
.addCapacityDimension(BIKES_DIMENSION_INDEX, 2)
.setCostPerDistance(1.0)
.setCostPerServiceTime(1.0)
.build();
final VehicleImpl vehicle = VehicleImpl.Builder.newInstance("vehicle")
.setStartLocation(loc(Coordinate.newInstance(0, 0)))
.setReturnToDepot(true)
.setType(type).build();
final VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2")
.setStartLocation(loc(Coordinate.newInstance(0, 0)))
.setReturnToDepot(true)
.setType(type).build();
Pair<List<Pickup>, Integer> listOfPickups = createListOfPickups(14);
Pair<List<Delivery>, Integer> listOfDeliveries = createListOfDeliveries(14);
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance()
.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
.addAllJobs(listOfPickups.getKey())
.addAllJobs(listOfDeliveries.getKey())
.addVehicle(vehicle)
.addVehicle(vehicle2);
VehicleRoutingTransportCostsMatrix costMatrix = createMatrix(vrpBuilder);
vrpBuilder.setRoutingCost(costMatrix);
VehicleRoutingProblem vrp = vrpBuilder.build();
final StateManager stateManager = new StateManager(vrp);
StateId bikes = stateManager.createStateId("bikes");
int bikesFromDepot = 0;
int dif = listOfPickups.getValue() - listOfDeliveries.getValue();
if (dif < 0) {
//This difference must be distributed for each vehicle
bikesFromDepot = Math.abs(dif);
}
System.out.println("BIKES FROM DEPOT:" + bikesFromDepot);
BikesStateUpdater bikesStateUpdater = new BikesStateUpdater(stateManager, bikes, bikesFromDepot);
stateManager.addStateUpdater(bikesStateUpdater);
stateManager.updateLoadStates();
ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
constraintManager.addLoadConstraint();
constraintManager.addConstraint(new EnoughPickupsForDeliveries(stateManager), ConstraintManager.Priority.CRITICAL);
VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp)
.addCoreStateAndConstraintStuff(true)
.setStateAndConstraintManager(stateManager, constraintManager)
.buildAlgorithm();
vra.addListener(new IterationStartsListener() {
@Override
public void informIterationStarts(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {
System.out.println("iteration = " + i);
}
});
vra.addListener(new InsertionStartsListener() {
@Override
public void informInsertionStarts(Collection<VehicleRoute> vehicleRoutes, Collection<Job> unassignedJobs) {
for (VehicleRoute route : vehicleRoutes) {
int bikes = 0;
Collection<Job> jobs = new HashSet<Job>();
for (TourActivity activity : route.getActivities()) {
if (activity instanceof DeliverService) {
int bikesToDeliver = (int) ((DeliverService) activity).getJob().getUserData();
if (bikes < bikesToDeliver) {
jobs.add(((DeliverService) activity).getJob());
} else
bikes -= bikesToDeliver;
} else if (activity.getName().equals("pickup")) {
int bikesToPickup = (int) ((PickupService) activity).getJob().getUserData();
int maxCapacity = route.getVehicle().getType().getCapacityDimensions().get(BIKES_DIMENSION_INDEX);
if ((bikes + bikesToPickup) <= maxCapacity) {
bikes += bikesToPickup;
} else {
jobs.add(((PickupService) activity).getJob());
}
}
}
for (Job job : jobs) {
if (route.getTourActivities().servesJob(job)) {
if (route.getTourActivities().removeJob(job)) {
unassignedJobs.add(job);
}
}
}
stateManager.reCalculateStates(route);
}
}
});
vra.setMaxIterations(50000);
Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
VehicleRoutingProblemSolution valid = null;
for (VehicleRoutingProblemSolution solution : solutions) {
List<VehicleRoute> vehicleRoutes = (List<VehicleRoute>) solution.getRoutes();
boolean result = isValidRoute(vehicleRoutes.get(0).getTourActivities().getActivities(), 0, vehicleRoutes.get(0).
getVehicle().getType().getCapacityDimensions().get(BIKES_DIMENSION_INDEX));
System.out.print("RESULT:" + result);
if (result)
valid = solution;
}
if (valid != null) {
SolutionPrinter.print(vrp, valid, SolutionPrinter.Print.VERBOSE);
new GraphStreamViewer(vrp, valid).labelWith(GraphStreamViewer.Label.ID).setRenderShipments(true).display();
}
}
private static boolean isValidSolution(Collection<VehicleRoutingProblemSolution> collection) {
for (VehicleRoutingProblemSolution solution : collection) {
List<VehicleRoute> vehicleRoutes = (List<VehicleRoute>) solution.getRoutes();
boolean result = isValidRoute(vehicleRoutes.get(0).getTourActivities().getActivities(), 0, vehicleRoutes.get(0).
getVehicle().getType().getCapacityDimensions().get(BIKES_DIMENSION_INDEX));
System.out.print("RESULT:" + result);
if (!result)
return false;
}
return true;
}
private static boolean isValidRoute(List<TourActivity> tourActivities, int initialBikes, int capacity) {
int b = initialBikes;
for (TourActivity t : tourActivities) {
if (t instanceof DeliverService) {
b -= (int) ((DeliverService) t).getJob().getUserData();
} else if (t instanceof PickupService) {
b += (int) ((PickupService) t).getJob().getUserData();
}
if (b < 0 || b > capacity) {
return false;
}
}
return true;
}
private static class BikesStateUpdater implements StateUpdater, ActivityVisitor {
private final StateManager stateManager;
private final StateId bikesInVehicle;
private VehicleRoute route;
private Integer bikes;
public BikesStateUpdater(StateManager stateManager, StateId bikesInVehicle, Integer initialBikes) {
this.stateManager = stateManager;
this.bikesInVehicle = bikesInVehicle;
}
@Override
public void begin(VehicleRoute route) {
this.route = route;
bikes = 0;
stateManager.putRouteState(route, bikesInVehicle, bikes);
}
@Override
public void visit(TourActivity activity) {
if (activity.getName().equals("delivery")) {
bikes -= (int) ((DeliverService) activity).getJob().getUserData();
} else if (activity.getName().equals("pickup")) {
bikes += (int) ((PickupService) activity).getJob().getUserData();
}
stateManager.putActivityState(activity, bikesInVehicle, bikes);
}
@Override
public void finish() {
}
}
static class EnoughPickupsForDeliveries implements HardActivityConstraint {
private StateManager stateManager;
EnoughPickupsForDeliveries(StateManager stateManager) {
this.stateManager = stateManager;
}
private Integer getLoadAtPreviousAct(TourActivity prevAct) {
Integer prevLoad = stateManager.getActivityState(prevAct, stateManager.createStateId("bikes"), Integer.class); //1.3.2-SNAPSHOT & upcoming release v1.4
if (prevLoad != null) {
return prevLoad;
} else {
return 0;
}
}
private Integer getMaxLoadVehicle(JobInsertionContext jobInsertionContext) {
return jobInsertionContext.getNewVehicle().getType().getCapacityDimensions().get(BIKES_DIMENSION_INDEX);
}
@Override
public ConstraintsStatus fulfilled(JobInsertionContext jobInsertionContext, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double departureTimeAtPrevAct) {
int loadAtPrevAct = getLoadAtPreviousAct(prevAct);
if (loadAtPrevAct < 0 || loadAtPrevAct > getMaxLoadVehicle(jobInsertionContext)) {
System.out.println("this should not happen");
return ConstraintsStatus.NOT_FULFILLED_BREAK;
} else {
if (newAct.getName().equals("delivery") && nextAct.getName().equals("delivery")) {
int currentSize = (int) ((DeliverService) newAct).getJob().getUserData();
int futureSize = (int) ((DeliverService) nextAct).getJob().getUserData();
// Enough load for delivery*2
if (loadAtPrevAct >= (currentSize + futureSize)) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
} else if (newAct.getName().equals("pickup") && nextAct.getName().equals("pickup")) {
int currentSize = (int) ((PickupService) newAct).getJob().getUserData();
int futureSize = (int) ((PickupService) nextAct).getJob().getUserData();
int maxLoad = getMaxLoadVehicle(jobInsertionContext);
int availableSpace = maxLoad - loadAtPrevAct;
// Enough space for pickup*2
if ((loadAtPrevAct >= currentSize) && (currentSize + futureSize) <= loadAtPrevAct) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
} else if (newAct.getName().equals("delivery") && nextAct.getName().equals("pickup")) {
int currentSize = (int) ((DeliverService) newAct).getJob().getUserData();
int futureSize = (int) ((PickupService) nextAct).getJob().getUserData();
int maxLoad = getMaxLoadVehicle(jobInsertionContext);
int availableSpace = maxLoad - loadAtPrevAct;
// Enough load for delivery and enough space for pickup
if ((loadAtPrevAct >= currentSize) && ((loadAtPrevAct - currentSize) + futureSize) <= availableSpace) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
} else if (newAct.getName().equals("pickup") && nextAct.getName().equals("delivery")) {
int currentSize = (int) ((PickupService) newAct).getJob().getUserData();
int futureSize = (int) ((DeliverService) nextAct).getJob().getUserData();
int maxLoad = getMaxLoadVehicle(jobInsertionContext);
int availableSpace = maxLoad - loadAtPrevAct;
// Enough space for pickup and enough space for delivery
if ((currentSize <= availableSpace) && ((loadAtPrevAct + currentSize) >= futureSize)) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
} else if (newAct.getName().equals("delivery") && nextAct.getName().equals("end")) {
int currentSize = (int) ((DeliverService) newAct).getJob().getUserData();
// Enough load for delivery
if (loadAtPrevAct >= (currentSize)) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
} else if (newAct.getName().equals("pickup") && nextAct.getName().equals("end")) {
int currentSize = (int) ((PickupService) newAct).getJob().getUserData();
int maxLoad = getMaxLoadVehicle(jobInsertionContext);
int availableSpace = maxLoad - loadAtPrevAct;
// Enough space for pickup
if (currentSize <= availableSpace) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
} else {
return ConstraintsStatus.FULFILLED;
}
}
}
}
private static Pair<List<Delivery>, Integer> createListOfDeliveries(int numberOfDeliveries) {
List<Delivery> list = new ArrayList<>();
int totalNumberOfBikesToDeliver = 0;
for (int i = 0; i < numberOfDeliveries; i++) {
// Now only 1 bike per job
Integer numberOfBikesToDeliver = getRandomIntBetween(1, 2);
Delivery bike = Delivery.Builder.newInstance("bikes_" + i + "_delivery" + " " + numberOfBikesToDeliver)
.addSizeDimension(BIKES_DIMENSION_INDEX, 0)
.setUserData(numberOfBikesToDeliver)
.setServiceTime(1)
.setLocation(loc(getUniqueRandomCoordinate()))
.build();
list.add(bike);
totalNumberOfBikesToDeliver += numberOfBikesToDeliver;
}
return new Pair<>(list, totalNumberOfBikesToDeliver);
}
private static Pair<List<Pickup>, Integer> createListOfPickups(int numberOfPickups) {
List<Pickup> list = new ArrayList<>();
int totalNumberBikesToPickup = 0;
for (int i = 0; i < numberOfPickups; i++) {
int numberOfBikesToPickup = getRandomIntBetween(1, 2);
// Now only 1 bike per job
Pickup bike = Pickup.Builder.newInstance("bikes_" + i + "_pickup" + " " + numberOfBikesToPickup)
.addSizeDimension(BIKES_DIMENSION_INDEX, 0)
.setUserData(numberOfBikesToPickup)
.setServiceTime(1)
.setLocation(loc(getUniqueRandomCoordinate())).build();
list.add(bike);
totalNumberBikesToPickup += numberOfBikesToPickup;
}
return new Pair<>(list, totalNumberBikesToPickup);
}
private static int getRandomIntBetween(int low, int high) {
return r.nextInt(high - low) + low;
}
private static Coordinate getUniqueRandomCoordinate() {
Coordinate coordinate = Coordinate.newInstance(getRandomIntBetween(1, 100), getRandomIntBetween(1, 100));
while (true) {
if (!uniqueCoordinates.contains(coordinate)) {
uniqueCoordinates.add(coordinate);
return coordinate;
}
coordinate = Coordinate.newInstance(getRandomIntBetween(1, 100), getRandomIntBetween(1, 100));
}
}
private static VehicleRoutingTransportCostsMatrix createMatrix(VehicleRoutingProblem.Builder vrpBuilder) {
VehicleRoutingTransportCostsMatrix.Builder matrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
for (String from : vrpBuilder.getLocationMap().keySet()) {
for (String to : vrpBuilder.getLocationMap().keySet()) {
Coordinate fromCoord = vrpBuilder.getLocationMap().get(from);
Coordinate toCoord = vrpBuilder.getLocationMap().get(to);
double distance = EuclideanDistanceCalculator.calculateDistance(fromCoord, toCoord);
matrixBuilder.addTransportDistance(from, to, distance);
matrixBuilder.addTransportTime(from, to, (distance / 2.));
}
}
return matrixBuilder.build();
}
private static Location loc(Coordinate coordinate) {
return Location.Builder.newInstance().setCoordinate(coordinate).build();
}}