Teep

130 Reputation

5 Badges

11 years, 325 days

MaplePrimes Activity


These are replies submitted by Teep

@gkokovidis 

Many thanks, Georgios ... much appreciated!

@tomleslie 

Thank you for clearing this up .... I appreciate your help.

@mehdi jafari 

 

That's great! I appreciate it ...

Thanks for this. 

However, I initially used that command and am still receiving an error message. As follows ...

Error, invalid input: rand expects its first argument, r,  to be of the type {posint, integer..integer} but received -.5 .. .5

@tomleslie 

Thanks .... I guessed so.

Thanks for that .... it works fine!

@Kitonum 

That works fine .... thank you!

@Thomas Richard 

That matches my result ... thanks, Thomas.

The equation structure is rather mis-leading (at least to me), so you've clarified my thinking here.

I appreciate it.

@Thomas Richard 

I appreciate the response, Thomas. Thanks.

However, that routine returns L := [d[0]*x[i, 0, 1]+d[0]*x[i, 1, 1]+d[1]*x[i, 0, 1]+d[1]*x[i, 1, 1], d[0]*x[i, 0, 2]+d[0]*x[i, 1, 2]+d[1]*x[i, 0, 2]+d[1]*x[i, 1, 2]].

As you can see, the values, i=0 and i=1 are not carried through to the full series; we only receive unknown terms, for instance x[i, 1,2] and so on. This is what I am trying to protect against. As the equation is stated, one would think that your routine would work ... but you see the problem. If we then take the values i=0 and i=1, then we will obtain two sequences ... however, I need to be sure.

Any other suggestions?


 

 

Constraint Problem

 

Given the sets:

• 

C = {1,2, ..., n}

• 

K = {1,2, ...., m}

• 

Arcs, A ={i,j},  representing connections between locations, i and j. For each arc, (i,j), i≠j, i≠n+1 and j≠0.

 

For each arc, {i,j}, i≠j, there are two matrices namely c[i, j]  and t[i, j] and for each point, i, there is a specified positive quantity, " d[i]."

Further, we impose a positive integer value on "q and fix a positive value to the parameter, S[j,k ]"NULL

There are two decision variables under consideration; one of which is binary.

• 

"s[i,k ] and "

• 

x[i, j, k] " = 1,  if  k  moves from vertex  i to  j; 0, otherwise."

 

"We seek to minimize  the function, z, where: "

" z=(∑)  (∑)  (∑)c[i,j]  x[i,j,k]"

 

subject to the constraints

NULL

"(i)    (∑)  (∑)x[i,j,k ] =1,           ∀i in C"

 

"(ii)  (&sum;)d[i ]  (&sum;)()[ ]x[i,j,k ]<=   q,    &forall;k in K"

 

"(iii)    (&sum;)x[0,j,k ] = 1,   &forall; k in K"

 

"(iv)    (&sum;)x[i,h,k ] - (&sum;)x[h, j,k ]= 0,    &forall; h in C,  &forall; k in K"

 

"(v)    (&sum;)x[i, n+1,  k ] = 1,    &forall; k in K"

NULLNULL

 

(vi)  "s[i,k]+ t[i,j]-K ( 1-  x[i,j, k]  ) <=  S[j,k] ,      &forall;i, j  in N,  &forall; k in K"

 

 

(vii)  "a[i]  <=  s[i,k] <=  b[i] ,         &forall; i in N,  &forall; k in K"

 

 

(viii)  "x[i, j, k ]  in {0,1}, " " &forall;i, j  in N,  &forall; k in K"

 

 

restart; with(Optimization)

 

 

The following model values are set-up for simplicity.

 

 

m := 1:

The values for "c[i,j ]and t[i,j ]are taken to be:"

c[0, 0] := 0:

t[0, 0] := 0:

S[j, k]*values*are

S[0, 0] := 0:

The vector, d[i]:

d[1] := 10000:

The quantitity q:

q := 2000:

The objective function:

z := add(add(add(c[i, j]*x[i, j, k], j = 0 .. n), i = 0 .. n), k = 1 .. m):

Constraint (1)

constraint1 := {seq(add(add(x[i, j, k], j = 0 .. n), k = 1 .. m) = 1, i = 1 .. n)}:

2*Constraint

constraint2 := expand({seq(add(d[i]*add(x[i, j, k], j = 0 .. n), i = 1 .. n) >= q, k = 1 .. m)}):

3*Constraint

constraint3 := {seq(add(x[0, j, k], j = 0 .. n) = 1, k = 1 .. m)}:

4*Constraint

constraint4 := {seq(seq(add(x[i, h, k], i = 0 .. n)-add(x[h, j, k], j = 0 .. n) = 0, h = 1 .. n), k = 1 .. m)}:

5*Constraint

constraint5 := {seq(add(x[i, n+1, k], i = 0 .. n) = 1, k = 1 .. m)}:

6*Constraint

e[1] := 1:

constraint6 := {seq(seq(seq(s[i, k]+t[i, j]-(l[i]+t[i, j]-e[j])*(1-x[i, j, k]) <= S[j, k], i = 1 .. n), j = 1 .. n), k = 1 .. m)}:

Constraint (7)

c3 := {seq(seq(e[i] <= s[i, k], i = 1 .. n), k = 1 .. m)}:

constraint7 := `union`(c3, c4):

 

For x[i, j, k] and s[i, k], we*require

 

Constraint (8): Setting the condition i ≠ j

                          OPEN

 

