VRP Routes that seem to violate accumulated time of vehicle route

[Christopher Pflaum]

I am getting routes that seem to violate the cumulative time for a vehicle. 

• Route for vehicle 2: 0 Time(0,0) -> 4 Time(120,120) -> 3 Time(120,120) -> 2 Time(120,120) -> 1 Time(120,120) -> 0 Time(120,120) Time of the route: 120min Route for vehicle 3: 0 Time(0,0) -> 9 Time(0,120) -> 8 Time(120,120) -> 7 Time(120,120) -> 6 Time(120,120) -> 5 Time(120,120) -> 0 Time(120,120) Time of the route: 120min

The distance matrix holds travel time + 60min for duration of a job. 

Each stop should accumulate at least an hour of time and make the third stop (#1) impossible as the vehicle accumulated time should be > 120 min. 

Any help would be appreciate, probably a simple error as I am new to OR, and modifying so that the time at a node is the travel time + the time duration of that job. 

I added code to limit a vehicle to 5 jobs because the locations were all going to a single vehicle route. It seems like there is a constraint missing. 



"""Vehicles Routing Problem (VRP) with Time Windows."""
from ortools.constraint_solver import pywrapcp

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["time_matrix"] = dm #calculated in minutes
    data["time_windows"] = timewin #In minutes, zero time is 8AM, all window from/to are in minutes from 8AM
    data["num_vehicles"] = 12 #91
    data["duration"] = duration #CP ADDED duration, not used coded direct in time_callback
    data["depot"] = 0
    return data

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    time_dimension = routing.GetDimensionOrDie("Time")
    total_time = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += (
                f"{manager.IndexToNode(index)}"
                f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
                " -> "
            )
            index = solution.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += (
            f"{manager.IndexToNode(index)}"
            f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
        )
        plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
        print(plan_output)
        total_time += solution.Min(time_var)
    print(f"Total time of all routes: {total_time}min")

def main():
    """Solve the VRP with time windows."""
    # 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"]
        #Arguments: int num_nodes, int num_vehicles, const std::vector<NodeIndex>& starts, const std::vector<NodeIndex>& ends
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        ret=0.0
        for location_idx, time_window in enumerate(data["time_windows"]):
            if location_idx == data["depot"]:
                ret=data["time_matrix"][from_node][to_node] + 0 #job duration minutes
            else:
                ret=data["time_matrix"][from_node][to_node] + 60 #job duration minutes
        return ret #data["time_matrix"][from_node][to_node] + 60 #duration[to_node]  #CP ADDED duration, now travel time + duration 'to_index'

    transit_callback_index = routing.RegisterTransitCallback(time_callback)

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

    # Add time dimension based on time callback. Callback based on travel time and job time total
    time = "Time"
    routing.AddDimension(
        transit_callback_index,
        480,  # allow waiting time
        10000,  # maximum time per vehicle. Total time or from start route only?
        False,  # Don't force start cumul to zero.
        time,
    )
    time_dimension = routing.GetDimensionOrDie(time)
   
    # Add time window constraints for each location except depot.
    for location_idx, time_window in enumerate(data["time_windows"]): #iterate each location and associated time window
        if location_idx == data["depot"]:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) # set range of location start and end times for route start
       
    # Add time window constraints for each vehicle route start node.
    depot_idx = data["depot"]
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange( data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]  )
        #set range for vehicle route start time job.

   # Create counter for vehicle total job count. Added to force code to use all techs.
    def counter_callback(from_index):
        """Returns 1 for any locations except depot."""
        # Convert from routing variable Index to user NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return 1 if (from_node != 0) else 0; #not depot
   
    counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)
    routing.AddDimensionWithVehicleCapacity(
        counter_callback_index,
        0,  # null slack
        [5]*data["num_vehicles"],  # maximum locations per vehicle
        True,  # start cumul to zero
        'Counter')
       
    # Instantiate route start and end times to produce feasible times.
    for i in range(data["num_vehicles"]):
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)) )
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)) )

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

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

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("****NO SOLUTION*****")
     
if __name__ == "__main__":
    main()
    #stop()
    

[Laurent Perron]

most likely your data contains floating points < 1.0 rounded to 0 as the solver is integral.

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

--
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/60f7a1f1-dc1b-4a21-869d-30088565a578n%40googlegroups.com.

[Mizux Seiha]

In ` def time_callback(from_index, to_index):`
you initialise `ret` as a float variable (whose value is 0.0), also we dont know if your matrix `data["time_matrix"]` only contains integer values or not...

you should:
* initialise `ret` as a integer aka `ret = 0`
* force the value return to be an int (beware of rounding)
i.e. `return int(ret)` in def time_callback ...