我一直在努力解决路由问题,比如 TSP
(旅行商问题),但有一些曲折 . 我使用线性编程( CPlex library
)和有向图(带有原点顶点)( Coin-Or::Lemon library
)对问题进行了建模 .
线性程序找到解决方案,但我的问题在于如何检索路径 . 我可以迭代图形的每个顶点和边缘以找出线性程序正在使用的内容,所以我想我只是从Origin开始并使用所选边缘到达下一个节点,直到我再次到达Origin .
问题是CPlex路径可能会多次遍历任何顶点 . 所以我决定使用递归算法 . 但我无法弄明白 . 这是我尝试过的:
FindPath ( node N, path P)
AddedAnyPath <- false
for each edge E out of N that hasn't been used yet
T is the target of E
add T to P
if findPath ( E, P )
AddedAnyPath = true
end for each
if AddedAnyPath
if all edges were used
return true
else
return false
end if
endif
end
该算法无法找到路径 . 如果你能指出我的任何方向,我将非常感激 .
编辑
提供的答案帮助我找到了答案 . 这是 C++
中的代码:
bool findPath2 ( Store_Instance &T, DiNode ¤t, list <DiNode> &path, ListDigraph::ArcMap<bool> &usedArcs, IloCplex &cplex, ListDigraph::ArcMap<IloNumVar> &x) {
DiNode currentNode = current;
bool success = false;
int positionToInsert = 1;
while (true) {
//Find an unvisited edge E whose value is 1.
Arc unvisitedArc = INVALID;
for(Digraph::OutArcIt a(T.g, currentNode); a != INVALID; ++a) {
if(cplex.getValue(x[a]) >= 1-EPS && !usedArcs[a]) {
unvisitedArc = a;
break;
}
}
if (unvisitedArc != INVALID) {
//Mark edge as visited
usedArcs[unvisitedArc] = true;
//Get the target T of the edge
DiNode target = T.g.target(unvisitedArc);
//Add Edge E to the path
list<DiNode>::iterator iterator = path.begin();
advance(iterator, positionToInsert);
path.insert(iterator, target);
//Increase the iterator
positionToInsert++;
//If all the edges whose value is 1 are visited, stop
bool usedAllEdges = true;
for (ArcIt a(T.g); a != INVALID; ++a){
if (cplex.getValue(x[a]) > 1-EPS && usedArcs[a] == false) {
usedAllEdges = false;
break;
}
}
if (usedAllEdges) {
success = true;
break;
}
//Else, Set N to be T and repeat
else currentNode = target;
} else {
//No arcs were found. Find a node from the path that has unvisited Arc
positionToInsert = 0;
DiNode target = INVALID;
for (list<DiNode>::const_iterator iterator = path.begin(), end = path.end(); iterator != end; ++iterator) {
DiNode v = *iterator;
for(Digraph::OutArcIt a(T.g, v); a != INVALID; ++a) {
if(cplex.getValue(x[a]) >= 1-EPS && !usedArcs[a]) {
target = v;
break;
}
}
positionToInsert ++;
if (target != INVALID) break;
}
if (target != INVALID) {
//cout << "found lost node" << endl;
currentNode = target;
} else {
success = false;
break;
}
}
}
return success;
}
1 回答
TSP(路径)的解决方案是有序的顶点列表,它们在原点开始和结束,访问每个顶点 . 有两种可能的情况 .
如果您允许两次访问顶点,那么在您的变体中,您将允许“子游览” . (案例2)
您将拥有变量X_nt,它将是1.(将节点n连接到节点t的边变量) .
如果您没有小计:情况1,您可以在返回原点节点后停止 .
看起来您正在允许子游览(多个循环,上面的情况2) . 如果是这样,您必须访问作为TSP解决方案一部分的所有边,其值为1.(修改代码以跟踪每个节点到其终端节点的任何一个边,一次一个边 . )
希望有所帮助 .