CPLEX Optimization Studio - No feasible solution - Quadratic Constraints

Question

I try to implement a Vehicle Routing Problem with two vehicles.

One vehicle is a carrier, the other one is a drone which can start from the carrier.

Both vehicles start at the point (0/0). Then both vehicles move to a point where the drone should start from the carrier an visit some target locations consecutively. In the beginning I only assume two targets located at t1(2/8) and t2(5/8). After visiting the targets the drone should land on the carrier and both vehicles shoul go back to the starting point (0/0).

So the points where the drone launches and lands on the carrier are to choose optimally to minimze the tour of the carrier.

I have a visualization of the problem here: visualization

My Code looks like this:

//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 ensures that kombiniertZeit0 is at least as large as the distance from the start to the launch point of the drone.

E2 ensures that getrenntZeit1 is at least as large as the distance from the launch point to the land point of the drone.

E3 ensures that kombiniertZeit1 is at least as large as the distance from the land point of the drone to the start.

E4 ensures that wegFlugDist1 is at least as large as the distance from the launch point of the drone to the first target.

E5 ensures that hinFlugDist1 is at least as large as the distance from the last target to the land point of drone.

E7 ensures that getrenntZeit1 is at least as large as the sum of hinFlugDist1, intraFlugDist1 and wegFlugDist1 divided by the speed of the drone a.

E8 ensures that getrenntZeit1 is not larger than the max flight time of the drone R.

When I debug the programm I get no feasible solution and I can`t figure out why.

I am very thankful for every hint! Thanks in Advance!

Sven

Answer 1

I ported your problem to MiniZinc and added some domain limits for distances and times:

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);

This leads to the following:

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]);

This means that the carrier stays in the start position and the drone travels all alone. The constraints have to be modified to enforce a less trivial behaviour. R = 6 is an easy way to prevent the drone from a solo.