# HardConstraints Bike Sharing Problem

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")
.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)

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

ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);

VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp)
.setStateAndConstraintManager(stateManager, constraintManager)
.buildAlgorithm();

@Override
public void informIterationStarts(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {
System.out.println("iteration = " + i);
}
});

@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) {
} 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 {
}

}
}
for (Job job : jobs) {
if (route.getTourActivities().servesJob(job)) {
if (route.getTourActivities().removeJob(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;
}

Integer prevLoad = stateManager.getActivityState(prevAct, stateManager.createStateId("bikes"), Integer.class); //1.3.2-SNAPSHOT & upcoming release v1.4
} else {
return 0;
}
}

return jobInsertionContext.getNewVehicle().getType().getCapacityDimensions().get(BIKES_DIMENSION_INDEX);
}

@Override
public ConstraintsStatus fulfilled(JobInsertionContext jobInsertionContext, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double departureTimeAtPrevAct) {

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();

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();

// Enough space for pickup*2
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();

// 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();

// 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();

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();

// 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)
.setUserData(numberOfBikesToDeliver)
.setServiceTime(1)
.setLocation(loc(getUniqueRandomCoordinate()))
.build();

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)
.setUserData(numberOfBikesToPickup)
.setServiceTime(1)
.setLocation(loc(getUniqueRandomCoordinate())).build();

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)) {
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);