Linköping studies in science and technology Dissertations, No. 1107 Multi-year maintenance optimisation for paved public roads – segment based modelling and price-directive decomposition Per-Åke Andersson Department of Mathematics Linköping 2007 Multi-year maintenance optimisation for paved public roads – – segment based modelling and price-directive decomposition © 2007 Per-Åke Andersson Matematiska institutionen Linköpings universitet SE-581 83 Linköping, Sweden [email protected] Linköping studies in science and technology. Dissertations, No. 1107 ISBN: 978-91-85831-73-9 ISSN 0345-7524 Printed by LiU-Tryck, Linköping 2007 Acknowledgements This project has been administered by CDU, KTH (Centre for research and education in operation and maintenance of infrastructure, Royal institute of technology) and performed at MAI, LiU (Department of mathematics, Linköping university), with financial support from VV (Swedish road administration), Vinnova, VTI (Swedish national road and transport research institute), Örebro university and my wife Lena. I thank • professor em. Sven Erlander, MAI, for giving me a 1st chance and for introducing me into optimisation and traffic, professor em. Gunnar Aronsson, MAI, for a 2nd and my main supervisor professor em. Per Olov Lindberg for a 3rd chance and for his patience and the constructive-minded reading, • my other supervisors Torbjörn Larsson, MAI, for his wit at meetings, and Lars-Göran Wågberg, VTI, • the other members of the project consultative group Hans Cedermark / Håkan Westerlund, CDU, for their commitment, Jaro Potucek / Arne Johansson, VV – and Carl-Gösta Enocksson and Johan Lang, VV, both also crucial members of the modelling and validation group, • Jörgen Blomvall, MAI, for making my parallelisation runs on the Penta PC-cluster possible, • NSC for granting me 48 000 CPU-hours in all on the Monolith PC-cluster, • all personnel at MAI, especially the optimisation group, for their kindness and service- mindedness, and Tommy Elfving, MAI, for his encouragement. Linköping May, 2007 Per-Åke Andersson iii iv Abstract The thesis deals with the generation of cost efficient maintenance plans for paved roads, based on database information about the current surface conditions and functional models for costs and state changes, partly developed in co- operation with Vägverket (VV, Swedish Road Administration). The intended use is in a stage of budgeting and planning, before concrete project information is available. Unlike the up to now used models, individual maintenance plans can be formulated for each segment (a homogeneous road section as to the cur- rent pavement state and paving history), in continuous state and works spaces. By using Lagrangean relaxation optimisation techniques, the special benefit/- cost-ratio constraints that VV puts on each maintenance project can be naturally mastered by dual prices for the budget constraints. The number of segments competing for budget resources is usually large. Data from VV Vägdatabank (SRA Road Database) in county Värmland were used, comprising around 9000 road segments. Due to the large data amount the implemented programs rely on parallel computation. During the thesis work, access to the PC-cluster Monolith at NSC was granted. In order to reduce optimisation run times, model & method development was needed. By aggregating the road segments into road classes, good initial values of the dual prices were achieved. By adding new state dimensions, the use of the Markov property could be motivated. By developing a special residual value routine, the explicitly considered time period could be reduced. At solving the dual subproblem special attention was paid to the discretization effects in the dynamic programming approach. One type of study is on a sub-network, e.g. a road. Validation studies were performed on road 63 in Värmland – with promising but not satisfactory results (see below). A special model for co-ordinated maintenance considers the fine-tuned cost effects of simultaneous maintenance of contiguous road segments. The other main type of study is for a whole network. Several method types have been applied, both for solving the relaxed optimisation problems and for generating maintenance plans that fit to the budgets. For a decent discretization, the run time for the whole Värmland network is less than 80 CPU-hrs.A posterior primal heuristics reduces the demands for parallel processing to a small PC-cluster.The thesis further studies the effects of redistributing budget means, as well as turning to a trans- parent stochastic model – both showing modest deviations from the basic model. Optimisation results for Värmland indicate budget levels around 40% of the actual Värmland budget as sufficient. However, important cost triggers are missing in this first model round, e.g., certain functional performance (safety), all environmental performance (noise etc.) and structural performance (e.g. bearing capacity, only modelled by an age measure). For increased credibility of PMS in general and optimisation in particular, the discrepancies should be further analysed and lead to improvements as to condition monitoring, state effect & cost modelling and mathematical modelling & implementation. v vi Sammanfattning I avhandlingen studeras hur kostnadseffektiva underhålls- (uh-)planer för belagd väg kan genereras, på basis av information om aktuellt vägytetillstånd och funktionella modeller för kostnads- och tillståndsförändringar, delvis utvecklade i samarbete med svenska Vägverket (VV). Tilltänkt användning är på strategisk och programnivå, innan mer detaljerad objektinformation finns att tillgå. Till skillnad från hittills använda modeller, så genereras individuella uh-planer för varje vägsegment (en homogen vägsträcka vad gäller aktuellt beläggnings- tillstånd och beläggningshistorik), i kontinuerliga tillstånds- och åtgärdsrum. Genom användning av Lagrangerelaxerande optimeringsteknik, så kan de speciella nytto/kostnads-kvot-villkor som VV ålägger varje uh-objekt naturligen hanteras med dualpriser för budgetvillkoren. Antalet vägsegment som konkurrerar om budgetmedlen är vanligtvis stort. Data från VV:s Vägdatabank för Värmland har använts, omfattande ca 9000 vägsegment. Genom den stora datamängden har datorprogrammen implementerats för parallellbearbetning. Under avhandlingsarbetet har projektet beviljats tillgång till Monolith PC- klustret vid NSC. För att kunna reducera optimeringskörtiderna har modell- och metodutveckling varit nödvändig. Genom att aggregera vägsegmenten till vägklasser har goda startvärden på dualpriserna erhållits. Genom utvecklingen av en speciell restvärdesrutin har den explicit behandlade tidsperioden kunnat reduceras. Vid lösandet av det duala subproblemet har speciell uppmärksamhet ägnats åt de diskretiseringseffekter som uppstår i metoden dynamisk program- mering. En typ av tillämpning avser ett delvägnät, exempelvis en väg. Valid- eringsstudier har genomförts på väg 63 i Värmland – med lovande men inte tillfredsställande resultat (se nedan). En speciell modell för samordnat uh beaktar stordriftsfördelarna vid samtidig åtgärd på en hel vägsträcka. Den andra huvudtypen av studier gäller ett helt nätverk. Flera metodtyper har tillämpats, både för att lösa de relaxerade optimeringsproblemen och för att generera uh- planer som uppfyller budgetvillkoren. För en anständig diskretisering är körtiderna för hela Värmland mindre än 80 CPU-timmar. Genom en a posteriori primal heuristik reduceras kraven på parallellbearbetning till ett litet PC-kluster. Avhandlingen studerar vidare effekterna av omfördelade budgetmedel samt en övergång till en transparent, stokastisk modell – vilka båda visar små avvikelser från basmodellen. Optimeringsresultaten för Värmland indikerar att budgetnivåer på ca 40% av Värmlands verkliga uh-budget är tillräckliga. Dock saknas viktiga kostnads- drivande faktorer i denna första modellomgång, exempelvis vissa funktionella prestanda (säkerhet), all miljöpåverkande prestanda (buller etc.) och strukturell prestanda (ex.vis bärighet, som enbart modelleras via ett åldersmått). För ökad tilltro till PMS i allmänhet och optimering i synnerhet, bör avvikelserna analyseras ytterligare och leda till förbättringar vad gäller tillståndsmätning, tillståndseffekt- & kostnadsmodellering samt matematisk modellering & implementering. vii viii Contents Contents 1 Introduction 1.1 Maintenance problem 1 1.2 Optimisation 3 1.2.1 Simplified optimisation model 4 1.2.2 Lagrangean relaxation 4 1.2.3 Dual optimisation by subgradient methods 6 1.2.4 Dual optimisation by the Dantzig-Wolfe method 7 1.2.5 Subproblem solving by dynamic programming 9 1.3 Program system 11 1.4 Earlier studies 15 1.4.1 Systems based on Markov decision processes (MDPs) 15 1.4.2 The Arizona model 16 1.4.3 The NOS-based PM-systems in Kansas, Alaska and Finland 17 1.4.4 Swedish PMS-based optimisation 18 1.4.5 PMS-systems in Denmark and Norway 18 1.4.6 Other optimisation techniques 18 1.4.7 Decision support systems and integration 19 1.4.8 Survey articles and implementation experience 20 1.5 Study aim and outline 21 1.5.1 Aim of study 21 1.5.2 Outline of the thesis 21 2 Initial study 2.1 Introduction 23 2.2 Model 24 2.2.1 Problem description 24 2.2.2 Mathematical formulation 25 2.3 Method 26 2.3.1 Main procedure 26 2.3.2 Subproblem characteristics 26 2.3.3 Start routine 28 2.3.4 Primal Feasibility Heuristics 29 2.4 Application: PMS- and HIPS-based data 29 2.4.1 Data conversion to OPM 30 2.4.2 Discretization and interpolation experiments 31 2.4.3 Some results 33 2.5 Outlook 36 3 Main study: Problem description 3.1 Road data 37 3.1.1 Road segments 37 3.1.2 Road classes 38 3.1.3 Road constants and pavement data 38 ix Contents 3.2 Pavement state 39 3.2.1 State variables 39 3.2.2 State limits 40 3.2.3 IRI-value limits 40 3.2.4 Rut depth limits 40 3.2.5 Age limits 40 3.3 Maintenance 41 3.3.1 Works types 41 3.3.2 Works extent: Layer thickness 41 3.3.3 Restrictions on layer thickness 42 3.4 Traffic effects and costs 42 3.4.1 Travel time cost 42 3.4.2 Vehicle operating cost 42 3.5 Maintenance effects (state transitions) 43 3.5.1 IRI-value immediately after a major maintenance operation, IRI 43 after 3.5.2 IRI-deterioration rate after a major maintenance operation, ΔIRI 43 after 3.5.3 Rut depth immediately after a major maintenance operation, RD 44 after 3.5.4 Deterioration rate of rut depth after a major maint. operation, ΔRD 44 after 3.5.5 Age immediately after a major maintenance operation, Age 44 after 3.5.6 Updated IRI-value, rut depth and age after one year of routine maint. 45 3.6 Maintenance costs 45 3.6.1 Fixed major maintenance costs 46 3.6.2 Variable major maintenance costs 46 3.6.3 Cost of routine maintenance 47 3.7 General data 47 3.7.1 Interest rate 47 3.7.2 Capital scarcity factor 47 3.8 Stochastic submodels 48 3.8.1 Interpolation of state limits 48 3.8.2 Stochastic state transitions 50 3.9 Discussion 52 3.9.1 Limitation 52 3.9.2 Homogeneous segments 53 3.9.3 Robustness 53 3.9.4 Data corrections 54 4 Main study: Basic model and subnet results 4.1 Model 56 4.1.1 Return rate restrictions 56 4.1.2 Segment oriented problem 57 4.1.3 Road class oriented problem 58 4.2 Method 60 4.2.1 Dual optimisation 60 4.2.2 Dual subproblem solving 62 4.2.3 Primal heuristics 64 x