Solution to find optimal number of vehicles (instead of given as input)

[bilics]

Hello!

I have successfully ran the vehicle routing example. But my question is:

Is it possible to model the problem such as that the number of vehicles is not given as input?

Imagine that I need to find the optimal number of vehicles that minimizes a cost function that is related to "price per km" - so for instance, there are several types of vehicles (with different capacities, different fuel consumptions, etc) that can be "grabbed" from a pool.

Is this possible with optapy? If so, how would I model this?

Thanks in advance!

[Christopher-Chianelli]

Currently, the number of vehicles need to be known from advance. The way this problem is solved in OptaPlanner (and thus OptaPy) is to use virtual values (https://www.optapy.org/docs/latest/repeated-planning/repeated-planning.html#overconstrainedPlanningWithVirtualValues). A model would probably look like this:

class VehicleKind(Enum):
    KIND_A
    KIND_B
    KIND_C
    # ...

@planning_entity
class Vehicle:
    id: int
    capacity: int
    depot: Depot
    kind: VehicleKind
    customer_list: list[Customer]

    def __init__(self, _id, kind, capacity, depot, customer_list=None):
        self.id = _id
        self.capacity = capacity
        self.kind = kind
        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_cost(self):
        if kind == KIND_A:
            return calc_cost_a(...)
        ...

Your @planning_entity_collection_property will have more vehicles than will be used; the vehicles that are unused will have an empty customer_list. To minimize the number of vehicles used, use a medium constraint that penalizes vehicles with a non-empty customer list (so it'll weigh more than all soft, and less than any hard).

def minimize_used_vehicles(constraint_factory):
    return (
        constraint_factory.for_each(Vehicle)
                                    .filter(lambda vehicle: len(vehicle.customer_list) > 0)
                                    .penalize('Minimize Used Vehicles', HardMediumSoftScore.ONE_MEDIUM)
    )

[bilics]

Thanks @Christopher-Chianelli - that was fast! I will try these suggestions and post back here.

[bilics]

Hi again @Christopher-Chianelli -

HardMediumSoftScore.ONE_MEDIUM) should be HardSoftScore.ONE_MEDIUM?

And regarding the

 def get_cost(self):
        if kind == KIND_A:
            return calc_cost_a(...)
        ...

where/how exactly do I call this function? I thought it would be called in the filter inside def minimize_used_vehicles(constraint_factory): but your example shows otherwise a different filter.

Thanks again

[Christopher-Chianelli]

HardMediumSoftScore.ONE_MEDIUM should be HardMediumSoftScore.ONE_MEDIUM; OptaPlanner and OptaPy have different score types, which are used in different situations. You need to change HardSoftScore to HardMediumSoftScore in all your constraints and also in the @planning_score decorator of the @planning_solution.

You call the get_cost function in a penalize call (like total_distance):

def total_cost(constraint_factory: ConstraintFactory):
    return constraint_factory.for_each(Vehicle) \
        .penalize("minimize cost", HardMediumSoftScore.ONE_SOFT,
                  lambda vehicle: vehicle.get_cost())

[bilics]

Thanks @Christopher-Chianelli - made it run, and seems to work!

One more question regarding the cost functions get_total_distance_meters and get_total_demand (and the newly introduced one total_cost):

Should these values be normalized? For instance, demands are in Kg and distance in meters, but the total_cost is "unitless". How are they compared (and taken into account) in the optimization?

Sorry about these newby questions - trying to learn how to use this library.

[Christopher-Chianelli]

Units are not taken into account during optimization; all penalties and rewards are unitless. What you want to do is determine how much score impact you want to have per unit. For instance, you might want to impact the score by -1soft for each 100 meters travelled. In which case, you will do penalize('distance travelled', HardMediumSoftScore.ONE_SOFT, lambda distance_travelled: distance_travelled // 100) (note: use int division; you cannot return a float in penalize). You can also impact by a nonlinear amount; for instance, to impact the score by -1 by the square of distance travelled, do penalize('distance travelled', HardMediumSoftScore.ONE_SOFT, lambda distance_travelled: distance_travelled**2)

[bilics]

Understood thanks - testing out various combinations here.

However, this

def total_cost(constraint_factory: ConstraintFactory):
    return constraint_factory.for_each(Vehicle) \
        .penalize("minimize cost", HardMediumSoftScore.ONE_SOFT,
                  lambda vehicle: vehicle.get_cost())

does not seems to influence the results - no matter how high (or low) I set the cost for a particular "kind" of vehicle.

Any pointers on how I can debug this?

Thanks again @Christopher-Chianelli

[Christopher-Chianelli]

Did you add it in the @constraint_provider function? i.e. @constraint_provider should look like this:

@constraint_provider
def vehicle_routing_constraints(constraint_factory: ConstraintFactory):
    return [
            vehicle_capacity(constraint_factory),
            total_distance(constraint_factory),
            total_cost(constraint_factory) # this line was added
        ]

[bilics]

Yes I did