Messy routes in case of nodes with late Time Window start

Question

SeeI'm facing an issue when I have a node with late time window.

In more detail:

I have 10 nodes with TWs [ 0,horizon ] and one node with TW start at 2pm until horizon.

When I ask for routing without that node the whole route ends at 12pm.

When I introduce that node, the route is full of circles, trying to delay so the time will be 2pm in order to fulfil that node.

I have slack enabled but it never use this slack, routing prefers to make messy routes.

Time windows are modeled on solver through time dimension's CumulVal limits link Setting CumulVar's Min [ ->SetMin() ] and Max [ ->SetMax() ].

Also, for the slack we set its Node's SlackVar [ ->SetMax() ] equal to Horizon.

Finally, on time dimension we set slack_max = horizon and force_start_cumul_to_zero = false

The thing I want to achieve is to make the solver to offer a optimized route with that node at the end of the sequence (and use slack at that point).

#include "ortools/constraint_solver/routing_parameters.h"
#include "ortools/constraint_solver/routing_parameters.pb.h"
#include "ortools/constraint_solver/routing.h"

using operations_research::RoutingIndexManager;
using operations_research::RoutingModel;
using operations_research::RoutingDimension;
using operations_research::Assignment;
using operations_research::DefaultRoutingSearchParameters;


