Problem with job unssigned and less vehicle used

jsprit
1

I have a GREAT problem, I have 2 types of vehicles, 34 vehicles (29 type 1 and 5 of type 2), I
also have 500 jobs between pick-ups and deliveries, when I look for the
solution, it tells me that I must use 22 vehicles, but I leave 51 jobs
unssigned, Why Do not use the other vehicles available?
I used these two statements but I get similar results (even using sepriority (1) in the jobs)
------- option 1 -----
VrpBuilder.setRoutingCost (costMatrix);
VrpBuilder.setFleetSize (VehicleRoutingProblem.FleetSize.FINITE);

        VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance (vrp)
                .setProperty (Jsprit.Parameter.THREADS, "5").
                .buildAlgorithm ();
        Collection <VehicleRoutingProblemSolution> solutions = vra.searchSolutions ();
        VehicleRoutingProblemSolution solution = new SelectBest (). SelectSolution (solutions);

------ option 2 ---------

        VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance (vrp)
                .setStateAndConstraintManager (stateManager, constraintManager)
                .setProperty (Jsprit.Parameter.THREADS, "5")
                .setProperty (Jsprit.Parameter.FIXED_COST_PARAM, "1.5")
                .setProperty (Jsprit.Strategy.CLUSTER_REGRET, "0.3")
                .setProperty (Jsprit.Strategy.CLUSTER_BEST, "10.0")
                .setProperty (Jsprit.Parameter.VEHICLE_SWITCH, "true")
                .setProperty (Jsprit.Parameter.THRESHOLD_ALPHA, "0.0")
                .setObjectiveFunction (new SolutionCostCalculator () {
                    @Override
                    Public double getCosts (VehicleRoutingProblemSolution solution)
                        Double costs = 0 .;
                        For (VehicleRoute route: solution.getRoutes ()) {
                            Costs + = route.getVehicle (). GetType (). GetVehicleCostParams (). Fix;
                            TourActivity prevAct = route.getStart ();
                            For (TourActivity act: route.getActivities ()) {
                                Costs + = vrp.getTransportCosts

(). GetTransportCost (prevAct.getLocation (), act.getLocation (),
prevAct.getEndTime (), route.getDriver (), route.getVehicle ());
Costs + = vrp.getActivityCosts (). GetActivityCost (act, act.getArrTime (), route.getDriver (), route.getVehicle ());
PrevAct = act;
}
Costs + = vrp.getTransportCosts ().
GetTransportCost (prevAct.getLocation (), route.getEnd ()) getLocation
(), prevAct.getEndTime (), route.getDriver (), route.getVehicle ());
}
Costs + = solution.getUnassignedJobs (). Size () * 200000;
Return costs;
}
})
.buildAlgorithm ();
Collection solutions = vra.searchSolutions ();
VehicleRoutingProblemSolution solution = new SelectBest (). SelectSolution (solutions);

thanks

2

So the problem seems to be, that the other 51 unassigned jobs donĀ“t fullfill your or the jsprit constraints. Maybe the other jobs are too far away, they have skills that the vehicles canĀ“t do or with the given timewindows it will not work. You should check the distance or the other things from the unassigned jobs.

3

What you can do is,
remove all the assigned jobs from your problem definition and try to run with those 51 unassigned jobs. See if those get assigned. If not then it is due to violation of some constraint as mentioned by @patrick_wisniewski19

4

I have very similar problem: a finite set of vehicles (3), but the algorithm could assign almost all jobs by less vehicles (2) and decides to leave unassigned jobs instead of bringing in more vehicles.
There are general situations where leaving unassinged jobs is not an option, so I guess there is (or at least there should be) a way to force all job to be assigned as long as the fleet is sufficient. In other words, penalize (raise the cost) of unassigned jobs so high it is too high to prevent solutions with unassigned jobs.

5

Just try to refine the costs function by increasing the penalty for unassigned jobs or set your own one. This is the default function.

This is how unassigned jobs are penalyzed in the default function.

2 Likes
6

I did it and worked.
@stefan: Now I have an idea to make the objective function modular. What it really does is calculating different cost aspects and sums them. In my head, What I propose is some modulare function.
There is a new interface for the aspects. It has a function which returns a cost value.
The main function contains a collection of aspects and calls them after each other and sums the returned costs (even weighting could be applied).
The new interface could allow any new aspect to implement and add, or allow the user to pick only the aspects he wants. We could give a set of commonly used aspects to start with and a default configuration of aspects matching the current implementation.
The separation of the aspects also allows them to configure separately.
This makes the objective function flexible with a little effort. I could even create a prototype tomorrow.

7

Hey @Balage1551,

Even I have something similar in mind. Have you started working on your implementation? If you donā€™t mind we can work on this together.

1 Like
8

Hello,

It is ready and on pending state (an open pull request is there) to be integrated to the main branch.
You can have a sneak peek on the implementation in this pull request:

(Note,that minor changes are still possible on the new API.)

However, this will only be available in the new major version of the jsprit planned to be released on early 2017. :frowning:
The reason: There are so much changed in the new release, I had no time to implement it in both versions. It needs some change in core code and the new SolutionPrinter to display the results.

If you eager to use it now, it could be migrated and I could give you some helping hands how to do it.

4 Likes
9

Hi I tried with the latest code. And even though i have more vehicles left, some of the jobs are still unassigned. i have even tried bumping up penalty costs of unassigned jobs. but it increased overall cost of the solution but still jobs remained unassigned. pl help.

1 Like
10

What do these Jsprit.Parameter and Jsprit.Strategy properties mean?

11

Hi I tried with the latest code. And even though i have more vehicles left, some of the jobs are still unassigned. i have even tried bumping up penalty costs of unassigned jobs. but it increased overall cost of the solution but still jobs remained unassigned. pl help.

Hi @Balage1551 @Bhoumik_Shah @Nane_Petrosyan @patrick_wisniewski19 @stefan I also tried with increasing the penalty but still the number of unassigned jobs are same with more cost added into it. Can you please help me out in same?

Thanks
Rishabh