B R efACA
e

Einar LeifNielsen s041910

Deember 3,2006

Supervisor: Professor Jesper Larsen

Informatis and Mathematial Modelling

Tehnial University of Denmark

In this thesis a problem, presented by ALCAN Ieland, is put forth. The problem, alled

the bus route problem, examines the pikup of employees on route to an aluminium plant.

Thereforeadepotisdenedandalsoasetofpikuploations.Abusmustnavigatethroughthe

pointshoosing onlythe most importantloations.Theproblemispresentedmathematially

andameta-heuristi, simulated annealing, isusedto solve theproblem.Thearea numberof

testsputforth.Agoodoolingsheduleisalulated.Amatrixdeterminingtheprobabilityof

aneighborhoodis onstruted.The best method ofnode insertion into thesolution isfound.

The algorithm alulated strutured solutions provided with non-randomly generated data

sets.The simulated annealingalgorithm was thenvompared to aGAMS program, returning

values between the upperbound and theobjetive value alulated withGAMS. Comparison

between tabu searh algorithm for TOP and the simulated annealing algorithm showed that

the former is faster for small data sets and nearly always returns better objetive values.

Finally a onstraint foring a bus to travel for a eratain amount of time before stopping

again wasimplemented.

Iwouldlike tothankProfessorJesperLarsen mysupervisorontheprojetfor always lending

a helping handwhenneededandProfessor JensClausenfor llinghisshoeswhenJesperwas

absent.I would also like to thank Min Wen whoassisted meinany way thatwasrequested,

among other things she ontributed greatly to theGAMS program, disovered how to make

the modellinear andadded the distaneonstraint to themodel. Snorri Páll Sigurdsson, my

oe neighbour,whohelped innumerus waysandinspetedmyreport.ProfessorPállJenson

wasinstrumentalintheprojetashewastheonewhofoundtheproblemandhandedittome.

HewasalsotheprojetsupervisorfortheUniversityofIeland. AtALCANIwouldespeially

like to thank Þorsteinn Ingi Magnússon whowasthe projet supervisorfor theompany, he

got me all the data that ALCANsupplied and a desk at there oe when that was needed.

AlsoIwouldliketothankArngrímurEinarssonandFannarØrnThordarsonforproofreading

the thesis.

1 Introdution 11

1.1 Status Desription andMotivation . . . 11

1.2 Outline of the Thesis . . . 12

2 Bus Route Problem 15 2.1 Analysis ofthe RealistiPossibilities . . . 15

2.1.1 SWOT Analysis . . . 15

2.1.2 Combined Solutions . . . 16

2.1.3 Chosen Solution . . . 19

2.2 Problem Denitionand Desription . . . 19

2.3 A MathematialModelfor BRP. . . 21

2.3.1 Objetive Funtion . . . 22

2.3.2 Constraints . . . 22

2.3.3 Linearity . . . 24

2.3.4 UpperBounds . . . 24

2.4 Review of Relevant Problems . . . 25

2.4.1 TSP . . . 25

2.4.2 PCTSP . . . 26

2.4.3 VehileRouting Problem . . . 27

2.4.4 OpenVehileRouting Problem . . . 28

2.4.5 TeamOrienteering Problem . . . 29

2.5 Review of Methods . . . 30

