Skip to main content
SpringerLink
Log in

An analysis of generalised heuristics for vehicle routing and personnel rostering problems

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

The present study investigates the performance of heuristics while solving problems with routing and rostering characteristics. The target problems include scheduling and routing home care, security and maintenance personnel. In analysing the behaviour of the heuristics and determining the requirements for solving the aforementioned problems, the winning hyper-heuristic from the first International Cross-domain Heuristic Search Challenge (CHeSC 2011) is employed. The completely new application of a hyper-heuristic as an analysis tool offers promising perspectives for supporting dedicated heuristic development. The experimental results reveal that different low-level heuristics perform better on different problems and that their performance varies during a search process. The following characteristics affect the performance of the heuristics: the planning horizon, the number of activities and lastly the number of resources. The body of this paper details both these characteristics and also discusses the required features for embedding in an algorithm to solve problems particularly with a vehicle routing component.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9

Similar content being viewed by others

References

  • Akjiratikarl C, Yenradee P and Drake P (2007). PSO-based algorithm for home care worker scheduling in the UK. Computers and Industrial Engineering 53 (4): 559–583.

    Article  Google Scholar 

  • Bai R and Kendall G (2005). An investigation of automated planograms using a simulated annealing based hyper-heuristics. In: Ibaraki T, Nonobe K and Yagiura M (eds). Meta-heuristics: Progress as Real Problem Solvers, Selected Papers from the 5th Metaheuristics International Conference (MIC'03). Springer: Kyoto, Japan, pp 87–108.

    Chapter  Google Scholar 

  • Begur S, Miller D and Weaver J (1997). An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces 27 (4): 35–48.

    Article  Google Scholar 

  • Bertels S and Fahle T (2006). A hybrid setup for a hybrid scenario: Combining heuristics for the home health care problem. Computers & Operations Research 33 (10): 2866–2890.

    Article  Google Scholar 

  • Bräysy O and Gendreau M (2005). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science 39 (1): 104–118.

    Article  Google Scholar 

  • Burke E, Kendall G and Soubeiga E (2003). A tabu-search hyper-heuristic for timetabling and rostering. Journal of Heuristics 9 (3): 451–470.

    Article  Google Scholar 

  • Burke E, De Causmaecker P, Vanden Berghe G and Van Landeghem H (2004). The state of the art of nurse rostering. Journal of Scheduling 7 (6): 441–499.

    Article  Google Scholar 

  • Burke E, Petrovic S and Qu R (2006). Case-based heuristic selection for timetabling problems. Journal of Scheduling 9 (2): 115–132.

    Article  Google Scholar 

  • Burke E, Kendall G, Mısır M and Özcan E (2012). Monte carlo hyperheuristics for examination timetabling. Annals of Operations Research 196 (1): 73–90.

    Article  Google Scholar 

  • Burke E et al (2013). Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society 64 (12): 1695–1724.

    Article  Google Scholar 

  • Calvo RW and Cordone R (2003). A heuristic approach to the overnight security service problem. Computers & Operations Research 30 (9): 1269–1287.

    Article  Google Scholar 

  • Cordeau J-F, Desaulniers G, Desrosiers J, Solomon M and Soumis F (2002). VRP with time windows. In: Toth P and Vigo D (eds). The Vehicle Routing Problem. SIAM Publishing: Philadelphia, PA, pp 157–193.

    Chapter  Google Scholar 

  • Cowling P, Kendall G and Soubeiga E (2001). A hyperheuristic approach to scheduling a sales summit. In: Burke EK and Erben W (eds). Selected Papers from the 3rd International Conference on Practice and Theory of Automated Timetabling (PATAT'00), Vol. 2079 of LNCS Springer-Verlag: London, UK, pp 176–190.

    Google Scholar 

  • Crama Y, Moonen L, Spieksma F and Talloen E (2007). The tool switching problem revisited. European Journal of Operational Research 182 (2): 952–957.

    Article  Google Scholar 

  • Easton K, Nemhauser G and Trick M (2001). The traveling tournament problem description and benchmarks. In: Walsh T (ed). Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming (CP'01), Vol. 2239 of LNCS Springer: London, UK, pp 580–584.

    Google Scholar 

  • Ernst A, Jiang H, Krishnamoorthy M and Sier D (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research 153 (1): 3–27.

    Article  Google Scholar 

  • Eveborn P, Flisberg P and Ronnqvist M (2006). Laps Care—an operational system for staff planning of home care. European Journal of Operational Research 171 (3): 962–976.

    Article  Google Scholar 

  • Günther M and Nissen V (2012). Application of particle swarm optimization to the british telecom workforce scheduling problem. In: Kjenstad D, Nordlander TE, Riise A, McCollum B and Burke E (eds). Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT'12), Son, Norway, pp 242–256.

  • Justesen T and Rasmussen M (2008). The home care crew scheduling problem. Master’s thesis, University of Denmark and University of Copenhagen.

  • Kovacs AA, Parragh SN, Doerner KF and Hartl RF (2012). Adaptive large neighborhood search for service technician routing and scheduling problems. Journal of Scheduling 15 (5): 579–600.

    Article  Google Scholar 

  • Krumke SO, Rambau J and Torres LM (2002). Online-dispatching of automobile service units. Technical Report 02-44, ZIB, Berlin.

  • Mısır M (2012). Intelligent hyper-heuristics: A tool for solving generic optimisation problems. PhD thesis, Department of Computer Science, KU Leuven.

  • Mısır M, Verbeeck K, De Causmaecker P and Vanden Berghe G (2010). Hyper-heuristics with a dynamic heuristic set for the home care scheduling problem. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC'10). IEEE: Barcelona, Spain, pp 2875–2882.

  • Mısır M, Smet P, Verbeeck K and Vanden Berghe G (2011a). Security personnel routing and rostering: A hyper-heuristic approach. In: Gunalay Y and Kadipasaoglu S (eds). Proceedings of the 3rd International Conference on Applied Operational Research (ICAOR'11), Vol. 3 of LNMS, Istanbul, Turkey, pp 193–205.

  • Mısır M, Verbeeck K, De Causmaecker P and Vanden Berghe G (2011b). A new hyper-heuristic implementation in HyFlex: A study on generality. In: Fowler J, Kendall G and McCollum B (eds). Proceedings of the 5th Multidisciplinary International Scheduling Conference: Theory & Applications (MISTA’11). IEEE: Phoenix/Arizona, USA, pp 374–393.

    Google Scholar 

  • Mısır M, Wauters T, Verbeeck K and Vanden Berghe G (2011c). A hyper-heuristic with learning automata for the traveling tournament problem. In: Voss S and Caserta M (eds). Metaheuristics: Intelligent Decision Making, the 8th Metaheuristics International Conference—Post Conference Volume. Operations Research/Computer Science Interfaces Series. Springer.

  • Mısır M, Verbeeck K, De Causmaecker P and Vanden Berghe G (2012). An intelligent hyper-heuristic framework for CHeSC 2011. In: Hamadi Y and Schoenauer M (eds). Proceedings of the 6th Learning and Intelligent OptimizatioN Conference (LION’12), Vol. 7219 of LNCS Springer: New York.

    Google Scholar 

  • Mısır M, Verbeeck K, De Causmaecker P and Vanden Berghe G (2013). A new hyper-heuristic as a general problem solver: An implementation in HyFlex. Journal of Scheduling 16 (3): 291–311.

    Article  Google Scholar 

  • Nareyek A (2003). Choosing search heuristics by non-stationary reinforcement learning. In: Resende MGC and Pinho de Sousa J (eds). Metaheuristics: Computer Decision-Making. Kluwer Academic Publishers: Dordrecht, the Netherlands, pp 523–544.

    Chapter  Google Scholar 

  • Özcan E, Bykov Y, Birben M and Burke E (2009). Examination timetabling using late acceptance hyper-heuristics. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC'09). IEEE: Trondheim, Norway, pp 997–1004.

  • Özcan E, Mısır M, Ochoa G and Burke E (2010). A reinforcement learning—great-deluge hyper-heuristic for examination timetabling. International Journal of Applied Metaheuristic Computing 1 (1): 39–59.

    Article  Google Scholar 

  • Potvin J-Y and Rousseau J-M (1995). An exchange heuristic for routeing problems with time windows. Journal of the Operational Research Society 46 (12): 1433–1446.

    Article  Google Scholar 

  • Thathachar M and Sastry P (2004). Networks of Learning Automata: Techniques for Online Stochastic Optimization. Kluwer Academic Publishers: Dordrecht, the Netherlands.

    Book  Google Scholar 

  • Trautsamwieser A and Hirsch P (2011). Optimization of daily scheduling for home health care services. Journal of Applied Operational Research 3 (3): 124–136.

    Google Scholar 

  • Verstichel J and Vanden Berghe G (2009). A late acceptance algorithm for the lock scheduling problem. In: Voss S, Pahl J and Schwarze S (eds). Logistik Management. Springer: Heidelberg, pp 457–478.

    Chapter  Google Scholar 

  • Willemse EJ and Joubert JW (2012). Applying min-max k postmen problems to the routing of security guards. Journal of the Operational Research Society 63 (2): 245–260.

    Article  Google Scholar 

Download references

Acknowledgements

This research was carried out within the IWT 090549 project.

Author information

Authors and Affiliations

  1. Department of Computer Science, KU Leuven, CODeS & iMinds-ITEC, Gent, Belgium

    Mustafa Mısır, Pieter Smet & Greet Vanden Berghe

Authors
  1. Mustafa Mısır
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pieter Smet
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Greet Vanden Berghe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mustafa Mısır.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mısır, M., Smet, P. & Vanden Berghe, G. An analysis of generalised heuristics for vehicle routing and personnel rostering problems. J Oper Res Soc 66, 858–870 (2015). https://doi.org/10.1057/jors.2014.11

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2014.11

Keywords

Search

Navigation