Optimize by time

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.

Hi @glorfindeil,

Some sample code will be very useful.

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?

Hi @Bhoumik_Shah!

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.

Seems similar to: https://github.com/graphhopper/jsprit/issues/239

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.

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

  2. .setCostPerDistance(0.0) and only add cost penalties for waiting time and driving time.

Might be worth a shot?

Is your goal to balance the workload between the vehicles ?

If so, you should probably edit the objective function in order to minimize the Maximum TimeCost of the vehicle.

1 Like

I have a problem that every time the cost of every solution is becomes zero.

                        costPerWaiting = 100.0, fixedCost = 0.0, capacity = 100, dropTime = 5.0, pickupTime = 5.0))```

Ok I have reached goal using custom objective function - now I trying to calculate maxDeliveryTime for every route and add time price to costs.

I have another problem.
Default insertion strategy always tries not to insert jobs to new routes, but I wait a different behavour.

According to this I have never find a good solution because it tries to use 1-2 cars while searching in acceptable number of iterations.

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.

@glorfindeil I’m with the same challenge, did you do it?

I want to get the fasted solution, it doesn’t matter route costs…

@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

got it D:

Did you inject an new objective function? do you have same piece of sample code to help me out?

Do you have a sample of that?

You should have a look to this : https://github.com/jsprit/playground/blob/master/src/abe/AbeProblemMinMax.java
:wink:

That is pretty helpful. But I noticed that is a implementation using jsprit version 1.3 (pretty old).

Why this solution was not included on branch master since is a common problem that many people is trying to solve?
Weirdo D:

But, sure, I’ll try to implement it using the jsprit lasted version.

Thank you @braktar.

@Ifreneda How is the implementation? I’m also doing it, let’s post them here to see if they are the same.

1 Like