Solving Time-constrained CVRP with two vehicle types in Google or-tools

Question

I am modeling a Time-constrained CVRP. The problem is to minimize the total travel time (not including the package dropping time) subject to vehicle (delivery) capacity and total time spent (per vehicle) constraints. The package dropping time refers to an additional time to be spent at each node, and the total time spent equals to the travel time plus this additional time. I have the below model that works for a single vehicle-type case. I would like to introduce two-vehicle type concept in there, meaning that I have a set of V1 type vehicles and another set of V2 type vehicles. The only difference of the vehicle-types is the per time cost of travel. Let x denote the per time unit cost of travel by V1, and y denote the per time unit travel cost of V2. How can I design the model so that it incorporates this additional aspect?

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model(n_vehicles):
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = TT #travel time
    data['num_vehicles'] = n_vehicles
    data['depot'] = 0
    data['demands'] = demands
    data['vehicle_capacities'] = vehicle_capacities
    data['service_time'] = service_time
    return data

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:
'.format(vehicle_id)
        route_time = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            tour[vehicle_id].append(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            if previous_index != 0 and previous_index <= len(data['service_time'])-1:
                service_time = data['service_time'][previous_index]
            else:
                service_time = 0
            route_time += (routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id) + service_time)
        plan_output += '{}
'.format(manager.IndexToNode(index))
        tour[vehicle_id].append(manager.IndexToNode(index))
        plan_output += 'Travel time of the route: {} sec
'.format(route_time)
        print(plan_output)
        max_route_time = max(route_time, max_route_time)
    print('Maximum of the route time: {} sec'.format(max_route_time))
    return(tour)

