Drools Planner: Vehicle routing problems

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Drools Planner: Vehicle routing problems

davidglassborow
Hi,
      as discussed the other day with Ge0ffrey on IRC, I've been trying to get some vehicle routing done using the new TSP / chaining functionality in drools planner.

I've written an example, but am having problems with the chaining of jobs together.  After pulling my hair out, I've put together an example into my fork of planner, showing a simplified example of how I am approaching it, and the problem that can be replicated.

https://github.com/davidglassborow/drools-planner/tree/vehicle_routing

It is a very simple console app along the same lines as the hello world example for NQueens.

On running it will print out the chains, and you will see the some Jobs appear more than once in the same list.

On the planning variable it seems to be get assigned in front of itself, I've put some notes in the source, and checked that the same doesn't occur in your TSP example.

I'm not sure if its a bug in the way I've setup things, or whether its an issue in the chain move code.

Greatly appreciated if anybody in the know gets a chance to have a look.
Thanks,
David
Reply | Threaded
Open this post in threaded view
|

Re: Drools Planner: Vehicle routing problems

davidglassborow
Some more details on my problem:


Here is an example of a vehicle routing solution, 2 crews and 4 Jobs A, B, C and D.
The print out below is the solver and solutions found at each step (it prints out each chain of jobs)
As you can see the initial solution is valid.
The next and last solutions are invalid though, with the same job appearing more than once in a chain.

At 109:
B => Crew1
D => Crew2
A => B => Crew1
C => A => B => Crew1

2012-02-24 15:20:39,160 [main] DEBUG     Step index (3), time spend (110), score (0hard/-17soft), initialized planning entity (Job D ( linked to Crew Crew2)).
2012-02-24 15:20:39,160 [main] INFO  Phase construction heuristic ended: step total (4), time spend (110), best score (0hard/-17soft).

At 127:
D => Crew2
A => B => Crew1
B => A => B => Crew1
C => A => B => Crew1

2012-02-24 15:20:39,177 [main] DEBUG     Step index (0), time spend (127), score (0hard/-15soft), new best score (0hard/-15soft), accepted move size (18) for picked step (Job B ( linked to Crew Crew1) => Job A ( linked to Job B)).
2012-02-24 15:20:39,191 [main] DEBUG     Step index (1), time spend (141), score (0hard/-15soft),     best score (0hard/-15soft), accepted move size (14) for picked step (Job D ( linked to Crew Crew2) => Crew1).
2012-02-24 15:20:39,206 [main] DEBUG     Step index (2), time spend (156), score (0hard/-16soft),     best score (0hard/-15soft), accepted move size (10) for picked step (Job C ( linked to Job A) => Job B ( linked to Job A)).
2012-02-24 15:20:39,223 [main] DEBUG     Step index (3), time spend (173), score (0hard/-16soft),     best score (0hard/-15soft), accepted move size (5) for picked step (Job A ( linked to Job B) => Job B ( linked to Job A)).
2012-02-24 15:20:39,239 [main] WARN      Cancelled step index (4), time spend (189): there is no doable move. Terminating phase early.
2012-02-24 15:20:39,239 [main] INFO  Phase local search ended: step total (4), time spend (189), best score (0hard/-15soft).
2012-02-24 15:20:39,239 [main] INFO  Solving ended: time spend (189), best score (0hard/-15soft), average calculate count per second (1089).

Best:
D => Crew2
A => B => Crew1
C => A => B => Crew1
B => A => B => B => Crew1
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

ge0ffrey
Administrator
Hi David,



