CPLEX Optimization Studio - 无可行解 - 二次约束

Question

我尝试用两辆车实现车辆路径问题。

一辆车是载体，另一辆车是无人机，可以从载体出发。

两辆车都从点 (0/0) 开始。然后两辆车都移动到无人机应该从载体开始并连续访问一些目标位置的点。一开始我只假设两个目标位于 t1(2/8) 和 t2(5/8)。在访问目标后，无人机应降落在载体上，两辆车都应返回起点 (0/0)。

所以无人机在航母上起飞和降落的点要选择最优，尽量减少航母的航程。

我在这里对问题进行了可视化：visualization

我的代码如下所示：

//Data

int start[1..2]=[0,0]; //start

int R=10; //max drone flight time
int a=2;  //speed of drone

int z1A1[1..2]=[2,8]; //target1
int z2A1[1..2]=[7,8]; //target2

float intraDist1=sqrt(((z2A1[1]-z1A1[1])^2)+(z2A1[2]-z1A1[2])^2); //distance between targets
float intraFlugDist1;

float wegFlugDist1;
float hinFlugDist1; 

float kombiniertZeit0;
float kombiniertZeit1;
float getrenntZeit1;

//Dvar

dvar int+ sA1[1..2];
dvar int+ lA1[1..2];

//Model

minimize kombiniertZeit0+getrenntZeit1+kombiniertZeit1;

subject to{

E1:
kombiniertZeit0>=0;
(((sA1[1]-start[1])^2)+(sA1[2]-start[2])^2)<=kombiniertZeit0^2;

E2:
getrenntZeit1>=0;
(((lA1[1]-sA1[1])^2)+(lA1[2]-sA1[2])^2)<=getrenntZeit1^2;

E3:
kombiniertZeit1>=0;
(((start[1]-lA1[1])^2)+(start[2]-lA1[2])^2)<=kombiniertZeit1^2;

E4:
wegFlugDist1>=0;
(((z1A1[1]-sA1[1])^2)+(z1A1[2]-sA1[2])^2)<=wegFlugDist1^2;

E5:
hinFlugDist1>=0;
(((lA1[1]-z2A1[1])^2)+(lA1[2]-z2A1[2])^2)<=hinFlugDist1^2;

E6:
intraDist1<=intraFlugDist1;

E7:
(wegFlugDist1+intraFlugDist1+hinFlugDist1)/a<=getrenntZeit1;

E8:
R>=getrenntZeit1;

}

E1 确保 kombiniertZeit0 至少与从起点到无人机发射点的距离一样大。

E2保证getrenntZeit1至少和无人机发射点到着陆点的距离一样大

E3 确保 kombiniertZeit1 至少与无人机着陆点到起点的距离一样大。

E4确保wegFlugDist1至少与无人机发射点到第一个目标的距离一样大。

E5保证hinFlugDist1至少和最后一个目标到无人机着陆点的距离一样大

E7确保getrenntZeit1至少等于hinFlugDist1、intraFlugDist1和wegFlugDist1之和除以无人机速度a。

E8保证getrenntZeit1不大于无人机R的最大飞行时间

当我调试程序时，我没有找到可行的解决方案，我也不知道为什么。

非常感谢您的每一个提示！提前致谢！

斯文

Answer 1

我将你的问题移植到 MiniZinc 并添加了一些距离和时间的域限制：

array[1..2] of int: start = [0,0]; % start location

int: R=10; % max drone flight time
int: vDrone=2;    % speed of drone
int: vCarrier=1;  %  speed of carrier
float: minDist = 0.0;
float: maxDist = 100.0;
float: minTime = 0.0;
float: maxTime = 20.0;

array[1..2] of int: z1A1=[2,8]; %  target1
array[1..2] of int: z2A1=[7,8]; %  target2

function var float: sqr(float: x) = x * x;
function var float: sqr(var float: x) = x * x;
function var int:   sqr(var int: x) = x * x;

float: intraDist1=sqrt((z2A1[1]-z1A1[1])*(z2A1[1]-z1A1[1]) + 
                       (z2A1[2]-z1A1[2])*(z2A1[2]-z1A1[2])); % distance between targets
var minDist .. maxDist: intraFlugDist1;

var minDist .. maxDist: wegFlugDist1;
var minDist .. maxDist: hinFlugDist1; 

var minTime .. maxTime: kombiniertZeit0;
var minTime .. maxTime: kombiniertZeit1;
var minTime .. maxTime: getrenntZeit1;

array[1..2] of var 0..100: sA1;
array[1..2] of var 0..100: sA2;


solve minimize kombiniertZeit0 + getrenntZeit1 + kombiniertZeit1;

% E1:
constraint ((sqr(sA1[1]-start[1])+sqr(sA1[2]-start[2])) <= sqr(kombiniertZeit0)*vCarrier);

% E2:
constraint ((sqr(sA1[1]-sA2[1]) + sqr(sA1[2]-sA2[2])) <= sqr(getrenntZeit1)*vCarrier);

% E3:
constraint ((sqr(start[1]-sA2[1]) + sqr(start[2]-sA2[2])) <= sqr(kombiniertZeit1)*vCarrier);

% E4:
constraint ((sqr(z1A1[1]-sA1[1]) + sqr(z1A1[2]-sA1[2])) <= sqr(wegFlugDist1)*vDrone);

% E5:
constraint ((sqr(sA2[1]-z2A1[1]) + sqr(sA2[2]-z2A1[2])) <= sqr(hinFlugDist1)*vDrone);

% E6:
constraint (intraDist1 <= intraFlugDist1);

% E7:
constraint ((wegFlugDist1 + intraFlugDist1 + hinFlugDist1) <= getrenntZeit1*vDrone);

% E8:
constraint (R >= getrenntZeit1);

这导致以下结果：

intraFlugDist1 = 5.0;
wegFlugDist1 = 5.8309518948453;
hinFlugDist1 = 7.51664818918645;
kombiniertZeit0 = 0.0;
kombiniertZeit1 = 0.0;
getrenntZeit1 = 9.173800042015881;
sA1 = array1d(1..2, [0, 0]);
sA2 = array1d(1..2, [0, 0]);

这意味着载体停留在起始位置，无人机独自飞行。必须修改约束以强制执行不那么琐碎的行为。 R = 6 是防止无人机单飞的简单方法。

CPLEX Optimization Studio - 无可行解 - 二次约束

CPLEX Optimization Studio - No feasible solution - Quadratic Constraints

optimization

constraints

quadratic

cplex