Request for Or-Tool sample code

[amit bangar]

Hi Team,

We have multiple vehicles which having different start and end locations. Vehicles wants to visit customers locations with in available time which is provided by customers (time_window). Additionally, each vehicle has their shift start and end time. Anybody have Or-Tool sample code which achieve the above requirement.

  

    

[Laurent Perron]

how is this different from https://developers.google.com/optimization/routing/routing_tasks#setting_start_and_end_locations_for_routes ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mer. 24 juil. 2024 à 07:02, amit bangar <amitba...@gmail.com> a écrit :

Hi Team,

We have multiple vehicles which having different start and end locations. Vehicles wants to visit customers locations with in available time which is provided by customers (time_window). Additionally, each vehicle has their shift start and end time. Anybody have Or-Tool sample code which achieve the above requirement.

  

    

--
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/34926852-a22c-4024-affe-99e26a9cfa7en%40googlegroups.com.

[amit bangar]

Thanks Laurent. We have already refer above link. Please find the sample code which we have created to achieve above requirement. Currently we have skip service_time

factor but rest of the factor we have used. Looking foreword to your help.  

from ortools.constraint_solver import pywrapcp

from ortools.constraint_solver import routing_enums_pb2

# Sample data for the problem

data = {  

    "time_matrix": [

        [0, 11, 19, 19, 12, 23, 19, 15, 8, 17],

        [10, 0, 10, 11, 12, 22, 19, 16, 8, 17],

        [19, 10, 0, 10, 17, 25, 20, 18, 17, 17],

        [19, 11, 11, 0, 14, 22, 18, 15, 15, 15],

        [12, 13, 17, 13, 0, 12, 9, 7, 9, 9],

        [22, 23, 25, 21, 12, 0, 5, 10, 18, 9],

        [19, 20, 21, 18, 9, 5, 0, 7, 16, 7],

        [15, 16, 18, 14, 9, 9, 6, 0, 11, 4],

        [8, 8, 16, 15, 8, 18, 14, 10, 0, 12],

        [16, 16, 18, 14, 10, 10, 7, 5, 12, 0]

    ],

    "num_vehicles": 3,

    "vehicle_starts": [0, 1, 2],  # Start location for each vehicle

    "vehicle_ends": [0, 1, 2],  # End location for each vehicle

    "service_times": [0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],  # Service time at each location

    "time_windows": [

        # Time windows for each location

        (1, 23),  # 0

        (1, 23),  # 1

        (1, 23),  # 2

        (1, 23),  # 1

        (1, 23),  # 1

        (1, 23),  # 1

        (1, 23),  # 1

        (1, 23),  # 1

        (1, 23),  # 1

        (1, 23)  # 1

    ],

    "vehicle_shifts": [

        # Vehicle shift times (start, end)

        (1, 23),  # Vehicle 0

        (1, 23),  # Vehicle 1

        (1, 23)   # Vehicle 2

    ],

}

# Create the routing index manager

manager = pywrapcp.RoutingIndexManager(

        len(data["time_matrix"]), data["num_vehicles"], data["vehicle_starts"], data["vehicle_ends"]

    )

# Create Routing Model

routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback

def time_callback(from_index, to_index):

    from_node = manager.IndexToNode(from_index)

    to_node = manager.IndexToNode(to_index)

    travel_time = data["time_matrix"][from_node][to_node]

    #service_time = data["service_times"][from_node]

    return travel_time #+ service_time

transit_callback_index = routing.RegisterTransitCallback(time_callback)

# Define cost of each arc

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Time dimension

time = "Time"

routing.AddDimension(

        transit_callback_index,

        0,  # allow waiting time

        400,  # maximum time per vehicle

        False,  # Don't force start cumul to zero.

        time,

)

time_dimension = routing.GetDimensionOrDie(time)

time_dimension.SetGlobalSpanCostCoefficient(100)

# Add time window constraints for each location except depot.

for location_idx, time_window in enumerate(data["time_windows"]):

        if location_idx in data["vehicle_starts"] or location_idx in data["vehicle_ends"]:

            continue

        index = manager.NodeToIndex(location_idx)

        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

        # Add time window constraints for each vehicle start node.

       

for vehicle_id in range(data["num_vehicles"]):

        index = routing.Start(vehicle_id)

        time_dimension.CumulVar(index).SetRange(

            data["vehicle_shifts"][vehicle_id][0], data["vehicle_shifts"][vehicle_id][1]

        )

# Add time window constraints for each vehicle end node.

for vehicle_id in range(data["num_vehicles"]):

    index = routing.End(vehicle_id)

    time_dimension.CumulVar(index).SetRange(

            data["vehicle_shifts"][vehicle_id][0], data["vehicle_shifts"][vehicle_id][1]

        )

# [END time_windows_constraint]

# Instantiate route start and end times to produce feasible times.

# [START depot_start_end_times]

for i in range(data["num_vehicles"]):

    routing.AddVariableMinimizedByFinalizer(

        time_dimension.CumulVar(routing.Start(i))

    )

    routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

# [END depot_start_end_times]

# Setting first solution heuristic.

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

search_parameters.first_solution_strategy = (

    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

search_parameters.time_limit.seconds = 90

# Solve the problem

solution = routing.SolveWithParameters(search_parameters)

# Print solution on console

if solution:

    for vehicle_id in range(data["num_vehicles"]):

        index = routing.Start(vehicle_id)

        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)

        while not routing.IsEnd(index):

            plan_output += ' {} -> '.format(manager.IndexToNode(index))

            index = solution.Value(routing.NextVar(index))

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

        print(plan_output)

else:

    print('No solution found !')