OR routing. VRP: Distance from the last locations back to the depot not counted when using arbitrary start and end points for each vehicle and short tours?

[bmorlo]

Hi all,
as I am running both OR routing and other VRP solvers in parallel to each other I encountered the following: When there are only a few locations to be visited, and vehicles start at their individual starting points only to return to the same (0, 0) depot location, the objective value of OR routing is lower by exactly the total distance of the vehicles last client locations in their tours back to the same depot location.
Has anyone had the same issue? Does OR routing NOT count the "last drive" of a vehicle back to its depot?

Thanks for your answer(s)!

Best,
Benedikt

[jmarca]

What you are describing is unclear. Can you give example with numbers and node ids please? JamesOn Apr 21, 2024, at 05:38, bmorlo ***@***.***> wrote: Hi all, as I am running both OR routing and other VRP solvers in parallel to each other I encountered the following: When there are only a few locations to be visited, and vehicles start at their individual starting points only to return to the same (0, 0) depot location, the objective value of OR routing is lower by exactly the total distance of the vehicles last client locations in their tours back to the same depot location. Has anyone had the same issue? Does OR routing NOT count the "last drive" of a vehicle back to its depot? Thanks for your answer(s)! Best, Benedikt —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[bmorlo]

Hi,
let me try to explain it a bit differently. I hope this makes it clearer:

The setting: I reoptimize VRP routes moving forward one location at a time such that in each optimization a vehicles' starting location is set to the location that it visited first in the previous optimization. I'm using "start, end" points with the OR routing library for this.

The issue: OR-routing seems to try to keep the tour lengths of the different vehicles quite similar to each other compared to other solvers. This is even though I did not set the Globalspancoefficient.

Would you have any suggestions on why OR routing does this? Is the Globalspancoefficient set to a default value, internally? I am not using a distance dimension. I am solving a capacitated VRP.

"""Generates optimized routes for the vehicles using the OR Routing solver. Outputs a list of int lists"""
    node_indices_all_tours_current_optimization_or_routing = []

    # Create the routing index manager.
    routing_manager = pywrapcp.RoutingIndexManager(len(_full_distances), len(_functional_vehicle_ids),
                                                   _starting_points_indices, _end_points_indices)
    # Create Routing Model.
    routing_model = pywrapcp.RoutingModel(routing_manager)

    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = routing_manager.IndexToNode(from_index)
        to_node = routing_manager.IndexToNode(to_index)
        return _full_distances[from_node][to_node]

    transit_callback_index = routing_model.RegisterTransitCallback(distance_callback)
    # Define cost of each arc.
    routing_model.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = routing_manager.IndexToNode(from_index)
        return _full_demands[from_node]

    demand_callback_index = routing_model.RegisterUnaryTransitCallback(demand_callback)
    routing_model.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        _vehicle_capacities,  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    # First solution strategy.
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    # Local search strategy.
    search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    # Other parameters.
    search_parameters.time_limit.FromSeconds(_max_runtime_in_seconds)
    # search_parameters.solution_limit = 50000
    search_parameters.log_search = False

    # Solve the problem.
    solution = routing_model.SolveWithParameters(search_parameters)

    # Makes sure that the problem is not infeasible!
    assert routing_model.status() != 6

    # Print solution on console.
    print(f"Objective value OR_Routing: {solution.ObjectiveValue()}")

    total_distance = 0
    for vehicle_idx in range(len(_functional_vehicle_ids)):
        index = routing_model.Start(vehicle_idx)
        # plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        tour_k_indices = []
        while not routing_model.IsEnd(index):
            node_index = routing_manager.IndexToNode(index)
            # plan_output += f" {node_index} -> "
            tour_k_indices.append(node_index)
            previous_index = index
            index = solution.Value(routing_model.NextVar(index))
            route_distance += routing_model.GetArcCostForVehicle(
                previous_index, index, vehicle_idx
            )
        # This prints the last node I think!
        end_index = routing_manager.IndexToNode(index)
        # plan_output += f" {end_index}\n"
        tour_k_indices.append(end_index)
        # plan_output += f"Distance of the route: {route_distance}\n"
        # print(plan_output)
        total_distance += route_distance
        node_indices_all_tours_current_optimization_or_routing.append(tour_k_indices)

    return node_indices_all_tours_current_optimization_or_routing

Best,
Benedikt

[Mizux]

by default, the only transit cost which are ignored is any arc from start to end even if the start and end node do have different location. Aka empty route from start to end are ignored.

note: The is an option to force this arc to be counted as part of the objective value.

[bmorlo]

@Mizux Ah, I think this explains it, actually. Could you point me to this option?

Many thanks!

[Mizux]

I guess it is this, need to double check...

or-tools/ortools/constraint_solver/routing.h

Lines 1243 to 1251 in e32c5e0

	void SetVehicleUsedWhenEmpty(bool is_used, int vehicle) {
	DCHECK_LT(vehicle, vehicles_);
	vehicle_used_when_empty_[vehicle] = is_used;
	}
	bool IsVehicleUsedWhenEmpty(int vehicle) const {
	DCHECK_LT(vehicle, vehicles_);
	return vehicle_used_when_empty_[vehicle];
	}