CVRP with delivery time

[Taner Cokyasar]

I am modeling a CVRP with a single vehicle type. The objective is to minimize the travel time. Total time (travel + delivery/service at nodes) is capped by 36,000 for each vehicle. Each node demands 3 units of deliveries, and the vehicle capacity is 120 units for each vehicle.

I programmed it in Python following the CVRP examples. The code is below. As a newbie, I have the below listed questions:

1. Time_matrix data seems to be converted to integers though I use floats. Is it possible to change this?

2. How can I add a node-dependent delivery/service time that does not count on to the objective function? In other words, I would like the service time to be counted towards the total time constraint but not in the objective.

3. When I have use a time limit of 120 (as seen below), I got a solution that violates the vehicle capacity constraint by 1 unit, i.e., one of the vehicles delivered 121 packages. Is it possible to get a feasible solution after the time limit is reached?

4. Is it possible to receive a quick, (meta-) heuristic, feasible solution?

5. Is there a way to consider the number of vehicles a variable in my problem setting?

6. Is there an option to see the optimality gap (or at least gap from the lower bound)?

7. Is there a solver selection option, like Gurobi, CPLEX, etc.?

8. Is there a way to see the logs while solving?

9. Up to how many nodes should I expect a good solution in this setting? I understand it depends on the data, and so on; but, I am just chasing an estimate.

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

def create_data_model():

    """Stores the data for the problem."""

    data = {}

    TT = np.array(df.values)

    data['time_matrix'] = TT

    data['num_vehicles'] = 15

    data['depot'] = 0

    data['demands'] = [1]*len(TT)

    data['vehicle_capacities'] = [120]*data['num_vehicles']

    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 {}:\n'.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))

            route_time += routing.GetArcCostForVehicle(

                previous_index, index, vehicle_id)

        plan_output += '{}\n'.format(manager.IndexToNode(index))

        tour[vehicle_id].append(manager.IndexToNode(index))

        plan_output += 'Travel time of the route: {} sec\n'.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)

"""Entry point of the program."""

# Instantiate the data problem.

data = create_data_model()

# 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)

# Add Distance constraint.

dimension_name = 'Time'

routing.AddDimension(

    transit_callback_index,

    0,  # no slack

    36000,  # vehicle maximum travel time

    True,  # start cumul to zero

    dimension_name)

distance_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(120)

# Solve the problem.

solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.

if solution:

    tour = print_solution(data, manager, routing, solution)

else:

    print('No solution found !')

Best,

Taner

[blind.line]

In-line response below, but a lot of these questions are answered over and over again i this forum, and there are lots of excellent examples in the github source code repo. I recommend doing the work. 

On May 15, 2021, at 00:15, Taner Cokyasar <tanerc...@gmail.com> wrote:

I am modeling a CVRP with a single vehicle type. The objective is to minimize the travel time. Total time (travel + delivery/service at nodes) is capped by 36,000 for each vehicle. Each node demands 3 units of deliveries, and the vehicle capacity is 120 units for each vehicle.

I programmed it in Python following the CVRP examples. The code is below. As a newbie, I have the below listed questions:

1. Time_matrix data seems to be converted to integers though I use floats. Is it possible to change this?

No it must be integers

If you want more precision, use seconds for time, meters or centimeters for distance…

2. How can I add a node-dependent delivery/service time that does not count on to the objective function? In other words, I would like the service time to be counted towards the total time constraint but not in the objective.

Make a dimension for it but don’t call SetArcCostEvaluatorOfAllVehicles for the dimension. If you copy-paste code, make an effort to understand what each line is doing. 

3. When I have use a time limit of 120 (as seen below), I got a solution that violates the vehicle capacity constraint by 1 unit, i.e., one of the vehicles delivered 121 packages. Is it possible to get a feasible solution after the time limit is reached?

Not possible to get a violation of a constraint, by definition, so check your code. You either didn’t set the constraint, or there is a rounding error you’ve missed. 

4. Is it possible to receive a quick, (meta-) heuristic, feasible solution?

Yes, simplify your problem. The solver is not magical. Switch to hours for time, kilometers for distance, and relax constraints, etc. 

5. Is there a way to consider the number of vehicles a variable in my problem setting?

Add a cost for using each vehicle to minimize vehicles. Look through this forum or the examples. 

6. Is there an option to see the optimality gap (or at least gap from the lower bound)?

No idea. I think you can do that in a solution callback. 

7. Is there a solver selection option, like Gurobi, CPLEX, etc.?

Apparently, but I’ve no experience with that. 

8. Is there a way to see the logs while solving?

Yes there is an api setting. Read the examples or grep for “log”

9. Up to how many nodes should I expect a good solution in this setting? I understand it depends on the data, and so on; but, I am just chasing an estimate.

A lot. Probably more than you would expect. 

Try it and see. 

Regards, 

James

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e3f4621d-79e2-4f33-868d-f5b94a18110dn%40googlegroups.com.

[Mizux Seiha]

Please add link when you cross post, it will avoid splitting the community...
Here the duplicate discussion with my answers: https://github.com/google/or-tools/discussions/2548