在 OR-tools 车辆路径问题中仍然访问可选节点

Question

在由 Google OR-tools 库解决的一个简单车辆路径问题中，两个节点 (2, 3) 被标记为可选，访问惩罚设置为 0。从仓库到垃圾填埋场的距离 2 的最短路径是 0 -> 1 -> 4，但是，求解器最终得到距离 4 的路径 0 -> 2 -> 3 -> 1 -> 4.

问题出在哪里？为什么求解器坚持通过可选节点的较长路径而不跳过它们？

#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;
}

有趣的是，对于 I = 1，找到了正确的解决方案 0 -> 1 -> 4。然而，这样的 dist 矩阵是微不足道的。

Answer 1

已在 or-tools-discuss 邮件列表中对此进行了回答。

您遇到了默认参数设置的极端情况。感谢您转发此信息，我们将努力进行适当的修复。要解决此问题，您可以按如下方式修改默认参数：选项 1 - 激活 make_chain_inactive - 更快的选项

    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);

选项 2 - 激活 inactive_lns - 较慢的选项但稍微更通用

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

在 OR-tools 车辆路径问题中仍然访问可选节点

Optional node still visited in OR-tools vehicle routing problem

c++

or-tools

vehicle-routing