Advanced Search

Teep

195 Reputation

5 Badges

16 years, 70 days
Contact Teep

MaplePrimes Activity


These are replies submitted by Teep

Thank you!...

Teep 195
August 10 2017
0 0

@gkokovidis 

Many thanks, Georgios ... much appreciated!

Great!...

Teep 195
August 10 2017
0 0

@tomleslie 

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

Thanks!...

Teep 195
August 10 2017
0 0

@mehdi jafari 

 

That's great! I appreciate it ...

Thanks .... but still no luck!...

Teep 195
August 09 2017
0 0

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

As expected....

Teep 195
August 02 2017
0 0

@tomleslie 

Thanks .... I guessed so.

That's clever!...

Teep 195
February 04 2017
0 0

Thanks for that .... it works fine!

Thanks!...

Teep 195
January 29 2017
0 0

@Kitonum 

That works fine .... thank you!

Agreed...

Teep 195
January 20 2017
0 0

@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.

Not quite!...

Teep 195
January 20 2017
0 2

@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?

Model Detail...

Teep 195
January 17 2017
0 0


 

 

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!

 

indets...

Teep 195
January 07 2017
0 0

Thanks so much!

@vv 

Great idea (and attitude)!...

Teep 195
December 22 2016
0 0


 

``

> 

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 

Consolidated matrix form...

Teep 195
December 11 2016
0 0

The use of matrices is really useful here.

Many thanks!

@Carl Love 

it works now...

Teep 195
December 11 2016
0 0

That's great!

Thanks for your interest and help.

@brian bovril 

Reconsidered constraints...

Teep 195
December 10 2016
0 0

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

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

@vv 

First 6 7 8 9 Page 8 of 9