Routing not respecting time window and breaks not working properly.

[ibiscp]

Hello everyone,

I have been working on this project for a month, continuously adding new requirements. Recently, I implemented breaks, which work in some scenarios, but I am still encountering issues with specific examples.

In the current example, there are visits that should be included in the routing, specified in fixed_visits. However, the generated route does not respect the time window for visit 78a9hx3wu9i3. Additionally, the break window is not being respected.

Any insights or suggestions to address these issues would be greatly appreciated.

import time
from typing import List, Optional

from ortools.constraint_solver import pywrapcp, routing_enums_pb2  # type: ignore


def print_time(value):
    return time.strftime("%H:%M:%S", time.gmtime(value))


class DeepdiveRouting:

    def __init__(
        self,
        customer_location_mapping: list[tuple[str, str]],
        location_mapping: dict,
        time_matrix: list[list[int]],
        time_windows: list[list[int]] | list[list[list[int]]],
        service_times: list[int],
        shift_hours: list[list[int]],
        visit_numbers: dict = {},
        fixed_visits: list[str] = [],
        depot: Optional[str] = None,
    ):
        self.customer_location_mapping = customer_location_mapping
        self.location_mapping = location_mapping
        self.time_matrix = time_matrix
        self.service_times = service_times
        self.visit_numbers = visit_numbers or {i: 1 for i in location_mapping.keys()}
        self.shift_hours = shift_hours
        self.fixed_visits = fixed_visits
        self.num_workers = 1
        self.depot = depot or list(self.location_mapping.keys())[0]
        self.penalty = [100000000 for _ in range(len(self.time_matrix))]

        # Format location mapping
        for key, value in self.location_mapping.items():
            if isinstance(value, int):
                self.location_mapping[key] = [value]

        # Invert location mapping
        self._inv_location_mapping = self.collect_inv_location_mapping(self.location_mapping)

        # Format time windows
        self.time_windows: list[list[list[int]]] = []
        for time_window in time_windows:
            if all(isinstance(i, int) for i in time_window):
                self.time_windows.append([time_window])  # type: ignore
            elif all(isinstance(i, list) for i in time_window):
                self.time_windows.append(time_window)  # type: ignore
            else:
                raise ValueError("Invalid format for time windows")

        # Check length of time windows
        if len(self.time_windows) != len(self._inv_location_mapping):
            raise ValueError("Length of time windows must match the number of addresses")

        # Check length of service times
        if len(self.service_times) != len(self._inv_location_mapping):
            raise ValueError("Length of service times must match the number of addresses")

        # Check length of time matrix
        if len(self.time_matrix) != len(self._inv_location_mapping):
            raise ValueError("Length of time matrix must match the number of addresses")
        
        # Check if time matrix is square
        if any(len(row) != len(self.time_matrix) for row in self.time_matrix):
            raise ValueError("Time matrix must be square")

        # Check length of visit numbers
        if len(self.visit_numbers) != len(self.location_mapping):
            raise ValueError("Length of visit numbers must match the number of clients")

        # Check if fixed visits have only one location
        for visit in fixed_visits:
            if len(location_mapping[visit]) > 1:
                raise ValueError(f"Fixed visits {visit} cannot have more than one location.")

        self.solutions: dict = {}

    @property
    def break_times(self):
        breaks = 0
        for idx in range(len(self.shift_hours) - 1):
            breaks += self.shift_hours[idx + 1][0] - self.shift_hours[idx][1]

        return breaks

    @property
    def total_shift_time(self):
        return self.shift_hours[-1][1] + self.break_times

    @property
    def solution_ids(self):
        locations = []

        for value in self.solutions.values():
            locations += value["locations"]

        return locations

    @property
    def total_visits(self):
        return sum([value for key, value in self.visit_numbers.items() if key != self.depot])

    @property
    def progress(self):
        # Remove self.depot from solution_indexes
        visited = [i for i in self.solution_ids if i != self.depot]

        return len(visited) / self.total_visits

    @property
    def visits_planned(self):
        return {key: self.visit_numbers[key] for key in self.location_mapping.keys()}

    @property
    def visits_made(self):
        visits_made = {}
        for _, value in self.solutions.items():
            for location in value["locations"]:
                if location not in visits_made:
                    visits_made[location] = 1
                else:
                    visits_made[location] += 1

        return visits_made

    @property
    def visits_missed(self):
        visits_missed = {}
        visits_made = self.visits_made
        visits_planned = self.visits_planned
        for key in visits_planned.keys():
            if key == self.depot:
                continue  # Skip depot
            number_missed = visits_planned[key] - visits_made[key]
            if number_missed:
                visits_missed[key] = number_missed

        return visits_missed

    def collect_inv_location_mapping(self, location_mapping: dict[str, list[int]]):
        inv_location_mapping = {}
        for key, values in location_mapping.items():
            for value in values:
                inv_location_mapping[value] = key
        return inv_location_mapping

    def get_next_batch(self):
        # Indexes to keep initially
        keep_ids = []
        for visit_id in self.location_mapping.keys():
            if visit_id == self.depot:
                continue

            desired_visits = self.visit_numbers[visit_id]
            visits_made = sum(1 for i in self.solution_ids if i == visit_id)

            if self.progress >= visits_made / desired_visits and self.progress != 1.0:
                keep_ids.append(visit_id)

        # Add the depot to the list
        keep_ids = [self.depot] + keep_ids

        # Create sub_time_matrix
        keep_idx = [item for sublist in [self.location_mapping[i] for i in keep_ids] for item in sublist]
        sub_time_matrix = [[self.time_matrix[i][j] for j in keep_idx] for i in keep_idx]

        # Create sub_time_windows
        sub_time_windows = [self.time_windows[i] for i in keep_idx]

        # Create sub_service_times
        sub_service_times = [self.service_times[i] for i in keep_idx]

        # Create sub_location_mapping, ensuring each new index is mapped correctly
        sub_location_mapping = {}
        for idx, i in enumerate(keep_idx):
            if self._inv_location_mapping[i] in sub_location_mapping:
                sub_location_mapping[self._inv_location_mapping[i]].append(idx)
            else:
                sub_location_mapping[self._inv_location_mapping[i]] = [idx]

        # Create customer_location_mapping
        sub_customer_location_mapping = [self.customer_location_mapping[i] for i in keep_idx]

        # Create sub_penalty
        sub_penalty = [self.penalty[i] for i in keep_idx]

        return (
            sub_time_matrix,
            sub_time_windows,
            sub_service_times,
            sub_location_mapping,
            sub_penalty,
            sub_customer_location_mapping,
        )

    def collect_route_data(
        self,
        manager,
        routing,
        solution,
        time_matrix,
        time_windows,
        service_times,
        location_mapping: dict[str, list[int]],
        customer_location_mapping: list[tuple[str, str]],
    ):
        """Collects data from the routing solution."""
        route_data: dict[str, List] = {"visits": [], "breaks": []}
        time_dimension = routing.GetDimensionOrDie("Time")

        inv_location_mapping = self.collect_inv_location_mapping(location_mapping)

        # Only vehicle 0
        index = routing.Start(0)
        previous_index = index

        intervals = solution.IntervalVarContainer()
        for i in range(intervals.Size()):
            brk = intervals.Element(i)
            if brk.PerformedValue() == 1:
                route_data["breaks"].append(
                    {
                        "name": brk.Var().Name(),
                        "start": brk.StartValue(),
                        "duration": brk.DurationValue(),
                        "end": brk.EndValue(),
                    }
                )

        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)

            departure_time = solution.Min(time_var)
            # Get breaks duration before departure_time
            brk_durations = [brk["duration"] for brk in route_data["breaks"] if brk["end"] == departure_time]
            departure_time -= sum(brk_durations)

            current_index = manager.IndexToNode(index)
            travel_time = time_matrix[manager.IndexToNode(previous_index)][current_index]
            service_time = service_times[current_index]
            arrival_time = departure_time - service_time

            if len(time_windows[current_index]) == 1 and time_windows[current_index][0] and service_time == time_windows[current_index][0][1] - time_windows[current_index][0][0]:
                arrival_time = time_windows[current_index][0][0]
                departure_time = time_windows[current_index][0][1]

            stop_info = {
                "location": inv_location_mapping[current_index],
                "customer": customer_location_mapping[current_index][0],
                "travel_time": travel_time,
                "arrival_time": arrival_time,
                "departure_time": departure_time,
                "service_time": service_time,
                "service_window": time_windows[current_index],
            }
            route_data["visits"].append(stop_info)
            previous_index = index
            index = solution.Value(routing.NextVar(index))

        # Handling the final stop
        time_var = time_dimension.CumulVar(index)

        current_index = manager.IndexToNode(index)
        travel_time = time_matrix[manager.IndexToNode(previous_index)][current_index]
        service_time = service_times[current_index]
        # arrival_time = departure_time - service_time
        arrival_time = solution.Min(time_dimension.CumulVar(previous_index)) + travel_time

        stop_info = {
            "location": inv_location_mapping[current_index],
            "customer": customer_location_mapping[current_index][0],
            "travel_time": travel_time,
            "arrival_time": arrival_time,
            "departure_time": arrival_time,
            "service_time": service_time,
            "service_window": time_windows[current_index],
        }
        route_data["visits"].append(stop_info)

        route_data["total_time"] = departure_time
        route_data["locations"] = [stop["location"] for stop in route_data["visits"] if stop["location"] != 0]

        return route_data

    def print_route_data(self, solution: Optional[dict] = None):
        print(self.generate_route_data(solution))

    def generate_route_data(self, solution: Optional[dict] = None):

        output = ""

        solution = solution or self.solutions

        for key, value in solution.items():
            total_time = print_time(value["total_time"])
            output += f"Day: {key + 1}\n"
            output += f"\tTotal time: {total_time}\n"

            for idx, breaks in enumerate(value["breaks"]):
                output += f"\n\t{breaks['name']}\n"
                output += f"\t\tStart time: {print_time(breaks['start'])}\n"
                output += f"\t\tDuration: {print_time(breaks['duration'])}\n"
                output += f"\t\tEnd time: {print_time(breaks['end'])}\n"

            output += "\n\t----------------------------------------\n"

            for idx, visit in enumerate(value["visits"][:-1]):

                from_visit = visit
                to_visit = value["visits"][idx + 1]

                if idx == 0:
                    output += "\n\tHome\n"
                    output += f"\t\tDeparture time: {print_time(from_visit['departure_time'])}\n"

                # Find any breaks in between
                brk_found = None
                for brk in value["breaks"]:
                    if from_visit["departure_time"] <= brk["start"] and to_visit["arrival_time"] >= brk["start"]:
                        brk_found = brk
                        break

                # Check if there is any break in between
                if brk_found:
                    # print(brk_found)
                    output += f"\n\tTravel from {from_visit['location']} to {brk_found['name']}\n"
                    to_break_duration = brk_found["start"] - from_visit["departure_time"]
                    output += f"\t\tTravel time: {print_time(to_break_duration)}\n"

                    output += f"\n\t{brk_found['name']}\n"
                    output += f"\t\tStart time: {print_time(brk_found['start'])}\n"
                    output += f"\t\tDuration: {print_time(brk_found['duration'])}\n"
                    output += f"\t\tEnd time: {print_time(brk_found['end'])}\n"

                    output += f"\n\tTravel from {brk_found['name']} to {to_visit['location']}\n"
                    output += f"\t\tTravel time: {print_time(to_visit['travel_time'] - to_break_duration)}\n"
                else:
                    output += f"\n\tTravel from {from_visit['location']} to {to_visit['location']}\n"
                    output += f"\t\tTravel time: {print_time(to_visit['travel_time'])}\n"

                if idx != len(value["visits"]) - 2:
                    output += f"\n\tVisit {to_visit['location']}\n"
                    service_windows = ", ".join(
                        f"{print_time(window[0])} - {print_time(window[1])}" for window in to_visit["service_window"]
                    )
                    output += f"\t\tService windows: {service_windows}\n"
                else:
                    output += "\n\tHome\n"

                output += f"\t\tWait time: {print_time(to_visit['arrival_time'] - from_visit['departure_time'] - to_visit['travel_time'])}\n"
                output += f"\t\tArrival time: {print_time(to_visit['arrival_time'])}\n"

                if idx != len(value["visits"]) - 2:
                    output += f"\t\tVisit time: {print_time(to_visit['service_time'])}\n"
                    output += f"\t\tDeparture time: {print_time(to_visit['departure_time'])}\n"

            output += "\n"

        return output

    def calculate_solution(self, days: int = 1000):
        """Solve the VRP with time windows."""

        day = 0
        previous_progress = 0

        while day < days:

            # Get data for the run
            time_matrix, time_windows, service_times, location_mapping, penalty, customer_location_mapping = (
                self.get_next_batch()
            )

            # Break if progress stopped increasing
            if self.progress == previous_progress and day != 0:
                break
            previous_progress = self.progress

            # Create the routing index manager.
            manager = pywrapcp.RoutingIndexManager(
                len(time_matrix), self.num_workers, self.location_mapping[self.depot][0]
            )

            # 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."""
                # Convert from routing variable Index to time matrix NodeIndex.
                if from_index == to_index:
                    return 0
                from_node = manager.IndexToNode(from_index)
                to_node = manager.IndexToNode(to_index)
                return time_matrix[from_node][to_node] + service_times[to_node]

            transit_callback_index = routing.RegisterTransitCallback(time_callback)

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

            # Add Time Windows constraint.
            time = "Time"
            routing.AddDimension(
                transit_callback_index,
                self.total_shift_time,  # allow waiting time
                self.total_shift_time,  # maximum time per vehicle
                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(time_windows):
                if location_idx == location_mapping[self.depot][0]:
                    continue
                index = manager.NodeToIndex(location_idx)
                earliest_start = time_window[0][0]
                latest_end = time_window[len(time_window) - 1][1]
                time_dimension.CumulVar(index).SetRange(earliest_start, latest_end)

                for tw_index, tw in enumerate(time_window):
                    if tw_index == len(time_window) - 1:
                        break
                    time_window_end = tw[1]
                    next_time_window_start = time_window[tw_index + 1][0]

                    time_dimension.CumulVar(index).RemoveInterval(time_window_end, next_time_window_start)
                # routing.AddToAssignment(time_dimension.SlackVar(index))
                # time_dimension.SlackVar(index).SetRange(0, 0)

            # Add one-of constraint for each location group
            for value in location_mapping.values():
                if len(value) > 1:
                    location_indexes = [manager.NodeToIndex(idx) for idx in value]
                    # Create binary variables to represent whether each location is visited
                    visited_vars = [routing.ActiveVar(index) for index in location_indexes]
                    # Add constraint to ensure only one of the locations is visited
                    routing.solver().Add(sum(visited_vars) == 1)

            # Allow to drop nodes.
            fixed_visits = [
                item
                for sublist in [location_mapping[visit] for visit in self.fixed_visits if visit in location_mapping]
                for item in sublist
            ]
            for node in range(1, len(time_matrix)):
                if node not in fixed_visits:  # Do not allow to drop the special node
                    penalty_value = penalty[node]
                    routing.AddDisjunction([manager.NodeToIndex(node)], penalty_value)

            # Start time of the routes
            for vehicle_id in range(manager.GetNumberOfVehicles()):
                index = routing.Start(vehicle_id)
                time_dimension.CumulVar(index).SetValue(self.shift_hours[0][0])
                # routing.AddToAssignment(time_dimension.SlackVar(index))
                # time_dimension.SlackVar(index).SetRange(0, 500)

            # Add breaks
            if len(self.shift_hours) > 1:
                node_visit_transit = [0] * manager.GetNumberOfIndices()
                for index in range(manager.GetNumberOfIndices()):
                    node = manager.IndexToNode(index)
                    node_visit_transit[index] = service_times[node]

                for v in range(manager.GetNumberOfVehicles()):
                    # start_var = time_dimension.CumulVar(routing.Start(v))
                    break_intervals = []
                    for i in range(1, len(self.shift_hours)):
                        break_start_time = self.shift_hours[i - 1][1]
                        break_end_time = self.shift_hours[i][0]
                        break_duration = break_end_time - break_start_time

                        # Create a fixed duration interval for the break
                        interval = routing.solver().FixedInterval(break_start_time, break_duration, f"Break {i}")
                        break_intervals.append(interval)

                    time_dimension.SetBreakIntervalsOfVehicle(break_intervals, v, node_visit_transit)

            # Instantiate route start and end times to produce feasible times.
            for i in range(self.num_workers):
                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
            search_parameters.time_limit.seconds = 10

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

            # Print solution on console.
            if not solution:
                print("No solution found!")
                break

            route_data = self.collect_route_data(
                manager,
                routing,
                solution,
                time_matrix,
                time_windows,
                service_times,
                location_mapping,
                customer_location_mapping,
            )

            if len(route_data["visits"]) > 2:
                self.solutions[day] = route_data

            day += 1

        return self.solutions


if __name__ == "__main__":

    customer_location_mapping = [
        ("depot", "depot"),
        ("r7iuc5kmbwju", "fa55w0is2hiz"),
        ("swfyyhi454ce", "93jcpnovc2i6"),
        ("p1105vwawg0w", "6u41843q97k6"),
        ("8agfzkpyab49", "ovwhyw9gr1ti"),
        ("85vwinxkuonw", "27d7it46mmyb"),
        ("85vwinxkuonw", "xr1yljs8z3ob"),
        ("vranfv90oqo3", "5s42w163mea9"),
        ("j9t99ucuumzn", "c2kzicjio624"),
        ("85vwinxkuonw", "2lqqob5xfub6"),
        ("yozzo0k2wikc", "9baewbjqvyzf"),
        ("y02fia9r0jgq", "78a9hx3wu9i3"),
        ("y02fia9r0jgq", "mno8w399zgdl"),
    ]
    location_mapping = {
        "depot": [0],
        "fa55w0is2hiz": [1],
        "93jcpnovc2i6": [2],
        "6u41843q97k6": [3],
        "ovwhyw9gr1ti": [4],
        "27d7it46mmyb": [5],
        "xr1yljs8z3ob": [6],
        "5s42w163mea9": [7],
        "c2kzicjio624": [8],
        "2lqqob5xfub6": [9],
        "9baewbjqvyzf": [10],
        "78a9hx3wu9i3": [11],
        "mno8w399zgdl": [12],
    }
    time_matrix = [
        [0, 688, 839, 724, 752, 758, 1064, 1138, 1644, 2155, 5239, 541, 687],
        [672, 0, 1421, 1290, 1318, 1324, 458, 532, 2035, 1810, 5822, 1124, 1253],
        [847, 1393, 0, 255, 410, 393, 1769, 1843, 1900, 2411, 4777, 907, 247],
        [814, 1360, 198, 0, 209, 160, 1735, 1810, 1867, 2378, 4631, 817, 75],
        [722, 1268, 381, 212, 0, 153, 1644, 1718, 1775, 2286, 4667, 837, 176],
        [866, 1412, 407, 257, 146, 0, 1788, 1862, 1919, 2430, 4627, 981, 185],
        [1077, 423, 1827, 1696, 1724, 1730, 0, 80, 2440, 1358, 6228, 1529, 1659],
        [1152, 497, 1902, 1770, 1798, 1805, 80, 0, 2515, 1386, 6302, 1604, 1733],
        [1634, 2082, 1953, 1810, 1838, 1845, 2458, 2532, 0, 1497, 6359, 1895, 1773],
        [2212, 1787, 2531, 2388, 2417, 2423, 1370, 1398, 1449, 0, 6937, 2473, 2352],
        [5392, 5909, 4831, 4856, 4763, 4707, 6285, 6359, 6533, 7044, 0, 5290, 4788],
        [496, 1084, 532, 595, 659, 597, 1459, 1534, 1809, 2320, 4933, 0, 638],
        [755, 1301, 310, 112, 219, 212, 1676, 1751, 1808, 2319, 4735, 870, 0],
    ]
    time_windows = [
        [],
        [[28800, 43200]],
        [[32400, 43200], [46800, 61200]],
        [[28800, 43200]],
        [[28800, 43200]],
        [[28800, 43200]],
        [[46800, 64800]],
        [[28800, 43200]],
        [[28800, 43200]],
        [[28800, 43200]],
        [[28800, 43200]],
        [[37800, 39600]],
        [[54000, 55800]],
    ]
    service_times = [0, 3600, 3600, 3600, 3600, 3600, 3600, 3600, 3600, 3600, 3600, 1800, 1800]
    shift_hours = [[30600, 43200], [46800, 64800]]
    fixed_visits = ["78a9hx3wu9i3", "mno8w399zgdl"]

    # Print data to test
    print("Data:")
    for idx, tw in enumerate(time_windows):
        if not tw:
            continue
        for window in tw:
            print(
                f"\t{customer_location_mapping[idx][1]}: {print_time(window[0])} - {print_time(window[1])}\t{print_time(service_times[idx])}"
            )

    # Instantiate routing
    routing = DeepdiveRouting(
        customer_location_mapping=customer_location_mapping,
        location_mapping=location_mapping,
        time_matrix=time_matrix,
        time_windows=time_windows,
        service_times=service_times,
        shift_hours=shift_hours,
        fixed_visits=fixed_visits,
        depot="depot",
    )

    # Generate solutions for one day
    solution = routing.calculate_solution(days=1)
    routing.print_route_data(solution=solution)