我们能否将 CPLEX/Docplex 用于网络中的单源和多目标问题?例如,在一次行程中将车辆从源头路由到多个目的地,从而最大限度地减少总行程时间。
问问题
65 次
1 回答
0
你好,
您可以查看 tsp OPL 示例
examples/opl/models/TravelingSalesmanProblem
如果你想做单一来源和多目的地,你可以改变目标
minimize sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];
至
minimize sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>]-max(j in Cities:<1,j> in Edges) dist[<1,j>]*x[<1,j>];
您在https://raw.githubusercontent.com/IBMDecisionOptimization/cplex_code_examples/master/docplex/tsp.py的 python docplex 中有相同的示例
对于您的特定实例:
using CP;
execute
{
cp.param.timelimit=10;
}
{string} nodes={"O","A","B","C","D","E","T"};
tuple edge
{
key string o;
key string d;
int time;
}
{edge} edges with o,d in nodes=
{
<"O","A",40>,
<"O","B",60>,
<"O","C",50>,
<"A","B",10>,
<"C","B",20>,
<"A","D",70>,
<"B","D",55>,
<"B","E",40>,
<"D","E",10>,
<"D","T",60>,
<"E","T",80>
};
string origin="O";
{string} targets={"A","C"};
int bigvalue=1000;
int repeat=3;
range ranks=1..repeat;
{edge} edgeswithsym=edges union {<d,o,t> | <o,d,t> in edges};
{edge} transitions=edgeswithsym union {<o,d,bigvalue> | o,d in nodes: <o,d> not in edgeswithsym};
tuple triplet {int id1; int id2; int value;};
{triplet} M = {<ord(nodes,tr.o)+1,ord(nodes,tr.d)+1,tr.time> | tr in transitions};
assert card(transitions)==card(nodes)*(card(nodes));
// Interval for visiting a node
dvar interval itvs[nodes][ranks] optional;
// Sequence means visits
dvar sequence seq in all(n in nodes,r in ranks)itvs[n][r] types
all(n in nodes,r in ranks)(ord(nodes,n)+1);
// First we want to minimize the time for latest visit
// Second we want to minimize present intervals
minimize
staticLex(max(t in targets) min(r in ranks) startOf(itvs[t,r],bigvalue),
sum(n in nodes,r in ranks) presenceOf(itvs[n][r]));
subject to
{
// We visit origin at time 0
startOf(itvs[origin,1])==0;
// origin and destinations should be present
presenceOf(itvs[origin,1])==1;
forall(t in targets) presenceOf(itvs[t,1])==1;
// noOverlap constraint will enforce time matrix
noOverlap(seq,M,true);
// break sym
forall(n in nodes) forall(r in ranks:r!=1)
presenceOf(itvs[n,r-1])>=presenceOf(itvs[n,r]);
}
int nbActiveIntervals=sum(n in nodes,r in ranks) presenceOf(itvs[n][r]);
range R=1..nbActiveIntervals;
// Display solution
execute {
writeln(origin);
var s=seq.first();
for(var i in R)
{
if (i!=nbActiveIntervals)
writeln(Opl.item(nodes,-1+Opl.typeOfNext(seq,s,bigvalue,0)));
s=seq.next(s);
}
}
/*
gives
O
A
B
C
*/
于 2021-04-22T16:28:15.740 回答