Teep

135 Reputation

5 Badges

12 years, 77 days

MaplePrimes Activity


These are replies submitted by Teep


 

``

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 

Hi again.

The procedure you sent worked fine.

However, I need to alter the first constraint to account for a realistic situation. This involved switching the order of i and j.  I get an error message to adjust the feasibility tolerance; when I try to do that, I am prompted to alter the depth limit. I have tried various values .... with no luck (worksheet is uploaded).


 

``

 

 

restart; with(Optimization)

m := 9;

9

 

9

 

3

(1)

 

dist := Matrix(m, n, [[0, 720, 790, 297, 283, 296, 461, 769, 996], [720, 0, 884, 555, 722, 461, 685, 245, 1099], [790, 884, 0, 976, 614, 667, 371, 645, 219], [297, 555, 976, 0, 531, 359, 602, 715, 1217], [283, 722, 614, 531, 0, 263, 286, 629, 721], [296, 461, 667, 359, 263, 0, 288, 479, 907], [461, 685, 371, 602, 286, 288, 0, 448, 589], [769, 245, 645, 715, 629, 479, 448, 0, 867], [996, 1099, 219, 1217, 721, 907, 589, 867, 0]]):

 

d := Vector([2870000, 572000, 8450000, 350000, 901000, 333000, 306000, 723000, 610000]):

To minimize the objective function, z:

z := add(add(dist[i, j]*d[j]*Y[i, j], j = 1 .. n), i = 1 .. m):

The first constraint is:

for j to n do constraint[j] := add(Y[i, j], i = 1 .. m) = 1 end do;

Y[1, 1]+Y[2, 1]+Y[3, 1]+Y[4, 1]+Y[5, 1]+Y[6, 1]+Y[7, 1]+Y[8, 1]+Y[9, 1] = 1

 

Y[1, 2]+Y[2, 2]+Y[3, 2]+Y[4, 2]+Y[5, 2]+Y[6, 2]+Y[7, 2]+Y[8, 2]+Y[9, 2] = 1

 

Y[1, 3]+Y[2, 3]+Y[3, 3]+Y[4, 3]+Y[5, 3]+Y[6, 3]+Y[7, 3]+Y[8, 3]+Y[9, 3] = 1

 

Y[1, 4]+Y[2, 4]+Y[3, 4]+Y[4, 4]+Y[5, 4]+Y[6, 4]+Y[7, 4]+Y[8, 4]+Y[9, 4] = 1

 

Y[1, 5]+Y[2, 5]+Y[3, 5]+Y[4, 5]+Y[5, 5]+Y[6, 5]+Y[7, 5]+Y[8, 5]+Y[9, 5] = 1

 

Y[1, 6]+Y[2, 6]+Y[3, 6]+Y[4, 6]+Y[5, 6]+Y[6, 6]+Y[7, 6]+Y[8, 6]+Y[9, 6] = 1

 

Y[1, 7]+Y[2, 7]+Y[3, 7]+Y[4, 7]+Y[5, 7]+Y[6, 7]+Y[7, 7]+Y[8, 7]+Y[9, 7] = 1

 

Y[1, 8]+Y[2, 8]+Y[3, 8]+Y[4, 8]+Y[5, 8]+Y[6, 8]+Y[7, 8]+Y[8, 8]+Y[9, 8] = 1

 

Y[1, 9]+Y[2, 9]+Y[3, 9]+Y[4, 9]+Y[5, 9]+Y[6, 9]+Y[7, 9]+Y[8, 9]+Y[9, 9] = 1

(2)

constraint1 := `union`(`union`(`union`(`union`(`union`(`union`(`union`(`union`({constraint[1]}, {constraint[2]}), {constraint[3]}), {constraint[4]}), {constraint[5]}), {constraint[6]}), {constraint[7]}), {constraint[8]}), {constraint[9]}):

The second constraint is:

constraint2 := {add(X[i], i = 1 .. m) = p}:

The third constraint is:

constraint3 := {seq(seq(Y[i, j] <= X[j], i = 1 .. m), j = 1 .. n)}:

The constraints (4 and 5) require binary outputs; zero or one.  This is automatically accounted for, so removed, since all variables will be assumed binary.

Thus, the consolidated constraints are:

 

constraints := `union`(`union`(constraint1, constraint2), constraint3):

 

The minimized solution is:

z[min] := LPSolve(z, constraints, assume = binary)

Error, (in Optimization:-LPSolve) no feasible integer point found; use feasibilitytolerance option to adjust tolerance

 

``

 

 

 

NULL


 

Download Feasibility_Tolerance.mw

Could you suggest any possible fixes?

Thanks in advance.

@ 

Many thanks!

@vv 

I appreciate the guidance - I'm obliged. I did post the worksheet .... thanks again..

@brian bovril 

Many thanks for the response and effort.

However, the link to the solution is incomplete (I get a blank Word document!).

Would you please re-send the .mws file?

5 6 7 Page 7 of 7