Solving multiple travelling officers problem with population-basedoptimization algorithms

Publication Year: 2020 Publication Type : JournalArticle

Abstract:


The Travelling Officer Problem (TOP) is a graph-based orienteering problem for modelling the patrolling routines of a parking officer monitoring an area. Recently, a spatiotemporal probabilistic model was built for TOP to estimate the leaving probability of parking cars, and relevant algorithms were applied to search for the optimal path for a parking officer to maximize the collection of parking fines from cars in violation. However, there are often multiple parking officers on duty during business hours in the central business district, which provides us with the opportunities to introduce cooperation among officers for efficient car parking management. The Multiple Travelling Officers Problem (MTOP) is a more complex problem than the TOP because multiple officers are involved simultaneously in paths construction. In this study, the MTOP is formulated and new components are established for solving the problem. One essential component called the Leader-based Random Keys Encoding Scheme (LERK) is developed for the representation of possible solutions. Then, Cuckoo Search (CS), Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) are implemented using the proposed components and compared with other state-of-the-art GA and PSO using other solution encoding schemes to solve MTOP. In addition, two greedy selection algorithms are adopted as baselines. The performance of the algorithms is evaluated with real parking sensors data and different metrics. The experimental results show that the performance of CS and GA using LERK are considerably improved in comparison to that of other implemented algorithms.


BibTex:

@article{DBLP:journals/nca/QinSRCS20,
    author = {Kyle Kai Qin and Wei Shao and Yongli Ren and Jeffrey Chan and Flora D. Salim},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    biburl = {https://dblp.org/rec/journals/nca/QinSRCS20.bib},
    doi = {10.1007/s00521-019-04237-2},
    journal = {Neural Computing and Applications},
    number = {16},
    pages = {12033--12059},
    timestamp = {Wed, 05 Aug 2020 01:00:00 +0200},
    title = {Solving multiple travelling officers problem with population-based optimization algorithms},
    url = {https://doi.org/10.1007/s00521-019-04237-2},
    volume = {32},
    year = {2020}
}

Cite:

Related Publications

RUP: Large Room Utilisation Prediction with carbon dioxide sensor
Type : JournalArticle
Show More
A Scalable Room Occupancy Prediction with Transferable Time Series Decomposition of CO 2 Sensor Data
Type : JournalArticle
Show More
Topical Event Detection on Twitter
Type : ConferenceProceeding
Show More

© 2021 Flora Salim - CRUISE Research Group.