## 884 Reputation

16 years, 210 days

## Outstanding work!...

@Carl Love Thanks very much.

I wondered myself how much they charged for the consultation?. The problem is to find such work in the first place. The first barrier is requiring someone at the farm to realise its a scheduling problem and the need for a specialist such as yourself.

In terms of speed, Evolver took less than 5 seconds to get to the minimum for both the 7 block and the 5 block.

The advantage of such a platform is it suits someone with my coding skills (ie very little needed). The disadvantage is that it doesn't always find the minimum. Take the last problem in the document. The number of partitions of it into 3 blocks with the sizes as even as possible is PartCount([2\$5, 4])=945945. (Higher than the 7 block, but lower than 5 block), but Evolver can't seem to get lower than 1205.9 even when I left it going for 45 mins and many trials. (Your procedure gets 1107.1). Now there may be a trick to it, tweaking crossover/mutation rate (it uses genetic algorithms), but I am no expert in it. There may be a forum? This is my worksheet anyways TRP5.xls

As an aside, does Maple do genetic algorithms and neural networks (AI) ?

## SetPartitionFixedSizes...

Its a pity when the facts get in the way isn't it? I guess I should have guessed I had the matrix wrong when a lot of it violated the triangle inequality and my answers differed significantly from the pdf's.  I'll stop the self flagellation now.

So the real distance matrix is

N:=14:
c:=Matrix(
(N+1)\$2, shape= symmetric, scan= triangular,
[0, op]~([[222,65.4,217,136,115,119,47.9,206,56.5,73,119,189,25.2,104],
[251,24.4,284,262,103,213,23,204,155,266,29.2,246,131],
[247,76.8,47.4,148,109,235,47.9,103,58.9,218,61.5,168],
[279,258,98.9,247,45.1,199,151,261,32.6,242,153],
[31.8,181,184,267,80.4,135,41.3,251,137,201],
[159,162,246,59,113,38.9,230,109,179],
[148,87.1,101,53,163,70.9,144,139],
[189,104,102,165,205,53.4,82.3],
[187,139,249,35.2,230,108],
[55,62.6,171,80.9,121],
[117,123,98,93.1],
[233,120,183],
[214,135],
[123]]

));

Using this matrix the answer to

a) is 2041.8 (agrees with the pdf). ok  i see how you got 135,135 partitions: nops(setpartition([seq(2..15)],2))

b) 1563 is the published answer. But when I crunched the data using Palisade Evolver, it found a lower minimum (1552.6) with these tours:  [[[1, 3,10,11], [1, 6,5,12], [1, 7,9,15],[1,13,2,4],[1,14,8]]]:

with Maple I got 1580, but I didn't generate enough routes, only a fraction of them.

I had a look at the help for SetPartitionFixedSizes, but frankly I don't know how to code it....

## Apologies for brevity...

Thankyou for your interest. I found this problem trawling the net for for VRP's:

TRP.pdf

Edited.

In summary, a truck leaves a depot (node 1 in Maple) and has to visit 14 stores (nodes 2-15 in Maple) in various formations and return to the depot.

(a) The first part is to visit the 14 stores over 7 trips, ie visit 2 stores and return to the depot each trip.

Both Maple and Evolver agree the minimum is 2770.9, but the authors say its 2041.....

TRP_14x2.mw

(b) The problem as submitted. Visit all 14 stores over 5 trips. Maximum 3 stores and return to depot per trip. [p9]

14 is not divisible by 3, so an extra "slack" variable is added (node 16). After the permutations of the partitions, node 16 is removed.

## Just...

@Seb1123 remove the word "maximize" from the above expression. The default setting in Dr. Sergey Moiseev's package is minimize.

## That's it!...

@Carl Love I wish I could give it an upvote

## What I really meant was...

thanks. But when I look at the problem I want to apply this to, I need a variation:

Given S := [seq(2..5)]

P:=combinat:-setpartition(S, 2);

[[[2, 3], [4, 5]], [[2, 4], [3, 5]], [[2, 5], [3, 4]]]

I want to remove the instances of 5.

leaving

[[[2, 3],[4]], [[2, 4],[3]], [[2],[3, 4]]]

## min...

@vv too easy. I presume. As a constraint

min(a,b) >= c   <==>  a>=c, b>=c.

## Thanks vv...

@vv I was kind of hoping for a LPSolve solution, (you did mention you had one but it was incomplete). Anyways, what you've done is great.

I did use your TSP code for the first part, because in effect it was a TSP problem (1 path starting and ending at the depot). the second and third parts were not.

For what its worth I managed  "sledgehammer to crush a walnut code" to solve the problem [with the assistance of Carl Love and Tom], but I get memory overload for N=14...
Tours_CL_Dataframe_2.mw

## thanks Yury...

@Kitonum I have just posted another question on this theme
http://www.mapleprimes.com/questions/221834-Convert-Max-To-ILP-Constraint?sq=221834

## nearly...

thanks. I was tired when I wrote the original Q. I change what i want, slightly.

Trying this input:

I get for the second partition:
Max(d[1]*x[1, 2]), Max(d[1]*x[1, 3]+d[3]*x[3, 4])<=K

But what i want is

max(d[1]*x[1, 2] , d[1]*x[1, 3]+d[3]*x[3, 4] )<=K

for all indices in Tour2

## Just what I needed...

@tomleslie and Carl, thanks

## redirect from...

Here is a question and answer which doesn't violate the triangle inequality.

