Vehicle Routing drop visit demand if hard score goes to negative

[sharmas1ddharth]

I am developing a Vehicle Routing application using timefold and want to drop visit demand if my constraint hard score go to negative, for example my vehicle capacity is 5 and I have total 8 orders my constraint is vehicle capacity with hard score penalize , currently timefold will assign all 8 orders to that vehicle but with negative hard score, how to achieve that timefold will drop some demands to make score positive

[Christopher-Chianelli]

Use allows_unassigned_values on the PlanningListVariable annotation, and add a constraint that penalize by a medium score for each unassigned order.

For example, on your vehicle class:

@planning_entity
class Vehicle:
    orders: Annotated[list[Order], PlanningListVariable(allows_unassigned_values=True)]
    ...

on your order class, there should be a InverseRelationShadowVariable attribute:

@planning_entity
class Order:
    vehicle: Annotated[Vehicle | None, InverseRelationShadowVariable(source_variable_name='orders')]
    ...

and in your constraint provider

def unassigned_order(constraint_factory: ConstraintFactory) -> Constraint:
    return (constraint_factory.for_each_including_unassigned(Order)
                                                  .filter(lambda order: order.vehicle is None)
                                                  .penalize(HardMediumSoftScore.ONE_MEDIUM)
                                                  .as_constraint("Unassigned Order")
    )

You will need to change the score type in your planning_solution and other constraints to HardMediumSoftScore.

[sharmas1ddharth]

I did the same but customers are not assigning to vehicle and status changes to NOT_SOLVING without any error

My constraints:

from timefold.solver.score import ConstraintFactory, HardMediumSoftScore, constraint_provider

from src.domain.customer_vehicle import Customer, Vehicle

VEHICLE_CAPACITY = "vehicleCapacity"
MINIMIZE_TRAVEL_TIME = "minimizeTravelTime"
SERVICE_FINISHED_AFTER_MAX_END_TIME = "serviceFinishedAfterMaxEndTime"
PRIORITIZE_OLDER_DATES = "prioritize_older_dates"
MINIMIZE_TRAVEL_DISTANCE = "minimizeTravelDistance"
UNASSIGNED_CUSTOMER = "UnassignedCustomer"


@constraint_provider
def define_constraints(factory: ConstraintFactory):
    return [
        # Hard constraints
        vehicle_capacity(factory),
        service_finished_after_max_end_time(factory),
        prioritize_older_dates(factory),
        minimize_travel_distance(factory),
        # Soft constraints
        minimize_travel_time(factory),
        unassigned_order(factory)
    ]


##############################################
# Hard constraints
##############################################


def vehicle_capacity(factory: ConstraintFactory):
    return (
        factory.for_each(Vehicle)
        .filter(lambda vehicle: vehicle.calculate_total_demand() > vehicle.capacity)
        .penalize(
            HardMediumSoftScore.of_hard(5),
            lambda vehicle: vehicle.calculate_total_demand() - vehicle.capacity,
        )
        .as_constraint(VEHICLE_CAPACITY)
    )


def service_finished_after_max_end_time(factory: ConstraintFactory):
    return (
        factory.for_each(Customer)
        .filter(lambda customer: customer.is_service_finished_after_due_time())
        .penalize(
            HardMediumSoftScore.of_hard(1),
            lambda customer: customer.get_service_finished_delay_in_minutes(),
        )
        .as_constraint(SERVICE_FINISHED_AFTER_MAX_END_TIME)
    )


def prioritize_older_dates(factory: ConstraintFactory):
    return (
        factory.for_each(Customer)
        .filter(lambda customer: customer.get_days_since_request() < customer.days)
        .penalize(
            HardMediumSoftScore.of_hard(1), lambda customer: customer.get_days_since_request()
        )
        .as_constraint(PRIORITIZE_OLDER_DATES)
    )


def minimize_travel_distance(factory: ConstraintFactory):
    return (
        factory.for_each(Vehicle)
        .penalize(
            HardMediumSoftScore.of_soft(5),
            lambda vehicle: vehicle.calculate_total_driving_distance_meters(),
        )
        .as_constraint(MINIMIZE_TRAVEL_DISTANCE)
    )


def minimize_travel_time(factory: ConstraintFactory):
    return (
        factory.for_each(Vehicle)
        .penalize(
            HardMediumSoftScore.of_soft(1),
            lambda vehicle: vehicle.calculate_total_driving_time_seconds(),
        )
        .as_constraint(MINIMIZE_TRAVEL_TIME)
    )

