VRP with capacity constraints

[nol...@mymail.vcu.edu]

New to program but am trying to run VRP with capacity constraints of 7 vehicles, each with a pallet capacity of 24.  6 locations to deliver to where demand is entered as pallets.  All was working great as long as my demand looks something like 0, 4, 12, 14, 9, 9, 8 (where the first is the depot).  The trouble started when I wanted one location to have 36 pallets.  I was hoping program would use two vehicles, one with 24 and the other with the rest of the order.  However, where other combinations return a solution in seconds this either takes forever! or doesn't return a solution at all.  Any suggestions?  

[blind.line]

The solver isn’t “smart” enough to do the behind the scenes work that is necessary here. 

What you are missing is that each node can only be visited once. So when you ask for 36 at a node, the solver can only visit that node once, and none of the vehicle will ever have enough to satisfy, as max is 24. 

You can manually solve this however, by creating “dummy” nodes whenever the demand at a node is higher than vehicle capacity. The difficulty is how to do that, but easiest I can see after thinking about it for all of 10seconds is to split it into 36 co-located dummy nodes all with a demand of 1, and with travel time of zero. 

If you do this for all nodes, then you can get as granular a solution as possible, as suddenly every location can be served by multiple vehicles. 

So your example of 

0, 4, 12, 14, 9, 9, 8

Will become 

0

1,1,1,1

etc

Does that make sense?

James

On Mar 17, 2019, at 14:04, nol...@mymail.vcu.edu wrote:

New to program but am trying to run VRP with capacity constraints of 7 vehicles, each with a pallet capacity of 24.  6 locations to deliver to where demand is entered as pallets.  All was working great as long as my demand looks something like 0, 4, 12, 14, 9, 9, 8 (where the first is the depot).  The trouble started when I wanted one location to have 36 pallets.  I was hoping program would use two vehicles, one with 24 and the other with the rest of the order.  However, where other combinations return a solution in seconds this either takes forever! or doesn't return a solution at all.  Any suggestions?  

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[blind.line]

Adding on my previous reply, you will also have issues if your demand is aliased just right. So with two trucks at 24 capacity, a demand of 23,23,2 will also fail...the two 23s can be served, but then each truck only has 1 pallet left, and only one visit is allowed to the final 2 pallet demand node. Splitting the nodes into a bunch of one pallet dummy nodes is the only way. 

James

On Mar 17, 2019, at 14:04, nol...@mymail.vcu.edu wrote:

New to program but am trying to run VRP with capacity constraints of 7 vehicles, each with a pallet capacity of 24.  6 locations to deliver to where demand is entered as pallets.  All was working great as long as my demand looks something like 0, 4, 12, 14, 9, 9, 8 (where the first is the depot).  The trouble started when I wanted one location to have 36 pallets.  I was hoping program would use two vehicles, one with 24 and the other with the rest of the order.  However, where other combinations return a solution in seconds this either takes forever! or doesn't return a solution at all.  Any suggestions?  

[Mary Beth Nolan]

Thank you so much for your answer and we found a way for it to work.  If a stop needs over one vehicle's capacity, let's say 36, we just enter it in as two demands.  One for 24 and one for 12 for the same location.  Works like a charm.  Now we are working on making the suggested route have a beautiful visualization and are researching various libraries.  Any suggestions?  Because this is just not "presentation ready"!  

[Sampson Akwafuo]

This is exactly my issue right now! 😁  Hope we get a suggestion

[blind.lin...@gmail.com]

My only caution about splitting the demand into chunks like 36 = 12
and 24 is that you *might* be preventing feasible solutions, as I
noted in my earlier comment. On the other hand, I'm a *big* fan of
doing what works and adding complexity only when it doesn't!

On the issue of a "beautiful visualization" I've got not
recommendations aside from rolling your own. I use the OSRM library
for distances between locations, and you can also use it to get the
actual routes. But the standard web page generated by the
OSRM-frontend project (https://github.com/Project-OSRM/osrm-frontend)
is extremely clunky for displaying multiple routes at once, but it
might serve as a starting point.

James E. Marca

[core...@google.com]

Otherwise we "provide"

https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/VRP.md#capacity-constraints

using a svg to console generator in python call from a sh script

sh: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/generate_svg.sh

python:  https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/routing_svg.py

otherwise we also have a python example using matplotlib:

https://github.com/google/or-tools/blob/master/examples/python/cvrptw_plot.py

> > email to or-tools-discuss+unsubscribe@googlegroups.com.

> > For more options, visit https://groups.google.com/d/optout.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "or-tools-discuss" group.
> > To unsubscribe from this group and stop receiving emails from it, send an

> > email to or-tools-discuss+unsubscribe@googlegroups.com.

> > For more options, visit https://groups.google.com/d/optout.
> >
>
> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

[Mary Beth Nolan]

Question on having excel read the output:  For example:

We want to be able to have this output more readable for the client.  Instead of just showing number 1, 2, 3, etc for locations it would display the more user friendly location name.  The same input that the user are entering to start the program.  

Any suggestions?

> > email to or-tools-discu...@googlegroups.com.

> > For more options, visit https://groups.google.com/d/optout.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "or-tools-discuss" group.
> > To unsubscribe from this group and stop receiving emails from it, send an

> > email to or-tools-discu...@googlegroups.com.

> > For more options, visit https://groups.google.com/d/optout.
> >
>
> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.



--

James E. Marca

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[blind.line]

Well, the obvious answer is to just implement your own print function to spit out CSV data, with a header row. Am I missing something?  

James

On Mar 27, 2019, at 16:10, Mary Beth Nolan <nol...@mymail.vcu.edu> wrote:

Question on having excel read the output:  For example:

[Mary Beth Nolan]

Nope, that's exactly correct!

[blind.line]

Okay...so is there a problem with writing that code?

I’d suggest writing one line per event (leave depot, return to depot, pick up, or delivery). But otherwise it seems straightforward, esp given you have the existing example to start from. Do you have any specific problems?  

James

[Mary Beth Nolan]

No, the others in my group know how to write better Python code than I do so they are going to handle it.  I just wanted to make sure we were on the correct path.  My group mate was just trying to figure out the final print statement where he could insert his own print statements.  I'm sure he will figure it out!

Thank you!