No solution found when forcing all vehicles to be used

[TeodoraBogdan]

Hello!

I have an input with 400 stops + 1 stop as departure and 8 vehicles. I wanted to combine different types of vehicles (cars and trucks for example), so I have different matrices for each vehicle type. I want to force all the vehicles to be used, but I get no solution.
I set the matrices in the following way:

for (int32 vehicle = 0; vehicle < manager->num_vehicles(); vehicle++)
{
	timeEvaluatorIndices.push_back(m_routing->RegisterTransitCallback(
		[this, vehicle](int64 from_index, int64 to_index) -> int64 {
			auto from_node = manager->IndexToNode(from_index);
			auto to_node = manager->IndexToNode(to_index);

			int64 time = 0;

			if (!m_vServiceTime.empty())
				time = m_vServiceTime[from_node.value()];
			time += m_timeMatrices[m_vehicleTypes[vehicle]][from_node.value()][to_node.value()];
			return time;
		}));

	distanceEvaluatorIndices.push_back(m_routing->RegisterTransitCallback(
		[this, vehicle](int64 from_index, int64 to_index) -> int64 {
			auto from_node = manager->IndexToNode(from_index);
			auto to_node = manager->IndexToNode(to_index);

			return m_distanceMatrices[m_vehicleTypes[vehicle]][from_node.value()][to_node.value()];
		}));
}
m_routing->AddDimensionWithVehicleTransitAndCapacity(timeEvaluatorIndices, m_stops->GetMaxWaitTime(), m_vehicles->GetEndTimes(), false, "Time");
m_routing->AddDimensionWithVehicleTransitAndCapacity(distanceEvaluatorIndices, 0, m_vehicles->GetMaxDistForVehicles(), true, "Distance");


//set the cost function of the solution and try to minimize their values
const operations_research::RoutingDimension* dimension;
std::vector<int> evaluator;
if (*optimized by time*)
{
	dimension = m_routing->GetMutableDimension("Time");
	evaluator = timeEvaluatorIndices;
}
else
{
	dimension = m_routing->GetMutableDimension("Distance");
	evaluator = distanceEvaluatorIndices;
}

for (int32 vehicle = 0; vehicle < manager->num_vehicles(); vehicle++)
{
	m_routing->AddVariableMinimizedByFinalizer(dimension->CumulVar(manager->IndexToNode(manager->GetEndIndex(vehicle)).value()));
}

This is how I set the minimum and maximum number a vehicle can visit:

	std::vector<int> minNrStops = m_vehicles->GetMinNrOfStopsForVehicles();
	std::vector<int> maxNrStops = m_vehicles->GetMaxNrStopsForVehicles();
	if (!minNrStops.empty() || !maxNrStops.empty())
	{
		//return 1 for each stop
		const int32 nrStopsCallback = m_routing->RegisterUnaryTransitCallback([](int64 from_index)->int64 { return 1; });

		int maxTransits = manager->num_nodes();

		m_routing->AddDimension(nrStopsCallback, 0, maxTransits, true, "NrStops");

		const operations_research::RoutingDimension* nrStopsDimension = m_routing->GetMutableDimension("NrStops");

		for (int32 i = 0; i < m_vehiclesSize; i++)
		{
			int minNrOfStops = !minNrStops.empty() ? minNrStops.at(i) : 0;
			int maxNrOfStops = !maxNrStops.empty() ? maxNrStops.at(i) : m_stopsSize;

			//if the route is round, the range is +1 because the vehicle will return to the start point by default
			if (minNrOfStops != 0)
			{
				minNrOfStops += 1;
				nrStopsDimension->CumulVar(manager->GetEndIndex(i))->SetMin(minNrOfStops);
			}
			if (maxNrOfStops < maxTransits)
			{
				maxNrOfStops += 1;
				nrStopsDimension->CumulVar(manager->GetEndIndex(i))->SetMax(maxNrOfStops);
			}
		}
	}

For my case, I set the minNrOfStops to 2, which means 2 transits 1 from depot to location1 and the other one from location1 to depot.

Can anyone tell me what am I doing wrong?

[Mizux]

IMHO, The problem is the first solution is built by adding node iteratively i.e. at beginning all vehicles have an empty route....
which is out of the range of the num stop allowed i.e. your model is infeasible when solver try to build little by little a first solution.

Try to set a RoutingDimension::SetCumulVarSoftLowerBound instead...

[TeodoraBogdan]

And should I set nrStopsDimension->SetCumulVarSoftLowerBound(vehicleEnd, 1, 100000) or nrStopsDimension->SetCumulVarSoftLowerBound(vehicleEnd, 2, 100000)? I mean the "lower_bound" in this case is the number of transits or the number of stops?

[TeodoraBogdan]

I tried setting different lower bounds, even 5 and a penalty of int32 max and int64 max, but it uses only 2 vehicles each time.
Do you have other ideas?

[TeodoraBogdan]

I also added SetFixedCostOfAllVehicles(0), but still no change. It created just 2 routes.
Also I put SetCumulVarSoftLowerBound() on the distance dimension, but no change

[TeodoraBogdan]

I tried with Guided local search, still no difference

[TeodoraBogdan]

I have the version 9.5. Do you think that a newer version will solve this issue?

[TeodoraBogdan]

It works with 4,5,6 or 7 vehicles. But with 8 it doesn't work. And I have a big end time set, so it should work.

[Mizux]

possibly, VRP is NP-Hard and routing team may tweak so internal heuristic according to internal living test set so from one version to another GLS may have some behavior changes, usually improving the mean time but could be bad for a specific type of problem/model.