Optional node still visited in OR-tools vehicle routing problem

Question

In a simple vehicle routing problem solved by Google OR-tools library, two nodes (2, 3) are marked as optional with visiting penalty set to 0. The shortest path of distance 2 from the depot to the landfill is 0 -> 1 -> 4, however, the solver ends-up with path 0 -> 2 -> 3 -> 1 -> 4 of distance 4.

Where is the problem? Why the solver insists on the longer path through optional nodes and does not skip them?

#include "ortools/constraint_solver/routing.h"

using namespace operations_research;

struct DataModel {
    static constexpr int I = 2;
    const std::vector<std::vector<int>> dist {
        { 0, 1, 1, I, I},
        { I, 0, I, 1, 1},
        { I, I, 0, 1, 1},
        { I, 1, 1, 0, I},
        { I, I, I, 1, 0},
    };
    const RoutingIndexManager::NodeIndex depot{0};
    const RoutingIndexManager::NodeIndex landfill{4};
};

void printSolution(const RoutingIndexManager& manager,
                   const RoutingModel& routing,
                   const Assignment& solution)
{
    if (routing.status() != RoutingModel::Status::ROUTING_SUCCESS)
        return;

    int index = routing.Start(0);
    std::ostringstream route;
    while (routing.IsEnd(index) == false) {
        route << manager.IndexToNode(index).value() << " -> ";
        index = solution.Value(routing.NextVar(index));
    }

    LOG(INFO) << route.str() << manager.IndexToNode(index).value();
    LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

int main(int /*argc*/, char** /*argv*/)
{
    DataModel data;
    RoutingIndexManager manager(data.dist.size(), 1, {data.depot}, {data.landfill});
    RoutingModel routing(manager);

    const int callback = routing.RegisterTransitCallback(
                [&data, &manager](int from_index, int to_index) -> int {
        auto from_node = manager.IndexToNode(from_index).value();
        auto to_node = manager.IndexToNode(to_index).value();

        return data.dist[from_node][to_node];
    });

    routing.SetArcCostEvaluatorOfAllVehicles(callback);

    // make nodes 2, 3 optional
    routing.AddDisjunction({manager.NodeToIndex(RoutingIndexManager::NodeIndex(2))}, 0, 1);
    routing.AddDisjunction({manager.NodeToIndex(RoutingIndexManager::NodeIndex(3))}, 0, 1);

    const Assignment* solution = routing.Solve();
    printSolution(manager, routing, *solution);

    return 0;
}

Interestingly, for I = 1, the correct solution 0 -> 1 -> 4 is found. However, such dist matrix is trivial.

Answer 1

This was answered on the or-tools-discuss mailing list.

You encountered a corner case for the default parameter setup. Thanks for forwarding this, we will work on a proper fix. To work around the problem, you can modify the default parameters as follows: Option 1 - activate make_chain_inactive - faster option

    RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters();
    search_parameters.mutable_local_search_operators()->set_use_make_chain_inactive(OptionalBoolean::BOOL_TRUE);
    const Assignment* solution = routing.SolveWithParameters(search_parameters);

Option 2 - activate inactive_lns - slower option but slightly more generic

    RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters();
    search_parameters.mutable_local_search_operators()->set_use_inactive_lns(OptionalBoolean::BOOL_TRUE);
    const Assignment* solution = routing.SolveWithParameters(search_parameters);