2. Given the following cij matrix, determine the shortest vehicle routes and their lengths to distribute goods from one warehouse, denoted 1 below, to the eight customers, denoted 2 9 below, when:

a)  all vehicles have a capacity of 200 units.
b)  all vehicles have a capacity of 100 units.
c)  all vehicles have a capacity of 70 units.

The Depot is located at (40,40).

restart:

 (1)
 > city :=  [[40,40], [22,22], [36,26], [21, 45], [45,35], [55,20], [55,45], [26,59] ,[55,65]]; N:=nops(city):
 (2)
 > #c := array(1..N,1..N,[evalf(seq([seq(((city[i][1]-city[j][1])^2 + (city[i][2]-city[j][2])^2)^(1/2)                                     ,j=1..N)],i=1..N))]);

N:=9:

 > c:= Matrix(    N\$2, shape= symmetric, scan= triangular,    [0, op]~([[26,15,20,7 ,25,16,24,29],                 [15,23,26,33,40,38,54],                    [24,13,20,27,35,43],                       [26,42,34,15,39],                          [18,14,31,32],                             [25,49,45],                                [32,20],                                   [30]] )):

d:=<0, 18,26,11,30,21,16,29,37>:

P:=plots[pointplot](city, color=red, thickness=2, connect=false):
T:=plots[textplot]([seq([op(city[i]),i],i=1..9)],align=right, font=[TIMES,ROMAN,15]):
S:=plots[textplot]([40,40,"Depot"]):
plots[display](T,P,S);

Triangle inequality holds:

seq(seq([i,j,c[i,j]+c[j,N],c[i,N],c[i,j]+c[j,N]>=c[i,N],is(c[i,j]+c[j,N]>=c[i,N])],i=1..N ),j=1..N )[1..5];

 (3)

a)  Vehicle capacity < 200        note: only 1 route will be needed (TSP)

K:=200: n := sqrt(numelems(c)): N:={seq(1..n)};

 (4)

 (5)

conx:= seq( add(x[i,j], i=N minus {j})=1,j=N); #expression 2.3

 (6)

conK:= add(add(d[i]*add(x[i, j], j = N minus {i}), i = N minus {j})) <= K; #expression 2.4

 (7)

conV:= seq(add(x[i, k], i = N)-add(x[k, j], j = N) = 0, k = N); #expression 2.6

 (8)

binaryvariables={ seq(seq(x[i,j],i=N minus {j}),j=N)}; #expression 2.7

 (9)

conu:= seq(seq(u[i]-u[j]+n*x[i,j] <= n-1, i=N minus {1,j}), j=N minus {1}): #vv code to avoid subtours
Sol := Optimization[LPSolve](z, {conx,  conK,conV,  conu},

binaryvariables={ seq(seq(x[i,j],i=N minus {j}),j=N)} ); #vv's code

 (10)

X:=eval(Matrix(n, symbol=x),{Sol[2][], seq(x[i,i]=0,i=1..n)});

ord:=1: k:=1: to n do k:=max[index](X[k]); ord:=ord,k od:'order'=ord; #vv's code
trace(Sol);

 (11)

f:=[1,7,9,8,4,2,3,6,5,1]

 (12)

 (13)

 (14)

b) Require capacity<=100. Two routes are needed to minimize cost z.  The answers are z=198.......

f:=[1,4,8,9,7,1]

 (15)

 (16)

 (17)

f:=[1,2,3,6,5,1]

 (18)

 (19)

 (20)

now, how to get these results programmatically: (?)

K:=100: #with new K, repeat above procedure. Hardly surprisingly, it doesnt work,

c) Require capacity <=70. Three routes are needed to minimize cost z. Answer z=223.....

f:=[1,7,9,1]

 (21)

 (22)

 (23)

f:=[1,2,3,6,1]

 (24)

 (25)

 (26)

f:=[1,5,4,8,1]

 (27)

 (28)

 (29)

## Thankyou for your interest in my problem...

What is the role of the node 0? I have replaced node 0 with 1, since as you previously point out 0 is not indexable in a matrix.
- Is it in N? in C? N={1..9}
- What is c[0, j]  ?   Or is it not defined/necessary? I see you are reading this from the .dk insert. c is the distance matrix. I made it c[1,j] for my problem,
- Are (some) (0,j), (i,0) in A? I have changed it to  (1,j), (i,1).

I have reposted the problem (with proper question and answers supplied) at

## One more imposition.......

@Carl Love thanks for your efforts on my problem.

I wonder if using the DataFrame structure, the 6th index only could be displayed ( minimum of +tour dists which in this case is 98), so it displays [6,[[1,2,3,4,5]],[98],98,[85],85]]] . At the moment I have to guess the range where the mimima of +tour dists is.

I tried

MM[min(MM[`+tour dists`])];

AND/OR

given

MM[MM[`+tour dists`] >=~ 90 and MM[`+tour dists`] <=~ 120];

sort the resulting output in Ascending order of `+tour dists' ie  [6,[[1,2,3,4,5]],[98],98,[85],85]]] is at the top. Thankyou

PS I'm aware if I right click on the DataFrame output I can get Data Manipulation menu, but it doesnt quite do what I want....

## Error, (in unknown) adding lists of diff...

@Carl Love Sorry to bother you. I tried to do add an uneven length list but I got this error. I hope you can fix it

Tours_CL_between.mw

 First 6 7 8 9 10 11 12 Last Page 8 of 25
﻿