<jupyter_start><jupyter_text>OptaPy - OptaPlanner in PythonOptaPy is an **AI constraint solver for Python** to optimize the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more planning problems.OptaPy wraps the [OptaPlanner](https://www.optaplanner.org/) engine internally, but using OptaPy in Python is significantly slower than using OptaPlanner in Java or Kotlin.WARNING:  OptaPy is an experimental technology. It is at least 20 times slower than using OptaPlanner in Java or Kotlin. What is OptaPlanner?OptaPlanner is an AI constraint solver. It optimizes planning and scheduling problems, such as the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more. Every organization faces such challenges: assign a limited set of constrained resources (employees, assets, time and/or money) to provide products or services. OptaPlanner delivers more efficient plans, which reduce costs and improve service quality.Constraints apply on plain domain objects and can call existing code. There’s no need to input constraints as mathematical equations. Under the hood, OptaPlanner combines sophisticated Artificial Intelligence optimization algorithms (such as Tabu Search, Simulated Annealing, Late Acceptance and other metaheuristics) with very efficient score calculation and other state-of-the-art constraint solving techniques. Vehicle Routing Quickstart Model the domain objects and constraintsUsing a fleet of vehicles, pick up the objects of each customer and bring them to the depot. Each vehicle can service multiple customers, but it has a limited capacity. Problem FactsProblem facts are facts about the problem. As such, they do not change during solving (and thus cannot have any planning variables). For Vehicle Routing, the problem facts are the locations a vehicle can visit, the depots, and the customers to visit:<jupyter_code>from optapy import planning_id

class Location:
    def __init__(self, latitude, longitude, distance_map=None):
        self.latitude = latitude
        self.longitude = longitude
        self.distance_map = distance_map

    def set_distance_map(self, distance_map):
        self.distance_map = distance_map

    def get_distance_to(self, location):
        return self.distance_map[location]

    def get_angle(self, location):
        latitude_difference = location.latitude - self.latitude
        longitude_difference = location.longitude - self.longitude
        return math.atan2(latitude_difference, longitude_difference)

    def to_lat_long_tuple(self):
        return (
            self.latitude,
            self.longitude
        )

    def __str__(self):
        return f'[{self.latitude}, {self.longitude}]'<jupyter_output><empty_output><jupyter_text>A location is composed of its latitude and longitude. It distance to other locations is stored in a distance map, which is populated by a distance calculator:<jupyter_code>import math

class EuclideanDistanceCalculator:
    METERS_PER_DEGREE = 111_000
    
    def __init__(self):
        pass

    def calculate_distance(self, start, end):
        if start == end:
            return 0
        latitude_diff = end.latitude - start.latitude
        longitude_diff = end.longitude - start.longitude
        return math.ceil(math.sqrt(latitude_diff * latitude_diff + longitude_diff * longitude_diff) *
                         EuclideanDistanceCalculator.METERS_PER_DEGREE)

    def init_distance_maps(self, location_list):
        for location in location_list:
            distance_map = dict()
            for other_location in location_list:
                distance_map[other_location] = self.calculate_distance(location, other_location)
            location.set_distance_map(distance_map)<jupyter_output><empty_output><jupyter_text>A vehicle departs from and return to its depot:<jupyter_code>class Depot:
    def __init__(self, name, location):
        self.name = name
        self.location = location

    def __str__(self):
        return f'Depot {self.name}'<jupyter_output><empty_output><jupyter_text>A vehicle visits customers to deliever items, which take up some capacity of the vehicle:<jupyter_code>from optapy import problem_fact

@problem_fact
class Customer:
    def __init__(self, name, location, demand):
        self.name = name
        self.location = location
        self.demand = demand


    def __str__(self):
        return f'Customer {self.name}'<jupyter_output><empty_output><jupyter_text>---**NOTE**You may have noticed none of the problem fact classes are decorated with `@problem_fact`. That is because they are not referenced directly in constraints, but accessed indirectly via the Vehicle class.--- Planning EntitiesIn Vehicle Routing, vehicles are the planning entities. Each vehicle has a fixed depot to depart from and return to, and a list of customers to visit which we want to plan. In particular:- A customer is visited by exactly one vehicle- The order of the customer in the list is significantas such, the customer list can be modelled as a planning list variable:<jupyter_code>from optapy import planning_entity, planning_list_variable

@planning_entity
class Vehicle:
    def __init__(self, name, capacity, depot, customer_list=None):
        self.name = name
        self.capacity = capacity
        self.depot = depot
        if customer_list is None:
            self.customer_list = []
        else:
            self.customer_list = customer_list

    @planning_list_variable(Customer, ['customer_range'])
    def get_customer_list(self):
        return self.customer_list

    def set_customer_list(self, customer_list):
        self.customer_list = customer_list

    def get_route(self):
        if len(self.customer_list) == 0:
            return []
        route = [self.depot.location]
        for customer in self.customer_list:
            route.append(customer.location)
        route.append(self.depot.location)
        return route
    
    def __str__(self):
        return f'Vehicle {self.name}'<jupyter_output><empty_output><jupyter_text>The `@planning_list_variable` decorator tells OptaPy the method is a getter for a planning list variable. It takes two parameters:- The first parameter is the type this planning variable takes.- The second parameter, `value_range_provider_refs`, describes where it gets its values from.  It a list of the id of its value range providers. This is defined later in the `@planning_solution` class. The ConstraintsIn vehicle routing, we have one hard constraint: no vehicle can go over its capacity<jupyter_code>from optapy import get_class
from optapy.score import HardSoftScore

VehicleClass = get_class(Vehicle)

def get_total_demand(vehicle):
    total_demand = 0
    for customer in vehicle.customer_list:
        total_demand += customer.demand
    return total_demand

def vehicle_capacity(constraint_factory):
    return constraint_factory.forEach(VehicleClass) \
               .filter(lambda vehicle: get_total_demand(vehicle) > vehicle.capacity) \
               .penalize("Over vehicle capacity", HardSoftScore.ONE_HARD,
                         lambda vehicle: int(get_total_demand(vehicle) - vehicle.capacity))<jupyter_output><empty_output><jupyter_text>The lambda in penalize controls how much to penalize for a violation. We want a vehicle 5 over capacity to be penalized more than a vehicle only 1 over capacity. Hence we penalize by`get_total_demand(vehicle) - vehicle.capacity`which is how much over capacity the vehicle is.We also have one soft constraint: minimize the total distance<jupyter_code>def get_total_distance_meters(vehicle):
    total_distance = 1
    last_location = vehicle.depot.location
    for customer in vehicle.customer_list:
        total_distance += customer.location.get_distance_to(last_location)
        last_location = customer.location
    if last_location is not vehicle.depot.location:
        total_distance += vehicle.depot.location.get_distance_to(last_location)
    return total_distance

def total_distance(constraint_factory):
    return constraint_factory.forEach(VehicleClass) \
        .penalize("Minimize total distance", HardSoftScore.ONE_SOFT,
                  lambda vehicle: int(get_total_distance_meters(vehicle)))<jupyter_output><empty_output><jupyter_text>Every initialized Vehicle is penalized in the constraint, since we want to minimalize total distance.Return a list containing the constraints in a `@constraint_provider` decorated function:<jupyter_code>from optapy import constraint_provider


@constraint_provider
def vehicle_routing_constraints(constraint_factory):
    return [
        # Hard constraints
        vehicle_capacity(constraint_factory),
        
        # Soft constraints
        total_distance(constraint_factory)
    ]<jupyter_output><empty_output><jupyter_text>Planning SolutionFinally, there is the planning solution. The planning solution stores references to all the problem facts and planning entities that define the problem. Additionally, it also contain the score of the solution. The planning solution class represent both the problem and the solution; as such, a problem can be viewed as an unintialized planning solution.In Vehicle Routing, it need to container the customer list, vehicle list, and the score. The bounds are included for easier visualization of the route:<jupyter_code>from optapy import planning_solution, planning_entity_collection_property, problem_fact_collection_property, \
    value_range_provider, planning_score


@planning_solution
class VehicleRoutingSolution:
    def __init__(self,  name, location_list, depot_list, vehicle_list, customer_list,
                 south_west_corner, north_east_corner, score=None):
        self.name = name
        self.location_list = location_list
        self.depot_list = depot_list
        self.vehicle_list = vehicle_list
        self.customer_list = customer_list
        self.south_west_corner = south_west_corner
        self.north_east_corner = north_east_corner
        self.score = score

    @planning_entity_collection_property(Vehicle)
    def get_vehicle_list(self):
        return self.vehicle_list

    @problem_fact_collection_property(Customer)
    @value_range_provider('customer_range', value_range_type=list)
    def get_customer_list(self):
        return self.customer_list

    @planning_score(HardSoftScore)
    def get_score(self):
        return self.score

    def set_score(self, score):
        self.score = score

    def get_bounds(self):
        return [self.south_west_corner.to_lat_long_tuple(), self.north_east_corner.to_lat_long_tuple()]

    def get_distance_meters(self):
        return -self.score.getSoftScore() if self.score is not None else 0<jupyter_output><empty_output><jupyter_text>SolvingNow that we defined our model and constraints, let create an instance of the problem:<jupyter_code>from datetime import time

from demo import DemoDataBuilder

problem = DemoDataBuilder.builder(Location, Depot, Customer, Vehicle, VehicleRoutingSolution, 
                                  EuclideanDistanceCalculator()) \
                                 .set_min_demand(1).set_max_demand(2).set_vehicle_capacity(25) \
                                 .set_customer_count(77).set_vehicle_count(6).set_depot_count(2) \
                                 .set_south_west_corner(Location(43.751466, 11.177210)) \
                                 .set_north_east_corner(Location(43.809291, 11.290195)).build()<jupyter_output><empty_output><jupyter_text>and solve it:<jupyter_code>from optapy import solver_manager_create
import optapy.config
from optapy.types import Duration
from ipyleaflet import Map, CircleMarker, Polyline, basemaps

SINGLETON_ID = 1
solver_config = optapy.config.solver.SolverConfig()
solver_config \
    .withSolutionClass(get_class(VehicleRoutingSolution)) \
    .withEntityClasses(get_class(Vehicle)) \
    .withConstraintProviderClass(get_class(vehicle_routing_constraints)) \
    .withTerminationSpentLimit(Duration.ofSeconds(30))

solver_manager = solver_manager_create(solver_config)
last_score = HardSoftScore.ZERO

vehicle_routing_solution = problem

color_index = 0
def generate_color():
    global color_index
    colors =  (
      'aqua',
      'aquamarine',
      'blue',
      'blueviolet',
      'chocolate',
      'cornflowerblue',
      'crimson',
      'forestgreen',
      'gold',
      'lawngreen',
      'limegreen',
      'maroon',
      'mediumvioletred',
      'orange',
      'slateblue',
      'tomato'
    )
    out = colors[color_index]
    color_index = (color_index + 1) % len(colors)
    return out

routing_plan = Map(basemap=basemaps.OpenStreetMap.Mapnik)


vehicle_to_route_dict = dict()
customer_to_marker_dict = dict()

for customer in problem.customer_list:
    marker = CircleMarker(location=customer.location.to_lat_long_tuple(), color='white',
                          radius=5)
    customer_to_marker_dict[customer.name] = marker
    routing_plan.add_layer(marker)
    
for depot in problem.depot_list:
    routing_plan.add_layer(CircleMarker(location=depot.location.to_lat_long_tuple(), color='black',
                                        radius=10))


for vehicle in problem.vehicle_list:
    vehicle_to_route_dict[vehicle.name] = Polyline(
        locations=[],
        color=generate_color(),
        fill=False)
    routing_plan.add_layer(vehicle_to_route_dict[vehicle.name])
    
def update_routes(best_solution):
    for vehicle in best_solution.vehicle_list:
        route = vehicle_to_route_dict[vehicle.name]
        for customer in vehicle.customer_list:
            customer_to_marker_dict[customer.name].color = route.color
        locations = [vehicle.depot.location.to_lat_long_tuple()]
        locations.extend(map(lambda customer: customer.location.to_lat_long_tuple(), vehicle.customer_list))
        locations.append(locations[0])
        route.locations = locations

routing_plan.fit_bounds(problem.get_bounds())
solver_manager.solveAndListen(SINGLETON_ID, lambda _: problem, update_routes)
routing_plan<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0677243500139782, 'fraction_numerical': 0.004542913055633212, 'mean_word_length': 3.8554462164913472, 'pattern_counts': {'":': 0, '<': 45, '<?xml version=': 0, '>': 46, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '215748', 'license': 'Apache-2.0', 'n_tokens_mistral': 4047, 'n_tokens_neox': 3864, 'n_words': 1164, 'path': 'vehicle-routing/vehicle-routing-quickstart.ipynb', 'repo_name': 'optapy/optapy-quickstarts', 'size': '14308'}