VRP that uses maximum allowed days

704
4
Jump to solution
08-23-2018 11:48 AM
LouwrensCronje
New Contributor II

Hello All,

Thanks for accepting me to the community. This is my first post - please be gentle!

I NEED YOUR HELP

I have the following scenario:

- One week to run a distribution for some goods

- Vehicles to start and end each day at the same depot (cannot take a break on route)

- StartWindowTime = 8am and EndWindowTime = 12pm i.e. 4hr available every day to deliver

- Each order point is only required to be serviced once

How do I configure my VRP in order to use the least amount of vehicles across the 5 days?

Regards,

Louwrens 

0 Kudos
1 Solution

Accepted Solutions
HeatherMoe
Esri Contributor

Hi Louwrens,

I think if your orders do not have any day of the week constraints and you are just trying to minimize the number of routes that are needed for this we can simplify your problem quite a bit by taking the "day" out of the planning process and deciding afterwards which routes will be run on each day.  

So for this on the orders you can just put the times (8am to 12pm) in without the date if using ArcMap or a GP tool to solve the problem.  If using a rest request then give all of the orders the same day and time when converting your problem to Milliseconds since epoch.  If the routes need to be contained within that same time frame you could even eliminate the order time windows all together and just rely on the start time of the route and the max total time values to restrict the work day to 4 hours.  Having the time windows is really just necessary if you allow the drivers some extra time to get from the depot to the first order or back after the last depot.  For example if they leave the depot at 7:30 and can get back at 12:30.

For the routes, put in essentially five copies of the routes that you have for one day.  So for example if you have 6 vehicles available to you, then you will put in 30 total routes in the problem.  If you are able to get vehicles on demand to be able to cover all of the orders then you want to make sure you have enough vehicles in the problem to be able to get to all of the orders.  For example if your drivers can get to 20 stops in a day and you have 600 orders, you would need a minimum of 30 vehicles in the model but to be on the safe side add a few extra.  The solver will naturally try to minimize the number of vehicles used but it does have a multi value objective with other costs such as time and distance so you can add a fixed cost to the routes which would make the cost of starting a new route more expensive and less likely for the solver to add unnecessary routes.  

This set up would divide all of the orders across the routes without regard to which day the route is to be driven.  Once you have the routes with orders, you can then decide which of them will be done on a specific day and divide the work across your five day time horizon.  

If I am missing a requirement for pre-specifying the day for routes then let me know and we can work through ways to get the problem to work.  

View solution in original post

4 Replies
HeatherMoe
Esri Contributor

Hi Louwrens,

Welcome to GeoNet! I have a few questions to help clarify the problem that you are trying to solve.  Your question title is asking about using the maximum allowed days but then ask how to configure it to use the minimum number of vehicles across all 5 days.  I can think of two ways to interpret this and maybe neither of them is correct so help point me in the direction you are actually needing.  The first way I see this is that you want to minimize the number of vehicles used each day independent of the other four days in your five day plan and therefore minimize how many total vehicle days are needed (say for example 2 vehicle for day 1, 3 for day 2, 1 for day 3, 3 for day 4, and 3 for day 5).  The second way I can interpret this is you want to use the minimum number of vehicles but if you use say 3 on the first day you want to use 3 every day for the rest of the week.  And what you are wanting to know is what is the minimum number of trucks you need to "own" to get the whole weeks worth of work done.  Are either of these two interpretations correct?  

Another question I have is on the orders.  You mention only needing to visit them once but do they have day of the week constraints on them such as it must be visited on day2?  If so is their a day of the week constraint on all orders or only some and are the constraints for a specific day or for a subset of days?

In the mean time this tutorial is a great reference for getting you started with the VRP set up.  Exercise 7: Servicing a set of orders with a fleet of vehicles—Help | ArcGIS Desktop  

LouwrensCronje
New Contributor II

Thank you very much for the quick reply Heather!

Your first part of the question - the number of vehicles used may differ. I do not have to use the same vehicles for the whole week. This is directly related to the demand for each individual depot.

Second part of the question - the order point can be serviced on any day of the week only once. Hence my difficulty to set up the order attributes (time windows)

0 Kudos
HeatherMoe
Esri Contributor

Hi Louwrens,

I think if your orders do not have any day of the week constraints and you are just trying to minimize the number of routes that are needed for this we can simplify your problem quite a bit by taking the "day" out of the planning process and deciding afterwards which routes will be run on each day.  

So for this on the orders you can just put the times (8am to 12pm) in without the date if using ArcMap or a GP tool to solve the problem.  If using a rest request then give all of the orders the same day and time when converting your problem to Milliseconds since epoch.  If the routes need to be contained within that same time frame you could even eliminate the order time windows all together and just rely on the start time of the route and the max total time values to restrict the work day to 4 hours.  Having the time windows is really just necessary if you allow the drivers some extra time to get from the depot to the first order or back after the last depot.  For example if they leave the depot at 7:30 and can get back at 12:30.

For the routes, put in essentially five copies of the routes that you have for one day.  So for example if you have 6 vehicles available to you, then you will put in 30 total routes in the problem.  If you are able to get vehicles on demand to be able to cover all of the orders then you want to make sure you have enough vehicles in the problem to be able to get to all of the orders.  For example if your drivers can get to 20 stops in a day and you have 600 orders, you would need a minimum of 30 vehicles in the model but to be on the safe side add a few extra.  The solver will naturally try to minimize the number of vehicles used but it does have a multi value objective with other costs such as time and distance so you can add a fixed cost to the routes which would make the cost of starting a new route more expensive and less likely for the solver to add unnecessary routes.  

This set up would divide all of the orders across the routes without regard to which day the route is to be driven.  Once you have the routes with orders, you can then decide which of them will be done on a specific day and divide the work across your five day time horizon.  

If I am missing a requirement for pre-specifying the day for routes then let me know and we can work through ways to get the problem to work.  

LouwrensCronje
New Contributor II

Hello Heather,

Thank you for the time to give such a detailed description. I appreciate your effort.

I modeled it in this manner and the results were acceptable, thank you.

Regards,

Louwrens

0 Kudos