Valid input to CVRPTW

[onecable5781]

Hello,

Following the advice provided #4171, I have been able to get the code https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_time_windows.cc up and running on Windows and Linux (there was a versioning issue on Windows with ZLib which I fixed)

I have a few questions on the sample vrp_time_windows.cc file.

(a) traditional VRPTWs have a vehicle capacity as well as customer demand. The example provided does not seem to take as input customer demand and vehicle capacity. Is there a different canonical example that does this?

(b) Additionally, the solomon instances have a service time at each customer. That does not seem to be taken as input either in the example code.

(c) VRPTWs have to traditionally find out the optimal number of vehicles to use, while the example provided takes
const int num_vehicles = 4;

Is it possible to solve the capacitated vehicle routing problem with time windows (where each customer has a demand, vehicles are capacitated, there is a positive service time at each customer) where the number of vehicles used is not an input and is figured out endogeneously by the algorithm?

Thank you.

[sschnug]

a) See https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_capacity.cc#L150
Basically a (constrained) dimension linked to 1-dimensional transit (we don't care about "a -> moves to-> b", but add capacity due to "leaving a"). Keep in mind: dimensions are additive. You can use dimensions of vrptw example as well as dimensions of cvrp examples (but respect uniqueness -> see return-type of AddDimensionXXX).

It's important to understand the underlying theory of dimensions: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L3017

b) Most solvers (or academic resources) assume that you can embed this service into the transit. Often at departure-time.

You will find this in https://github.com/google/or-tools/blob/stable/examples/cpp/cvrptw.cc#L116

As this is quite common (as well as objective-weight tuning), some of my code looks like:

  Matrix transit_driving_time = Matrix(4, 4);
  transit_driving_time << 1,   2,  3,  4,
                          5,   6,  7,  8,
                          9,  10, 11, 12,
                          13, 14, 15, 16;

  Vector source_service_time = Vector(4);
  source_service_time << 200, 201, 202, 203;

  // callback-functions will be created which add up the variadic arguments and respect the underlying dimensionality (here cardinality = 2) 
  auto [working_time_cb_ptr, working_time_eval_ptr] = tf.construct_callback_evaluator_pair(transit_driving_time * 1, source_service_time * 1);

c) Most solvers (or solver-models) assume that you can give an upper-bound. This is exactly what or-tools is asking for too. The solver can always "not use a vehicle / tour" and with https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L1193 you can add costs for assignments giving the solver an incentive to not use some vehicle.

See also: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L1642

---

Summary: or-tools routing-solver is more a rich VRP solver (and not limited to XX_VRP_YY) -> there is a lot which can be modelled.

Greetings,
Sascha

[jmarca]

Totally off topic, but wow, modern C++ certainly looks different from what I used back in the old days ('96).

…

On Tue, Apr 09, 2024 at 09:20:56AM -0700, sschnug wrote: **a)** See https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_capacity.cc#L150 Basically a (constrained) *dimension* linked to 1-dimensional transit (we don't care about "a -> moves to-> b", but add capacity due to "leaving a"). Keep in mind: dimensions are additive. You can use dimensions of vrptw example as well as dimensions of cvrp examples (but respect uniqueness -> see return-type of AddDimensionXXX). It's important to understand the underlying theory of dimensions: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L3017 **b)** Most solvers (or academic resources) assume that you can embed this service into the transit. Often at departure-time. You will find this in https://github.com/google/or-tools/blob/stable/examples/cpp/cvrptw.cc#L116 As this is quite common (as well as objective-weight tuning), some of my code looks like: ```cpp Matrix transit_driving_time = Matrix(4, 4); transit_driving_time << 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16; Vector source_service_time = Vector(4); source_service_time << 200, 201, 202, 203; auto [working_time_cb_ptr, working_time_eval_ptr] = tf.construct_callback_evaluator_pair(transit_driving_time * 1, source_service_time * 1); ``` **c)** Most solvers (or solver-models) assume that you can give an upper-bound. This is exactly what or-tools is asking for too. The solver can always "not use a vehicle / tour" and with https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L1193 you can add costs for assignments giving the solver an incentive to not use some vehicle. See also: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L1642 Greetings, Sascha -- Reply to this email directly or view it on GitHub: #4173 (comment) You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

-- James E. Marca Activimetrics LLC

[onecable5781]

@sschnug Based on your response, I am working on trying to incorporate it into my context. I am still unclear how to incorporate your suggestions fully. I have figured out the capacity part using the example you gave. I am now trying to incorporate the service time part.

Suppose there is a 2 customer problem with 3 nodes, 0 (depot), 1 and 2
Say all purely travel times are 1 unit. Service time at 1 and 2 are 1 unit also.
Say the time window at 1 is [0,1] and the time window at 2 is [2,3]. Suppose there is ample vehicle capacity so it is a purely time window constrained problem. The optimal solution is 0 -> 1 -> 2 -> 0 for a total minimum cost (where cost = transit time without including service time) of 3. The vehicle will reach customer 1 at time 1, which is also the closing time windows (so it is feasible). Then, it services at 1 for 1 time unit. At time 2, it leaves for 2 and arrives at 2 at time 3 which is feasible as it is the closing time window. It services 2 for 1 time unit. Then, at time 4 it begins going back to the depot and reaches depot at time 5.

