Additional materials

In addition to vehicle time windows, vehicles may also have break time windows in the middle of their shift. If the time windows represent a driver’s working hours in a day, the break time window may represent their lunch break . The integer representation is consistent with the time windows. Given raw input data is in UTC timestamp, if a vehicle is working a shift of 9:00 am - 6:00 pm, then in a 24-hour period, this is equivalent to [540, 1080]. If the vehicle has a break from 1 pm - 1:30 pm, then the break time window would be [780, 810].

This is represented in a list separate from vehicle time windows. Both vehicle_time_windows and vehicle_break_time_windows are both nested lists. The length of both lists is equivalent to the size of the fleet, and each item in the list is a nested list that represents time windows. Note that in vehicle_time_windows each vehicle must have only one time window, but in vehicle_break_time_windows each vehicle can have multiple time windows (i.e. a driver can have multiple breaks in one shift).

For a fleet of three vehicles, these lists would be:

Let’s say that the first driver has 2 breaks in a shift, but the rest of the drivers have only one.

Additionally, break durations within the break time windows can be specified. For example, a vehicle’s break time is 12pm to 2pm, which can be represented as [720, 840]. Setting break duration to 45 minutes means that the driver can take a 45 minute break sometime in the middle of the indicated break time window. The length of this list is equivalent to the number of vehicles in the fleet.

Note: cuOpt 23.08 release supports only one break window per vehicle although the underlying representation supports multiple break windows per vehicle

Prior to cuOpt 23.08, the cuOpt solver returned status 1 along with an empty solution for infeasible solves. An infeasible solve is the case when one or more constraints could not be met and the resulting solution is therefore infeasible with respect to meeting constraints, whereas a feasible solve meets all specified constraints. cuOpt 23.08 supports both infeasible and feasible solves and returns the solution found in both cases. For an infeasible solve, the solver returns the best solution which is closest to feasibility. The solver also returns which constraints were violated by the solution returned for the infeasible solve.

Determinism in this context refers to repeatability of solver results under unchanging inputs. Variance here refers to the magnitude of the spread between the best and worst candidate results (based on the multi-variable cost metric) over multiple runs on the same input. cuOpt managed service under the hood employs heuristics and estimates the solver time based on size of inputs with a ceiling value. In general, the longer the solver time, the less spread in variability of results over multiple runs on the same input and closer it asymptotically approaches to a deterministic and repeatable solution.

On Homberger CVRPTW benchmarks, 84.21% of the runs produce the identical optimal fleet size while remaining produce solutions with +/- 1 vehicle. For those 84.21% cases, the average standard deviation in cost is 2.19%, and the maximum deviation is 5.18%

Usecase

Can the cuOpt solver handle scenarios where the total demand surpasses the total capacity of the fleet, requiring for multiple trips to the depot?

Suggestion

The cuOpt solver accommodates this scenario using its Pickup and Delivery (PDP) feature. To implement this:

• Create N pickup orders that start from customer order locations

• Pair these with N corresponding delivery orders that head to depot

• If you are incorporating time windows:

  • Ensure the pickup time windows accurately reflect real-world delivery constraints.

  • Make the time windows for delivery orders (to the depot) broad enough to guarantee fit with whatever delivery schedule turns out to be most efficent

• For users of the cuOpt managed service, you would need to define this pairing using the pickup_and_delivery_pairs field in your task data.