Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Solving multiple travelling officers problem with population-based optimization algorithms

  • Real-world Optimization Problems and Meta-heuristics
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

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 is considerably improved in comparison with that of other implemented algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Akçay Y, Li H, Xu SH (2007) Greedy algorithm for the general multidimensional knapsack problem. Ann Oper Res 150(1):17

    MathSciNet  MATH  Google Scholar 

  2. Arain QA, Memon H, Memon I, Memon MH, Shaikh RA, Mangi FA (2017) Intelligent travel information platform based on location base services to predict user travel behavior from user-generated gps traces. Int J Comput Appl 39(3):155–168

    Google Scholar 

  3. Ayala D, Wolfson O, Dasgupta B, Lin J, Xu B (2018) Spatio-temporal matching for urban transportation applications. ACM Trans Spat Algorithms Syst (TSAS) 3(4):11

    Google Scholar 

  4. Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6(2):154–160

    MATH  Google Scholar 

  5. Beheshti Z, Shamsuddin SMH (2013) A review of population-based meta-heuristic algorithms. Int J Adv Soft Comput Appl 5(1):1–35

    Google Scholar 

  6. Benson JP, O’Donovan T, O’Sullivan P, Roedig U, Sreenan C, Barton J, Murphy A, O’Flynn B (2006) Car-park management using wireless sensor networks. In: Proceedings 2006 31st IEEE conference on local computer networks. IEEE, pp 588–595

  7. Bonyadi MR, Azghadi MR, Shah-Hosseini H (2008) Population-based optimization algorithms for solving the travelling salesman problem. In: Traveling salesman problem. IntechOpen

  8. Burke EK, Cowling PI, Keuthen R (2001) Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In: Workshops on applications of evolutionary computation. Springer, Berlin, pp 203–212

  9. Carlton WB, Barnes JW (1996) Solving the traveling-salesman problem with time windows using tabu search. IIE Trans 28(8):617–629

    Google Scholar 

  10. Carrabs F, Cordeau JF, Laporte G (2007) Variable neighborhood search for the pickup and delivery traveling salesman problem with lifo loading. INFORMS J Comput 19(4):618–632

    MathSciNet  MATH  Google Scholar 

  11. Carter AE, Ragsdale CT (2006) A new approach to solving the multiple traveling salesperson problem using genetic algorithms. Eur J Oper Res 175(1):246–257

    MathSciNet  MATH  Google Scholar 

  12. Chatterjee S, Carrera C, Lynch LA (1996) Genetic algorithms and traveling salesman problems. Eur J Oper Res 93(3):490–510

    MATH  Google Scholar 

  13. Dorigo M, Birattari M (2011) Ant colony optimization. In: Encyclopedia of machine learning. Springer, Berlin, pp 36–39

  14. Ezugwu AES, Adewumi AO (2017) Discrete symbiotic organisms search algorithm for travelling salesman problem. Exp Syst Appl 87:70–78

    Google Scholar 

  15. Fiechter CN (1994) A parallel tabu search algorithm for large traveling salesman problems. Discrete Appl Math 51(3):243–267

    MathSciNet  MATH  Google Scholar 

  16. Gandomi AH, Yang XS, Alavi AH (2013) Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems. Eng Comput 29(1):17–35

    Google Scholar 

  17. Gendreau M, Potvin JY (2005) Metaheuristics in combinatorial optimization. Ann Oper Res 140(1):189–213

    MathSciNet  MATH  Google Scholar 

  18. Geng X, Chen Z, Yang W, Shi D, Zhao K (2011) Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl Soft Comput 11(4):3680–3689

    Google Scholar 

  19. Glover F, Laguna M (1998) Tabu search. In: Handbook of combinatorial optimization. Springer, Berlin, pp 2093–2229

  20. Google: Google matrix api. https://developers.google.com/maps/documentation/distance-matrix/intro. Accessed 11 Aug 2018

  21. Guo Q, Wolfson O (2018) Probabilistic spatio-temporal resource search. GeoInformatica 22(1):75–103

    Google Scholar 

  22. Hemmelmayr VC, Doerner KF, Hartl RF (2009) A variable neighborhood search heuristic for periodic routing problems. Eur J Oper Res 195(3):791–802

    MATH  Google Scholar 

  23. Jiang Zb, Yang Q (2016) A discrete fruit fly optimization algorithm for the traveling salesman problem. PLoS ONE 11(11):e0165804

    Google Scholar 

  24. Junjie P, Dingwei W (2006) An ant colony optimization algorithm for multiple travelling salesman problem. In: First international conference on innovative computing, information and control, 2006. ICICIC’06, vol 1. IEEE, pp 210–213

  25. Kennedy J (2010) Particle swarm optimization. Encyclopedia of machine learning. pp 760–766

  26. Kıran MS, İşcan H, Gündüz M (2013) The analysis of discrete artificial bee colony algorithm with neighborhood operator on traveling salesman problem. Neural Comput Appl 23(1):9–21

    Google Scholar 

  27. Malek M, Guruswamy M, Pandya M, Owens H (1989) Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Ann Oper Res 21(1):59–84

    MathSciNet  MATH  Google Scholar 

  28. Marinakis Y, Marinaki M (2010) A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. Comput Oper Res 37(3):432–442

    MathSciNet  MATH  Google Scholar 

  29. Melbourne CC. Car parking data. https://data.melbourne.vic.gov.au/Transport-Movement/On-street-Car-Parking-Sensor-Data-2016/dj7e-rdx9. Accessed 11 Aug 2018

  30. Melbourne CC. On-street parking data. https://www.melbourne.vic.gov.au/about-council/governance-transparency/open-data/Pages/on-street-parking-data.aspx. Accessed 11 Aug 2018

  31. Memon I, Chen L, Majid A, Lv M, Hussain I, Chen G (2015) Travel recommendation using geo-tagged photos in social media for tourist. Wireless Pers Commun 80(4):1347–1362

    Google Scholar 

  32. Meng T, Pan QK (2017) An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem. Appl Soft Comput 50:79–93

    Google Scholar 

  33. Mirjalili S (2016) Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems. Neural Comput Appl 27(4):1053–1073

    Google Scholar 

  34. Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51–67

    Google Scholar 

  35. Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61

    Google Scholar 

  36. Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097–1100

    MathSciNet  MATH  Google Scholar 

  37. Mohamad A, Zain AM, Bazin NEN, Udin A (2013) Cuckoo search algorithm for optimization problems-a literature review. Appl Mech Mater 421:502–506

    Google Scholar 

  38. Moon C, Kim J, Choi G, Seo Y (2002) An efficient genetic algorithm for the traveling salesman problem with precedence constraints. Eur J Oper Res 140(3):606–617

    MathSciNet  MATH  Google Scholar 

  39. Osaba E, Del Ser J, Sadollah A, Bilbao MN, Camacho D (2018) A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem. Appl Soft Comput 71:277–290

    Google Scholar 

  40. Osaba E, Yang XS, Diaz F, Lopez-Garcia P, Carballedo R (2016) An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intell 48:59–71

    Google Scholar 

  41. Ouaarab A, Ahiod B, Yang XS (2014) Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl 24(7–8):1659–1669

    Google Scholar 

  42. Ouaarab A, Ahiod B, Yang XS (2015) Random-key cuckoo search for the travelling salesman problem. Soft Comput 19(4):1099–1106

    Google Scholar 

  43. Pavlyukevich I (2007) Lévy flights, non-local search and simulated annealing. J Comput Phys 226(2):1830–1844

    MathSciNet  MATH  Google Scholar 

  44. Ribas I, Companys R, Tort-Martorell X (2011) An iterated greedy algorithm for the flowshop scheduling problem with blocking. Omega 39(3):293–301

    Google Scholar 

  45. Shao W, Salim FD, Gu T, Dinh NT, Chan J (2018) Traveling officer problem: Managing car parking violations efficiently using sensor data. IEEE Internet Things J 5(2):802–810

    Google Scholar 

  46. Shao W, Salim FD, Song A, Bouguettaya A (2016) Clustering big spatiotemporal-interval data. IEEE Trans Big Data 2(3):190–203

    Google Scholar 

  47. Shao W, Zhang Y, Guo B, Qin K, Chan J, Salim FD (2018) Parking availability prediction with long short term memory model. In: International conference on green, pervasive, and cloud computing. Springer, Berlin, pp 124–137

  48. Shi Y, Eberhart RC (2001) Fuzzy adaptive particle swarm optimization. In: Proceedings of the 2001 congress on evolutionary computation (IEEE Cat. No. 01TH8546), vol 1. IEEE, pp 101–106

  49. Snyder LV, Daskin MS (2006) A random-key genetic algorithm for the generalized traveling salesman problem. Eur J Oper Res 174(1):38–53

    MathSciNet  MATH  Google Scholar 

  50. Song CH, Lee K, Lee WD (2003) Extended simulated annealing for augmented TSP and multi-salesmen TSP. In: Proceedings of the international joint conference on neural networks, 2003, vol 3. IEEE, pp 2340–2343

  51. Wang KP, Huang L, Zhou CG, Pang W (2003) Particle swarm optimization for traveling salesman problem. In: International conference on machine learning and cybernetics, 2003, vol 3. IEEE, pp 1583–1585

  52. Wang L, Zheng Xl, Wang Sy (2013) A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowl-Based Syst 48:17–23

    Google Scholar 

  53. Wong LP, Low MYH, Chong CS (2008) A bee colony optimization algorithm for traveling salesman problem. In: Second Asia international conference on modeling & simulation, 2008. AICMS 08. IEEE, pp 818–823

  54. Yang XS, Deb S (2009) Cuckoo search via lévy flights. In: World congress on nature & biologically inspired computing, NaBIC 2009. IEEE, pp 210–214

  55. Yuan S, Skinner B, Huang S, Liu D (2013) A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. Eur J Oper Res 228(1):72–82

    MathSciNet  MATH  Google Scholar 

  56. Zanella A, Bui N, Castellani A, Vangelista L, Zorzi M (2014) Internet of things for smart cities. IEEE Internet Things J 1(1):22–32

    Google Scholar 

  57. Zhou H, Song M, Pedrycz W (2018) A comparative study of improved ga and pso in solving multiple traveling salesmen problem. Appl Soft Comput 64:564–580

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. RMIT University, 124 La Trobe St, Melbourne, VIC, 3000, Australia

    Kyle K. Qin, Wei Shao, Yongli Ren, Jeffrey Chan & Flora D. Salim

Authors
  1. Kyle K. Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei Shao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yongli Ren
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jeffrey Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Flora D. Salim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kyle K. Qin.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Qin, K.K., Shao, W., Ren, Y. et al. Solving multiple travelling officers problem with population-based optimization algorithms. Neural Comput & Applic 32, 12033–12059 (2020). https://doi.org/10.1007/s00521-019-04237-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-019-04237-2

Keywords

Search

Navigation