How to disallow some roads (subtour) in jsprit?

jsprit
1

Hi,

I would like to disallow some roads in my MVR problem. In other words, I do NOT want to consider a complete graph in my model. Certain roads (i.e., edges) should not be a part of my problem definition. For example, I do not want to have a solution with a route including service1 is done before service2. Can you help me how to model this, in Jsprit.

Best, Iran

2

Hello,

You should have a look to this example :
JobAndActivityDependenciesExample.java

If you want to exclude a direct sequence, you will only need a HardActivityConstraint.
Otherwise you will need to have a StateUpdater, which allow you to know if the first activity is already performed.

1 Like
3

Great, Thanks for the fast response

4

Hi again,
Is it possible that the algorithm does not find a solution when a set of hard constraints is added. I used the example which you mentioned above to impose hard sequencing constraints, but I get a solution with unassigned jobs. There are solutions even under my hard constraints. How can I force the algorithm not to leave any unassigned job?

Thanks a lot

5

You’ll need to override the objective function, in order to penalize the unassigned job.

Have a look to this thread :
https://groups.google.com/d/msg/jsprit-mailing-list/c6ZSa38lEGA/sVeZn94nwz8J

6

and you should make sure that your constraints specification allow feasible solutions at all. For example, driver operation time is a hard contraint. If you have only one driver and his latest_end is 0 then all your jobs end up in the unassigned job list.

7

Thank you, I learned how to change the penalty for unassigned job and still, I am not 100% sure whether my constraints exclude all solutions (but i debug a lot, and I dont think so it is the case). Anyway, if I deactivate all my hard constraints, and I get 2 solutions only. If the algorithm only finds two solutions without any constraints, for 9 jobs, and WITHOUT ANY TIME OR CAPACITY SETTING, roughly speaking, is not it expected not to find any solution with some constraints? I use this example jobandActivityDependency for creating the problem with different number of jobs and positions. Is it normal to get only 2 solutions?

8

If you mean that vra.searchSolutions() returns 2 solutions, than yes, it is normal. The reason is that in some cases the solution found after lets write 2000 iterations is worse than a solution found in course of finding this solution. Therefore, the algorithm always stores the best and the solution after 2000 iterations. Usually, they are the equal.

9

Sorry to bother you again, I have to make this work! so still, I believe my constraints does not exclude all solutions, however, I suspect those solutions are never generated (i.e., the algorithm cannot find them). Is it ever possible? How can I force algorithm to find more solutions? Moreover, I have another question: I make different “solution” when i use ConstraintsStatus.NOT_FULFILLED_BREAK and ConstraintsStatus.NOT_FULFILLED. in the latter, my constraints are not respected fully, and in the former, I get many unassigned jobs, even I set high penalty for that. Which one I should use?

Thanks a lot for your time

10

A first thing is to understand how a job is tested before insertion.

Once you want to insert a job, it will test a route, in this route, it will test every position (between Start and A, btw A and B, btw B and End) For every position it will test the constraints.

ConstraintsStatus.NOT_FULFILLED_BREAK define that once it is rised, you can’t insert the job anymore.

ConstraintsStatus.NOT_FULFILLED define only that to this specific position you can’t insert this job.

11

Ok, I understand, it means that I have to use ConstraintsStatus.NOT_FULFILLED, however, as I said before, it gives me a solution which does not respect the constraint, I traces the code, and I realized that the algorithm rejects the route which does not satisfy the constraints, but at the end, the solution contains the assignment which has been already rejected. I do not understand this part. The constraints are hard, and priroty is critical. How is that possible?

I have to mention that If I lower the amount of penalty for unassigned jobs, it respects to the constraints, but it leaves some unassigned jobs. My main question from the begining is that how to enforce the algorithm try more solutions and routes, so it can find a feasible solution (i.e., respecting the constraints, without no unassgined job)?

Again, Thanks a lot for all responses

12

Hi again, where can I add heuristics for selecting new unassigned jobs? as I guessed correctly, many routes even have not generated (I just trace the code and log it), so I want to implement a domain specific heuristic to guide the search to find the routes which I like.

Thanks