2.5.1 A Lagrangian heuristi for the Prize Colleting Travelling Salesman Problem [8℄ . . . 30

2.5.2 Prie Colleting Travelling SalesmanProblem [1℄ . . . 30

2.5.3 On Prize-Colleting Tours and The Asymmetri Travelling Salesman Problem [9℄ . . . 30

2.5.4 Hybrid algorithms with detetion of promising areas for the prize ol- leting travelling salesman problem[4℄ . . . 31

2.5.5 A tabu searhalgorithm fortheopen vehilerouting problem[3℄ . . . . 31

2.5.6 OpenVehileRoutingProblemwithTimeDeadlines:SolutionsMethods and Appliation [17 ℄ . . . 32

2.5.7 A general heuristi for vehilerouting problems [11 ℄ . . . 32

2.5.8 Openvehile routing problemwithdriver nodesandtimedeadlines [16℄ 33 2.5.9 A TABU Searh Heuristifor the Team OrienteeringProblem [13℄ . . . 33

3 Simulated Annealing for the BRP 35

3.1 Simulated AnnealingAlgorithm . . . 35

3.1.1 Neighborhoods . . . 36

3.1.2 Adapting SA forBRP . . . 38

3.2 Implementation Details . . . 39

3.3 Classes . . . 40

3.3.1 Run.java . . . 40

3.3.2 SimulatedAnnealing.java . . . 40

3.3.3 Moves.java . . . 40

3.3.4 Neighborhood Classes . . . 40

3.3.5 Other Classes . . . 41

4 Tests 43 4.1 Data Sets . . . 43

4.1.1 Construted Datasets . . . 43

4.1.2 Obtained DataSets . . . 45

4.2 CoolingShedule . . . 45

4.2.1 First Trials for Calulatinga Cooling Sheduleusing DataSet 50a . . . 47

4.2.2 Seond Trialsfor Calulating a Cooling Shedule using DataSet50a . . 52

4.2.3 Cooling Shedual Trialsfor Data Set

3

^_

50

^_

a

^{. . . . . . . . . . . . . . . 57}

4.3 Determining the ProbabilityMatrix . . . 60

4.3.1 Results for DataSet

3

^_

50

^_

a

^{. . . . . . . . . . . . . . . . . . . . . . . . 63}

4.3.2 Results for DataSet

50a

^{. . . . . . . . . . . . . . . . . . . . . . . . . . . 64}

4.4 Exploring Dierent InsertMoves . . . 65

4.4.1 Results . . . 66

4.5 Non-RandomlyGenerated Data Sets . . . 70

4.5.1 Results DataSet

3

^_

50

^_

a

^{. . . . . . . . . . . . . . . . . . . . . . . . . . 70}

4.5.2 Results for DataSets

3

^_

50

^_

a, b

^and

c

^{. . . . . . . . . . . . . . . . . . . 72}

4.5.3 Results for DataSets

3

^_

100

^_

a, b

^and

c

^{. . . . . . . . . . . . . . . . . . 74}

4.5.4 Results for DataSets

4

^_

50

^_

a, b

^and

c

^{. . . . . . . . . . . . . . . . . . . 77}

4.5.5 Conlusion inDataSets

4

^_

100

^_

a, b

^and

c

^{. . . . . . . . . . . . . . . . . 79}

4.6 Randomly Generated DataSets . . . 80

4.6.1 Testwithdatasets 50a,b,,d and ewith450,000 iterations . . . 81

4.6.2 Comparing Probability matries

P ₂

^and

P ₂ ^∗

^{. . . . . . . . . . . . . . . . 82}

4.7 Comparison to GAMS . . . 84

4.7.1 Results Comparisonto GAMS . . . 84

4.7.2 Results Comparisonto Derease.java with NewCoolingShedule . . . . 86

4.8 Obtained DataSets. . . 88

4.8.1 Results for DataSet32 . . . 88

4.8.2 Results for DataSet33 . . . 89

4.8.3 Results for DataSet102 . . . 89

4.9 Distane Constraint . . . 90

5 Conlusions 97

5.1 Further Work . . . 98

5.1.1 Real WorldAppliation . . . 98

5.1.2 Algorithm Improvement . . . 98

5.2 A Learning Experiane . . . 99

A Results 103 B Solution Types 115 B.0.1 Combined solutions. . . .119

C Algorithm 135 C.1 Numberof Possible Solutions . . . .135

C.2 Algorithm . . . .136

C.2.1 Run.java . . . .136

C.2.2 SimulatedAnnealing.java . . . .139

C.2.3 moves.java . . . .143

C.2.4 InitialGuess.java . . . .147

C.2.5 alulateOpt.java . . . .148

C.2.6 alulateTime.java . . . .149

C.2.7 UnvisitedPoints.java . . . .149

C.2.8 NumberOfBuses.java . . . .151

C.2.9 InsertMove11.java . . . .151

C.2.10 BusMove.java . . . .153

C.2.11 SwapMove11.java . . . .156

C.2.12 SwapMove21.java . . . .157

C.2.13 SwapMove31.java . . . .159

D Test 163 D.1 Non-RandomlyGenerated Data Sets . . . .163

D.1.1 Results DataSet

3

^_

50

^_

b

^{. . . . . . . . . . . . . . . . . . . . . . . . . .163}

D.1.2 Results DataSet

3

^_

50

^_

c

^{. . . . . . . . . . . . . . . . . . . . . . . . . .163}

D.1.3 Results DataSet

3

^_

100

^_

a

^{. . . . . . . . . . . . . . . . . . . . . . . . .165}

D.1.4 Results DataSet

3

^_

100

^_

b

^{. . . . . . . . . . . . . . . . . . . . . . . . . .166}

D.1.5 Results DataSet

3

^_

100

^_

c

^{. . . . . . . . . . . . . . . . . . . . . . . . . .167}

D.1.6 Results DataSet

4

^_

50

^_

a

^{. . . . . . . . . . . . . . . . . . . . . . . . . .168}

D.1.7 Results DataSet

4

^_

50

^_

b

^{. . . . . . . . . . . . . . . . . . . . . . . . . .169}

D.1.8 Results DataSet

4

^_

50

^_

c

^{. . . . . . . . . . . . . . . . . . . . . . . . . .169}

D.1.9 Results DataSet

4

^_

100

^_

a

^{. . . . . . . . . . . . . . . . . . . . . . . . .170}

D.1.10 Results DataSet

4

^_

100

^_

b

^{. . . . . . . . . . . . . . . . . . . . . . . . . .171}

D.1.11 Results DataSet

4

^_

100

^_

c

^{. . . . . . . . . . . . . . . . . . . . . . . . . .172}

D.2 CoolingShedule . . . .173

D.2.1 Results for temperature,

T

^{,rst run . . . . . . . . . . . . . . . . . . . .173}

D.2.2 Results for redutionfator,

r

^{,rstrun . . . . . . . . . . . . . . . . . .182}

D.2.3 Results for stopping riteria,

F

^{,rst run . . . . . . . . . . . . . . . . . .186}

D.2.4 Results for temperature,

T

^{,seond run . . . . . . . . . . . . . . . . . . .191}

D.2.5 Results for redutionfator,

r

^{,seondrun . . . . . . . . . . . . . . . . .198}

D.2.6 Results for Temperature,

T

^,DataSet

3

^_

50

^_

a

^{. . . . . . . . . . . . . .206}

D.2.7 Results for Redution Fator,

r

^,DataSet

3

^_

50

^_

a

^{. . . . . . . . . . . .206}

D.2.8 Results for FrozenFator,

F

^{,Data Set}

3

^_

50

^_

a

^{. . . . . . . . . . . . . .217}

D.3 Randomly Generated DataSets . . . .217

D.3.1 50 point protvetor. . . .217

D.3.2 100 point protvetor . . . .219

D.3.3 Testwithdatasets 50a,b,,d and ewith450,000 Iterations. . . 223

D.4 Results Comparisonto Derease.java withNewCoolingShedule . . . 226

D.4.1 Results for theDistaneConstraint . . . .226

Introdution

1.1 Status Desription and Motivation

This exam projet is done by Einar Leif Nielsen for ALCAN in Straumsvík, Ieland. Main

supervisoron this projet was JesperLarsen, at IMM DTU. Co supervisors were Min Wen,

PhD student at IMM DTU, and Páll Jenson, professor at the University of Ieland. In the

middle of the projet Jesper Larsen had to leave for New Zealand, for a few months, inthe

meantimeProfessor JensClausentook overJespersduties on theprojet.

ThisprojetdealswiththepikupofemployeesfortheALCANaluminiumplantatStraumsvík

Ieland. ALCANis the seond largestaluminium manufaturer intheworld. Itsname isde-

rived from the wordsALuminium and CANanda.It hasover470 failities in55 ountries 1

.

Thealuminium fatory inIeland is the 11th [5℄, largest, in theorporation. It isloatedin

Straumsvík,whihisajustoutsideofHafnarfjördur,asuburbofReykjavík.Aluminiumoxide

is imported fromAustraliaand manufatured intoaluminium. Themetalisthentransported

overseas for further work.ALCAN Ieland employees a around 470 persons [5 ℄ and wasthe

rst aluminiumplant onstruted inIeland. There arenowthree andmore areplanned.

ALCAN's bus system,whih piks up employees, was rsttaken into use30 years ago. That

system has sine grown and new pikup points have been added without alulating their

loation. Now the system is very ompliated and has grown very expensive. A newly im-

plemented taxondiesel fuel,bytheIelandigovernment, haslinreased theostevenmore.

ThereforeALCANdeidedtoseeifamoreeonomialmethodforpikingupemployeesexists.

The goal of this projet is to nd more eonomial bus routes and to see if the number of

buses,andtherebyroutes,anbedereased.ALCANhopesto dereasetheostofthesystem

byat least10-15%.Thisan beahieved byinspeting theloation ofpikup pointsto seeif

all urrent pikuppointsareneessary.Alsonewpikuppointsan beintrodued thatwould

be better loated than those urrently in use. New areas 2

will not be added to the urrent

system.ALCANalsohopesthatthis will dereasetravel timefor theemployees assome em-

ployeesspend nearlyan hour onthebus.

1

http://en.wikipedia.org/wiki/Alan

2

Neighborhoodsandsuburbs.

ALCANprefersageneral solutionasitreeivesalarge workforeduringthesummermonths

thatrelieveother employeesduring summervaations. Thisdoesnot meanthatspeial solu-

tions should be exluded. Theywill be looked into and their importane estimated. ALCAN

hasrequested that various typesof solutions areto be inspeted.

TheurrentnumberofemployeesatALCANis467dividedonthreeshifts.Adayshift,08-16;

an afternoon shift, 16-00; and a night shift, 00-08. There are also three types of employees.

Those whoworkthedayshift,thosewhoworkthedayshiftandtheafternoonshiftandthose

whowork onall three shifts.Also there arethosewho work weekends andthose whodo not.

Asis thease with most workplaes, that use ashift system, at no timeis all the workfore

present attheplant.Sothelargestworkforeispresentduringthedayshiftontheweekdays

whilethesmallest workforeis present during night timeontheweekends.

For the day shift pikup ALCAN uses 68 pikup points and approximately another 15 are

addedforthe nightand afternoonpikup(during thesetimessomeoftheotherpikuppoints

are exluded). New pikup point will be added to the system, these points an be loalbus

stopsorotherstrategiallyhosenpoints,whileotherswillberemoved.Theurrentroutesare

ofdierentlengthsthelongesttakingapproximately52minutes,driveninthemorningduring

weekendsand holidays;and theshortestapproximately 29minutes, driveninthemorningon

weekdays.

Currently Hópbílarsupplythebuses usedinpiking upemployeesforthealuminiumplantin

Straumsvík. Hópbílar is a privat bus ompany and one of the biggest in its eld inIeland.

They have served ALCANwell andboth ompanies want to ontinue that ooperation.

Other transportation possibilities mentioned in this report are: theloal bus system,run by

a ompany alledStrætó; andthe loaltaxiservies,whiharemany.

1.2 Outline of the Thesis

There arevehapters inthis thesisexludingtherst,thisone.Eahofthese vehapeters

examina dierent partof theproblem thathasbeenintrodued.

Theseond hapter annalysisthe problempresented, denes itand presentsa mathematial

model. There is also a review of relevant problems. The nal setionin the rst hapter ex-

aminsmethods thathave beenimplemented onsimilar problemsand their results.

The third hapter looks at the theory of the algorithm used for solving the problem. Also

implementation ofthis algorithm isexplaind.

The fourth hapter looks at various tests, or ompuational experiments. In this hapter the

bestparameters arealulated andimplemented. Various datasets weregenerated and other

datasetsobtained.

Thefthandnalhaptersummarisestheonlusionsreahedinthisprojet.Thefth hap-

teralsopossesquestionsregardingfurtherwork, suhas:Is thereanyfurther development of

There is also a large appendix in this report ontaining various results from experiments,

analysisandthe algortihm used.

Bus Route Problem

Inthissetionanumberofdierentsolutionsforsolvingthisproblem,areexplored.ALCAN's

bus route problemwill fromnowon simlpy be reeredto asthebus routeproblem.

2.1 Analysis of the Realisti Possibilities

For this problem there are many possible solutions, these types of solutions have been ate-

gorized in two types.

1. First type of solutions only rely on one transportation possibility. That is only one

ompanywill transportemployeesto and fromthealuminium plant.

2. The seond type of solutions areombinationsof two transportation possibilities.

It was onsidered and rejeted to use ombinations of more than two transportation possi-

bilites. The reason for this is that solutions of theseond type overed all hours of the day,

365 days a year. Therefore a new more omplex ombinations would oer no improvement

over the solutions of type 2.Also ombinations of more than two transportation possibilities

arelikely tobe tooexpensive.

In total there are 8 solutions of the rst type and 25 ombined solutions. Solutions of type

onearedened intable 2.2.

2.1.1 SWOT Analysis

Strength, weakness, opportunity and threatsanalysis, or SWOT analysis, wasusedto deter-

minewhih solutionwouldbebestsuited insolving the busroute problem.Thisis amethod

oftenusedto dene the prosand ons.In thismethod:

strength represents helpfulinternal fators

weakness represents harmful internal fators

opertunitiesrepresents helpfulexternal fators

threats representsharmful external fators

Whenusing SWOTanalysisone hasto deneinternal andexternal fators.Intheaseofthe

bus routeproblem internal fatorswere dened as: Theauthor of theprojet, ALCANand

theprojetsupervisors.

External fatorswere dened as: The employees of ALCAN, transportation ompanies and

thegeneral publiof thegreaterReykjavíkarea.

Afterinternal and external fator have been dened a table is onstruted. An example of a

SWOT analysistablean beseen inTable

2.1

^.

Helpful to ahieving the ob-

jetive

Harmful to ahieving theob-

jetive

Internal Dereases ost. Dereases

travel time. A general solu-

tion that takes into aount

employee turnover. Works

all year round, 24 hours a

day. This solution is not too

simple to be onsidered a

exam projet.

Not ALCAN's desired solu-

tion. In this solution new

nodeswithouta predenedlo-

ation annot be used. Hard

to estimate the general popu-

lation of an area.

External Dereasestraveltime. Dereases prot for Hópbílar.

Dereases the urrent amount

of servie provided by AL-

CAN.

Table2.1:Thistableshowhowsolutionoftype1wasanalysed.SWOTanalysisofallsolutions

an be viewed inappendix

B

^.

2.1.2 Combined Solutions

All possible ombined solutions are shown intable 2.3. Although due to the number of pos-

sible ombinations more information ould not be inluded in the table. Therefore a short

explination, of Table

2.3

^{, isin order for example lookat ombination 1(Combo 1).This is a}

ombinationofsolutions oftype4andtype1,both aredenedintable2.2.Thisombination

proposes the use of Strætó, the loal bus system, when possible and Hóbílar, a private bus

ompany, whenStrætó islosed. Thisisuseful asthe loalbus systemis losed duringnight

timeandduring holidays suh asChristmas.

Adierent ombination type, isombination 15(Combo 15).Thisombinationusessolutions

of type 2 and 5. Note though that the ombination uses an extreme solution of type 2. An

extremesolution triestolimit the numberofroutes andtravel timeof asinglerouteasmuh

as possible. So the solution would provide a few pikup points were Hópbílar would stop.

Employees howeverwould have to getto these pikuppointsbythemselves.

Inappendix

B

^{all ombinationsolutions aredened and analyzedwiththeSWOT method.}

Table 2.2: Possible solutions for theproblem

Name Desription Transportation

Type 1 Useurrentpikuppointsalongwithnewones

(predened,suhasloalbusstops).Estimate

the importane of eah pikup point by the

numberofpeoplelivinglosetoit,theamount

ofparkingandonnetionto loaltransitsys-

tem.BusesfromHópbílarareusedto pikup

employees.

Hópbílar

Type 2 Same as type 1 exept importane of pikup

pointsis deidedbythenumberof employees

thatlive lose to them.Buses

Hópbílar

Type 3 Same as type 2 exept a software, suh as

ShorTre fromAGR hf.,is usedto determine

thebusroutes.Anewrouteanbealulated

asoftenasALCANdesires.Buses

Hópbílar

Type 4 Usestheloalbussystem,buses,topikupem-

ployees andreturn them.

Strætó

Type 5 Car pooling. Eah ar will be given a driving

diary and reeive a payment for gas used at

the end of the month. It would be neessary

to writeaprogramthatwouldputvepeople

togetherasa partof aarpoolingteam.

Employees

Type 6 Drivinggrant.Eahemployeewouldreeivean

inrease in payto ompensate for the lak of

buses.Theemployees wouldthendrive them-

selvesto work.

Employees

Type 7 Car pooling with taxis. A taxi would pikup

employees and return them. Eah taxi would

belledwithpassengers.Aprogramwouldtell

thetaxiserviewhere andwhentopikupan

employee.

Taxi servie

Type 8 Sameastype1exeptthepikuppointswould

bealulated sothat thereloation wasgood

and not frompredetermined points. Buses

Hópbílar

Table 2.3: Possible solutions for theproblem

Name Desription Transportation

Combo 1 Type 4and type 1. Hópbílarand Strætó

Combo 2 Type 2and type 4. Hópbílarand Strætó

Combo 3 Type 3and type 4. Hópbílarand Strætó

Combo 4 Type 5and type 4. Employees and Strætó

Combo 5 Type 6and type 4. Employees and Strætó

Combo 6 Type 7and type 4. Taxi servieandStrætó

Combo 7 Type 8and type 4. Hópbílarand Strætó

Combo 8 Type 5and type 6. Hópbílarand Strætó

Combo 9 Type 7and type 6. Hópbílarand Strætó

Combo 10 Extremesolution using type1 andthenuse type4. Hópbílarand Strætó

Combo 11 Extremesolution using type2 andthenuse type4. Hópbílarand Strætó

Combo 12 Extremesolution using type3 andthenuse type4. Hópbílarand Strætó

Combo 13 Extremesolution using type8 andthenuse type4. Hópbílarand Strætó

Combo 14 Extremesolution using type1 andthenuse type5. Hópbílarand employees

Combo 15 Extremesolution using type2 andthenuse type5. Hópbílarand employees

Combo 16 Extremesolution using type3 andthenuse type5. Employees and Hópbílar

Combo 17 Extremesolution using type8 andthenuse type5. Employees and Hópbílar

Combo 18 Extremesolution using type1 andthenuse type6. Employees and Hópbílar

Combo 19 Extremesolution using type2 andthenuse type6. Employees and Hópbílar

Combo 20 Extremesolution using type3 andthenuse type6. Employees and Hópbílar

Combo 21 Extremesolution using type8 andthenuse type6. Employees and Hópbílar

Combo 22 Extremesolution using type1 andthenuse type7. Taxi servieandHópbílar

Combo 23 Extremesolution using type2 andthenuse type7. Taxi servieandHópbílar

Combo 24 Extremesolution using type3 andthenuse type7. Taxi servieandHópbílar

Combo 25 Extremesolution using type8 andthenuse type7. Taxi servieandHópbílar

2.1.3 Chosen Solution

FromtheSWOTanalysisitwasdeterminedthatsolutionoftype2wasbestsuited.Thereason

for this hoieis thatthis solutionisrelatively simple to program andtherefore agood plae

to start theprojet. Alsothis would provide asolution for ALCAN.Although not asgeneral

asthey mayhave preferredbut ga oodspeialsolution. The denitionof solutiontype 2 an

be seenintable 2.2. Smallhangeshave beenmade to this solutionto better suite theneeds

of ALCAN.Solution oftype 2wasdened as:

Useurrentpikuppointsalongwithnewones(predened,suhasloalbusstops).

Estimatetheimportaneofpikuppointsbythenumberofemployeesthatlive

lose to them, the amount of parking and onnetion to loal transit system.

Busesfrom Hópbílarareusedto pikup employees.

2.2 Problem Denition and Desription

The problem as presented by ALCAN gives a geographial set, a set of employees, a set of

buses and a set ofloations(pikuppoints).The aluminiumplant also hasa predened loa-

tion and allbuses mustnish theirroute there.

Let us rst lookat thegeographial set. Within this set are thepossible loations of pikup

points, as ALCANhas dened some areas outside of there routes and they do not intend to

inrease this area. Therefore new pikup pointsmust be loated within thegeographial set.

ThetravelbetweenallpointsinasetisalledthetravellingsalesmanproblemorTSP.Inthis

problemonemustnavigatetrhoughanumberofpointsandthenreturntothepointoforigin,

via theshortest traveldistane.

ThesetofemployeesinludesallemployeesatALCAN.Althoughsomeemployeesliveoutside

ofthegeographialsetandarethereforenotrelevanttotheproblem.Thissetisnotveryruial

totheproblembutanbeusefulindeterminingtheimportaneofasinglepikuppoint.Trav-

eling througha set of points eah assigneda prot issimilar to theprie olletingtraveling

salesman problem,PCTSP.Inthatproblemonemustnavigatetrhoughasetofpointsleaving

from a sourepoint and returnhaving olleted aminimumnumber of protonthe way, via

theshortestroute.Notethoughthatonedoesnothavetovisitallpoints,intheset,inPCTSP.

The set ofbuses is important asthe number ofbuses urrently inuse, inthesystem, annot

beexeeded. Theset ofbuses willfromnowbereeredto asthesetof routes.Ifasingle bus

is in use, that bus will be alled an ative route or a route in use. The apaity of a bus is

not important as the number of people working at ALCAN ar not that many. Therfore the

apasityofa singlebus isunimportant.Aproblemdealing withmorethan onerouteisalled

a vehile routing problem or VRP. In VRP one must navigate more than one route leaving

from a depot, visiting all points in the set, and the returning again to the soure, via the

shortespossible routes.

Loationsareruialtothisprojet.Thehoieofwhereabusshouldstopornotisimportant

indeterminingthe ostofthesystem.Theonlyfatoronerningthissetisthattheloations

loation is. To determin this prot the number of employees living within a ertain radius,

available parking, onnetionto loal transit and otherfatorsan be inspeted. To simplify

for nowwe willassumethatthe importaneofanodeisdeterminedbythenumber ofpeople,

within the set of employees, that are living inside a ertain radius from the loation. These

loationswillnowbereferredtoasnodes.Nodesinuseanalsobealledanativenodes.The

are many possibiltiees to add nodes to the existing set of loations as long as those nodes

are within the geographial set. As time is more of an issue than distane the travel time

between individual nodes will be inspeted, not the distane. This problem, as it has been

dened, is verysimilar to the teamorienteeringproblem, TOP.There a teamof moutaineers

must navigate, eahon hisown,though anumberof nodes, therbyolletingprot. Thegoal

of TOP istoollet asmuh protaspossibleand itisnot neessaryto visit allnodesinthe

set. Also inTOP one mustreturn to thepoint of origin.

Another problem, regarding the nodes, onerns the distane, or travel time, between two

nodes. If two nodes are situated very lose to one another the may have overlapping prot.

This means that some of the people living within a ertain radius from node one also live

within said radius from node two. Therefore a onstraint foring the bus to travel a ertain

time before stopping again an be implemented. Another solution regarding this problem

wouldinvolve not hoosing twonodestoo lose toone another.

It is the wish of ALCANto derease the ost of the bus sytem. Thisan be ahived in two

ways. First by dereasing the number of routes in useor seondly by dereasing thenumber

of ative nodes. Thesearetherefore denedasthe twomain fatorinALCAN's problem,the

problem will fromnow on be reeredto asthe bus route problem. ALCAN's whishes are to

limitthenumberofnodesand/orrouteswhilepikingupasmanyemployeesaspossible.This

means that not all nodes have to be visited, only those who are deemed important enough.

AlsoasthebusesthemselvesarenotowedbyALCAN,butbyanoutsideontrator,thebuses

therefore do not have to start at the plant. This means a if a route is used it will originate

from therst node itvisitsand thenmake itswayto thealuminium plant.The open vehile

routing proble,OVRP,is simlar to this.In OVRP one mustnavigatea number ofroutes, all

leaving fromthe samedepot,thougha setofnodes. Allnodesmustbevisitedbut theroutes

do not have to return to the depot. The aluminiumplant will fromhere on be referredto as

a depot.

By ombining ertain elementsof the methods desribed one anformulated amathematial

modelofthebus routeproblem. Alternative methods thanthose previously desribed anbe

used to solve the problem. For example one ould assign all employees to ertain bus stops

and then one would add those bus stops to a bus route. If the route is too long one would

thendereasethenumberofbusstopsandreassigntheemployeestofewerpikuppoints.This

wouldbedone asoftenasneessary.Afteremployees have been assignedtothebus stopsthe

problem beomesa OVRP.

Thismethodwillmost likelyhavea shorteralulationperiodthanthebusrouteproblem. It

wouldtakeintoaounttheapaityofeahvehileandthereisnohanethatabuswillstop

at twopointswithoverlappingprot.Ontheotherhand thebus routeproblemismore likely

to hoosethe bestpossible routes,itis amore general solution and might possiblyhoose to

problem seems to t more to the wishes of ALCAN and therefore is a better andidate for

solvingtheproblem presented.

Todeterminetheloationofnodesapopulationfuntionfortheareaanbeonstruted.This

funtionwouldmapoutthemostpopulatedareasandthepointswiththehighestpopulation,

hot spots, would dene nodes and there prot. The reason this will not be done is that

onstruting a population funtion of a ityis outsidethe sope of this projet, even though

it would give a very general solution. Therefore the method of predened pikup points is

deemedbetter inomparison.

2.3 A Mathematial Model for BRP

The problem dened is the bus route problem, BRP, and it has been ompared to various

methodssuhasPCTSP,TOPandOVRP.Ithasbeen shownthatthebus routeproblemhas

alotinommon withthese otherproblems but isnot thesame asany ofthem.

In this model there are a few sets whih need to be dened.

L

^{is the set of}

n

^loations,

nodes, where pikup of employees is possible. Not all of these loations have to be visited.

V = L ∪ { 0, n + 1 }

^{isthe set of allnodes,}

{ 0 }

^{representsfatory out and}

{ n + 1 }

^represents

fatoryin.Traveltimefromnode

0

^{toanyothernodeisnone,0.Thisisbeausethebusroute}

problem is an open problem, like the OVRP, and it is not neessary for the busses to start

there routeat the depot,plant.

A

^{isthesetof arsbetween nodesandKisthesetof busses,}

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

Toonstrut a modelofthe bus route problem, threevariables have to bedened.

Name Desription

x ^k _i,j

^{The arbetween}

i

^and

j

^{,equal to 1 ifthearisdriven, bybus}

k

^{,else itis equal to}

0.

y i

^{A binarynumberequal to 1ifnode}

i

^{isvisitedelse itis 0}

s ^k _i

^{Thisis the stopping time for bus}

k

^{at node}

i

^.

The time,

s ^k _i

^{, is dened as the time when bus}

k

^{stops at node}

i

^{and is therefore dependant}

on previous

s ^k _j

^{ifthe bus stopped at node}

j ∈ L

^{. Alsothere are afew onstants thatneed to}

bedened beforethe modelispresented. Constantsareall represent withtheGreek sympols

exept forthe upper.

Name Desription

τ _i,j

^{The traveltimebetween nodes}

i

^and

j

^.

φ i

^{The protfor stopping at node}

i

^.

δ _i

^{Indiatespenaltyforstopping atanygivennode,i.e.thetimeittakestostopatany}

give pikup point. Inmost ases there isno penaltyfor stopping at thesoure and

sink.

α

^{Thisis abonus fator for prots,a bonus reeived when apik uppointis hosen.}

β

^{Thisis abonus fator for not usinga bus.}

M

^{An uppertime limit is put on eah route, so thattraveltime for a single employee}

is not greaterthan thisnumber.

N

^{Maximumnumberofbuses.Itisnot desiredto usemorebusesthan areurrently in}

use.

Note that

τ _0i = 0

^{, when}

i ∈ V

^{, beause it is not neessary for a bus to drive from node 0,}

but ithelps to start therewhen onstruting theroutes.Protan be determined by looking

at: population of area, number of employees living lose to the node, parking, bus stops or

ommere inthe area.Someor allofthese fatorswillbeusedwhendeterminingtheprotof

a node. The solution will try to maximize the prot olleted, while minimizing thenumber

ofbuses used.Timewillbe aonstraintrather thanpartoftheobjetivefuntion,thisisalso

doneinTOP.

Aprot,of

β

^{isgainedbynot usingabus.Thereforewhenabusisnotusedittravelsstraight}

form soure to sink,

x ^k _0,n+1 = 1

^.

The bus route problem might be appliable in other ases. In these other appliations some

of these onstants might be unneessary,or others might need to beadded. Thiswill depend

entirely on the problem the model is applied to. Also ost may vary depending on time of

day,or ifthereis aholiday.Thisis beause aost ofusing abus an havemanyfators. The

greatest of these is probably the start up ost for a single bus. Costs an be onsidered as

many things for example maintenane, driver salary and bus ompany prot. Also in some

asesompanies mayhargefor eah kilometer or eahliter ofgasoline used.

2.3.1 Objetive Funtion

Theobjetive funtion for thebus routeproblemis now put forth.

max Y = α P

i φ _i y _i + β P

k x ^k _0,n+1

There aretwofatorsintheobjetivefuntion.Thersthalfoftheequationshowstheprots

gainedstopping ataertainnodeandthatisthenmultipliedwithabonus fator.Theseond

isapositiveontributionforeverybusnotused,

x ^k _0,n+1 = 1

^andallother

x ^k _ij = 0

^,thatisthen

multiplied witha bonus fator.The bonus fator represents for example theost ofa single

bus,

β

^{,or the importane of asingle protpoint,}

α

^.

2.3.2 Constraints

X

k∈K

X

j∈V \{i}

x ^k _ij = y _i ∀ i ∈ V

^(2.3.1)

X

k∈K

X

i∈V \{j}

x ^k _ij = y _j ∀ j ∈ V

^(2.3.2)

Thesetwoonstraints(

2.3.1

^{)and (}

2.3.2

^{) saythatif}

y _i = 1

^,for

i ∈ L

^{,thenthenodeisentered}

and exited.

x ^k _0,j (s ^k ₀ + τ _0,j ) ≤ s ^k _j ∀ k ∈ K

^and

j ∈ V

^(2.3.3)

x ^k _ij (s ^k _i + δ j + τ ij ) ≤ s ^k _j ∀ k ∈ K

^,

i ∈ L

^and

j ∈ V

^(2.3.4)

Theseonstraints(

2.3.3

^{) and(}

2.3.4

^{)ensuresthatifabustravelsbetween}

i

^and

j

^,onroute

k

^,

thenthestopping timeonloation

i

^{is onstraint to theprevious timethebus hastravelled.}

s ^k _n+1 ≤ M ∀ k ∈ K

^(2.3.5)

Constraint (

2.3.5

^{) doesnot allowany routeto havea travel timegreater than}

M

^.

X

k∈K

X

j∈V

x ^k _ij ≤ 1 ∀ i ∈ L

^(2.3.6)

Constraint (

2.3.5

^{) restrits morethan one bus driving between}

i

^and

j

^.

X

j∈V

x ^k _0j = 1 ∀ k ∈ K

^(2.3.7)

Constraint (

2.3.7

^{) ensuresthat abus drivesout of thefatory.}

X

i∈V

x ^k _ih − X

j∈V

x ^k _hj = 0 ∀ h ∈ L

^,

k ∈ K

^(2.3.8)

Here inequation(

2.3.8

^{)it ismadesurethat ifa busdrivesinto a nodeitisrequired to drive}

out of itaswell, ifthenode isintheset ofloations (pikuppoints).

X

i∈N

x ^k _i,n+1 = 1 ∀ k ∈ K

^(2.3.9)

Constraint (

2.3.9

^{) requiresall buses toend there routes at thefatory.}

x ^k _i,j ≤ τ _ij

a ∀ k ∈ K, i ∈ V, j ∈ V

^(2.3.10)

In(

2.3.10

^{) s bus must travelfor a ertain amount of time,}

a

^{,beforestoping at anew pikup}

2.3.3 Linearity

Themodel,aspresentedintheprevioussetion,isnotlinearandthereforesome hangeshave

to bemadeifitistobesolvedinGAMS 1

.Thenon-linearityanbefoundinequations(

2.3.3

⁾

and (

2.3.4

^{), where two variables are} multiplied. To ensure linearity thehanges listed below have to be applied,to the model.

s ^k ₀ = 0 ∀ k ∈ K

^(2.3.11)

s ^k ₀ + τ _0,j − s ^k _j = (1 − x _0,j )W ∀ k ∈ Kj ∈ V

^(2.3.12)

s ^k _i + δ + τ ij − s ^k _j = (1 − x ij )W ∀ k ∈ K, i ∈ Lj ∈ L

^(2.3.13)

s ^k _i + τ _i,n+1 − s ^k _n+1 = (1 − x _i,n+1 )W ∀ k ∈ Ki ∈ V

^(2.3.14)

Here

W

^{is a large number and}

W > | V |

^{.Other onstraints are the same as in the previous}

setion. Although when dealing withaGAMS modelotheronstraintshave to be added:

X

i∈V

X

k∈K

x ^k _i,0 = 0

^(2.3.15)

X

j∈V

X

k∈K

x ^k _n+1,j = 0

^(2.3.16)

X

i∈V

X

k∈K

x ^k _ii = 0

^(2.3.17)

Theseonstraintensure thatanodedoesnot visititself,thatnoone anreturnto thesoure

andthatno one an leave the sink.

2.3.4 Upper Bounds

First andthemostobviousupperboundtotheproblemistoletone routevisit allthepoints.

U B = X

i∈V

φ _i + β( | K | − 1)

^(2.3.18)

This upper bound requirs one bus to ollet all the prots froom every node. All prots

are representedbythe rst halfof equation(

2.3.18

^{) and ifonly onebus isusedthena prot}

of

β( | K | − 1)

^{isolleted fromthe unusedbuses.}

Relaxations to travel time

The upperbound in (2.3.18) isthe samefor allvalues of

M

^{.Letus nowinorporate}

M

^into

the upperbound.Itisknownthattravelingfurtherthan

M

^{fromthedepotis}impossible.Let us nowdene

V _M

^{asthesetofallnodesloserthan}

M

^{to thedepot.Thenewupperboundis}

X

i∈V M

φ _i + β( | K | − 1)

^(2.3.19)

1

This upper bound, equation (

2.3.19

^{) does not allow prot outside the radius of maximum}

routelength.Allprotwithinthatradius,ofmaximumroutelength,isolletedwithasingle

bus.

2.4 Review of Relevant Problems

The bus route problem fouses on routes that make there waythrough a number of pik up

points before nallystopping at thelast point, knownas thedepot. Thisis similarto awell

knownproblemalledthetravellingsalesman problemor TSP.

2.4.1 TSP

TSP tries to ndthe optimal, shortest,route from a soure through a number ofnodes and

bak to the soure. A travelling salesman leaving from New York and visiting all the major

ities on theeastost,of the USA,hasto ndthe bestrouteto travel andthenreturn home

again, hene the nametravelling salesman problem.

This problemis, perhaps,thebestknownproblemin operations researh.For this problema

binary matrix isdened,

x ij

^.

x _ij =

1

^{Ifone travels fromnode}

i

^tonode

j

0

^{Ifone doesnot travelfromnode}

i

^{to node}

j

Also a ost,

c _ij

^{, is dened. This is the ost of travelling from node}

i

^{to node}

j

^{. The set of}

nodesis

V

^and

A

^{isthe setof all ars.A model, asdened inWosley [15 ℄is:}

min

X

i∈V

X

j∈V

c _ij x _ij

^(2.4.1)

s.t.

P

j:j6=i x _ij = 1 ∀ i ∈ V

^(2.4.2)

P

i:i6=j x _ij = 1 ∀ j ∈ V

^(2.4.3)

P

i∈S

P

j / ∈S x _ij ≥ 1

^for

S ⊂ V

^,

S 6 = ∅

^(2.4.4)

x ij ∈ { 0, 1 } ∀ i ∈ V, ∀ j ∈ V

^(2.4.5)

c _ij ≥ 0 ∀ i ∈ V, ∀ j ∈ V

^(2.4.6)

Constraints (2.4.2) and (2.4.3)ensure thatevery node isboth entered and exited. The most

ompliated onstraint is (2.4.4) for it is a sub tour elimination onstraint. The number of

sub tour elimination onstraints raises dramatily withthe number of nodesassigned to the

problem.

ThenumberofpossiblesolutionsforTSP,with

n

^nodes,is

(n − 1)!

^{.Halfthatforthesymmetri}

problem. The TSPproblemis NP-hard[6℄ Wosley[15 ℄ denes NP-hardinthefollwoing way:

"NP is a lass of deision problems with the property that: for any instane for wihthe an-

swerisYES thereisa"short"(polynomial)proof oftheYES."HeuristissuhasLagrangian

heuristi and meta heuristis, suh as tabu searh, areoften used to solve TSP. The largest

nd thesolution utting plain and branh-and-ut proesses were usedand it took almost a

yearto ndthe nalsolution [6℄.

Asan beseen thereareertainsimilarities between thetravelling salesman problemand

thebusrouteproblem. Althoughinthelatteritisnotneessarytostopatall pointsbutthat

is thease withTSP.Therefore inthebus routeproblem one mustdetermine whih pik up

pointsareimportant andwhiharenot.A variationofthetravellingsalesmanproblemalled

theprieolleting travelling salesmanproblem, PCTSP, dealswiththis problem.

2.4.2 PCTSP

In PCTSP, eah node is assigned a prize, or prot, gained when the node is visited. Not all

nodes have to be visitedinPCTSP but a penaltyis paidfor every node skipped. AsinTSP

V

^{istheset ofall nodes.}

Name Desription

x _ij

^{Is equallto 1 ifthe path between}

i

^and

j

^{is usedotherwiseit is0.}

y i

^{A binarynumberequal to 1ifnode}

i

^{isvisitedelse itis 0}

γ _i

^{Penalty to be paidifnode}

i

^{isnot visited.}

p _i

^{Prize gained fromvisiting node}

i

^.

c ij

^{Costof travelling from}

i

^to

j

^.

B

^{A minimum amount ofolleted prizes.}

ThePCTSP problem aspresented 2

inDell'Amio[8 ℄:

min

X

i∈V

X

j∈V \i

c _ij x _ij + X

i∈V

γ _i (1 − y _i )

^(2.4.7)

s.t.

P

j∈V \i x _ij = y _i ∀ i ∈ V

^(2.4.8)

P

i∈V \j x _ij = y _j ∀ j ∈ V

^(2.4.9)

y ₁ = 1

^(2.4.10)

P

i∈V p i y j ≥ B ∀ j ∈ V

^(2.4.11)

P

i∈S

P

j∈V \S x _ij ≥ y _h ∀ h ∈ V \ 1

^and

∀ S ⊂ V : 1 ∈ S, h ∈ V \ S

^(2.4.12)

x _ij ∈ { 0, 1 } ∀ i ∈ N, ∀ j ∈ N

^(2.4.13)

y _i ∈ { 0, 1 } ∀ i ∈ N

^(2.4.14)

(2.4.15)

Constraints(2.4.8)and(2.4.9)ensurethatifanodeisentereditisalsoexited.Constraint

(2.4.10) foresthedepottobeinluded intheyle.In(2.4.11)aertainamountofprizeshas

tobe gathered,a goalisdened, and(2.4.12) isa sub tourelimination onstraint.

PCTSP was introdued by Balas and Martin in onnetion with operations of a steel

rollingmill.A variant ofPCTSP istheprotable tourproblem, PTP. WhenaPTP modelis

2

SimilarmathematialpresentationswerepresentedinBalas[1 ℄andDell'Amio[9 ℄,butaslightlydierent

onstruted itisessentiallythesameasPCTSPexept(2.4.10)and (2.4.11)areremoved and

γ _i = 0

^{for all}

i ∈ V

^[9℄.

ManymethodshavebeenusedtosolvePCTSPforexampleLagrangian heuristi[8℄orhybrid

algorithms [4 ℄.

Inomparison thebusrouteproblemandPCTSP aresimilarbut PCTSPonlyallowsasingle

route to visit pik up points. The problempresented by ALCANan have up to ve routes.

A wellknowprobleminoperationsresearhdealswithmultipleroutes,thatproblemisalled

thevehilerouting problemor VRP.

2.4.3 Vehile Routing Problem

Alloating more than one route to a number of nodes, is generally alledthe vehile routing

problem.

Name Desription

x ^k _i,j

^{Is equal to one ifroute}

k

^{travels from}

i

^to

j

^{and 0otherwise.}

γ _i

^{Penalty to be paidifnode}

i

^{isnot visited.}

p i

^{Prize gained fromvisiting node}

i

^.

c _ij

^{Costof travelling from}

i

^to

j

^.

B

^{A minimum amount ofolleted prizes.}

Routing problemsareharateristially diulttorepresent oniselyinoptimization models

[12 ℄.Theseproblemsareoftenveryusefulintherealworld.Amathematialmodelispresented

inthefollowing way:

min

X

k∈K

X

i∈V

X

j∈V

c _ij x ^k _ij

^(2.4.16)

Here

K

^{is the set of routes and}

| K | = N

^while

V

^{is the set of nodes were}

| V | = n

^{.In this}

problem thedepot is presented bysoure node,

i = 0

^{, anda sinknode,}

i = n

^.

P

i∈V x ^k _ih − P

j∈V x ^k _hj = 0 ∀ h ∈ V \ { 0, n }

^,

k ∈ K

^(2.4.17)

P

k∈K x ^k _ij = 1 ∀ i ∈ V \ { 0 } , ∀ j ∈ V \ { n }

^(2.4.18)

P

i∈V x ^k _i,n = 1 ∀ k ∈ K

^(2.4.19)

P

j∈V x ^k _0,j = 1 ∀ k ∈ K

^(2.4.20)

P

k∈K

P

i∈S

P

j∈V \S x _ij ≥ 1 ∀ S ⊂ V : 0 ∈ S, n ∈ S

^(2.4.21)

x ^k _ij ∈ { 0, 1 } ∀ i ∈ V, ∀ j ∈ V, k ∈ K

^(2.4.22)

Therst onstraint (2.4.17) ensuresthatall nodesentered areexited. The seond onstraint

(2.4.18) restrits more than one vehile visiting any node. Then onstraints (

2.4.19

^{) and}

(

2.4.20

^{) foreall routes to leave thesoure and enter thesink. The subtour} elimination on- straint ispresentedin(2.4.21)and lastly(2.4.22) gives

x ^k _ij

^{a binaryvalue.}

The VRP is widely used in the real world. The best example is the delivery of goods from

suppliers to ustomers. Herethe numberof vehiles and apaityof vehiles an be afator.

These problemsareusually solved witha tabu searh or otherheuristis.

The VRPallows theuse ofmorethan one routes butthemethodrequireseah routeto have

thesame point of origin,alledasoure.The routesvisit allpointsin

V

^{but mustend atthe}

same point theystartedfrom. When theroutes returnthesoure point issometimes alleda

sink,thisisthesameloationbutithastwonames,soureandsink.Inthebusrouteproblem

this is not the ase, a bus an start at any node and then make its way to the depot. A

variation of VRP uses the same priniple. That variation of VRP is alled the open vehile

routing problem or OVRP.

2.4.4 Open Vehile Routing Problem

OVRP, is similar to the vehile routing problem exept when drivers have visited all nodes

theydo notneedto returntothe depot.Thisissimilartothebus routeproblemexeptthere

the bus starts at the last node and makes its way bak to the depot. OVRP uses a set of

Hamiltonian pathswhileVRP usesa Hamiltonianyles[3 ℄.Both aHamiltonianyleand a

Hamiltonian path aredened in [14 ℄asfollows:

Before deningapathorayleawalkmustrstbedened.Gisagraph,awalk

in G is a sequene of nodes and ars. A path is a walk with no repeated nodes

and a trail is a walk within repeated ars. Note that all paths aretrails but not

all trailsare paths.A iruitis alosed trailbut not apath. Ayleis dened as

a iruit withatleast onear andhasone repeatednode is

node 1 = node n

^.

In OVRP the drivers start at the depot and then nish at the last ustomer node. There

are normally ertain onstraints applied to this problem. A vehile has usually a maximum

predetermined apaityand thisapaityannotbeexeededbythedemandoftheostumer

nodes, on the route. Other onstraints may also apply, for example a maximum number of

vehiles or the maximum length of any single route. The OVRP has not been asextensively

studied asVRP [3℄.It was rst mentioned, aording to [3 ℄, in1981 bySharge inan artile

dediated to the desription of realisti routing problems. The mathematial formulation of

OVRPis the same asforVRP exept

c _0j = 0

^,

∀ j ∈ V

^.

OVRP is used for a number of problems, for example the shool bus problem [17 ℄. In that

problem a routefor shoolbuses isdetermined. In[17℄ tabu searhis usedto solve theprob-

lem. Other algorithms, aording to [16 ℄, that have been used inlude: list-based threshold

aepting, BoneRoute meta heuristi and reord to reord travel heuristi. The last one is a

deterministivariant of simulated annealing.

TheOVRP hassimilaritieswiththebus routeproblem butit hastovisit allpointsin

V

^.

In the bus route problem one is allowed to skip some nodes, pik up points, but this is not

possibleintheOVRP.Thebusrouteproblemdoesnothavetovisitallnodes,itdoesnothave

to beginat the soure and ithasto hoose nodes for thereimportane.A problemsimilar to

2.4.5 Team Orienteering Problem

The teamorienteeringproblem, or TOP,isaombination of PCTSPand VRP.Theproblem

denes asetof nodes

V

^{,aset ofars}

A

^{anda setofroutes}

K

^,were

| V | = n

^and

| K | = N

^.In

this problemNroutes visit npoints,but doesnot haveto stopat allpoints;eah point hasa

servietime and a prot.

Name Desription

x ^k _i,j

^{The numberoftimes edge}

(i, j)

transverseswithvehile

k

^.

y _ik

^{A binarynumber equal to 1 ifnode}

i

^{is visited by route}

k

^{otherwise it is 0,}

i ∈ V

and

k ∈ K

d _ij

^{Asthe distane between two pointsand}

(i, j) ∈ A

^.

s _i

^{Servise time atevertex}

i

^,

i ∈ V

^.

p _i

^{The protreeived for node}

i

^,

i ∈ V

^.

M

^{The total duration ofeah tour.}

This isinmanywayssimilar tothebus route problemasaprotisneeded for everynode to

determine whih areto bevisited. TheTOP problemaspresentedin[13℄:

max

n−1

X

i=1 N

X

k=1

p _i y _ik

^(2.4.23)

s. t.

P _n−1

j=1

P _N

k=1 x ^k _0j = 2N

^(2.4.24)

P

i<j x ^k _ij + P

i>j x ^k _ij = 2y _ik ∀ j ∈ V \ { n } , k ∈ K

^(2.4.25)

P n−2

i=0

P

j>i d _ij x ^k _ij + P n−1

i=1 s _i y _ik ≤ M k ∈ K

^(2.4.26)

P N

k=1 y _ik ≤ 1 ∀ i ∈ V \ { 0, n }

^(2.4.27)

P

i,j∈U,i<j x ^k _ij ≤ | U | − 1 U ⊂ V \ { 0 } , n − 2 ≥ | U | ≥ 2, k ∈ K

^(2.4.28)

x ^k _ij ∈ { 0, 1, 2 } ∀ i ∈ V \ { 0, n } , j ∈ V, k ∈ K

^(2.4.29)

x ^k _0,j ∈ { 0, 1 } ∀ j ∈ V \ { n } , k ∈ K

^(2.4.30)

y _ik ∈ { 0, 1 } ∀ i ∈ N

^(2.4.31)

(2.4.32)

The rst onstraint (

2.4.24

^{) ensures that}

N

^{tours leave the soure node andthen return.To}

ensure onnetion of seleted nodes is (

2.4.25

^{) and (}

2.4.26

^{) limits the length of any single}

tour. Theonstraint(

2.4.27

^{) preventsmorethanoneroutegoingthroughasinglenode,other}

thanthedepot.Thesub-toureliminationonstraintis(

2.4.28

^{).Thelastthreeonstraintshow}

allowed values for thevariables.

The TOP lets one onstrut

N

^{routes through}

n − 1

^{nodesand the depot. Stopping at any}

single point gives apenalty or servietime. Thisouldfor examplebe usedfor routing teh-

niians to servieustomersat geographially distributedpositions.

The TOP is a NP-hard problem as it is a varition of the seletive traveling salesman prob-

and5-stepheuristi.AsinglerouteTOP,alledtheorienteeringproblemorseletivetraveling

salesman problem, has been solved with up to 500 nodes. This was done using branh-and-

bound and branh-and-ut [13 ℄. Some times TOP is referred to as multiple tour maximum

olletionproblem.Ofallthedierentproblems presentedtheTOPismostsimilartothebus

route problem.

2.5 Review of Methods

2.5.1 A Lagrangian heuristi for the Prize Colleting Travelling Salesman

Problem [8℄

An artile inspetinghowto solve PCTSP witha Lagrangian heuristi byM. Dell'Amio, F.

Maoli and A. Siomahen. A good introdution to the PCTSP. The underlying unstru-

tion of the bus route problem, presented in the report, is based in partially on the PCTSP

modelinthisartile.Theproblempresentedintheartileisminimized. Thereforetoassistin

determining the valitityof alulatedsolutions a lowerbound wasalso alulated.Thislower

bound is found in [9 ℄. A feasible solution is found by using Adding-Nodes Proedure where

two rules, R1 and R2,are ompared. From these omparisons R2 was shown to be better in

this instane. Thisfeasible solution isthendened asan upperbound asnofeasible soultion

with alower value objetive valueisknow.

To improve upon feasible solutions two methods are ombined. The rst was the so alled

Extensionphasetriestoimprovetheoverallprotoftheurrentyle.Theseondmethodwas

alledCollapsephaseand ittriestoremovethemost expensive node eahtime.Togetherthe

methodwasalledExtensionandCollapse.LastlyaLagragianheuristiwasdevelopedsothat

Extension and Collapse was applied ineah omputation of the Lagrangian multiplier. This

methodwasthenusedonafewomputationalexperiments.Theonlusionoftheexperiments

was that with inreased prot, that needs to be olleted, the omputational time required

inreased while the quality of thesolutions dereases. Thisquality of solutions was mesured

asthe ratiobetween upperbound and lowerbound.

2.5.2 Prie Colleting Travelling Salesman Problem [1℄

This is an artile by E. Balas onerning theprie olleting travelling salesman problem. It

wasBalas who, along with Martin, rst introdued thePCTSP. There is an introdution to

PCTSP initsrstsetion.Afterthisthe artilebeomesverymathematial andompliated.

Themain fousofthis artile is to disussthe strutural propertiesof thePCTSP polytope,

theonvex hull ofthe solutions tothePCTSP.

2.5.3 On Prize-ColletingTours andThe AsymmetriTravellingSalesman

Problem [9℄

An artile by M. Dell'Amio, F. Maoli and P. V

¨ a

^{rbrand. The artile ontains a short in-}

trodutionto PCTSP anda modelispresented.There isalso adenitionfor PTP,protable