{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T05:22:01Z","timestamp":1773465721445,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T00:00:00Z","timestamp":1711756800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T00:00:00Z","timestamp":1711756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62202314,62203310"],"award-info":[{"award-number":["62202314,62203310"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62202314,62203310"],"award-info":[{"award-number":["62202314,62203310"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of Guangdong Province of China","award":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"],"award-info":[{"award-number":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"]}]},{"name":"Natural Science Foundation of Guangdong Province of China","award":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"],"award-info":[{"award-number":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"]}]},{"name":"Natural Science Foundation of Guangdong Province of China","award":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"],"award-info":[{"award-number":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"]}]},{"name":"Natural Science Foundation of Guangdong Province of China","award":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"],"award-info":[{"award-number":["2018A0303130055, 2018A030310664, 2022A1515011447,2022A1515010417"]}]},{"name":"Key Project of Shenzhen Municipality","award":["No.JSGG20211029095545002"],"award-info":[{"award-number":["No.JSGG20211029095545002"]}]},{"name":"School-enterprise Collaborative Innovation Project of SZIIT","award":["XQ2021"],"award-info":[{"award-number":["XQ2021"]}]},{"name":"Characteristic Innovation Projects of Department of Education of Guangdong Province","award":["2021KTSCX281"],"award-info":[{"award-number":["2021KTSCX281"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Memetic Comp."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The dynamic pickup and delivery problem (DPDP) is essential in supply chain management and logistics. In this study, we consider a real-world DPDP from daily delivery scenarios of a company. In the problem, orders are generated randomly and released periodically. The orders should be completed as soon as possible to minimize the cost. We propose a novel memetic algorithm (MA) to address this problem. The proposed MA consists of a genetic algorithm and a local search strategy that periodically solves a static pickup and delivery problem when new orders are released. We have conducted extensive experiments on 64 real-world instances to assess the performance of our method. Three state-of-the-art algorithms are chosen as the baseline algorithms. Experimental results demonstrate the effectiveness of the MA in solving the real-world DPDP.<\/jats:p>","DOI":"10.1007\/s12293-024-00407-5","type":"journal-article","created":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T10:01:41Z","timestamp":1711792901000},"page":"203-217","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A memetic algorithm for a real-world dynamic pickup and delivery problem"],"prefix":"10.1007","volume":"16","author":[{"given":"Ying","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lingjing","family":"Kong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijun","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunxia","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,30]]},"reference":[{"issue":"3","key":"407_CR1","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1109\/TETCI.2018.2886585","volume":"3","author":"J Ma\u0144dziuk","year":"2019","unstructured":"Ma\u0144dziuk J (2019) New shades of the vehicle routing problem: emerging problem formulations and computational intelligence solution methods. IEEE Trans Emerg Topics Comput Intell 3(3):230\u2013244","journal-title":"IEEE Trans Emerg Topics Comput Intell"},{"issue":"4","key":"407_CR2","doi-asserted-by":"publisher","first-page":"5253","DOI":"10.1109\/JSYST.2019.2959664","volume":"14","author":"Y Zhou","year":"2020","unstructured":"Zhou Y, Kong L, Cai Y, Wu Z, Liu S, Hong J, Wu K (2020) A decomposition-based local search for large-scale many-objective vehicle routing problems with simultaneous delivery and pickup and time windows. IEEE Syst J 14(4):5253\u20135264","journal-title":"IEEE Syst J"},{"key":"407_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.106242","volume":"40","author":"R Elshaer","year":"2020","unstructured":"Elshaer R, Awad H (2020) A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Comput Ind Eng 40:106242","journal-title":"Comput Ind Eng"},{"key":"407_CR4","doi-asserted-by":"crossref","unstructured":"Battarra M, Cordeau JF, Iori M (2014) Chapter 6: Pickup-and-delivery problems for goods transportation. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications, 2nd edn. vol 6. MOS-SIAM Series on Optimization, USA, pp 161\u2013191","DOI":"10.1137\/1.9781611973594.ch6"},{"issue":"2","key":"407_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/net.3230110211","volume":"11","author":"JK Lenstra","year":"1981","unstructured":"Lenstra JK, Kan AHGR (1981) Complexity of vehicle routing and scheduling problems. Networks 11(2):221\u2013227","journal-title":"Networks"},{"issue":"3","key":"407_CR6","first-page":"185","volume":"35","author":"M Abdel-Basset","year":"2018","unstructured":"Abdel-Basset M, Abdel-Fatah L, Sangaiah AK (2018) Metaheuristic algorithms: a comprehensive review. Comput Intell Multimed Big Data Cloud Eng Appl 35(3):185\u2013231","journal-title":"Comput Intell Multimed Big Data Cloud Eng Appl"},{"key":"407_CR7","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1016\/j.swevo.2018.10.015","volume":"44","author":"NR Sabar","year":"2019","unstructured":"Sabar NR, Bhaskar A, Chung E, Turky A, Song A (2019) A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm Evol Comput 44:1018\u20131027","journal-title":"Swarm Evol Comput"},{"issue":"6","key":"407_CR8","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1109\/TETCI.2020.3022372","volume":"5","author":"J-J Wang","year":"2021","unstructured":"Wang J-J, Wang L (2021) A bi-population cooperative memetic algorithm for distributed hybrid flow-shop scheduling. IEEE Trans Emerg Top Comput Intell 5(6):947\u2013961","journal-title":"IEEE Trans Emerg Top Comput Intell"},{"key":"407_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s12293-019-00291-4","volume":"12","author":"AV Eremeev","year":"2020","unstructured":"Eremeev AV, Kovalenko YV (2020) A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem. Memet Comput 12:23\u201336","journal-title":"Memet Comput"},{"key":"407_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2022.101047","volume":"70","author":"E Osaba","year":"2022","unstructured":"Osaba E, Del Ser J, Cotta C, Moscato P (2022) Editorial: Memetic computing: accelerating optimization heuristics with problem-dependent local search methods. Swarm Evol Comput 70:101047","journal-title":"Swarm Evol Comput"},{"key":"407_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2022.101182","volume":"75","author":"J Cai","year":"2022","unstructured":"Cai J, Zhu Q, Lin Q (2022) Variable neighborhood search for a new practical dynamic pickup and delivery problem. Swarm Evol Comput 75:101182","journal-title":"Swarm Evol Comput"},{"key":"407_CR12","unstructured":"Ma Y, Hao X, Hao J, Lu J, Liu X, Tong X, Yuan M, Li Z, Tang J, Meng Z (2021) A hierarchical reinforcement learning based optimization framework for large-scale dynamic pickup and delivery problems. In: 35th conference on neural information processing systems (NeurIPS 2021)"},{"issue":"1","key":"407_CR13","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci 6(1):80\u201391","journal-title":"Manag Sci"},{"issue":"1","key":"407_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/net.21628","volume":"67","author":"HN Psaraftis","year":"2016","unstructured":"Psaraftis HN, Wen M, Kontovas CA (2016) Dynamic vehicle routing problems: three decades and counting. Networks 67(1):3\u201331","journal-title":"Networks"},{"key":"407_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2021.107604","volume":"160","author":"BHO Rios","year":"2021","unstructured":"Rios BHO, Xavier EC, Miyazawa FK, Amorim P, Curcio E, Santos MJ (2021) Recent dynamic vehicle routing problems: a survey. Comput Ind Eng 160:107604","journal-title":"Comput Ind Eng"},{"key":"407_CR16","doi-asserted-by":"crossref","unstructured":"Ozbaygin G, Savelsbergh M (2019) An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations. Transp Res Part B Methodol 128:207\u2013235","DOI":"10.1016\/j.trb.2019.08.004"},{"issue":"3","key":"407_CR17","first-page":"165","volume":"46","author":"V Pureza","year":"2008","unstructured":"Pureza V, Laporte G (2008) Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows. Inf Syst Oper Res (INFOR) 46(3):165\u2013176","journal-title":"Inf Syst Oper Res (INFOR)"},{"issue":"3","key":"407_CR18","first-page":"1","volume":"10","author":"M Ulmer","year":"2017","unstructured":"Ulmer M (2017) Delivery deadlines in same-day delivery. Logist Res 10(3):1\u201315","journal-title":"Logist Res"},{"issue":"4","key":"407_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/net.21855","volume":"72","author":"MW Ulmer","year":"2018","unstructured":"Ulmer MW, Thomas BW (2018) Same-day delivery with heterogeneous fleets of drones and vehicles. Networks 72(4):1\u201331","journal-title":"Networks"},{"issue":"1","key":"407_CR20","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1287\/trsc.2020.1000","volume":"55","author":"MW Ulmer","year":"2020","unstructured":"Ulmer MW, Thomas BW, Campbell AM, Woyak N (2020) The restaurant meal delivery problem: dynamic pickup and delivery with deadlines and random ready times. Transp Sci 55(1):75\u2013100","journal-title":"Transp Sci"},{"issue":"8","key":"407_CR21","doi-asserted-by":"publisher","first-page":"3583","DOI":"10.1109\/TKDE.2020.3027200","volume":"34","author":"Y Xu","year":"2022","unstructured":"Xu Y, Tong Y, Shi Y, Tao Q, Xu K, Li W (2022) An efficient insertion operator in dynamic ridesharing services. IEEE Trans Knowl Data Eng 34(8):3583\u20133596","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"7","key":"407_CR22","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/j.trb.2003.09.002","volume":"38","author":"S Mitrovi\u0107-Mini\u0107","year":"2004","unstructured":"Mitrovi\u0107-Mini\u0107 S, Laporte G (2004) Waiting strategies for the dynamic pickup and delivery problem with time windows. Transp Res Part B Methodol 38(7):635\u2013655","journal-title":"Transp Res Part B Methodol"},{"key":"407_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.asoc.2017.01.047","volume":"55","author":"AMFM AbdAllah","year":"2017","unstructured":"AbdAllah AMFM, Essam DL, Sarker RA (2017) On solving periodic re-optimization dynamic vehicle routing problems. Appl Soft Comput 55:1\u201312","journal-title":"Appl Soft Comput"},{"key":"407_CR24","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/j.cie.2018.02.014","volume":"117","author":"C Fikar","year":"2018","unstructured":"Fikar C (2018) A decision support system to investigate food losses in e-grocery deliveries. Comput Ind Eng 117:282\u2013290","journal-title":"Comput Ind Eng"},{"issue":"1","key":"407_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113959","volume":"165","author":"H Park","year":"2021","unstructured":"Park H, Son D, Koo B, Jeong B (2021) Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm. Expert Syst Appl 165(1):113959","journal-title":"Expert Syst Appl"},{"key":"407_CR26","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s10951-020-00650-x","volume":"23","author":"F Karami","year":"2020","unstructured":"Karami F, Vancroonenburg W, Berghe GV (2020) A periodic optimization approach to dynamic pickup and delivery problems with time windows. J Sched 23:711\u2013731","journal-title":"J Sched"},{"key":"407_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105144","volume":"127","author":"C Archetti","year":"2021","unstructured":"Archetti C, Guerriero F, Macrina G (2021) The online vehicle routing problem with occasional drivers. Comput Oper Res 127:105144","journal-title":"Comput Oper Res"},{"key":"407_CR28","doi-asserted-by":"crossref","unstructured":"Xu X, Wei Z (2023) Dynamic pickup and delivery problem with transshipments and LIFO constraints. Comput Ind Eng 175:108835","DOI":"10.1016\/j.cie.2022.108835"},{"key":"407_CR29","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.swevo.2014.12.003","volume":"21","author":"J Euchi","year":"2015","unstructured":"Euchi J, Yassine A, Chabchoub H (2015) The dynamic vehicle routing problem: solution with hybrid metaheuristic approach. Swarm Evol Comput 21:41\u201353","journal-title":"Swarm Evol Comput"},{"key":"407_CR30","doi-asserted-by":"crossref","unstructured":"Necula R, Breaban M, Raschip M (2017) Tackling dynamic vehicle routing problem with time windows by means of ant colony system. In: IEEE Congress on evolutionary computation (CEC), p 17013934","DOI":"10.1109\/CEC.2017.7969606"},{"key":"407_CR31","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1016\/j.asoc.2016.06.032","volume":"48","author":"J Ma\u0144dziuk","year":"2016","unstructured":"Ma\u0144dziuk J, \u017bychowski A (2016) A memetic approach to vehicle routing problem with dynamic requests. Appl Soft Comput 48:522\u2013534","journal-title":"Appl Soft Comput"},{"key":"407_CR32","doi-asserted-by":"crossref","unstructured":"Berahhou A, Benadada Y (2020) Dynamic vehicle routing problem with simultaneous delivery and pickup: formulation and resolution. In: 2020 5th international conference on logistics operations management (GOL)","DOI":"10.1109\/GOL49479.2020.9314759"},{"key":"407_CR33","doi-asserted-by":"publisher","first-page":"2935","DOI":"10.1007\/s00500-020-05350-4","volume":"25","author":"OS da Silva J\u00fanior","year":"2021","unstructured":"da Silva J\u00fanior OS, Leal JE, Reimann M (2021) A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windows. Soft Comput 25:2935\u20132948","journal-title":"Soft Comput"},{"key":"407_CR34","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.106241","volume":"142","author":"B Peng","year":"2020","unstructured":"Peng B, Zhang Y, L\u00fc Z, Cheng TCE, Glover F (2020) A learning-based memetic algorithm for the multiple vehicle pickup and delivery problem with LIFO loading. Comput Ind Eng 142:106241","journal-title":"Comput Ind Eng"},{"key":"407_CR35","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2020.103890","volume":"95","author":"Y Lu","year":"2020","unstructured":"Lu Y, Benlic U, Wu Q (2020) An effective memetic algorithm for the generalized bike-sharing rebalancing problem. Eng Appl Artif Intell 95:103890","journal-title":"Eng Appl Artif Intell"},{"key":"407_CR36","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF00175354","volume":"4","author":"D Whitley","year":"1994","unstructured":"Whitley D (1994) A genetic algorithm tutorial. Stat Comput 4:65\u201385","journal-title":"Stat Comput"},{"key":"407_CR37","unstructured":"Hao J, Lu J, Li X, Tong X, Xiang X, Yuan M, Zhuo HH (2022) Introduction to the dynamic pickup and delivery problem benchmark\u2014ICAPS 2021 competition. arXiv:2202.01256"},{"key":"407_CR38","volume-title":"Orthogonal arrays: theory and applications","author":"AS Hedayat","year":"2012","unstructured":"Hedayat AS, Sloane NJA, Stufken J (2012) Orthogonal arrays: theory and applications. Springer, New York"},{"issue":"6","key":"407_CR39","doi-asserted-by":"publisher","first-page":"80","DOI":"10.2307\/3001968","volume":"1","author":"F Wilcoxon","year":"1945","unstructured":"Wilcoxon F (1945) Individual comparisons by ranking methods. Biometrics 1(6):80\u201383","journal-title":"Biometrics"},{"issue":"1","key":"407_CR40","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.swevo.2011.02.002","volume":"1","author":"J Derrac","year":"2011","unstructured":"Derrac J, Garc\u00eda S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3\u201318","journal-title":"Swarm Evol Comput"},{"key":"407_CR41","unstructured":"Lion D, Chiu A, Stumm M, Yuan D (2022) Investigating managed language runtime performance: why JavaScript and python are 8$$\\times $$ and 29$$\\times $$ slower than C++, yet java and go can be faster? In: Proceedings of the 2022 USENIX annual technical conference, pp 835\u2013851"},{"key":"407_CR42","doi-asserted-by":"crossref","unstructured":"Li X, Luo W, Yuan M, Wang J, Lu J, Wang J, L\u00fc J, Zeng J (2021) Learning to optimize industry-scale dynamic pickup and delivery problems. In: 2021 IEEE 37th international conference on data engineering (ICDE)","DOI":"10.1109\/ICDE51399.2021.00283"}],"container-title":["Memetic Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-024-00407-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12293-024-00407-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-024-00407-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,27]],"date-time":"2024-06-27T14:43:30Z","timestamp":1719499410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12293-024-00407-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,30]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["407"],"URL":"https:\/\/doi.org\/10.1007\/s12293-024-00407-5","relation":{},"ISSN":["1865-9284","1865-9292"],"issn-type":[{"value":"1865-9284","type":"print"},{"value":"1865-9292","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,30]]},"assertion":[{"value":"27 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}