VRP - OR-Tools not utilizing all vehicles

[Alexander Valdez]

I am having an issue with the VRP optimization. It is optimizing the routes properly, however, it is not utilizing all of the vehicles. For instance, I have tested with 15 addresses and 4 vehicles and it only uses 3 of the vehicles. Is there any constraint that I can configure to either limit the number of addresses per route, ensure that each vehicle has a route, or distribute the routes evenly? Also, I'm assuming in a much bigger problem (i.e. hundreds of addresses and multiple vehicles) this most likely won't be an issue. Any help would be appreciated.

[Vincent Furnon]

You can add a dimension counting the number of stops on a route (transition will be 1 in that case). Then you can constrain the upper bound of the cumul variable at the vehicle's end node to limit the number of nodes assigned to a vehicle (or put that limit in the capacity of the dimension). If you have existing dimensions such as time or distance you can do the same thing on these to limit the duration or the length of a route. Similarly if you have a capacity dimension you can artificially reduce the capacity value. This will not exactly balance your routes but will ensure all vehicles are used if the values are low enough.

On Wed, Jun 5, 2019 at 4:32 PM Alexander Valdez <alexva...@tamu.edu> wrote:

I am having an issue with the VRP optimization. It is optimizing the routes properly, however, it is not utilizing all of the vehicles. For instance, I have tested with 15 addresses and 4 vehicles and it only uses 3 of the vehicles. Is there any constraint that I can configure to either limit the number of addresses per route, ensure that each vehicle has a route, or distribute the routes evenly? Also, I'm assuming in a much bigger problem (i.e. hundreds of addresses and multiple vehicles) this most likely won't be an issue. Any help would be appreciated.

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4f7cb285-2e42-4729-91eb-f715a5d44189%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Alexander Valdez]

Thank you for the response! Just trying to understand it correctly: Are you suggesting to use the library's "AddDimension" function? Then utilizing that function to limit the capacity of each vehicle based on number of routes? I'm still just now understanding the OR-Tools library. Thanks for your help, Vincent.

On Wednesday, June 5, 2019 at 9:46:23 AM UTC-5, Vincent Furnon wrote:

You can add a dimension counting the number of stops on a route (transition will be 1 in that case). Then you can constrain the upper bound of the cumul variable at the vehicle's end node to limit the number of nodes assigned to a vehicle (or put that limit in the capacity of the dimension). If you have existing dimensions such as time or distance you can do the same thing on these to limit the duration or the length of a route. Similarly if you have a capacity dimension you can artificially reduce the capacity value. This will not exactly balance your routes but will ensure all vehicles are used if the values are low enough.

On Wed, Jun 5, 2019 at 4:32 PM Alexander Valdez <alexva...@tamu.edu> wrote:

I am having an issue with the VRP optimization. It is optimizing the routes properly, however, it is not utilizing all of the vehicles. For instance, I have tested with 15 addresses and 4 vehicles and it only uses 3 of the vehicles. Is there any constraint that I can configure to either limit the number of addresses per route, ensure that each vehicle has a route, or distribute the routes evenly? Also, I'm assuming in a much bigger problem (i.e. hundreds of addresses and multiple vehicles) this most likely won't be an issue. Any help would be appreciated.

--
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...@googlegroups.com.

[Alexander Valdez]

I'm still not quite sure how to implement this. Could you possibly provide a basic example? Thanks.

On Wednesday, June 5, 2019 at 9:46:23 AM UTC-5, Vincent Furnon wrote:

You can add a dimension counting the number of stops on a route (transition will be 1 in that case). Then you can constrain the upper bound of the cumul variable at the vehicle's end node to limit the number of nodes assigned to a vehicle (or put that limit in the capacity of the dimension). If you have existing dimensions such as time or distance you can do the same thing on these to limit the duration or the length of a route. Similarly if you have a capacity dimension you can artificially reduce the capacity value. This will not exactly balance your routes but will ensure all vehicles are used if the values are low enough.

On Wed, Jun 5, 2019 at 4:32 PM Alexander Valdez <alexva...@tamu.edu> wrote:

I am having an issue with the VRP optimization. It is optimizing the routes properly, however, it is not utilizing all of the vehicles. For instance, I have tested with 15 addresses and 4 vehicles and it only uses 3 of the vehicles. Is there any constraint that I can configure to either limit the number of addresses per route, ensure that each vehicle has a route, or distribute the routes evenly? Also, I'm assuming in a much bigger problem (i.e. hundreds of addresses and multiple vehicles) this most likely won't be an issue. Any help would be appreciated.

--
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...@googlegroups.com.

[blind.line]

I wrote a short blog post on this.  https://activimetrics.com/blog/ortools/counting_dimension/  Maybe it will help?

James

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/b74e3381-369b-44b5-a0d3-ac1532d9049c%40googlegroups.com.