{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T02:59:05Z","timestamp":1769914745093,"version":"3.49.0"},"reference-count":67,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Croatian Science Foundation","award":["IP-2019-04-4333"],"award-info":[{"award-number":["IP-2019-04-4333"]}]},{"name":"Croatian Science Foundation","award":["KK.01.2.1.01.0120"],"award-info":[{"award-number":["KK.01.2.1.01.0120"]}]},{"name":"European Regional Development Fund","award":["IP-2019-04-4333"],"award-info":[{"award-number":["IP-2019-04-4333"]}]},{"name":"European Regional Development Fund","award":["KK.01.2.1.01.0120"],"award-info":[{"award-number":["KK.01.2.1.01.0120"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Many real-world applications of the vehicle routing problem (VRP) are arising today, which range from physical resource planning to virtual resource management in the cloud computing domain. A common trait of these applications is usually the large scale size of problem instances, which require fast algorithms to generate solutions of acceptable quality. The basis for many VRP approaches is a heuristic which builds a candidate solution that may subsequently be improved by a local search procedure. Since there are many variants of the basic VRP model, specialised algorithms must be devised that take into account specific constraints and user-defined objective measures. Another factor is that the scheduling process may be carried out in dynamic conditions, where future information may be uncertain or unavailable or may be subject to change. When all of this is considered, there is a need for customised heuristics, devised for a specific problem variant, that could be used in highly dynamic environments. In this paper, we use genetic programming (GP) to evolve a suitable dispatching rule to build solutions for different objectives and classes of VRP problems, applicable in both dynamic and stochastic conditions. The results show great potential, since this method may be used for different problem classes and user-defined performance objectives.<\/jats:p>","DOI":"10.3390\/a16060285","type":"journal-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T01:33:54Z","timestamp":1685669634000},"page":"285","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Evolving Dispatching Rules for Dynamic Vehicle Routing with Genetic Programming"],"prefix":"10.3390","volume":"16","author":[{"given":"Domagoj","family":"Jakobovi\u0107","sequence":"first","affiliation":[{"name":"Faculty of Electrical Engineering and Computing, University of Zagreb, HR-10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marko","family":"\u0110urasevi\u0107","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering and Computing, University of Zagreb, HR-10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karla","family":"Brki\u0107","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering and Computing, University of Zagreb, HR-10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juraj","family":"Fosin","sequence":"additional","affiliation":[{"name":"Mireo d.d., HR-10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ton\u010di","family":"Cari\u0107","sequence":"additional","affiliation":[{"name":"Faculty of Transport and Traffic Sciences, University of Zagreb, HR-10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2649-9236","authenticated-orcid":false,"given":"Davor","family":"Davidovi\u0107","sequence":"additional","affiliation":[{"name":"Ru\u0111er Bo\u0161kovi\u0107 Institute, HR-10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The Truck Dispatching Problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/net.3230110211","article-title":"Complexity of vehicle routing and scheduling problems","volume":"11","author":"Lenstra","year":"1981","journal-title":"Networks"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2012.08.015","article-title":"A review of dynamic vehicle routing problems","volume":"225","author":"Pillac","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/s11036-008-0101-1","article-title":"A Stochastic and Dynamic Vehicle Routing Problem with Time Windows and Customer Impatience","volume":"14","author":"Pavone","year":"2008","journal-title":"Mob. Netw. Appl."},{"key":"ref_5","unstructured":"Poli, R., Langdon, W.B., and McPhee, N.F. (2023, May 29). Available online: http:\/\/gpbib.cs.ucl.ac.uk\/gp-html\/poli08_fieldguide.html."},{"key":"ref_6","unstructured":"Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., \u00d6zcan, E., and Woodward, J.R. (2010). International Series in Operations Research & Management Science, Springer."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1695","DOI":"10.1057\/jors.2013.71","article-title":"Hyper-heuristics: A survey of the state of the art","volume":"64","author":"Burke","year":"2013","journal-title":"J. Oper. Res. Soc."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1162\/EVCO_a_00131","article-title":"Hyper-heuristic Evolution of Dispatching Rules: A Comparison of Rule Representations","volume":"23","author":"Branke","year":"2015","journal-title":"Evol. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2781","DOI":"10.1016\/j.asoc.2012.03.065","article-title":"Evolving priority scheduling heuristics with genetic programming","volume":"12","year":"2012","journal-title":"Appl. Soft Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.asoc.2016.07.025","article-title":"Adaptive scheduling on unrelated machines with genetic programming","volume":"48","year":"2016","journal-title":"Appl. Soft Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/TEVC.2015.2429314","article-title":"Automated Design of Production Scheduling Heuristics: A Review","volume":"20","author":"Branke","year":"2016","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1007\/s13198-021-01468-2","article-title":"Efficient road traffic anti-collision warning system based on fuzzy nonlinear programming","volume":"13","author":"Peng","year":"2021","journal-title":"Int. J. Syst. Assur. Eng. Manag."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1007\/s00542-020-05132-w","article-title":"Optimizing compliant gripper mechanism design by employing an effective bi-algorithm: Fuzzy logic and ANFIS","volume":"27","author":"Nguyen","year":"2021","journal-title":"Microsyst. Technol."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"101649","DOI":"10.1016\/j.jocs.2022.101649","article-title":"Selection of dispatching rules evolved by genetic programming in dynamic unrelated machines scheduling based on problem characteristics","volume":"61","year":"2022","journal-title":"J. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2002). The Vehicle Routing Problem, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898718515"},{"key":"ref_16","first-page":"66","article-title":"A Survey on the Vehicle Routing Problem and Its Variants","volume":"4","author":"Kumar","year":"2012","journal-title":"Intell. Inf. Manag."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1016\/j.eswa.2013.07.107","article-title":"Survey of Green Vehicle Routing Problem: Past and future trends","volume":"41","author":"Lin","year":"2014","journal-title":"Expert Syst. Appl."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1080\/00207543.2015.1043403","article-title":"A survey on dynamic and stochastic vehicle routing problems","volume":"54","author":"Ritzinger","year":"2015","journal-title":"Int. J. Prod. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s10288-020-00433-2","article-title":"Vehicle routing problems over time: A survey","volume":"18","author":"Mor","year":"2020","journal-title":"4OR"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1287\/trsc.31.2.170","article-title":"A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows","volume":"31","author":"Taillard","year":"1997","journal-title":"Transp. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0377-2217(02)00486-1","article-title":"Local search with annealing-like restarts to solve the VRPTW","volume":"150","author":"Li","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1006\/jcph.1999.6413","article-title":"Record Breaking Optimization Results Using the Ruin and Recreate Principle","volume":"159","author":"Schrimpf","year":"2000","journal-title":"J. Comput. Phys."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1016\/j.cor.2003.11.017","article-title":"Active guided evolution strategies for large-scale vehicle routing problems with time windows","volume":"32","author":"Mester","year":"2005","journal-title":"Comput. Oper. Res."},{"key":"ref_24","unstructured":"Gambardella, L.M., Taillard, E., and Agazzi, G. (2023, May 29). Available online: https:\/\/people.idsia.ch\/~luca\/tr-idsia-06-99.pdf."},{"key":"ref_25","unstructured":"Gulic, M., Lucanin, D., and Skorin-Kapov, N. (2012, January 21\u201325). A two-phase vehicle based decomposition algorithm for large-scale capacitated vehicle routing with time windows. Proceedings of the 2012 35th International Convention MIPRO, Opatija, Croatia."},{"key":"ref_26","unstructured":"Bent, R., and Hentenryck, P.V. (2010). Principles and Practice of Constraint Programming\u2013CP 2010, Springer."},{"key":"ref_27","unstructured":"Gendreau, M., Potvin, J.Y., Br\u00e4umlaysy, O., Hasle, G., and L\u00f8kketangen, A. (2008). Operations Research\/Computer Science Interfaces, Springer."},{"key":"ref_28","unstructured":"S\u00e1nchez, F.F.S., Lazo, C.A.L., and Qui\u00f1\u00f3nez, F.Y.S. (2020). Novel Trends in the Traveling Salesman Problem, IntechOpen."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.cor.2019.01.002","article-title":"Knowledge-guided local search for the vehicle routing problem","volume":"105","author":"Arnold","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_30","unstructured":"Guli\u0107, M., and Jakobovi\u0107, D. (2013, January 19\u201324). Evolution of vehicle routing problem heuristics with genetic programming. Proceedings of the 2013 36th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), Opatia, Croatia."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Mlejnek, J., and Kubalik, J. (2013, January 15\u201319). Evolutionary hyperheuristic for capacitated vehicle routing problem. Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, Lisbon, Portugal.","DOI":"10.1145\/2464576.2464684"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/trsc.33.4.381","article-title":"Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching","volume":"33","author":"Gendreau","year":"1999","journal-title":"Transp. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0377-2217(02)00147-9","article-title":"Vehicle dispatching with time-dependent travel times","volume":"144","author":"Ichoua","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1287\/opre.1040.0124","article-title":"Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers","volume":"52","author":"Bent","year":"2004","journal-title":"Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1287\/trsc.1050.0114","article-title":"Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching","volume":"40","author":"Ichoua","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_36","unstructured":"van Hemert, J.I., and Poutr\u00e9, J.A.L. (2004). Lecture Notes in Computer Science, Springer."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1016\/j.ijpe.2007.10.018","article-title":"Dynamic routing model and solution methods for fleet management with mobile technologies","volume":"113","author":"Cheung","year":"2008","journal-title":"Int. J. Prod. Econ."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s10878-005-4922-6","article-title":"Ant Colony System for a Dynamic Vehicle Routing Problem","volume":"10","author":"Montemanni","year":"2005","journal-title":"J. Comb. Optim."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s11721-007-0005-x","article-title":"Ant colony optimization for real-world vehicle routing problems","volume":"1","author":"Rizzoli","year":"2007","journal-title":"Swarm Intell."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Necula, R., Breaban, M., and Raschip, M. (2017, January 5\u20138). Tackling Dynamic Vehicle Routing Problem with Time Windows by means of ant colony system. Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC), Donostia, Spain.","DOI":"10.1109\/CEC.2017.7969606"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1007\/s10732-010-9126-2","article-title":"DVRP: A hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic","volume":"16","author":"Garrido","year":"2010","journal-title":"J. Heuristics"},{"key":"ref_42","unstructured":"Saint-Guillain, M., Deville, Y., and Solnon, C. (2015). Integration of AI and OR Techniques in Constraint Programming, Springer International Publishing."},{"key":"ref_43","first-page":"93","article-title":"Optimizing agents with genetic programming: An evaluation of hyper-heuristics in dynamic real-time logistics","volume":"19","author":"Branke","year":"2017","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/j.eswa.2018.06.053","article-title":"A survey of dispatching rules for the dynamic unrelated machines environment","volume":"113","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_46","unstructured":"Jakobovi\u0107, D., and Budin, L. (2006). Lecture Notes in Computer Science, Springer."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/0377-2217(95)00357-6","article-title":"Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation","volume":"90","author":"Kolisch","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"106637","DOI":"10.1016\/j.asoc.2020.106637","article-title":"Comparison of schedule generation schemes for designing dispatching rules with genetic programming in the unrelated machines environment","volume":"96","year":"2020","journal-title":"Appl. Soft Comput."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Pinedo, M.L. (2012). Scheduling, Springer.","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"ref_50","unstructured":"Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10710-010-9112-3","article-title":"Human-competitive results produced by genetic programming","volume":"11","author":"Koza","year":"2010","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_52","unstructured":"Golden, B.L., Wasil, E.A., Kelly, J.P., and Chao, I.M. (1998). Fleet Management and Logistics, Springer."},{"key":"ref_53","unstructured":"Gehring, H. (1999). Proceedings of the EUROGEN99, Springer."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Deza, M.M., and Deza, E. (2013). Encyclopedia of Distances, Springer.","DOI":"10.1007\/978-3-642-30958-8"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.cor.2012.06.008","article-title":"Vehicle routing problem with stochastic travel times including soft time windows and service costs","volume":"40","author":"Dellaert","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1720","DOI":"10.1016\/j.ejor.2005.10.010","article-title":"A goal programming approach to vehicle routing problems with soft time windows","volume":"177","author":"Calvete","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_57","first-page":"9","article-title":"Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment","volume":"19","year":"2017","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1162\/evco_a_00273","article-title":"Genetic Programming with Delayed Routing for Multiobjective Dynamic Flexible Job Shop Scheduling","volume":"29","author":"Xu","year":"2021","journal-title":"Evol. Comput."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Zhang, F., Mei, Y., Nguyen, S., and Zhang, M. (2022). Multitask Multiobjective Genetic Programming for Automated Scheduling Heuristic Learning in Dynamic Flexible Job-Shop Scheduling. IEEE Trans. Cybern., 1\u201314.","DOI":"10.1109\/TCYB.2022.3196887"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1287\/opre.1120.1127","article-title":"Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits","volume":"61","author":"Goodson","year":"2013","journal-title":"Oper. Res."},{"key":"ref_61","first-page":"5043","article-title":"Automatic design of dispatching rules for static scheduling conditions","volume":"33","year":"2020","journal-title":"Neural Comput. Appl."},{"key":"ref_62","doi-asserted-by":"crossref","unstructured":"Miller, J.F. (2011). Cartesian Genetic Programming, Springer.","DOI":"10.1007\/978-3-642-17310-3"},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s00170-010-2518-5","article-title":"Evolving scheduling rules with gene expression programming for dynamic single-machine scheduling problems","volume":"50","author":"Nie","year":"2010","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_64","unstructured":"Moraglio, A., Krawiec, K., and Johnson, C.G. (2012). Lecture Notes in Computer Science, Springer."},{"key":"ref_65","first-page":"1069","article-title":"Dimensionally Aware Genetic Programming","volume":"Volume 2","author":"Keijzer","year":"1999","journal-title":"Gecco-99, Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, FL, USA, 13\u201319 July 1999"},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"22886","DOI":"10.1109\/ACCESS.2022.3151346","article-title":"A Comparative Study of Dispatching Rule Representations in Evolutionary Algorithms for the Dynamic Unrelated Machines Environment","volume":"10","author":"Planinic","year":"2022","journal-title":"IEEE Access"},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"106096","DOI":"10.1016\/j.engappai.2023.106096","article-title":"Collaboration methods for ensembles of dispatching rules for the dynamic unrelated machines environment","volume":"122","year":"2023","journal-title":"Eng. Appl. Artif. Intell."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/6\/285\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:47:02Z","timestamp":1760125622000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/6\/285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,1]]},"references-count":67,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["a16060285"],"URL":"https:\/\/doi.org\/10.3390\/a16060285","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,1]]}}}