Hi! I’m trying to solve a simple TSP with Jsprit. I only have 1 vehicle and a total of about 200 pickups.
This is my vehicle routing algorithm code:
val vrpBuilder = VehicleRoutingProblem.Builder.newInstance()
vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
vrpBuilder.setRoutingCost(costMatrix)
vrpBuilder.addAllVehicles(vehicles)
vrpBuilder.addAllJobs(pickups)
val vrp = vrpBuilder.build()
val builder = Jsprit.Builder.newInstance(vrp)
val stateManager = StateManager(vrp)
val constraintManager = ConstraintManager(vrp, stateManager)
constraintManager.addConstraint(object : HardActivityConstraint {
override fun fulfilled(
context: JobInsertionContext?,
prevActivity: TourActivity?,
newActivity: TourActivity?,
nextActivity: TourActivity?,
previousActivityDepartureTime: Double
): HardActivityConstraint.ConstraintsStatus {
if (prevActivity !== null && newActivity !== null && nextActivity !== null && context !== null) {
if (prevActivity.location.id === nextActivity.location.id) {
return HardActivityConstraint.ConstraintsStatus.FULFILLED
}
val distanceBetweenPrevAndNew = costMatrix.getDistance(
prevActivity.location,
newActivity.location,
prevActivity.endTime,
context.newVehicle
)
val distanceBetweenPrevAndNext = costMatrix.getDistance(
prevActivity.location,
nextActivity.location,
prevActivity.endTime,
context.newVehicle
)
if (distanceBetweenPrevAndNext > distanceBetweenPrevAndNew) {
return HardActivityConstraint.ConstraintsStatus.FULFILLED
} else {
return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED
}
}
return HardActivityConstraint.ConstraintsStatus.FULFILLED
}
}, ConstraintManager.Priority.CRITICAL)
builder.setProperty(Jsprit.Parameter.FAST_REGRET, true.toString())
builder.setProperty(Jsprit.Parameter.CONSTRUCTION, Construction.REGRET_INSERTION.toString())
builder.setProperty(Jsprit.Parameter.THREADS, threads.toString())
builder.setStateAndConstraintManager(stateManager, constraintManager)
val vra = builder.buildAlgorithm()
As routing cost i’m using a distance only FastVehicleRoutingTransportCostsMatrix built with the Graphhopper Matrix Api.
The vehicle should avoid passing in front of an uncollected pickup, I tried to set up an hard activity constraint that checks if the new inserted activity is further away than the next one. If it’s not further away, the constraint is not fulfilled. However the constraint does not work quite well.
Here’s an example of an optimized route with the constraint:
The correct order for my case should be: 46 43 45 44 , however Jsprit orders them in that way because after 44 the vehicle has to do an uturn and run through the street again to reach 47,48,49…
I’m not sure if setting up a constraint is the right way to solve this, do you have any advices?
Thanks