我正在尝试使用OR-Tools中的MinCostFlow来解决一个工程问题。有一个机械分配系统,有管道和一些供水阀。这些阀门需要连接到消费者。最初,我试图用匈牙利算法来解决这个问题,但后来我意识到通过路径的流不会被考虑在内。
我用最小成本流对问题进行了建模,如下所示:
节点0-4是用户,节点4-7是供水阀,节点8和9是管道。我在每个消费者上设置了一个“供应”,以显示它期望多少流量。我在最后放了一个水槽,以便从系统中获取补给。不是所有的消费者都有同样的需求。我们可以看到节点0需要10,我专门设计了一条路径(以红色突出显示),允许它将其带到那里。我现在已经把所有的价格都设为0。
我希望它能像这样解决这个系统:
然而,它实际上是这样解决它的:
出于某种原因,它决定将节点0拆分为2个节点(6和7),然后让较大的节点7同时从3和0接收5。从系统的角度来看,这并不理想,我不明白为什么它会以这种方式解决。在匈牙利算法中,它不允许一个工人接受多个Job。在该算法中,节点4-7将是Workers,而0-3将是Job。
我可以通过增加从节点1-3到节点7的弧的成本来获得所需的结果,但我不想操纵成本域来获得所需的结果。这似乎需要很多额外的工作来帮助优化工具选择正确的路径。
我如何使用OR-Tools来完成这个任务?
发布于 2019-12-06 18:08:36
为了简单起见,只要你想让求解器选择一条路径,它就变成了NP完全。最小成本流是多项式的,根据定义,它将在弧之间拆分流,而不是选择其中之一。
你想要的是一个整数线性问题。可以使用CP-SAT求解器或使用CBC或CP-SAT作为后端的线性求解器包装器来求解它。
https://stackoverflow.com/questions/59210360
复制相似问题