def main(n_vehicles):
    number_of_veh = [n_vehicles][0]
    solution_found = False
    while solution_found == False:
        """Entry point of the program."""
        # Instantiate the data problem.
        data = create_data_model(number_of_veh)

        # Create the routing index manager.
        manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
                                               data['num_vehicles'], data['depot'])
        # Create Routing Model.
        routing = pywrapcp.RoutingModel(manager)

        # Create and register a transit callback.
        def time_callback(from_index, to_index):
            """Returns the time between the two nodes."""
            # Convert from routing variable Index to time matrix NodeIndex.
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            return data['time_matrix'][from_node][to_node]

        transit_callback_index = routing.RegisterTransitCallback(time_callback)

        # Define cost of each arc.
        routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

        # Create and register a transit callback.
        def time_callback2(from_index, to_index):
            """Returns the time between the two nodes."""
            # Convert from routing variable Index to time matrix NodeIndex.
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            if from_node != 0:
                return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
            else:
                return data['time_matrix'][from_node][to_node]

        transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)

        # Add Time constraint.
        dimension_name = 'Time'
        routing.AddDimension(
            transit_callback_index2,
            0,  # no slack
            Operational_hours*3600,  # vehicle maximum travel time
            True,  # start cumul to zero
            dimension_name)
        time_dimension = routing.GetDimensionOrDie(dimension_name)

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

        demand_callback_index = routing.RegisterUnaryTransitCallback(
            demand_callback)
        routing.AddDimensionWithVehicleCapacity(
            demand_callback_index,
            0,  # null capacity slack
            data['vehicle_capacities'],  # vehicle maximum capacities
            True,  # start cumul to zero
            'Capacity')

        # Setting first solution heuristic.
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
        search_parameters.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
        search_parameters.time_limit.FromSeconds(VRP_time_limit)

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

        # Print solution on console.
        if solution:
            tour = print_solution(data, manager, routing, solution)
            solution_found = True
        else:
            print('No solution found! Increasing the vehicle numbers by one and resolving.
')
            solution_found = False
            number_of_veh += 1
    
    return(tour, number_of_veh)

EDIT

Based on @Mizux' answer, I have written the following, which produced the below error.

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model(n_vehicles):
    """Stores the data for the problem."""
    data = {}
    TT = np.array(df.values)
    data['time_matrix'] = TT
    data['num_vehicles'] = n_vehicles
    data['depot'] = 0
    data['demands'] = demands
    if len(vehicle_capacities) < n_vehicles:
        data['vehicle_capacities'] = [vehicle_capacities[0]]*n_vehicles
    else:
        data['vehicle_capacities'] = vehicle_capacities
    data['service_time'] = service_time
    return data

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:
'.format(vehicle_id)
        route_time = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            tour[vehicle_id].append(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            if previous_index != 0 and previous_index <= len(data['service_time'])-1:
                service_time = data['service_time'][previous_index]
            else:
                service_time = 0
            route_time += (routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id) + service_time)
        plan_output += '{}
'.format(manager.IndexToNode(index))
        tour[vehicle_id].append(manager.IndexToNode(index))
        plan_output += 'Travel time of the route: {} sec
'.format(route_time)
        print(plan_output)
        max_route_time = max(route_time, max_route_time)
    print('Maximum of the route time: {} sec'.format(max_route_time))
    return(tour)

def main(n_vehicles, cost1, cost2):
    number_of_veh = [n_vehicles][0]
    solution_found = False
    while solution_found == False:
        Num_of_Class6 = int(n_vehicles*Percent_of_Class6)
        Num_of_Hybrid = n_vehicles - Num_of_Class6
        V = list(range(n_vehicles))
        V2 = list(set(np.random.choice(V, size=Num_of_Class6, replace=False)))
        V1 = list(set(V)-set(V2))
        """Entry point of the program."""
        # Instantiate the data problem.
        data = create_data_model(number_of_veh)

        # Create the routing index manager.
        manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
                                               data['num_vehicles'], data['depot'])
        # Create Routing Model.
        routing = pywrapcp.RoutingModel(manager)
        '''Major Diff Starts Here'''
        # Create and register a transit callback.
        def time_callback(from_index, to_index, cost):
            """Returns the time between the two nodes."""
            # Convert from routing variable Index to time matrix NodeIndex.
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            return data['time_matrix'][from_node][to_node]*cost

        range_extender_callback = partial(time_callback, cost=cost1)
        class6_callback = partial(time_callback, cost=cost2)

        transit_callback_index_V1 = routing.RegisterTransitCallback(range_extender_callback)
        transit_callback_index_V2 = routing.RegisterTransitCallback(class6_callback)
        '''Major Diff Ends Here'''
        # Define cost of each arc.
        for v in V1:
            routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, v)
        for v in V2:
            routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, v)

        # Create and register a transit callback.
        def time_callback2(from_index, to_index):
            """Returns the time between the two nodes."""
            # Convert from routing variable Index to time matrix NodeIndex.
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            if from_node != 0:
                return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
            else:
                return data['time_matrix'][from_node][to_node]

        transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)

        # Add Time constraint.
        dimension_name = 'Time'
        routing.AddDimension(
            transit_callback_index2,
            0,  # no slack
            Operational_hours*3600,  # vehicle maximum travel time
            True,  # start cumul to zero
            dimension_name)
        time_dimension = routing.GetDimensionOrDie(dimension_name)

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

        demand_callback_index = routing.RegisterUnaryTransitCallback(
            demand_callback)
        routing.AddDimensionWithVehicleCapacity(
            demand_callback_index,
            0,  # null capacity slack
            data['vehicle_capacities'],  # vehicle maximum capacities
            True,  # start cumul to zero
            'Capacity')

        # Setting first solution heuristic.
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
        search_parameters.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
        search_parameters.time_limit.FromSeconds(VRP_time_limit)

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

        # Print solution on console.
        if solution:
            tour = print_solution(data, manager, routing, solution)
            solution_found = True
        else:
            print('No solution found! Increasing the vehicle numbers by one and resolving.
')
            solution_found = False
            number_of_veh += 1

    return(tour, number_of_veh, V1, V2)

main(n_vehicles, cost1, cost2)

The output is:

Beginning the Googe OR-tools to solve the problem.
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
 in 
    166     return(tour, number_of_veh, V1, V2)
    167 
--> 168 final_tour,number_of_veh, V1, V2 = main(n_vehicles, cost1, cost2)

 in main(n_vehicles, cost1, cost2)
    104             routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, v)
    105         for v in V2:
--> 106             routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, v)
    107 
    108         # Create and register a transit callback.

~/.local/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py in SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
   5224     def SetArcCostEvaluatorOfVehicle(self, evaluator_index: "int", vehicle: "int") -> "void":
   5225         r""" Sets the cost function for a given vehicle route."""
-> 5226         return _pywrapcp.RoutingModel_SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
   5227 
   5228     def SetFixedCostOfAllVehicles(self, cost: "int64_t") -> "void":

TypeError: in method 'RoutingModel_SetArcCostEvaluatorOfVehicle', argument 3 of type 'int'

Mizux · Accepted Answer

Simply register two transits callbacks (i.e. one per vehicle type)

Then use the overload of AddDimension() to pass an array of registered transit callback index.

e.G. Mizux/vrp_multiple_transit.py

Solving Time-constrained CVRP with two vehicle types in Google or-tools

Answers (2)

Related Questions