我正在研究一个拨号乘车问题(DARP)。我有大量的节点和边(338个节点和826条边)。我已经从OSMnx导入了节点/边缘数据,并试图用Python中的Gurobi Optimizer解决模型。
为了能够与Gurobi一起使用OSMnx数据,我创建了一个matrix = len(nodes) x len(nodes)
矩阵,并在其中打印两个节点连接时的边缘长度,否则打印大量的边缘长度。在优化中,使用x[i,j] = len(nodes) x len(nodes)
二元决策变量来决定是否遍历一条边。
我遇到的问题是一个请求的计算时间很长(+1小时)。我认为这是因为模型还必须考虑这个大矩阵中的所有其他索引,尽管它们可以完全忽略,因为它们表示两个节点没有连接。
因此,我的问题是,如果有人能帮助我找到一些预处理技术或其他可能减少我的计算时间的东西。例如,告诉模型,如果值太高,它可以忽略这个矩阵中的索引,或者可能是一个更有效的节点/边缘存储文件,robi可以更有效地使用。
提前感谢。
如果你的图是稀疏的,那么优化模型也应该是稀疏的。具体来说,只有在图中存在边(i,j)时,才应该创建变量x[i,j]
。有关如何做到这一点的示例,请参阅Gurobi的examples/python子目录中的netflow.py示例。