VRP model with maximum time constraint

[annis-souames]

I have been able to solve a vrp problem with ortools, but I have to add a new constraint, where the overall time of a route for a given vehicle should always be less then a maximum, obviously in this case I would add a new Dimension for Time and set a maximum equal to the constant T_MAX, however when I print the time of the route I'm using assignment.min(time_var) where time_var = time_dimension.CumulVar(index) , but it shows inaccurate results even though they always stay lower than T_MAX.

I have t(i)(j) which is the time to go from i to j, since the speed is constant, I'm just dividing d(i)(j) which I already have from solving the standard vrp, over the speed constant, I also have s(i) which is the service time (waiting time, it must wait that exact time) for a given node I.

I want to print the time of a route while respecting the constraint t(i)(j) + s(i) < T_MAX

When I print the distance of the route, the time of the route, and the sum of s(i) in the route for each vehicle, and I check by dividing route distance over speed and adding the sum of service time for that route and compare it to route time returned by assignment.Min it's very far.

Here are the related parts of my code:

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    max_route_distance = 0
    sum = 0
    count_v = 0
    time_dimension = routing.GetDimensionOrDie("Time")
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)

        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        route_time = 0
        time_length = 0
        sum_service = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(find_real_index(manager.IndexToNode(index), nodes))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
            #time_length += route_distance/Vitesse + get_service_time(find_real_index(manager.IndexToNode(previous_index),nodes))
            sum_service += get_service_time(find_real_index(manager.IndexToNode(previous_index),nodes))
        time_var = time_dimension.CumulVar(index)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {} km\n'.format(route_distance)
        plan_output += 'Time of route: {} h\n'.format(solution.Min(time_var))
        plan_output += 'Sum of srvc of route: {} h\n'.format(sum_service)
        if route_distance != 0:
            count_v = count_v + 1
        sum += route_distance
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {}km'.format(max_route_distance))
    print('sum of dist: {}'.format(sum))
    print('num of vehicles: ' + str(count_v))


def get_service_time(i):
    # Get service time in index i
    services = read_csv("services.csv")[0]

    print("The service time is " + str(services[i]))
    # pdb.set_trace()
    si = 0
    if i == 0:
        si = 0 # for depot
    else:
        si = int(float(services[i]))
    return si


Vitesse = 42


def main():
    """Solve the CVRP problem."""
    # Instantiate the data problem.
    data = create_data_model()

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

    # Create Routing Model.
    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 = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        #pdb.set_trace()
        time = data['distance_matrix'][from_node][to_node] / Vitesse + get_service_time(find_real_index(from_node,nodes))
        full_time = time

        return int(full_time)
    routing = pywrapcp.RoutingModel(manager)

    tarta = []
    # Create and register a transit callback.

    pdb.set_trace()

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    time_callback_index = routing.RegisterTransitCallback(time_callback)
    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        Vitesse * T,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)

    routing.AddDimension(
        time_callback_index,
        0,  # no slack
        T,  # vehicle maximum travel distance
        True,  # start cumul to zero
        "Time")

    distance_dimension = routing.GetDimensionOrDie(dimension_name)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

    """
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = 60 * 60 * 3  #1 hours
    """
    search_parameters.log_search = True
    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution")

Notes:

• find_real_index is just a helper function I made because of my VRP model (I have duplicates of nodes which should be printed as the same node, so this function does the mapping)
• I have to minimize the distance so cost is related to distance and not the time

So how can I achieve such constraint, are there some functions to use that can achieve t[i][j] + s[i] < T_MAX ?

I can't use slackmax, because I have to wait exacly s[i] hours on node i .