Transit stop inspection and maintenance scheduling: A GPU accelerated metaheuristics approach

Authors

Nikolaos Ath. Kallioras
Konstantinos Kepaptsoglou
Nikos D. Lagaros

Document Type

Journal Article

Publication Date

2015

Subject Area

infrastructure - maintainance, infrastructure - stop, mode - bus, place - europe

Keywords

Nature inspired search algorithms, Transit stop inspection and maintenance problem, Districting and scheduling problems, Harmony search, Ant colony optimization, GPGPU computing

Abstract

Bus stops are integral elements of a transit system and as such, their efficient inspection and maintenance is required, for proper and attractive transit operations. Nevertheless, spatial dispersion and the extensive number of bus stops, even for mid-size transit systems, complicates scheduling of inspection and maintenance tasks. In this context, the problem of scheduling transit stop inspection and maintenance activities (TSIMP) by a two-stage optimization approach, is formulated and discussed. In particular, the first stage involves districting of the bus stop locations into areas of responsibility for different inspection and maintenance crews (IMCs), while in the second stage, determination of the sequence of bus stops to be visited by an IMC is modelled as a vehicle routing problem. Given the complexity of proposed optimization models, advanced versions of different metaheuristic algorithms (Harmony Search and Ant Colony Optimization) are exploited and assessed as possible options for solving these models. Furthermore, two variants of ACO are implemented herein; one implemented into a CPU parallel computing environment along with an accelerated one by means of general-purpose graphics processing unit (GPGPU) computing. The model and algorithms are applied to the Athens (Greece) bus system, whose extensive number of transit stops (over 7500) offers a real-world test bed for assessing the potential of the proposed modelling approach and solution algorithms. As it was shown for the test example examined, both algorithms managed to achieve optimized solutions for the problem at hand while there were fund robust with respect to their algorithmic parameters. Furthermore, the use of graphics processing units (GPU) managed to reduce of computational time required.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part C Home Page:

http://www.sciencedirect.com/science/journal/0968090X

Recommended Citation

Kallioras, N.A., Kepaptsoglou, K., & Lagaros, N.D. (2015). Transit stop inspection and maintenance scheduling: A GPU accelerated metaheuristics approach. Transportation Research Part C: Emerging Technologies, Vol. 55, pp. 246-260.