A network flow model for clustering segments and minimizing total maintenance and rehabilitation cost

I-Lin Wang, Yi Chang James Tsai, Feng Li

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

Because of shrinking budgets, transportation agencies are facing severe challenges in the preservation of deteriorating pavements. There is an urgent need to develop a methodology that minimizes maintenance and rehabilitation (M&R) cost. To minimize total network M&R cost of clustering pavement segments, we propose an integer programming model similar to an uncapacitated facility location problem (UFLP) that clusters pavement segments contiguously. Based on the properties of contiguous clustered pavement segments, we have transformed the clustering problem into an equivalent network flow problem in which each possible clustering corresponds to a path in the proposed acyclic network model. Our proposed shortest-path algorithm gives an optimal clustering of segments that can be calculated in a time polynomial to the number of segments. Computational experiments indicate our proposed network model and algorithm can efficiently deal with real-world spatial clustering problems.

Original languageEnglish
Pages (from-to)593-601
Number of pages9
JournalComputers and Industrial Engineering
Volume60
Issue number4
DOIs
Publication statusPublished - 2011 May 1

Fingerprint

Pavements
Patient rehabilitation
Costs
Integer programming
Polynomials
Experiments

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Engineering(all)

Cite this

@article{59b4b0b93f1e48dfa96a5a4b6827cc00,
title = "A network flow model for clustering segments and minimizing total maintenance and rehabilitation cost",
abstract = "Because of shrinking budgets, transportation agencies are facing severe challenges in the preservation of deteriorating pavements. There is an urgent need to develop a methodology that minimizes maintenance and rehabilitation (M&R) cost. To minimize total network M&R cost of clustering pavement segments, we propose an integer programming model similar to an uncapacitated facility location problem (UFLP) that clusters pavement segments contiguously. Based on the properties of contiguous clustered pavement segments, we have transformed the clustering problem into an equivalent network flow problem in which each possible clustering corresponds to a path in the proposed acyclic network model. Our proposed shortest-path algorithm gives an optimal clustering of segments that can be calculated in a time polynomial to the number of segments. Computational experiments indicate our proposed network model and algorithm can efficiently deal with real-world spatial clustering problems.",
author = "I-Lin Wang and Tsai, {Yi Chang James} and Feng Li",
year = "2011",
month = "5",
day = "1",
doi = "10.1016/j.cie.2011.01.001",
language = "English",
volume = "60",
pages = "593--601",
journal = "Computers and Industrial Engineering",
issn = "0360-8352",
publisher = "Elsevier Limited",
number = "4",

}

A network flow model for clustering segments and minimizing total maintenance and rehabilitation cost. / Wang, I-Lin; Tsai, Yi Chang James; Li, Feng.

In: Computers and Industrial Engineering, Vol. 60, No. 4, 01.05.2011, p. 593-601.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A network flow model for clustering segments and minimizing total maintenance and rehabilitation cost

AU - Wang, I-Lin

AU - Tsai, Yi Chang James

AU - Li, Feng

PY - 2011/5/1

Y1 - 2011/5/1

N2 - Because of shrinking budgets, transportation agencies are facing severe challenges in the preservation of deteriorating pavements. There is an urgent need to develop a methodology that minimizes maintenance and rehabilitation (M&R) cost. To minimize total network M&R cost of clustering pavement segments, we propose an integer programming model similar to an uncapacitated facility location problem (UFLP) that clusters pavement segments contiguously. Based on the properties of contiguous clustered pavement segments, we have transformed the clustering problem into an equivalent network flow problem in which each possible clustering corresponds to a path in the proposed acyclic network model. Our proposed shortest-path algorithm gives an optimal clustering of segments that can be calculated in a time polynomial to the number of segments. Computational experiments indicate our proposed network model and algorithm can efficiently deal with real-world spatial clustering problems.

AB - Because of shrinking budgets, transportation agencies are facing severe challenges in the preservation of deteriorating pavements. There is an urgent need to develop a methodology that minimizes maintenance and rehabilitation (M&R) cost. To minimize total network M&R cost of clustering pavement segments, we propose an integer programming model similar to an uncapacitated facility location problem (UFLP) that clusters pavement segments contiguously. Based on the properties of contiguous clustered pavement segments, we have transformed the clustering problem into an equivalent network flow problem in which each possible clustering corresponds to a path in the proposed acyclic network model. Our proposed shortest-path algorithm gives an optimal clustering of segments that can be calculated in a time polynomial to the number of segments. Computational experiments indicate our proposed network model and algorithm can efficiently deal with real-world spatial clustering problems.

UR - http://www.scopus.com/inward/record.url?scp=79952627856&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952627856&partnerID=8YFLogxK

U2 - 10.1016/j.cie.2011.01.001

DO - 10.1016/j.cie.2011.01.001

M3 - Article

VL - 60

SP - 593

EP - 601

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

SN - 0360-8352

IS - 4

ER -