Hello!
I’m trying to solve many-vehicles-many-parcels problem, and have time restrictions from my business.
Jsprit always builds decisions with only one delivery car (another are ignored), except the case of low capacity. Low capacity is bad decision.
I think i need to have possibility to set a number of cars in decision, or possibility to optimize by time of delivery, not by cost.
I have readed mailing lists and docs about constraints, but cannot find an answer. There’s some recommendations about big waiting costs, and zero fixed costs, but this is don’t work. If you interested I can give some testing codes.
How I can solve my problem?
Thanks!
Best regards, Alex.
What do you mean by time restrictions? Do you mean a parcel has to be delivered within a delivery window? If so there should not be any issue with that. Jsprit handles TimeWindow constraint properly.
Is your objective is to minimize total number of hours taken by all cars to deliver?
Thanks for the reply!
Yes’ I’m trying to minimize total delivery time for all cars. In this case there must be maximum cars used in the most number of cases.
Unfortunately, I cannot upload archives here.
using this link you can find maven project on Kotlin language.
There is json file with some context (cars, parcels, and parcels already in cars) that parsed and loaded to Problem that solved in the DeliverySolver class.
This code is called from external system (Anylogic in our case)
You can find test with the fun solveRealProblemWithDelivery() that waiting for decision for more than one car.
I’m trying to configure model in the way of search fastest decision. Also I don’t sure How i can set the car speed for model, but this not so important.
Some musings of mine pending something more definitive, maybe 30 mins of playing to see if it has legs as a possible solution. If you’re only interested in total running time.
Set fixed cost to a negative number. Suspend all restrictions (iirc, there’s two restrictions on it being a positive value), it should still function and with the desired effect of deploying all vehicles (your fleet needs to be FINITE)
.setCostPerDistance(0.0) and only add cost penalties for waiting time and driving time.
My suggestion was to create a negative fixed cost, which will cause the algorithm to deploy all vehicles. Jsprit will shout if you do this but on the quick testing I did re: the link I provided, you can shut up that shouting pretty quickly and it appears to carry on as normal (note, I cannot guarantee that this negative cost does not have some implications somewhere).
For you to have exactly zero cost, that would mean that your travel costs balanced perfectly against the sum of negative fixed costs; I cannot see this being the case. I don’t have time right now to go digging but it’s also possible that there’s a restriction somewhere that a displayed cost is >= 0 by default.
What I would be more interested in is whether the routes looked at all sensible.
I was tried to make custom JobInsertionStrategy but I have failed.
I was implemented custom JSprit class with my custom JobInsertionStrategy, but when I have try to implement new routes and assign them to vehicles and choose the best program fails in runtime with
java.lang.IllegalStateException: cannot add vehicle twice 29
at com.graphhopper.jsprit.core.problem.vehicle.VehicleFleetManagerImpl$TypeContainer.add(VehicleFleetManagerImpl.java:48)
at com.graphhopper.jsprit.core.problem.vehicle.VehicleFleetManagerImpl.addVehicle(VehicleFleetManagerImpl.java:129)
My implementation is looks like
override fun insertUnassignedJobs(vehicleRoutes: MutableCollection<VehicleRoute>, unassignedJobs: Collection<Job>): Collection<Job> {
val badJobs = ArrayList<Job>(unassignedJobs.size)
val unassignedJobList = ArrayList(unassignedJobs)
Collections.shuffle(unassignedJobList, random)
val carNumber = this.vrp.vehicles.size
sometimesSortPriorities(unassignedJobList)
var routeCounter = vehicleRoutes.size
for (i in 1..(carNumber - routeCounter)) {
vehicleRoutes.add(VehicleRoute.Builder.newInstance(getUnassignedVehicle(vehicleRoutes)).build())
}
for (j in unassignedJobList) {
var bestInsertionData = InsertionData.createEmptyInsertionData()
var bestInsertionCost = bestInsertionData.insertionCost
var bestRoute: VehicleRoute? = null
var maxActivities: Int? = vehicleRoutes.map { it.tourActivities.jobs.size }.max()
//look for inserting unassigned job into existing route
for (r in vehicleRoutes) {
var penalty = (maxActivities!! - r.tourActivities.jobs.size) * 1000
val insertionData = bestInsertionCostCalculator.getInsertionData(r, j, r.vehicle, r.vehicle.earliestDeparture, r.driver, bestInsertionData.insertionCost)
if (insertionData is InsertionData.NoInsertionFound) continue
if (insertionData.getInsertionCost() - penalty < bestInsertionCost) {
bestInsertionData = insertionData
bestRoute = r
bestInsertionCost = bestInsertionData.insertionCost - penalty
}
}
//try whole new route
if (bestRoute != null)
insertJob(j, bestInsertionData, bestRoute)
else
badJobs.add(j)
}
return badJobs
}
So i’m trying to make penalty by cost when choosing route is busy.
Whooah, all of this is real hell:) I spend a day to research in jsprit core, that was interesting, but hard.
@lfreneda i was have food enough results using new insertion strategy, when car with big number of parcels have big penalty, so, parcels are putted in the different cars