Resource Constraints Task in Google OR-Tools with Fuzzy Logic (Coding)

Fuzzy logic is used as an optimization tool in various fields by providing a way to handle uncertainty and imprecision in complex systems.

Photo by Lukas S on Unsplash

Google OR-Tools is an open-source software suite developed by Google for solving combinatorial optimization problems. It provides a set of tools for constraint programming, linear programming, mixed-integer programming, and routing problems. While OR-Tools itself does not inherently integrate fuzzy logic, it can be combined with fuzzy logic concepts to handle uncertainty and imprecision in optimization problems. Here’s how you can leverage fuzzy logic with Google OR-Tools for optimization tasks:

Integrating Fuzzy Logic with Google OR-Tools

Defining Fuzzy Variables:

• Identify the variables in your optimization problem that have uncertainty or imprecision.
• Represent these variables using fuzzy sets and membership functions. For instance, if you have a variable for temperature, you might define fuzzy sets like “low,” “medium,” and “high” with corresponding membership functions.

Fuzzy Constraints and Objectives:

• Convert traditional crisp constraints and objectives into fuzzy ones. This involves defining fuzzy rules that describe how constraints and objectives behave under uncertainty.
• For example, instead of a strict constraint like 𝑥+𝑦≤10x+y≤10, you might have a fuzzy constraint where 𝑥+𝑦x+y should be “approximately” 10, represented by a fuzzy membership function.

Fuzzy Inference System:

• Create a fuzzy inference system (FIS) to evaluate the fuzzy rules. This system will take fuzzy inputs, apply fuzzy rules, and produce fuzzy outputs.
• For instance, in a routing problem, the FIS might consider factors like “traffic congestion” and “road conditions,” represented fuzzily, to determine the optimal route.

Hybrid Optimization Approach:

• Combine fuzzy logic with the optimization capabilities of OR-Tools. Use the fuzzy outputs from the FIS to guide the search process of the optimization algorithm.
• For example, in a vehicle routing problem, the fuzzy inference system can provide a degree of preference for different routes, which can be integrated into the routing algorithm provided by OR-Tools.

Defuzzification:

• Convert the fuzzy outputs back into crisp values that can be used by OR-Tools for final decision-making.
• Common defuzzification methods include the centroid method, the maximum membership method, and the mean of maximum method.

Example Workflow

Here’s a step-by-step example of how you might use fuzzy logic with Google OR-Tools:

Define the Problem:

Suppose you are solving a vehicle routing problem with uncertain traffic conditions.

Create Fuzzy Variables:

Define fuzzy sets for traffic conditions such as “low traffic,” “medium traffic,” and “high traffic” with corresponding membership functions.

Develop Fuzzy Rules:

Create rules like “If traffic is high, then increase travel time significantly,” “If traffic is medium, then increase travel time moderately,” and “If traffic is low, then travel time is normal.”

Fuzzy Inference:

Use a fuzzy inference system to evaluate the traffic conditions based on real-time data and apply the fuzzy rules.

Integrate with OR-Tools:

• Use the outputs from the fuzzy inference system to adjust the travel times in the OR-Tools vehicle routing solver.
• Solve the routing problem using OR-Tools, taking into account the adjusted travel times influenced by the fuzzy logic system.

Defuzzify and Interpret Results:

• Convert the fuzzy-adjusted travel times into crisp values for final route planning.
• Interpret the results to ensure the routes are optimized considering the traffic conditions.

Benefits

• Improved Decision-Making: By incorporating fuzzy logic, you can handle real-world uncertainties better than traditional crisp logic, leading to more robust and realistic optimization solutions.
• Flexibility: Fuzzy logic provides flexibility in modeling complex systems where precise mathematical formulations are difficult to derive.
• Enhanced Optimization: Combining fuzzy logic with OR-Tools can lead to enhanced optimization performance, especially in scenarios with high levels of uncertainty and imprecision.

Implementation

Present a VRPTW that also has constraints at the depot: all vehicles need to be loaded before departing the depot and unloaded upon return. Since there are only two available loading docks, at most two vehicles can be loaded or unloaded at the same time. As a result, some vehicles must wait for others to be loaded, delaying their departure from the depot. The problem is to find optimal vehicle routes for the VRPTW that also meet the loading and unloading constraints at the depot.

VRPTW example with resource constraints

The diagram below shows a VRPTW with resource constraints.

Source: https://developers.google.com/optimization/routing/vrptw_resources

To incorporate fuzzy logic with the Vehicle Routing Problem with Time Windows (VRPTW) using Google OR-Tools, we’ll expand the example.

Create the data

The following code creates the data for the example.

