jsprit too restrictive if no solution can be found?

[jsprit]

(For everyone's benefit except Stefan, who already knows about this) I'm incorporating jsprit into my recently released open source application Open Door Logistics Studio, which currently does territory management (see http://www.youtube.com/watch?v=cyIcVwHf524). ODL Studio will provide a UI for jsprit with data editing, geocoding mapping, reporting etc...

I've got an experimental jsprit integration partially running and come across the IllegalStateException which happens when jsprit can't load a job. I'm currently running the 1.2.0 jsprit release so apologies if this is out-of-date..

Anyway I know you can set infinite fleet size which will allow jobs to be loaded if there's not enough vehicles, but there are various scenarios when certain jobs can never be loaded. For example, if a stop (a) has a quantity bigger than the capacity of any vehicle or (b) has a time window that cannot be served by any vehicle as its end time is too close to the vehicle start time.

In this scenario, as far as I understand, jsprit will throw the IllegalStateException and not generate any solution, even for stops that could still be loaded.

The problem is that its always possible for a user to put in bad data for a single stop, which would then result in all stops not being loaded due to the exception In an automated vehicle routing system this turns a minor problem - one not load - into a critical failure. Really these 'bad' stops should not be loaded but the ok stops should still be loaded and optimised.

The only thing I can think of doing is to create a VehicleRoutingProblem and VehicleRoutingAlgorithm object for each job individually (i.e. each problem contains a single job). I then catch the exceptions for any bad jobs, one-by-one, and remove these jobs. Finally I build a VehicleRoutingProblem containing only the OK stops which threw no exceptions.

Is there any other (better) way to set jsprit to do this? The method I've outlined above has a number of drawbacks...

written by @PGWelch (Philip Welch)

[jsprit]

Until now, for me it was important to be noticed immediately if a problem cannot be solved, thus the exception is thrown. I defined 'problem solved' such that all jobs are optimized. But I understand your case and it thus makes sense to find another solution. Let me pickup what you proposed that jobs that can be loaded should still be optimized even there are 'bad' jobs. What if we remove the exception and introduce a bad-job-list. The VehicleRoutingProblemSolution does then not only contain optimized routes but also this bad-job-list. Thus bad jobs become part of the solution which is a minor refinement of the 'problem solved' definition.

[PGWelch]

Sounds great! If fleet size is not infinite would you add jobs which weren't loaded because there wasn't enough vehicles to this list? Philip WelchOpen Door Logistics LimitedSpecialists in open source solutions for transport logistics. _Tel:  +44 (0) 20 8144 4009__Email: _info@opendoorlogistics.com_Web: _www.opendoorlogistics.com [1]

----- Original Message ----- From: "jsprit/jsprit" To:"jsprit/jsprit" Cc:"Philip Welch" Sent:Mon, 30 Jun 2014 04:08:51 -0700 Subject:Re: [jsprit] jsprit too restrictive if no solution can be found? (#110)

Until now, for me it was important to be noticed immediately if a

problem cannot be solved, thus the exception is thrown I defined 'problem solved' such that all jobs are optimized. But I understand your case and it thus makes sense to find another solution. Let me pickup what you proposed that jobs that can be loaded should still be optimized even there are 'bad' jobs. What if we remove the exception and introduce a bad-job-list. The VehicleRoutingProblemSolution does then not only contain optimized routes but also this bad-job-list. Thus bad jobs become part of the solution which is a minor refinement of the 'problem solved' definition.

—

Reply to this email directly or view it on GitHub [2].

Links:

[1] http://www.opendoorlogistics.com [2] https://github.com/jsprit/jsprit/issues/110#issuecomment-47519599

[jsprit]

I would add jobs there that cannot be loaded for any reason. However, in the course of the iterations the algorithm should constantly try to insert these jobs as well (since some jobs can only be inserted after routes have reached a certain level of optimization). This - by the way - opens up a whole new problem type. For example, you can then define and add potential jobs that yield certain revenues, and serve only those that maximize profits given your resources; and all others end up in the bad-job-list.

[pierredavidbelanger]

Just a thought; I follow what you do with this great feature, and I wonder if it would be convenient (and easy to implement) to have something like that:

Instead of your Collection<Job> getUnassignedJobs() in VehicleRoutingProblemSolution

We could have a Collection<UnassignedJob> getUnassignedJobs().

And this new class UnassignedJob could have a Job getJob() method, along with a String getReason()... or even (better ?) a UnassignedJobReason getReason(), where UnassignedJobReason could be an enum ...

I am thinking out loud here.

I think my point here is that it would be practical to know the reason (time window, size constraint, etc..) why a job is rejected.

What do you think of this ?

[PGWelch]

 I think my point here is that it would be practical to know the reason (time window, size constraint, etc..) why a job is rejected. Great idea. This is practical and also very useful : )  Philip WelchOpen Door Logistics LimitedSpecialists in open source solutions for transport logistics. _Tel:  +44 (0) 20 8144 4009__Email: _info@opendoorlogistics.com_Skype: _opendoorlogistics_Web: _www.opendoorlogistics.com [1]

----- Original Message ----- From: "jsprit/jsprit" To:"jsprit/jsprit" Cc:"Philip Welch" Sent:Mon, 11 Aug 2014 20:10:03 -0700 Subject:Re: [jsprit] jsprit too restrictive if no solution can be found? (#110)

Just a thought; I follow what you do with this great feature, and I

wonder if it would be convenient (and easy to implement) to have something like that:

Instead of your Collection getUnassignedJobs() in

VehicleRoutingProblemSolution

We could have a Collection getUnassignedJobs(). 

And this new class UnassignedJob could have a Job getJob() method,

along with a String getReason()... or even (better ?) a UnassignedJobReason getReason(), where UnassignedJobReason could be an enum ...

I am thinking out loud here. 

I think my point here is that it would be practical to know the

reason (time window, size constraint, etc..) why a job is rejected.

What do you think of this ? 

—

Reply to this email directly or view it on GitHub [2].

Links:

[1] http://www.opendoorlogistics.com [2] https://github.com/jsprit/jsprit/issues/110#issuecomment-51868559

[jsprit]

I like your thoughts and it would be rather helpful to know the reasons behind. However, it is not as easy and scalable as it looks. Since sometimes capacity might be the reason, sometimes time windows or both or any other hard constraint that is implemented by the user. In some cases jobs might just be too unattractive in terms of profits to serve them with your own fleet etc.. Therefore, it is not that easy to implement. I am sure that it is possible but it will come with some overhead caused by investigating the real reason (that is not misleading).

[pierredavidbelanger]

I understand. Indeed, the same job can be rejected because it dose not fit the timewindows in one route, and because of a custom hard constraint in an other. Or simply because the job adds to much cost to the final solution. It will be hard at best, if possible at all, to find such a unique reason why it was rejected.

Thank you for your comments!

I am eager to test this "unassigned job list" feature!

[jsprit]

bad job list is now available (use latest 1.3.2-SNAPSHOT until v1.4 is released)

Note that I chose a "soft" approach to deal with unassigned jobs, i.e. each unassigned job will be penalyzed in the objective function (see default objective https://github.com/jsprit/jsprit/blob/master/jsprit-core/src/main/java/jsprit/core/algorithm/VariablePlusFixedSolutionCostCalculatorFactory.java [line 55]). If you omit penalyzing them, you probably end up with a solution consisting solely of unassigned jobs (the less the better in terms of total costs). This however easily enables you to define objective functions that maximizes profits. Thus, if you already use your own custom objective function, you need to manually adapt it and add penalties for unassigned jobs.