int main(int argc, char **argv) {
    // Orders
    int64_t const kNumberOfOrders = 10;

    // Time variables
    int64_t const kHorizon = 10000;
    int64_t const kTimeSlackMax = kHorizon;

    // Vehicles
    int64_t const kNumberOfVehicles = 1;
    int64_t const kVehicleMaxCapacity = 100;
    auto vehicle_starts = std::vector<RoutingIndexManager::NodeIndex>{0};
    auto vehicle_ends = std::vector<RoutingIndexManager::NodeIndex>{1};

    // Index & Routing model
    RoutingIndexManager routing_index_manager(
            kNumberOfOrders + vehicle_starts.size() + vehicle_ends.size(),
            kNumberOfVehicles,
            vehicle_starts,
            vehicle_ends
    );
    RoutingModel routing_model(routing_index_manager);


    ///// Setup Time Dimension /////
    // transit callback
    operations_research::RoutingModel::TransitCallback2 time_transit_callback_2 = [](
            int64_t from,
            int64_t to
    ) {
        // @NOTICE: JUST FOR DEMONSTRATION
        return 1;
    };

    // vector with time-transit-callback indices per vehicle
    auto time_transit_callback_2_indices = std::vector<int>{
            // Transit callback for vehicle 1
            routing_model.RegisterTransitCallback(
                    time_transit_callback_2
            )
    };

    // Help var
    std::vector<int64_t> vehicle_time_limits(
            kNumberOfVehicles,
            kHorizon
    );

    // Setup time dim
    routing_model.AddDimensionWithVehicleTransitAndCapacity(
            time_transit_callback_2_indices,
            kTimeSlackMax,
            vehicle_time_limits,
            false,
            "Time"
    );

    // Reference to Time Dimension
    const RoutingDimension &time_dimension = routing_model.GetDimensionOrDie("Time");


    ///// Setup Demand Dimension /////
    // The demand callback
    operations_research::RoutingModel::TransitCallback1 demand_transit_callback_1 = [](
            int64_t from
    ) {
        // @NOTICE: JUST FOR DEMONSTRATION
        return 1;
    };

    auto demand_transit_callback_1_index = routing_model.RegisterUnaryTransitCallback(
            demand_transit_callback_1
    );

    // Help var
    std::vector<int64_t> vehicle_capacity_limits(
            kNumberOfVehicles,
            kVehicleMaxCapacity
    );

    // Setup time dim
    routing_model.AddDimensionWithVehicleCapacity(
            demand_transit_callback_1_index,
            0,
            vehicle_capacity_limits,
            true,
            "Demand"
    );

    // Reference to Demand Dimension
    const RoutingDimension &demand_dimension = routing_model.GetDimensionOrDie("Demand");


    // Adding penalty costs to allow skipping orders.
    const int64_t kUnperformedNodePenalty = 30000;
    for (
            int64_t node_index = 0;
            node_index < routing_index_manager.num_indices();
            node_index++
            ) {
        if (
                !routing_model.IsStart(node_index) // not start
                && !routing_model.IsEnd(node_index) // not end
                ) {
            routing_model.AddDisjunction(
                    {node_index},
                    kUnperformedNodePenalty,
                    1
            );
        }
    }


     // Setup Time Windows (Non-Depot nodes)
     // I keep configs for each node and here I reference this array and take start/end.
     // So, each node can have different start/end

    for (
            int64_t node_index = 0;
            node_index < routing_index_manager.num_indices();
            node_index++
            ) {
        if (
                !routing_model.IsStart(node_index) // not start
                && !routing_model.IsEnd(node_index) // not end
                ) {
            // Start
            time_dimension.CumulVar(node_index)->SetMin(
                    0
                    // e.g `tw[node_index].start`
            );

            // End
            time_dimension.CumulVar(node_index)->SetMin(
                    kHorizon
                    // e.g `tw[node_index].end`
            );
        }
    }

    // Get solver
    operations_research::Solver *const solver = routing_model.solver();

    // Setup Time Windows (Depot nodes)
    // @NOTICE: Sometimes vehicles can start later (have some offset) or finish earlier.
    //          When this happens I use constraints to model that
    for (
            int64_t vehicle_idx = 0;
            vehicle_idx < routing_index_manager.num_vehicles();
            vehicle_idx++
            ) {
        // Constraint for start
        solver->AddConstraint(
                solver->MakeEquality(
                        time_dimension.CumulVar(routing_model.Start(vehicle_idx)),
                        0
                        // e.g `vehicle[vehicle_idx].start`
                )
        );

        // Fix end
        solver->AddConstraint(
                solver->MakeLessOrEqual(
                        time_dimension.CumulVar(routing_model.End(vehicle_idx)),
                        kHorizon
                        // e.g `vehicle[vehicle_idx].end`
                )
        );
    }


    // Setup Finalizers
    {
        // For depot nodes
        for (
                int64_t vehicle_idx = 0;
                vehicle_idx < routing_index_manager.num_vehicles();
                vehicle_idx++
                ) {
            // TimeDimension CumulVars/SlackVars to finalizer
            routing_model.AddVariableMaximizedByFinalizer(
                    time_dimension.CumulVar(routing_model.Start(vehicle_idx))
            );
            routing_model.AddVariableMinimizedByFinalizer(
                    time_dimension.CumulVar(routing_model.End(vehicle_idx))
            );
        }
    }


    // Setup objective
    {
        routing_model
                .GetMutableDimension("Time")
                ->SetSpanCostCoefficientForAllVehicles(1);
    }


    // PARAMS
    operations_research::RoutingSearchParameters parameters = operations_research::DefaultRoutingSearchParameters();

    {
        parameters.set_first_solution_strategy(
                operations_research::FirstSolutionStrategy::BEST_INSERTION
        );
        parameters.set_local_search_metaheuristic(
                operations_research::LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH
        );

        parameters.mutable_local_search_operators()->set_use_relocate_neighbors(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_cross_exchange(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_extended_swap_active(
                operations_research::OptionalBoolean::BOOL_FALSE
        );
        parameters.mutable_local_search_operators()->set_use_swap_active(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_exchange(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_make_active(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_make_inactive(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_path_lns(
                operations_research::OptionalBoolean::BOOL_FALSE
        );
        parameters.mutable_local_search_operators()->set_use_tsp_opt(
                operations_research::OptionalBoolean::BOOL_TRUE
        );
        parameters.mutable_local_search_operators()->set_use_inactive_lns(
                operations_research::OptionalBoolean::BOOL_FALSE
        );
        parameters.mutable_local_search_operators()->set_use_make_chain_inactive(
                operations_research::OptionalBoolean::BOOL_FALSE
        );
        parameters.mutable_local_search_operators()->set_use_relocate_and_make_active(
                operations_research::OptionalBoolean::BOOL_FALSE
        );
    }


    ///// Solve /////
    // Help var for collecting solutions
    std::vector<const operations_research::Assignment *> solutions_collector;

    // Solve
    const Assignment *solution = routing_model.SolveFromAssignmentWithParameters(
            nullptr,
            parameters,
            &solutions_collector
    );


    return 0;
}

Do you have any suggestions?

I also posted here for answers.