import numpy as np
import skfuzzy as fuzz
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 = {}
    data["time_matrix"] = [
        [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
        [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
        [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
        [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
        [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
        [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
        [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
        [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
        [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
        [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
        [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
        [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
    ]
    data["time_windows"] = [
        (0, 5),  # depot
        (7, 12),  # 1
        (10, 15),  # 2
        (5, 14),  # 3
        (5, 13),  # 4
        (0, 5),  # 5
        (5, 10),  # 6
        (0, 10),  # 7
        (5, 10),  # 8
        (0, 5),  # 9
        (10, 16),  # 10
        (10, 15),  # 11
        (0, 5),  # 12
        (5, 10),  # 13
        (7, 12),  # 14
        (10, 15),  # 15
        (5, 15),  # 16
    ]
    data["num_vehicles"] = 4
    data["vehicle_load_time"] = 5
    data["vehicle_unload_time"] = 5
    data["depot_capacity"] = 2
    data["depot"] = 0
    return data

Explanation

Data Model:

• data['time_matrix']: A predefined matrix representing base travel times between locations.
• data['time_windows']: An array of time windows for requested visits to the locations.
• data['num_vehicles']: Number of vehicles.
• data['vehicle_load_time'] and data['vehicle_unload_time']: Times for loading and unloading a vehicle.
• data['depot_capacity']: The maximum number of vehicles that can load or unload at the same time.
• data['depot']: The starting point for all vehicles.

Fuzzy Logic for Traffic Evaluation:

• evaluate_traffic(traffic_level): Determines the traffic condition ("low," "medium," "high") based on the traffic level using fuzzy logic.

Time Callback:

• time_callback(from_index, to_index): Adjusts the base travel time according to the evaluated traffic condition.

Routing and Optimization:

• Use OR-Tools to set up the problem and solve it, incorporating the adjusted travel times and constraints.

This approach integrates fuzzy logic to handle uncertainties in travel times due to varying traffic conditions, providing a more realistic model for routing and scheduling.

def evaluate_traffic(traffic_level):
    """Evaluate the traffic level using fuzzy logic."""
    traffic_conditions = np.arange(0, 101, 1)
    low_traffic = fuzz.trimf(traffic_conditions, [0, 0, 50])
    medium_traffic = fuzz.trimf(traffic_conditions, [30, 50, 70])
    high_traffic = fuzz.trimf(traffic_conditions, [50, 100, 100])

    low = fuzz.interp_membership(traffic_conditions, low_traffic, traffic_level)
    medium = fuzz.interp_membership(traffic_conditions, medium_traffic, traffic_level)
    high = fuzz.interp_membership(traffic_conditions, high_traffic, traffic_level)

    if high > medium and high > low:
        return "high"
    elif medium > low:
        return "medium"
    else:
        return "low"

def main():
    """Solve the CVRPTW problem with fuzzy logic for traffic conditions."""
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)

        # Simulate traffic level between 0 to 100 (e.g., from real-time data)
        traffic_level = np.random.randint(0, 101)
        traffic_condition = evaluate_traffic(traffic_level)
        
        #print("Traffic Condition:", traffic_condition)

        base_travel_time = data['time_matrix'][from_node][to_node]

        if traffic_condition == "high":
            adjusted_travel_time = base_travel_time * 1.5
        elif traffic_condition == "medium":
            adjusted_travel_time = base_travel_time * 1.2
        else:
            adjusted_travel_time = base_travel_time

        return int(adjusted_travel_time)

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time Window constraint
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        30,  # allow waiting time
        30,  # maximum time per vehicle
        False,  # don't force start cumul to zero
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == data['depot']:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

    # Instantiate route start and end times to produce feasible times.
    for i in range(data['num_vehicles']):
        index = routing.Start(i)
        time_dimension.CumulVar(index).SetRange(data['time_windows'][data['depot']][0],
                                                data['time_windows'][data['depot']][1])
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        print_solution(manager, routing, solution, data)
    else:
        print("No solution found !")

def print_solution(manager, routing, solution, data):
    """Prints solution on console."""
    print('Objective: {}'.format(solution.ObjectiveValue()))
    total_time = 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_time = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            time_var = time_dimension.CumulVar(index)
            plan_output += ' {0} Time({1},{2}) -> '.format(
                node_index,
                solution.Min(time_var),
                solution.Max(time_var))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_time += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        node_index = manager.IndexToNode(index)
        time_var = time_dimension.CumulVar(index)
        plan_output += ' {0} Time({1},{2})\n'.format(
            node_index,
            solution.Min(time_var),
            solution.Max(time_var))
        plan_output += 'Time of the route: {}\n'.format(route_time)
        print(plan_output)
        total_time += route_time
    print('Total time of all routes: {}'.format(total_time))

if __name__ == '__main__':
    main()

Key Adjustments:

1. Debugging Constraints: Ensured all constraints are properly defined and allow feasible solutions.
2. Evaluated Traffic Using Fuzzy Logic: The evaluate_traffic function uses fuzzy logic to determine traffic conditions.
3. Adjusted Travel Times: Based on the traffic condition, travel times are adjusted dynamically.

Objective: 90
Route for vehicle 0:
 0 Time(0,0) ->  12 Time(4,4) ->  1 Time(11,11) ->  4 Time(13,13) ->  3 Time(14,14) ->  0 Time(26,26)
Time of the route: 21

Route for vehicle 1:
 0 Time(0,0) ->  14 Time(7,7) ->  16 Time(9,9) ->  10 Time(13,13) ->  0 Time(19,19)
Time of the route: 24

Route for vehicle 2:
 0 Time(0,0) ->  7 Time(3,3) ->  13 Time(7,7) ->  11 Time(10,10) ->  15 Time(13,13) ->  0 Time(23,23)
Time of the route: 22

Route for vehicle 3:
 0 Time(0,0) ->  9 Time(2,2) ->  5 Time(5,5) ->  8 Time(8,8) ->  6 Time(10,10) ->  2 Time(13,13) ->  0 Time(22,22)
Time of the route: 23

Total time of all routes: 90

Great! It looks like the solver found a solution with a total route time of 90.

Useful Links

Resource Constraints | OR-Tools | Google for Developers

If you liked the article, you can support the author by clapping below 👏🏻 Thanks for reading!

Oleh Dubetsky|Linkedin