(巡回セールスマンの問題)のようなルーティングの問題を解決しようとしています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;
}