Constraint (9): Setting the condition i≠ n+1 

                          OPEN

 

Constraint (10): Setting the condition  j ≠ 0

                           OPEN

 

Constraint (11)

The final constraint ", x[i,j,k ] in  {0,1}, "require binary outputs, zero or one.

 

Excluding constraints (8) to (10), the consolidated constraints are:

constraints := `union`(`union`(`union`(`union`(`union`(`union`(constraint1, constraint2), constraint3), constraint4), constraint5), constraint6), constraint7):

 

 

The list, L, of all terms is given by the sequence:

L := `union`({seq(seq(seq(c[i, j]*x[i, j, k], j = 0 .. n), i = 0 .. n), k = 1 .. m)}, constraints):

 

The set of elements "x[i,j,k ] alone is constrained to "binary variables. The binaryvariables option may be given by the indets syntax.

The solution is:

Sol := LPSolve(z, constraints, binaryvariables = indets(L, specindex(integer, x)));

[2, [s[1, 1] = HFloat(1.0), s[2, 1] = HFloat(5.0), s[3, 1] = HFloat(10.0), s[4, 1] = HFloat(15.0), x[0, 0, 1] = 0, x[0, 1, 1] = 1, x[0, 2, 1] = 0, x[0, 3, 1] = 0, x[0, 4, 1] = 0, x[0, 5, 1] = 1, x[1, 0, 1] = 1, x[1, 1, 1] = 0, x[1, 2, 1] = 0, x[1, 3, 1] = 0, x[1, 4, 1] = 0, x[1, 5, 1] = 0, x[2, 0, 1] = 0, x[2, 1, 1] = 0, x[2, 2, 1] = 1, x[2, 3, 1] = 0, x[2, 4, 1] = 0, x[2, 5, 1] = 0, x[3, 0, 1] = 0, x[3, 1, 1] = 0, x[3, 2, 1] = 0, x[3, 3, 1] = 1, x[3, 4, 1] = 0, x[3, 5, 1] = 0, x[4, 0, 1] = 0, x[4, 1, 1] = 0, x[4, 2, 1] = 0, x[4, 3, 1] = 0, x[4, 4, 1] = 1, x[4, 5, 1] = 0]]

(1)

 

 

END

END

(2)

NULL


 

Download Constraint.mw

Many thanks for the effort and response - I appreciate it.

As you recommended, I have included the worksheet. The constraints are incomplete (missing the final three). If you could review the structure, I'd be interested in your comments / feedback.

Thanks again!

 

Thanks so much!

@vv 


 

``

restart

 

 

This is a combinatorial (multi-objective) optimization problem in which the minimization of the following is sought:

 

(a) No of vehicles

(b) Total travel time

(c) Waiting time

(d) Total distance incurred by the fleet

 

This is an extension of the classic vehicle routing problem. It accounts for the following features.

Let

 

V = Fleet of (homogeneous) vehicles

C = Customers (1,2,..., n)

c[i*j]= Cost

t[i*j]= Time (includes service time at customer j)

q = vehicle capacity

d[i] = customer*demand

Each customer has a time window,  [a[0], b[0]]

Assume the service time is in direct proportion to the demand at the location

Unused vehicle is modeled by driving the empty route, (0, n+1)

k 2 V

i 2 N

j 2 N

 

 

There are two decision variables, namely:

 

1. x[i*j*k]

2. "s[i k ] (the time vehicle k starts to service customer i)"

 

 

 

The objective to be minimized is:

 

sum(sum(sum(c[i*j]*x[i*j*k], j), i), k);

sum(sum(sum(c[i*j]*x[i*j*k], j), i), k)

(1)

 

subject to the following 8 constraints

 

Each customer is visited once only:

sum(sum(x[i*j*k], j), k) = 1;

sum(sum(x[i*j*k], j), k) = 1

(2)

 

The vehicle load limits are defined

sum(d[i]*(sum(x[i*j*k], j)), i) <= q;

sum(d[i]*(sum(x[i*j*k], j)), i) <= q

(3)

 

Each vehicle leaves depot 0

sum(x[(0*j)*k], j) = 1;

x[0]*j = 1

(4)

 

After arriving at a customer, the vehicle departs

sum(x[i*h*k], i)-(sum(x[h*j*k], j)) = 0;

sum(x[i*h*k], i)-(sum(x[h*j*k], j)) = 0

(5)

 

Finally, the vehicle arrives at the depot, n+1

sum(x[i, n+1, k], i) = 1;

sum(x[i, n+1, k], i) = 1

(6)

 

Vehicle k cannot arrive at j before "s[i k ]+ t[i j] if it travels from i to j"

s[i*k]+t[i*j]-K(1-x[i*j*k]) <= s[j*k];

s[i*k]+t[i*j]-K(1-x[i*j*k]) <= s[j*k]

(7)

 

The time windows must be observed (assume "a[0]=0) "

a[i] <= s[i*k] and s[i*k] <= b[i];

a[i] <= s[i*k] and s[i*k] <= b[i]

(8)

 

Integrality constraint

`in`(x[i*j*k], {0, 1});

`in`(x[i*j*k], {0, 1})

(9)

``

``

``


 

Download Optimization_Problem.mw

@Carl Love 

The use of matrices is really useful here.

Many thanks!

@Carl Love 

That's great!

Thanks for your interest and help.

@brian bovril 

Thanks for your timely response .... much appreciated.

I'll review the formulation in light of your advice.

@vv 

4 5 6 7 Page 6 of 7