Classes

All the lasses have dierent roles inthe whole algorithm, they an all be seen in appendix

C.2

^.

3.3.1 Run.java

This lass is the main le, it is used when the algorithm is to be run. In this lass

infor-mation dened from input les, using GetDataFrom*.java; the initial guess is dened, in

Ini-tialguess.java; and simulated annealing is performed, in SimulatedAnnealing.java. The whole

run ofthealgorithm istimedtoseehowlongaalulation takes.Manyoftheonstantsused

intheprogram aredenedinRun.javaandthereforeitisruialtohangetheleifadierent

data setisbeingtested.

The initial guess generated in this projet was an empty set, all buses driving from soure

to sink. There areother possibilities for generating this guess,for example in [13℄ a method

alled adaptive memoryproedure isusedto nd initial guesses.

3.3.2 SimulatedAnnealing.java

Thislassis theore ofthealgorithm asitperformsthesimulated annealing.Thislassalls

moves.java, CalulateOpt.java and CalulatedTime.java. All of the time onstraint are handled

inthislass.Thetemperature,redutionfator,frozenfator,maximumnumberofiterations

andthemaximumtravel timearedened inthis lass.

3.3.3 Moves.java

This lass alls the neighborhood lasses, UnvisitedPoints.java and NumberOfBuses.java. In

this lassthe probabilities of ertainneighborhoods are determined. Thisis done by using a

probability matrix,

P

^.

3.3.4 Neighborhood Classes

There are sixpreviously dened neighborhoods.

In BusMove.java a bus move is implemented. If the new proposed solution is infeasible, for

example theroute toolong, SimulatedAnnealing.javawill rejet it.

The three types of swap moves are alled in SwapMove11.java, SwapMove21.java and

Swap-Move31.java. Aswith the bus move ifanyof the solutions alulated bythe swap moves are

infeasible SimulatedAnnealing.javawillrejet it.

Therearefourdierentinsertmoves(11,12,14and15).ThesearedenedinInsertMove11.java,

InsertMove12.java, InsertMove14.javaand InsertMove15.java. Aswiththeothemoves ifa

solu-tion isinfeasible thesoltuion is rejeted. Whih insert move is best suited for thealgorithm

is determined intests.

InsertMove13.java was reated for a ertain ase. If an unimportant node was added to the

solution there wouldbea hane thatthis node wouldbe removed and replaedwitha more

important node.

3.3.5 Other Classes

TwolassesalledalulateTime.javaandalulteOpt.javaalulatethetraveltimeoftheroutes

and the objetive funtion. In alulatedOpt.java both onstants inthe objetive funtion,

α

and

β

^,aredened.

NumberOfBuses.java is usedto determine how many routes are urrently ative. This has to

be usedfor exampleinBusMove.java,beauseadding analready ative routeis impossible.

UnvisitedPoints.java is denitely the bottle nek of the program. It uses a triple for loop to

onstrut a vetor of unused points. This is neessary in theprogram, for one annot add a

point that is urrently inuse. The lass uses thetwo dimentional matrix route to determine

whih pointsarenotinuse.Routeisa

| K | × | V |

^{matrix thatshowsthealltheroutesandthe}

pointstheyvisit.In anearlierversionofUnvisitedPoints.javaavetor alled

Y

^wasused.This

versionwas simpler and faster but unfortunatetly beause of inheritane fators inJava this

didnotwork.Futureinspetionsoftheprogram might xtheproblembutinthisprojettoo

muh timehad been spent onthe problemsoit wasleftasis.

AseondversionofUnvisitedPoints.javawasonstruted thatremoved allpointswithin a

er-tainradius ofa hosennodefrom the setof usable nodes.

Very late in the projet's proess an important lass was reated alled Derease.java. The

objetive of this lass was to inspet whih points where within radius

M

^{from the depot}

and remove all other points. As it is impossible for a route to travel further than

M

^,

maxi-mum routelength,beauseall points at afurther distaneareunimportant. Thislasswasa

great susessdereasing runtimefromover100 seonds tounder10 seonds inone instane 4

.

This lassalso provided better solutions.Unfortunatetly thelass wasintrodued late inthe

projetsosoitwasnotinluded inalltests,thosetestthatusedthislassindiatesointhere

introdution.

Programs were also onstruted,during experiments, to run a number of testsonseutively.

Thesewereall simpleprograms only onstrutedfor optimal useof time.

4

Dataset50a,

M = 20

Tests

4.1 Data Sets

There were25datasetsandofthose22wereonstruted.Theotherthreewereobtaineddata

setsfrom Tang and Miller-Hooks[13 ℄.

Toverifythealgorithm,usedforsolvingthe busrouteproblem,testswereimplemented.Note

inthis hapter

τ _ij

^{are always Eulidian distanes, also note that}

τ _0,i = 0, f oralli ∈ V

^when

dealing with generated data sets. Also

δ _i

^{, penalty for stopping at a single node, an have}

dierrent values for all

i ∈ L

^{.In thetest performedfor onstruted datasets}

δ _i = 1, ∀ i ∈ L

^.

In test using obtaind datasets

δ _i = 0

^{for all}

i ∈ L

^{.For thedepot}

δ ₀ = 0

^and

δ _n+1 = 0

^inall

tests.

4.1.1 Construted Data sets

The onstruteddatasetsareatagorizedintotwo types,thenon-randomlyonstruted and

data setsand the randomly onstruted datasets.

The non-randomlyonstruteddatasets weresituatedinagraphof thesale

100 × 100

^.The

depot wasdened asthe enter,

(50, 50)

^{, and had a numberof routes ina ertain diretion.}

The possible number of these routes was 3 and 4. A typial data set with three routes an

beseen inFigure

4.1

^{.Eahnodewassituatedsothatithad theoordinates}

(m _x , m _y )

^,where

m _x ∈ Z +

^and

m _y ∈ Z +

^{(both positive integer numbers). This means that when using three}

routes, originating from the depot, the Eulidian distane between a point and its losest

neighbor waseither1or

√ 1 + 1

^{.Intheaseweretherewerefour routes,}originating fromthe depot, thedistanebetween apoint and istlosest menighbor wasalways 1.

Of the non-randomly generated data sets six had 50 points and six sets had 100. As these

datasets where supposedtobesimple,to inspetifthealgorithm worksfor thesimpleases,

the prot of every node was the same, witha value of 10. This was perhaps a bit to simple

so a numberof nodes had to beremoved or have there prots dereased, otherwise thedata

sets would ahve been to simple. Therefore a small number,

10%

^{, of points were hosen. the}

reason forhoosing

10%

^isthat

10%

^{issuently smallto hange thedataset butstillretain}

the original simpliity. This means that in a 100 points data set 10 were seleted. Of these

ten points ve were removed and ve had there prots dereased to 1. When dealing with

Depot

a1

a2

a(n−1)

a(n)

b1

b2

b(n−1)

b(n) c1

c2 c(n−1) c(n)

Figure4.1: Thisis atest,type 1,withthree routes and

n

^{points oneah route.}

50 point data sets ve points were seleted, of these three were removed and two had there

prots dereased to1.

Thenon-randomlygenerateddatasetswerenamedbythreeparameters.Firstwasthenumber

ofroutes,seondwasthenumberofpointsandthird wasthedatasetsnumberamongsimilar

data sets. Therefore athree route 50 point data setgenerated seond, among other 50 point

three routedatasets,wasnamed:

3

^_

50

^_

b

^{.There wereonly threesimilardata setsa,band.}

The randomly generated data sets were devided into two subgroups, the 50 point data sets

and the 100 point data sets. The 50 point data sets were generated on a

50 × 50

^{graph, as}

with thenon-random datasets eah oordinate onsistsof two positive integere numbers. In

the data sets the depot was dened in one orner,

(50, 50)

^{. This is similar to the loation}

of ALCAN aluminium plant with onern to Reykjavík. Of these 50 points eah was given

a protranging from one to ten, One representing an node of unimportane and tena node

of great importane. This sale was used beause it has, in the past, been used in similar

situations withgood result.These protswere randomly generated inJava.

The100pointrandomlygenerateddatasetsweresituatedona

100 × 100

^{graph.Thedepotfor}

the 100pointdatasetsisdenedasthepoint

(50, 50)

^{.Aswithotherdatasetstheoordinates}

onsistedof twopositive integer numbers. Prots rangedfromone to ten.

The randomly generated data sets were named aording to there rank among similar data

sets andthe numberof points inthem.The rankswere dened asa,b,,d and e where

a

^was

genratedrstand

e

^{last.Thereforea100pointdatasetgenratedfourthwasalleddataset}

50c

^.

A subset of dataset 50a was alsoonstruted. This subset onssited of the20 rst pointsin

the dataset50a.The setwasnamed dataset20.

4.1.2 Obtained Data Sets

When onstruting omputational experiments it is neessary to ompare your results to

othersimilar methods. Inthis projetthe TOP was most similar to theBRPand thus ideal

for omparison. The authors of [13℄ were kind enough to send supply data sets so that a

omparisonould be done.Thethree data sets usedhad102 points,32 pointsand33 points.

Allof thesewererandomly generated andhad prots ranging fromve to 50 1

.

In document B R efACA
e (Sider 40-45)