I am just starting using OptaPy, I tried to mimic the VRP quickstart and created the classes as such:
# The place to start the journey and end it.
@problem_fact
class Depot:
def __init__(self, name, location):
self.name = name
self.location = location
def __str__(self):
return f'Depot {self.name}'
# The customers information.
@problem_fact
class Customer:
def __init__(self, id, # Initially 1
name, # Will be the order_id
location,
demand, # Turned out, only 1 order per customer. So, Will always be initited with "1". Will leave it for flexibility, in case more than one order per order ID is placed.
cbm ,required_skills = set(),
order_weight=None,
polygon = None,
district = None,
):
self.id = id
self.name = name
self.location = location # The location of the customer, a location object
self.demand = demand # Number of Orders
self.cbm = cbm # Order CBM
self.required_skills = required_skills # A set of the skills in his orders.
self.order_weight = order_weight
self.polygon = polygon
self.district = district
def __str__(self):
return f'Customer {self.name}, In Polygon: {self.polygon}, In District: {self.district}'
And then the Vehicle Class:
from optapy import planning_entity, planning_list_variable
@planning_entity
class Vehicle:
def __init__(self, name, max_number_orders, # max_number_orders here refers to vehicles maximum number of orders it can carry.
cbm, depot, customer_list=None, working_seconds = 28_800, # 8 Hours of work days
service_time = 900, # Defaults to 15 minutes to drop an order.
car_skills = set(),
weight = None ,# If None, This means the vehicle has no constraints over weight.
fixed_cost = 0.0, # If 0.0, This means the vehicle has no cost, same goes for variable.
variable_cost = 0.0, # This should be the cost per kilometer E.G: 15 Price Unit / KM this means that this vehicle is paid 15 (any currency) Per Kilometer
):
self.name = name
self.max_number_orders = max_number_orders # Vehicle Constraint
self.cbm = cbm # Vehicle Constraint
self.depot = depot # Pass Object
if customer_list is None: # Pass Object Else Empty List
self.customer_list = []
else:
self.customer_list = customer_list
self.working_seconds = working_seconds # 8 Hours Shift
self.service_time = service_time # It typically takes 15 minutes to drop the order from the car to the retailer.
# Can be ignored and be precomputed with pandas and only assign vehicles to orders it can take ALL of it.
# But for testing purpose, I will implement it using sets and loops in a constraint fashion.
self.car_skills = car_skills # Should be a set that contains the contains the skills a vehicle can take, matching it with orders
self.weight = weight
self.fixed_cost = fixed_cost
self.variable_cost = variable_cost
# Because the order of the list is significant, optapy can alter or reindex the list given a Customer object
# And assign a range (index) to each customer
@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):
"""
The route is typically:
depot > location_1 > location_2 ..... > location_n > depot again
If no routes at all, return an empty list.
Optapy will change the order of the location for each customer after each evaluation iteration after the score updates.
"""
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}'
The problem is here:
from optapy.score import HardSoftScore
from optapy.constraint import Joiners
from optapy import get_class
def get_total_demand(vehicle):
"""
Calculate the total demand (e.g., number of items) assigned to a vehicle.
Args:
vehicle (Vehicle): The vehicle for which to calculate the total demand.
Returns:
int: The total demand assigned to the vehicle.
"""
total_demand = 0
for customer in vehicle.customer_list:
total_demand += int(customer.demand) # Explicitly cast to int
return total_demand
def vehicle_capacity(constraint_factory):
"""
Enforce the vehicle capacity constraint.
This constraint ensures that the total demand assigned to a vehicle does not exceed its capacity.
Args:
constraint_factory (ConstraintFactory): The factory to create constraints.
Returns:
Constraint: The constraint penalizing vehicles that exceed their capacity.
"""
return constraint_factory \
.for_each(get_class(Vehicle)) \
.filter(lambda vehicle: get_total_demand(vehicle) > int(vehicle.max_number_orders)) \
.penalize("Over vehicle max_number_orders", HardSoftScore.ONE_HARD,
lambda vehicle: int(get_total_demand(vehicle) - int(vehicle.max_number_orders)))
This constraint is not respected and then I followed the quickstart in configuring the model
from optapy import planning_solution, planning_entity_collection_property, problem_fact_collection_property, \
value_range_provider, planning_score
@planning_solution
class VehicleRoutingSolution:
"""
The VehicleRoutingSolution class represents both the problem and the solution
in the vehicle routing domain. It stores references to all the problem facts
(locations, depots, customers) and planning entities (vehicles) that define the problem.
Attributes:
name (str): The name of the solution.
location_list (list of Location): A list of all locations involved in the routing.
depot_list (list of Depot): A list of depots where vehicles start and end their routes.
vehicle_list (list of Vehicle): A list of all vehicles used in the routing problem.
customer_list (list of Customer): A list of all customers to be served by the vehicles.
south_west_corner (Location): The southwestern corner of the bounding box for visualization.
north_east_corner (Location): The northeastern corner of the bounding box for visualization.
score (HardSoftScore, optional): The score of the solution, reflecting the quality of the solution.
"""
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
@problem_fact_collection_property(Location)
def get_location_list(self):
return self.location_list
@problem_fact_collection_property(Depot)
def get_depot_list(self):
return self.depot_list
@planning_score(HardSoftScore)
def get_score(self):
return self.score
def set_score(self, score):
self.score = score
def get_bounds(self):
"""
Get the bounding box coordinates for visualizing the solution.
Returns:
list: A list containing the coordinates of the southwest and northeast corners.
"""
return [self.south_west_corner.to_lat_long_tuple(), self.north_east_corner.to_lat_long_tuple()]
def total_score(self):
"""
Calculate the total soft score.
"""
return -self.score.getSoftScore() if self.score is not None else 0
Here's the problem, I gave the model a vehicle with maximum_orders of 26, the model should not assign more than 26 customers or orders classes to that vehicle, but it gives it all the orders. If Increased the number of cars, it divides the routes on them randomly, also violating the constraint
# Step 1: Setup the solver manager with the appropriate config
solver_config = optapy.config.solver.SolverConfig()
solver_config \
.withEnvironmentMode(optapy.config.solver.EnvironmentMode.FULL_ASSERT)\
.withSolutionClass(VehicleRoutingSolution) \
.withEntityClasses(Vehicle) \
.withConstraintProviderClass(vehicle_routing_constraints) \
.withTerminationSpentLimit(Duration.ofSeconds(20)) # Adjust termination as necessary
# Step 2: Create the solver manager
solver_manager = solver_manager_create(solver_config)
# # Create the initial solution for the solver
solution = VehicleRoutingSolution(
name="Vehicle Routing Problem with Random Data",
location_list=locations,
depot_list=depots,
vehicle_list=vehicles,
customer_list=customers,
south_west_corner=Location(29.990707246305476, 31.229210746581806),
north_east_corner=Location(30.024396202211875, 31.262640488654238)
)
# Step 3: Solve the problem and get the solver job
SINGLETON_ID = 1 # A unique problem ID (can be any number)
solver_job = solver_manager.solve(SINGLETON_ID, lambda _: solution)
# Step 4: Get the best solution from the solver job
best_solution = solver_job.getFinalBestSolution()
# Step 5: Extract and print the results
def extract_vehicle_routes(best_solution):
for vehicle in best_solution.vehicle_list:
print(f"Vehicle: {vehicle.name}")
print("Route:")
total_orders = 0
total_weight = 0
total_cbm = 0
for customer in vehicle.customer_list:
location = customer.location.to_lat_long_tuple()
total_orders += 1
total_weight += customer.order_weight
total_cbm += customer.cbm
print(f"Customer {customer.name}: {location}")
# Print the return to depot
print(f"Return to depot: {vehicle.depot.location.to_lat_long_tuple()}")
print(f"Total Orders: {total_orders}")
print(f"Total Weight: {total_weight}")
print(f"Total CBM: {total_cbm}")
print("=" * 30)
# Call the function to display the routes
extract_vehicle_routes(best_solution)
The Output:
Customer Order ID: 8595424: (30.24544623697703, 31.24484896659851)
......
......
Return to depot: (29.996699, 31.278772)
Total Orders: 50
Total Weight: 3924.2847300000003
Total CBM: 7.518601279012999
==============================
And here're the vehicle's info:
vehicles[0].cbm, vehicles[0].weight, vehicles[0].max_number_orders
>>> (4.0, 1700.0, 27)
The problem was that the model cannot relax the problem, so instead of breaking it returned unreasonable results, When I gave it 1 vehicle and 50 orders and the vehicle capacity was 26, it assigned all the 50 orders on that vehicle.
But when I increased vehicles to 2, it found a feasible solution and returned 26, 24 respectively.