def unassigned_order(constraint_factory: ConstraintFactory):
    return (constraint_factory.for_each_including_unassigned(Customer)
                                                  .filter(lambda customer: customer.vehicle is None)
                                                  .penalize(HardMediumSoftScore.ONE_MEDIUM)
                                                  .as_constraint(UNASSIGNED_CUSTOMER)
    )

my planning solution class:

from datetime import datetime
from typing import Annotated, Any, List, Optional

from pydantic import Field, computed_field
from timefold.solver import SolverStatus
from timefold.solver.domain import (
    PlanningEntityCollectionProperty,
    PlanningScore,
    ValueRangeProvider,
    planning_solution,
)
from timefold.solver.score import ScoreExplanation, HardMediumSoftScore

from src.constraint_configuration import VehicleRoutingConstraintConfiguration
from src.domain.customer_vehicle import Customer, Vehicle
from src.domain.depot import Depot
from src.domain.location import Location
from src.duration_distance_service import (
    DurationDistanceResponse,
    DurationDistanceService,
)
from src.json_serialization import (
    BeforeValidator,
    JsonDomainBase,
    LocationSerializer,
    ScoreSerializer,
    ScoreValidator,
)


def location_validator(location):
    if isinstance(location, Location):
        return location
    elif isinstance(location, Depot):
        return location.location
    else:
        return Location(
            longitude=location[0],
            latitude=location[1],
        )


LocationValidator = BeforeValidator(lambda location: location_validator(location))


@planning_solution
class VehicleRoutePlan(JsonDomainBase):
    name: str
    depots: List[Depot]
    southWestCorner: Annotated[Location, LocationSerializer, LocationValidator]
    northEastCorner: Annotated[Location, LocationSerializer, LocationValidator]
    vehicles: Annotated[list[Vehicle], PlanningEntityCollectionProperty]
    customers: Annotated[
        list[Customer], PlanningEntityCollectionProperty, ValueRangeProvider
    ]
    score: Annotated[
        Optional[HardMediumSoftScore],
        PlanningScore,
        ScoreSerializer,
        ScoreValidator,
        Field(default=None),
    ]
    durationResponse: DurationDistanceResponse
    startDateTime: Optional[datetime] = None
    endDateTime: Optional[datetime] = None
    extraLocationCount: Optional[int] = 0

    def __init__(self, /, **data: Any):
        super().__init__(**data)
        if self.customers:
            locations = [vehicle.depot.location for vehicle in self.vehicles] + [
                customer.location for customer in self.customers
            ]
            duration_service = DurationDistanceService()
            duration_service.update_locations_with_durations(
                locations, self.durationResponse
            )
            duration_service.update_locations_with_distance(
                locations, self.durationResponse
            )

    @computed_field
    @property
    def total_driving_time_seconds(self) -> int:
        print("solving")
        out = 0
        for vehicle in self.vehicles:
            out += vehicle.total_driving_time_seconds

        for customer in self.customers:
            out += customer.service_duration.seconds

        return out

    @computed_field
    @property
    def total_driving_distance_meters(self) -> int:
        out = 0
        for vehicle in self.vehicles:
            out += vehicle.total_driving_distance_meters
        return out

    @computed_field
    @property
    def total_fuel_liter(self) -> float:
        out = 0
        for vehicle in self.vehicles:
            out += vehicle.total_fuel_litre
        return out

    def __str__(self):
        return f"VehicleRoutePlan(name={self.name}, vehicles={self.vehicles}, customers={self.customers}),\
        southWestCorner={self.southWestCorner}, extraLocationCount={self.extraLocationCount}"

[Christopher-Chianelli]

If some customers are not assigned a vehicle, that is expected when using allow_unassigned_values. If all customers are not assigned a vehicle, there is probably a bug in one of your constraints. To find it, either create ConstraintVerifier tests or use SolutionManager to explain the score of a solution you know to be feasible.

[sharmas1ddharth]

I have commented my all of the constraints except vehicle capacity still customer are not assigning to any vehicle, no customer is assigned to any vehicle

[Christopher-Chianelli]

Does your solver code look like this?

problem = ...
solver.solve(problem)
print(problem)

If so, that is expected; problem is unmodified; solve returns a new object. Do this instead:

problem = ...
solution = solver.solve(problem)
print(solution)

(note: you should have unassigned_order enabled; since otherwise the solver has no incentive to assign orders)

[sharmas1ddharth]

Hey, solved it successfully thank you so much for your help.