Vehicle routing problem with multiple time windows and capacity constraint

[rishil shah]

Hi All,

I'm working on a VRP in OR -tools.

I have 70 trucks and 341 locations with a single depot. All orders need to be served from this depot. All locations have an order weight which need to be served.

We have a travel time matrix for all the locations

The locations have multiple time windows which fall at the same time frame but on different days of the week. While some locations may have multiple time windows, others only have a single time window where order can be served, 

The trucks have capacity constraints. They can only take up-to a certain amount of load in lbs.

The trucks also have travel constraints. Trucks can only travel max 'X' hours in day. And after 'X' hours, a break-time of 'Y' hours needs to be provided and then the truck should restart again the next day and continue to serve orders until all orders on its manifest are served.

The objective is to serve all orders and minimize the number of trucks used along with distance traveled.

Firstly, has anyone used OR tools for multi-day optimization. I'm having trouble with this. Does OR tools have a library or any in-built functionality which can allow for easy set-up for running multiple days in a single solver run.?

We have tried a work around for running muli-day optimization by taking an iterative approach but it did not yield optimal results. 

The manual solution is using fewer trucks than the solver output and is also traveling less distance than the the solver results.

Any comments or suggestions are appreciated. 

The geography for the problem is continental US.

Thanks,

Rishil

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

Hi,

(My comments are threaded through your email.)

On Wed, Jul 03, 2019 at 04:23:23AM -0700, rishil shah wrote:
> Hi All,
>
> I'm working on a VRP in OR -tools.
>
> I have 70 trucks and 341 locations with a single depot. All orders need to
> be served from this depot. All locations have an order weight which need to
> be served.
>
> We have a travel time matrix for all the locations
>
> The locations have multiple time windows which fall at the same time frame
> but on different days of the week. While some locations may have multiple
> time windows, others only have a single time window where order can be
> served,

I've done that before in a few different ways, but multi-day and
multiple time windows is possible.

>
> The trucks have capacity constraints. They can only take up-to a certain
> amount of load in lbs.
>
> The trucks also have travel constraints. Trucks can only travel max 'X'
> hours in day. And after 'X' hours, a break-time of 'Y' hours needs to be
> provided and then the truck should restart again the next day and continue
> to serve orders until all orders on its manifest are served.

I just finished doing something like this, and opened an issue related
to breaks. I wanted to implement the US DOT break rules, but had to
do it with dummy nodes for breaks. The standard break functionality
would work okay for one vehicle, but not for multiple vehicles. (It is
a bug that will probably get fixed eventually). I assume since you're
using continental US you're also constrained by the US break rules?

>
> The objective is to serve all orders and minimize the number of trucks used
> along with distance traveled.
>

> Firstly, *has anyone used OR tools for multi-day optimization*. I'm having

> trouble with this. Does OR tools have a library or any in-built
> functionality which can allow for easy set-up for running multiple days in
> a single solver run.?

Yes I've done this. The trick is to keep track of time properly. One
client approached it by only using the operating hours, and "skipping"
off duty/overnight hours. I've done it in my code using 24 hr clock
and standard time libraries to avoid issues around daylight savings
time, etc.

The other issue is how do the demands line up versus your time. In
the longest duration problem I had, the problem was to schedule a
month of operations, knowing in advance that the goal was to visit
some customer locations once per week, others once every two weeks,
and others once per month.

If your demands are stochastic, you'll probably have to store the
current best solution and use a rolling horizon, updating the solution
as new demands come in.

>
> We have tried a work around for running muli-day optimization by taking an
> iterative approach but it did not yield optimal results.
>
> The manual solution is using fewer trucks than the solver output and is
> also traveling less distance than the the solver results.
>
> Any comments or suggestions are appreciated.

I think this is doable, but it might be difficult to program given the
issues with breaks. In my case, inserting dummy nodes for breaks
greatly increased the numbers of nodes in the problem, which means the
solver will have a tough time finding good solutions---the search
space is just too large, I think.

The code I wrote for breaks was for a client, but he said he was fine
with it being open source, so it is on github if you're interested.
Look under my username, jmarca. I think it was called something like
"initial_solution"

Feel free to email me directly if you have questions about that code.

Regards,
James

>
> The geography for the problem is continental US.
>
> Thanks,
> Rishil
>
>
>
>
>
>
>
>

> --
> 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/55d2c7ed-907c-4638-a006-5d170c2a5ede%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.


--

James E. Marca

[rishil shah]

Hi James, 

Thanks for your response.

Yes, we are constrained by US DOT rules and need to provide breaks after on-duty hours.

I've located your code and going through it and will definitely reach out if i have any questions.

Additionally, we are running weekly operations and our demands are not stochastic.

Thanks,

Rishil