Prioritizing high-cost deliveries with time windows and custom constraints

[Domeless]

Hello,
I'm working on a delivery routing problem that includes time windows and an additional constraint on the number of deliveries per driver, which depends on the route distance.
I wanted to introduce prioritization for deliveries, such that if there are multiple possible options, the solver prefers the ones with higher "cost" (priority).
To implement this, I added a custom dimension "Cost" that accumulates the delivery priority. Then, for each route end, I used:
cost_dimension.SetCumulVarSoftLowerBound(end, 300, 500)
to encourage the solver to select deliveries with a higher total cost per vehicle.
In this case, 300 is the total cost sum of all available deliveries, so this constraint essentially encourages the solver to keep as many high-cost deliveries as possible.

In my test, I have:

1. 4 identical delivery tasks (same time windows, distance, etc.),
2. only one vehicle available,
3. and my rules allow only 3 deliveries per route.

The only difference between the 4 deliveries is their cost value.
I expected the solver to exclude the lowest-cost delivery from the route. However, what I observe is that the last delivery in the list is always excluded — regardless of its cost. It seems the cost is not being taken into account during tie-breaking or final assignment.

How can I make sure that, when multiple delivery combinations are possible, the solver selects the set with the highest total cost, while still respecting the time windows and delivery limits per route?

Is there a better way to force the solver to optimize for delivery cost in this situation?

Any suggestions or patterns would be greatly appreciated!

Thank you!

def main(g: Graph):
    """Entry point of the program."""
    # Instantiate the data problem.
    manager = pywrapcp.RoutingIndexManager(len(g), len(g.trucks), 0)
    routing = pywrapcp.RoutingModel(manager)

    # penalty for skipping nodes
    for node in g._nodes:
        if node.is_skippable:
            routing.AddDisjunction([manager.NodeToIndex(node.index)], 0)
        else:
            routing.AddDisjunction([manager.NodeToIndex(node.index)], 1000000)

    ### TIME
    def time_callback(vehicle, from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        if from_node == to_node:
            return 0
        try:
            # route time + on node time
            # print(f"{from_node}({from_index})->{to_node}({to_index}) [{vehicle}---{d}]")
            return g.transit_with_conditionals(from_node, to_node, vehicle).time + g.hold_time(from_node)
        except Exception as e:
            pass
        return -1

    time_vehicle_transits = [routing.RegisterTransitCallback(partial(time_callback, v)) for v in range(len(g.trucks))]

    time_vehicle_costs = [
        routing.SetArcCostEvaluatorOfVehicle(t, v) for (t, v) in zip(time_vehicle_transits, range(len(g.trucks)))
    ]

    time = "Time"
    routing.AddDimensionWithVehicleTransits(
        time_vehicle_transits,
        120,  # slack
        100000,  # vehicle maximum travel distance
        False,  # start cumul to zero
        time,
    )
    time_dimension = routing.GetDimensionOrDie(time)

    for node in g._nodes:
        if node.time_window:
            index = manager.NodeToIndex(node.index)
            time_dimension.CumulVar(index).SetRange(node.time_window[0], node.time_window[1])

    for i in range(len(g.trucks)):
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

    ### TIME

    ### COST
    cost_dimension_name = "Cost"

    def cost_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return -g._nodes[from_node].cost

    cost_callback_index = routing.RegisterUnaryTransitCallback(cost_callback)

    routing.AddDimensionWithVehicleCapacity(
        cost_callback_index,
        1000,  # null capacity slack
        [g.full_cost + 1 for t in g.trucks],  # vehicle maximum capacities
        True,  # start cumul to zero
        cost_dimension_name,
    )
    cost_dimension = routing.GetDimensionOrDie(cost_dimension_name)

    for i in range(len(g.trucks)):
        end = routing.End(i)
        cost_dimension.SetCumulVarSoftLowerBound(end, 300, 500)

    ## COST

    ## COUNT
    count_dimension_name = "Count"

    def count_callback(from_index):
        """Returns the demand of the node."""
        from_node = manager.IndexToNode(from_index)
        return g._nodes[from_node].count

    count_callback_index = routing.RegisterUnaryTransitCallback(count_callback)
    routing.AddDimensionWithVehicleCapacity(
        count_callback_index,
        0,  # null capacity slack
        [t.max_delivery_count for t in g.trucks],  # vehicle maximum capacities
        True,  # start cumul to zero
        count_dimension_name,
    )
    count_dimension = routing.GetDimensionOrDie(count_dimension_name)

    solver = routing.solver()
    for t_id, t in enumerate(g.trucks):
        index = routing.End(t_id)
        end_count = count_dimension.CumulVar(index)
        c1 = [end_count == 0, (end_count > t.min_delivery_count) == (end_count < t.max_delivery_count)]
        # c1.append(end_count == 0)
        solver.Add(sum(c1) != 0)
        # solver.Add(end_count == 0)

    # forces drivers to do something
    for t_id, t in enumerate(g.trucks):
        index_end = routing.End(t_id)
        count_dimension.SetCumulVarSoftLowerBound(index_end, t.min_delivery_count, 50000)

    ### COUNT

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    # search_parameters.first_solution_strategy = (
    #     routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    # )
    search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    search_parameters.time_limit.seconds = 30
    # search_parameters.log_search = True
    # search_parameters.time_limit.FromSeconds(20)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(g, manager, routing, solution)
        return solution_to_dict(g, manager, routing, solution)
    else:
        print("Empty solution")
    return []

[weihenglim]

# penalty for skipping nodes
    for node in g._nodes:
        if node.is_skippable:
            routing.AddDisjunction([manager.NodeToIndex(node.index)], 0)

Why not set the cost as the penalty for dropping a node instead of setting it to 0 for all nodes? Though you might need to multiply the cost by a coefficient if you want it to be the predominant factor in the objective function.