我刚刚开始使用 OptaPy，我尝试模仿 VRP 快速入门 并创建了这样的类：
# 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}'
然后是车辆类别：
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}'
问题就在这里：
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)))
不遵守此约束，然后我按照快速入门配置模型
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
问题来了，我给模型一个
maximum_orders# 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)
输出：
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
==============================
这是车辆的信息：
vehicles[0].cbm, vehicles[0].weight, vehicles[0].max_number_orders
>>> (4.0, 1700.0, 27)
问题是模型无法放松问题，所以它没有打破它，而是返回了不合理的结果，当我给它 1 辆车和 50 个订单并且车辆容量为 26 时，它分配了该车辆上的所有 50 个订单。
但是当我将车辆增加到2时，它找到了可行的解决方案并分别返回了26、24。