Based on this, I have:

    struct DataModel {
		const std::vector<std::vector<int64_t>> time_matrix{
			{0, 1, 1},
			{1, 0, 1},
			{1, 1, 0}};
		const std::vector<std::pair<int64_t, int64_t>> time_windows{
			{0, 999}, // depot
			{0, 1},	  // 1
			{2, 3}	  // 2
		};
		// [START demands_capacities]
		const std::vector<int64_t> demands{0, 1, 1};
		const std::vector<int64_t> vehicle_capacities{999999};
		// [END demands_capacities]
		// Start service time at each node
		const std::vector<int64_t> service_times{0, 1, 1};
		const int num_vehicles = 1;
		const RoutingIndexManager::NodeIndex depot{0};
	};

Now, the only place where time_matrix is referred to in the template I am working with are:

or-tools/ortools/constraint_solver/samples/vrp_time_windows.cc

Lines 118 to 119 in 5f7eabb

	RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles,
	data.depot);

and

or-tools/ortools/constraint_solver/samples/vrp_time_windows.cc

Line 135 in 5f7eabb

return data.time_matrix[from_node][to_node];

Should I be doing in place of the line above the following?

return data.time_matrix[from_node][to_node] + data.service_times[from_node];

This does not appear right to me because in the traditional VRPTW, if a vehicle arrives at a customer before the starting/opening of the time window, it has to wait until the starting time windows before service can start. If purely transit time and service times are added together (if I understand your suggestion correctly), then, the algorithm will not be correct because it will not be able to account for this waiting time.

Could I request you to clarify?

Thank you.

[sschnug]

Waiting is handled by dimension-slacks. Read

or-tools/ortools/constraint_solver/routing.h

Line 677 in 5f7eabb

/// Methods to add dimensions to routes; dimensions represent quantities

carefully.

Optimizing travel-time, but respecting time-windows incl. travel-time + service-time means: two different transit-evaluators:

• SetArcCostEvaluatorOfAllVehicles(my_function_which_has_no_service_time) for optimization-costs
• AddDimension(my_function_which_has_service_time) for respecting constraints

Understanding those components, you can usually express your own semantics.

• Howewer: usually peoples semantics are all about: decide "node-service+immediate-departure time".
• Or straight from the next-best academic resource: "The travel-time t_ij includes a service time at node i, and a vehicle is permitted to arrive before the opening of the time window, and wait at no cost until service becomes possible, but it is not permitted to arrive after the latest time window. N"
  • I don't see the issue here with whats possible through dimensions
  • In some more complex cases (but i don't see it here) with driver-breaks, one might need additional info to inverse-transform the accumulation due to reasoning needs, but there is functionality for that too ->

    or-tools/ortools/constraint_solver/routing.h

    Line 3269 in 5f7eabb

    /// A break may take place before the start of a vehicle, after the end of

[onecable5781]

Got it (mostly)

Few final queries pertaining to the VRPTW (although I fully realize that the idea of dimension is much more powerful than this particular specialization):

or-tools/ortools/constraint_solver/samples/vrp_time_windows.cc

Lines 147 to 151 in 5f7eabb

	routing.AddDimension(transit_callback_index, // transit callback index
	int64_t{30}, // allow waiting time
	int64_t{30}, // maximum time per vehicle
	false, // Don't force start cumul to zero
	time);

consciously does NOT force cumul(0) to 0 for the starting node (depot). Should this not be set to 0 since we are indeed tracking the time of a vehicle beginning from 0 at the depot? Semantically, what does the above line do? To me the meaning seems to be:

The maximum (cumul) duration of a route can be 30 time units (but the starting value of cumul(0) is undefined), and the maximum waiting time at a node (not the cumulative waiting time thus far) can be 30 time units.

Is this correct interpretation?

Also, given:

cumul(j) = cumul(i) + transit(i,j) + slack(i), shouldn't slack(0) be initialized (to zero?) somewhere for the depot? Additionally, for the VRPTW, where exactly is slack(j) calculated if cumul(j) < OpeningTimeWindow(j) ? Internally, is

slack(j) = max(0, OpeningTimeWindow(j) - cumul(j) );

The way I picturize it, cumul(j) is essentially the arrival time at customer j.

I am confused about this because in the earlier suggestion you made for handling demand,

or-tools/ortools/constraint_solver/samples/vrp_capacity.cc

Lines 158 to 163 in 5f7eabb

	routing.AddDimensionWithVehicleCapacity(
	demand_callback_index, // transit callback index
	int64_t{0}, // null capacity slack
	data.vehicle_capacities, // vehicle maximum capacities
	true, // start cumul to zero
	"Capacity");

the cumul(0) value is indeed set to 0 and this makes sense and the maximum slack is 0.

So, cumul(j) = cumul(i) + transit(i,j) and this is perfectly correct from a demand point of view.

[sschnug]

The maximum (cumul) duration of a route can be 30 time units (but the starting value of cumul(0) is undefined), and the maximum waiting time at a node (not the cumulative waiting time thus far) can be 30 time units.

Yes. Undefined in a sense, that it's always nonnegative by design! Waiting/slack is about upper-bounding the variable in-between transits. max is an upper-bound for each visit-point / accumulation-step. (usually with a max at the end; but negative transits are possible too! It's important howewer, that accumulations are lower-bounded by 0 by design too).