Op 24-02-12 16:26, davidglassborow schreef:
> Some more details on my problem:
>
>
> Here is an example of a vehicle routing solution, 2 crews and 4 Jobs A, B, C
> and D.
> The print out below is the solver and solutions found at each step (it
> prints out each chain of jobs)
> As you can see the initial solution is valid.
What do you mean by initial solution? The setPlanningProblem() aka "the
uninitialed solution"
or the solution after the construction heuristic (aka "the initialized
solution")
> The next and last solutions are invalid though, with the same job appearing
> more than once in a chain.
>
> At 109:
What's "109"?
> B =>  Crew1
> D =>  Crew2
> A =>  B =>  Crew1
> C =>  A =>  B =>  Crew1
>
> 2012-02-24 15:20:39,160 [main] DEBUG     Step index (3), time spend (110),
> score (0hard/-17soft), initialized planning entity (Job D ( linked to Crew
> Crew2)).
Ok, if it's invalid here, it's invalid during the construction heuristic
already.
> 2012-02-24 15:20:39,160 [main] INFO  Phase construction heuristic ended:
> step total (4), time spend (110), best score (0hard/-17soft).
>
> At 127:
> D =>  Crew2
> A =>  B =>  Crew1
> B =>  A =>  B =>  Crew1
How is this possible? That means that B is pointing both to A and to Crew1 ?
It's only a single pointer? VrpCustomer.getPreviousAppereance()
> C =>  A =>  B =>  Crew1

> 2012-02-24 15:20:39,177 [main] DEBUG     Step index (0), time spend (127),
> score (0hard/-15soft), new best score (0hard/-15soft), accepted move size
> (18) for picked step (Job B ( linked to Crew Crew1) =>  Job A ( linked to Job
> B)).
> 2012-02-24 15:20:39,191 [main] DEBUG     Step index (1), time spend (141),
> score (0hard/-15soft),     best score (0hard/-15soft), accepted move size
> (14) for picked step (Job D ( linked to Crew Crew2) =>  Crew1).
> 2012-02-24 15:20:39,206 [main] DEBUG     Step index (2), time spend (156),
> score (0hard/-16soft),     best score (0hard/-15soft), accepted move size
> (10) for picked step (Job C ( linked to Job A) =>  Job B ( linked to Job A)).
> 2012-02-24 15:20:39,223 [main] DEBUG     Step index (3), time spend (173),
> score (0hard/-16soft),     best score (0hard/-15soft), accepted move size
> (5) for picked step (Job A ( linked to Job B) =>  Job B ( linked to Job A)).
> 2012-02-24 15:20:39,239 [main] WARN      Cancelled step index (4), time
> spend (189): there is no doable move. Terminating phase early.
> 2012-02-24 15:20:39,239 [main] INFO  Phase local search ended: step total
> (4), time spend (189), best score (0hard/-15soft).
> 2012-02-24 15:20:39,239 [main] INFO  Solving ended: time spend (189), best
> score (0hard/-15soft), average calculate count per second (1089).
>
> Best:
> D =>  Crew2
> A =>  B =>  Crew1
> C =>  A =>  B =>  Crew1
> B =>  A =>  B =>  B =>  Crew1
>
I hacked TSP to do multi TSP (see my google+ image), and it worked
without a problem, so there must be a difference somewhere in your code.

I am working on a vehicle routing example next, you might want to
compare code with that one as soon as it's done.
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-Vehicle-routing-problems-tp3772797p3772841.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

--
With kind regards,
Geoffrey De Smet


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

davidglassborow
Hi Ge0ffrey,

> What do you mean by initial solution? The setPlanningProblem() aka "the
> uninitialed solution"
> or the solution after the construction heuristic (aka "the initialized
> solution")

I mean the initialised solution

> What's "109"?

Sorry, the number is just the number of milliseconds as returns by the new solution event

> Ok, if it's invalid here, it's invalid during the construction heuristic
> already.

so at this point the solution is valid, its later steps where I get the problem

>> At 127:
>> D =>  Crew2
>> A =>  B =>  Crew1
>> B =>  A =>  B =>  Crew1

>How is this possible? That means that B is pointing both to A and to Crew1 ?
>It's only a single pointer? VrpCustomer.getPreviousAppereance()

Indeed this is my problem.  There seems to be more than 1 instance of B.
I've debugged my example code, and then issue seems to be:

https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/vehiclerouting/domain/Job.java#L33

The solver seems to be assigning the visit to be before itself !

If you look at:

https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/tsp/domain/Visit.java#L59

you'll see I have added a check to your Visit.java, which doesn't display the same problem.

So I'm not sure what is happening, domain objects seems to be cloned and assigned to themselves.
I have checked and double-checked the code inline with your TSP example, I'm sure it's nothing stupid I've done but can't for the life of me see anything wrong.

If you download the branch, and run the VehicleRoutingHelloWorld class, you'll see the problem occuring.

> I hacked TSP to do multi TSP (see my google+ image), and it worked
> without a problem, so there must be a difference somewhere in your code.

What did you need to change to get that to work ? Was it just a case of adding another domicile, and then removing the return to domicile cost rule ?

Cheers for the help,
Dave
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

ge0ffrey
Administrator


Op 27-02-12 10:46, davidglassborow schreef:

> Hi Ge0ffrey,
>
>> What do you mean by initial solution? The setPlanningProblem() aka "the
>> uninitialed solution"
>> or the solution after the construction heuristic (aka "the initialized
>> solution")
> I mean the initialised solution
>
>> What's "109"?
> Sorry, the number is just the number of milliseconds as returns by the new
> solution event
>
>> Ok, if it's invalid here, it's invalid during the construction heuristic
>> already.
> so at this point the solution is valid, its later steps where I get the
> problem
>
>>> At 127:
>>> D =>   Crew2
>>> A =>   B =>   Crew1
>>> B =>   A =>   B =>   Crew1
>> How is this possible? That means that B is pointing both to A and to Crew1
> ?
>> It's only a single pointer? VrpCustomer.getPreviousAppereance()
> Indeed this is my problem.  There seems to be more than 1 instance of B.
> I've debugged my example code, and then issue seems to be:
>
> https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/vehiclerouting/domain/Job.java#L33
>
> The solver seems to be assigning the visit to be before itself !
>
> If you look at:
>
> https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/tsp/domain/Visit.java#L59
>
> you'll see I have added a check to your Visit.java, which doesn't display
> the same problem.
>
> So I'm not sure what is happening, domain objects seems to be cloned and
> assigned to themselves.
Check your Solution's cloning method.

If you clone the Visit, you need to make sure that planning variables of
each cloned Visit are pointing to the new clones and not the original
Visits.
See my implementation in TSP.

> I have checked and double-checked the code inline with your TSP example, I'm
> sure it's nothing stupid I've done but can't for the life of me see anything
> wrong.
>
> If you download the branch, and run the VehicleRoutingHelloWorld class,
> you'll see the problem occuring.
>
>> I hacked TSP to do multi TSP (see my google+ image), and it worked
>> without a problem, so there must be a difference somewhere in your code.
> What did you need to change to get that to work ? Was it just a case of
> adding another domicile, and then removing the return to domicile cost rule
> ?
>
> Cheers for the help,
> Dave
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-Vehicle-routing-problems-tp3772797p3780139.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

--
With kind regards,
Geoffrey De Smet


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

davidglassborow
Geoffrey,

> Check your Solution's cloning method.

>If you clone the Visit, you need to make sure that planning variables of
>each cloned Visit are pointing to the new clones and not the original
>Visits.
>See my implementation in TSP.

Sure, my clone method is virtually the same as your TSP one (my whole project was basically a copy of TSP):

https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/tsp/domain/TravelingSalesmanTour.java#L96

and

https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/vehiclerouting/domain/VehicleRouter.java#L41

Did you have to make any other changes to make multi TSP work ?  Was it just a case of adding another domicile, and then removing the return to domicile cost rule ?

Cheers,
Dave
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

ge0ffrey
Administrator


Op 27-02-12 12:07, davidglassborow schreef:

> Geoffrey,
>
>> Check your Solution's cloning method.
>> If you clone the Visit, you need to make sure that planning variables of
>> each cloned Visit are pointing to the new clones and not the original
>> Visits.
>> See my implementation in TSP.
> Sure, my clone method is virtually the same as your TSP one (my whole
> project was basically a copy of TSP):
>
> https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/tsp/domain/TravelingSalesmanTour.java#L96
>
> and
>
> https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/vehiclerouting/domain/VehicleRouter.java#L41
>
> Did you have to make any other changes to make multi TSP work ?  Was it just
> a case of adding another domicile, and then removing the return to domicile
> cost rule ?
Yep and fix the gui not to draw it.

> Cheers,
> Dave
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-Vehicle-routing-problems-tp3772797p3780331.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

--
With kind regards,
Geoffrey De Smet


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

ge0ffrey
Administrator
Just pushed my vehicle routing prototype, it works pretty well :)

Op 27-02-12 12:16, Geoffrey De Smet schreef:

>
> Op 27-02-12 12:07, davidglassborow schreef:
>> Geoffrey,
>>
>>> Check your Solution's cloning method.
>>> If you clone the Visit, you need to make sure that planning variables of
>>> each cloned Visit are pointing to the new clones and not the original
>>> Visits.
>>> See my implementation in TSP.
>> Sure, my clone method is virtually the same as your TSP one (my whole
>> project was basically a copy of TSP):
>>
>> https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/tsp/domain/TravelingSalesmanTour.java#L96
>>
>> and
>>
>> https://github.com/davidglassborow/drools-planner/blob/vehicle_routing/drools-planner-examples/src/main/java/org/drools/planner/examples/vehiclerouting/domain/VehicleRouter.java#L41
>>
>> Did you have to make any other changes to make multi TSP work ?  Was it just
>> a case of adding another domicile, and then removing the return to domicile
>> cost rule ?
> Yep and fix the gui not to draw it.
>> Cheers,
>> Dave
>>
>> --
>> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-Vehicle-routing-problems-tp3772797p3780331.html
>> Sent from the Drools: User forum mailing list archive at Nabble.com.
>> _______________________________________________
>> rules-users mailing list
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>

--
With kind regards,
Geoffrey De Smet


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Neb
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

Neb
Hi ge0ffrey

In the optoplanner example of the vehicle routing is there a way to change the scale of the map?

as it is set to world and if locations are added within the same town or city they are too close on the map.

also how would this example be altered to show the travel time around the route?

Regards, Neb
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

ge0ffrey
Administrator
I guess it's a matter of adjusting these 2 files to your needs:

https://github.com/droolsjbpm/optaplanner/blob/master/optaplanner-examples/src/main/java/org/optaplanner/examples/vehiclerouting/swingui/VehicleRoutingWorldPanel.java
https://github.com/droolsjbpm/optaplanner/blob/master/optaplanner-examples/src/main/java/org/optaplanner/examples/vehiclerouting/swingui/VehicleRoutingSchedulePainter.java

Maybe someone else in the community has done similar changes and is
willing to share the implementation?

On 30-05-14 03:05, Neb wrote:

> Hi ge0ffrey
>
> In the optoplanner example of the vehicle routing is there a way to change
> the scale of the map?
>
> as it is set to world and if locations are added within the same town or
> city they are too close on the map.
>
> also how would this example be altered to show the travel time around the
> route?
>
> Regards, Neb
>
>
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-Vehicle-routing-problems-tp3772797p4029766.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Neb
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

Neb
Thanks Geoffrey

I have managed to get it working by manually changing some values in the latitude and longitude elements in the xml file.

What I am struggling with is generating an xml file with my own data in each element.

do you have any tips on how to create this xml to drive the vehicle routing solution. I have tried in c# but I cant get the nodes and attributes in the right order.

Many thanks
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] Drools Planner: Vehicle routing problems

ge0ffrey
Administrator

On 11-06-14 09:30, Neb wrote:

> Thanks Geoffrey
>
> I have managed to get it working by manually changing some values in the
> latitude and longitude elements in the xml file.
>
> What I am struggling with is generating an xml file with my own data in each
> element.
>
> do you have any tips on how to create this xml to drive the vehicle routing
> solution.

Learn XStream :)
   http://xstream.codehaus.org/
There are number of nice tutorials there.
XStream is independent of OptaPlanner, but they work together nicely.
Ask any questions related to the XML format on their mailing list (I am
subscribed there too).

Alternatively, use JAXB (which works nicely with OptaPlanner too).

>   I have tried in c# but I cant get the nodes and attributes in the
> right order.
>
> Many thanks
>
>
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-Vehicle-routing-problems-tp3772797p4029962.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users