Multiple time windows for the same stop

[TeodoraBogdan]

Hello!
I have an input with one vehicle. It starts the shift today at 11:00AM and ends tomorrow at 9:00 PM.
One of the stops have a time window between 5:00 PM and 11:00 PM. This means that the stop can be visited today between 5:00PM-11:00PM or tomorrow between 5:00PM-9:00PM (vehicle's end time).

I am using RemoveIntervals() and on parallel threads I am searching for a solution using combinations of FirstSolutionStrategy and LocalSearchMetaheuristic_Value:
LOCAL_CHEAPEST_INSERTION
PARALLEL_CHEAPEST_INSERTION
SEQUENTIAL_CHEAPEST_INSERTION
PATH_MOST_CONSTRAINED_ARC
PATH_CHEAPEST_ARC
LOCAL_CHEAPEST_ARC

LocalSearchMetaheuristic_Value_AUTOMATIC
LocalSearchMetaheuristic_Value_GREEDY_DESCENT

This is how i set the time window:

	int32 numberOfDays = maxEnd / DAY_IN_MILISECONDS;
	for (int32 i = 0; i < manager->num_nodes(); i++)
	{
		int32 nodeIndex = manager->IndexToNode(i).value();
		if (timeWindows.at(nodeIndex).first != 0 && timeWindows.at(nodeIndex).second != GP_INT_MAX)	//default values
		{
			time_dimension.CumulVar(i)->SetRange(0, (numberOfDays + 1) * DAY_IN_MILISECONDS);

			for (int32 day = 0; day <= numberOfDays; day++)
			{
				int32 dayInMilisec = day * DAY_IN_MILISECONDS;

				int32 twS = timeWindows.at(nodeIndex).first + dayInMilisec;
				time_dimension.CumulVar(i)->RemoveInterval(dayInMilisec, twS);

				int32 twE = timeWindows.at(nodeIndex).second + dayInMilisec;
				int32 nextDayInMilisec = (day + 1) * DAY_IN_MILISECONDS;
				time_dimension.CumulVar(i)->RemoveInterval(twE, nextDayInMilisec);
			}
		}
	}

Is there a first solution that works best with RemoveIntervals()? I don't want to need to use GUIDED_LOCAL_SEARCH because it needs a maximum calculation time and I don't want to set that, because it can be too big or too small depending on the input. I want the algorithm to decide how much time it needs.

Before, I was using epoch time, which meant that each stop had a single time window and the solutions were returned much faster (x5 times faster).

Do you know any approach on this; why is slower now and how can it be improved?

[sschnug]

It seems you already did exploit portfolio search to improve first-solution heuristics robustness. As insertion-style heuristics, enabled for you, are probably the most prominent for vrpTW problems, i don't see an easy solution.

If you have your own heuristic, you can try to warm-start from those, but warm-starting does need to do some work too (as only a linear order is provided and solver needs to shift things around).

I don't want to need to use GUIDED_LOCAL_SEARCH because it needs a maximum calculation time and I don't want to set that, because it can be too big or too small depending on the input.

I would say it's not uncommon to implement stopping-conditions like "no new incumbent for 1 minute" -> STOP or similar things using callbacks. So you can be adaptive despite providing an a-priori upper time-limit!

[TeodoraBogdan]

I improved the code by using only one RemoveInterval for each day. But it takes about 3 seconds each call of RemovalInterval, which is too much.

	for (int32 i = 0; i < manager->num_nodes(); i++)
	{
		int32 nodeIndex = manager->IndexToNode(i).value();
		int32 twS = timeWindows.at(nodeIndex).first;
		int32 twE = timeWindows.at(nodeIndex).second;

		if (twS != 0 && twE != GP_INT_MAX)	//default values
		{
			time_dimension.CumulVar(i)->SetRange(twS, twE + numberOfDays * DAY_IN_MILISECONDS);

			for (int32 day = 1; day <= numberOfDays; day++)
			{
				twS += DAY_IN_MILISECONDS;
				time_dimension.CumulVar(i)->RemoveInterval(twE, twS);
				twE += DAY_IN_MILISECONDS;
			}
		}
	}

Do you know any other approach for setting multiple possible intervals for a stop?

[sschnug]

The code behind RemoveInterval does indeed look rather unoptimized (i think there is even a TODO docstring; it's basically looping over each value such that the alternative API based on a vector will be somewhat equivalent), but 3 seconds still sounds like too much.

• Did you profile it correctly?
• Are you using an optimized/release-build? (i could believe 3 sec for debug-mode)

Apart from that, a question:

• Is the code correct?
  • time_dimension.CumulVar(i)->SetRange(twS, twE + numberOfDays * DAY_IN_MILISECONDS); implies twS < twE
  • time_dimension.CumulVar(i)->RemoveInterval(twE, twS); implies twE < twS
  • ???

Assuming the code is correct, one approach is trim down your variable domains. There is some constraint-programming tech involved and it makes a huge difference if your domain is defined on hours (e.g. 1 week = 168 hours = 168 values) vs. milliseconds (e.g. 1 week = 604800000 ms).