Cumul + Slacks are variables. Transits are constants!

Should this not be set to 0 since we are indeed tracking the time of a vehicle beginning from 0 at the depot?

Depends on what you like. In some use-cases, the driver is not working until he is needed. Than it might make a difference if his vehicle departs at 8:00 or 12:00, when both lead to feasible tours. Fixing 0 might lead to waiting-time not needed when leaving later. If minimizing waiting-time or working-time in general is one of your objectives, fixing might make no sense (assuming worker work-time assignmen-freedom).

Additionally, for the VRPTW, where exactly is slack(j) calculated if....

That's complicated and take the following with a grain of salt.

In general, everything we talk about are discrete variables in a constraint-programming sense. All those model-components (constraints, objectives) and decisions (e.g. i -> j) will lead to propagation on those variables which, for example due to some time-window at j, will remove valid instantiations of those variable-domains (aka propagation; see CP introduction) of those variables (cumul, slack, ...).

So in general, slack is a variable in [0, max-slack=30] and decisions/constraints might lead to removal of ranges from it (e.g. [0, 30] -> [7, 30]; we need to wait >= 7 because of TW.earliest of j) (or maybe holes -> multiple not necessarily continuous ranges; but let's ignore that).

Propagators therefore are removing invalid values / instantiations from this domain as a consequence of past decisions.
But as long as the domain is not a singleton (only one possible instantiation remaining), we need an additional decision-maker here to select one. Also: if any domain is empty, it's infeasible and we need to reconsider past decisions (imagine a case where you need to wait an hour=60, but max-slack is 30 -> solver won't find a solution but can't really tell you why!).

The solver will do it ("we need an additional decision-maker here to select one"). I cannot tell you in detail how and when (i'm not a ortools dev), but you should assume, that it's driven by your model given, especially the following 3 candidates come to mind which will potentially influence the slack-assignment decisions:

• span costs
• global span costs -> https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_global_span.cc#L141
• finalizers -> https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_time_windows.cc#L168
  • those are a bit special and imho only serve exactly this purpose: hint selection-direction where there is no other incentive (aka free variable)
  • can't tell you much more and those are a bit of a mystery to many people; for now i just consider adding them whenever i have a "as early as possible" dimension; like in the linked example

It's also absolutely possible, that there are customized decision-makers during construction-phase (

or-tools/ortools/constraint_solver/routing_enums.proto

Line 25 in 5f7eabb

message FirstSolutionStrategy {

) due to some special semantics (e.g. insertion-heuristics).

[onecable5781]

@sschnug

I have a query using an example we have referred to in this thread:

or-tools/ortools/constraint_solver/samples/vrp_time_windows.cc

Lines 51 to 52 in 5f7eabb

	const std::vector<std::pair<int64_t, int64_t>> time_windows{
	{0, 5}, // depot

I would like to impose a closing time window for the depot, which semantically means that the vehicle on its return back to the depot should be within this closing time window.

My interpretation of the lines quoted above was that this closing time window is 5. However, that does not seem to be the case and on running that code, there are very well feasible routes discovered that respect all other time windows as specified in lines subsequent to the ones I have quoted, but not the closing time window at the depot.

For instance, one of the routes returned back in the solution is:

I0000 00:00:1712921593.972883   18429 main.cpp:87] Route for vehicle 0:
I0000 00:00:1712921593.972972   18429 main.cpp:97] 0 Time(0, 0) -> 9 Time(2, 3) -> 14 Time(7, 8) -> 16 Time(11, 11) -> 0 Time(18, 18)

where the depot is reached at 18 time units on the vehicle's return.

or-tools/ortools/constraint_solver/samples/vrp_time_windows.cc

Lines 161 to 165 in 5f7eabb

	for (int i = 0; i < data.num_vehicles; ++i) {
	const int64_t index = routing.Start(i);
	time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
	data.time_windows[0].second);
	}

The above line is where data.time_windows[0].second is referred to. Could you suggest how one can implement a closing time window at the depot and also what the latter snippet of lines mean? What exactly is data.time_windows[0].second representing here?

Thank you.

[Mizux]

const int64_t index = routing.End(i); will give you the solver's depot end node index for vehicle i.

data.time_windows[0] i guess here it represent a std::pair<int64_t, int64_t> at user index 0 i.e. the TW for the depot.
you can reuse the same pair for "end depot" or have an other user index to store the TW for the end node.