{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T18:27:04Z","timestamp":1772303224682,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T00:00:00Z","timestamp":1702857600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T00:00:00Z","timestamp":1702857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001858","name":"VINNOVA","doi-asserted-by":"publisher","award":["2022-01345"],"award-info":[{"award-number":["2022-01345"]}],"id":[{"id":"10.13039\/501100001858","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EUREKA ITEA3 AIToC","award":["2020-01947"],"award-info":[{"award-number":["2020-01947"]}]},{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Chalmers AI Research Centre"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Event Dyn Syst"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Conflict-Free Electric Vehicle Routing Problem (CF-EVRP) is a combinatorial optimization problem of designing routes for vehicles to execute tasks such that a cost function, typically the number of vehicles or the total travelled distance, is minimized. The CF-EVRP involves constraints such as time windows on the tasks\u2019 execution, limited operating range of the vehicles, and limited capacity on the number of vehicles that a road segment can simultaneously accommodate. In previous work, the compositional algorithm <jats:italic>ComSat<\/jats:italic> was introduced to solve the CF-EVRP by breaking it down into sub-problems and iteratively solve them to build an overall solution. Though ComSat showed good performance in general, some problem instances took significant time to solve due to the high number of iterations required to find solutions for two sub-problems, namely the <jats:italic>Routing Problem<\/jats:italic>, and the <jats:italic>Paths Changing Problem<\/jats:italic>. This paper addresses the bottlenecks of ComSat and presents new formulations for both sub-problems in order to reduce the number of iterations required to find feasible solutions to the CF-EVRP. Experiments on sets of benchmark instances show the effectiveness of the presented improvements.<\/jats:p>","DOI":"10.1007\/s10626-023-00388-6","type":"journal-article","created":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T10:02:38Z","timestamp":1702893758000},"page":"21-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Conflict-free electric vehicle routing problem: an improved compositional algorithm"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4845-3565","authenticated-orcid":false,"given":"Sabino Francesco","family":"Roselli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Fabian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Knut","family":"\u00c5kesson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,18]]},"reference":[{"issue":"18","key":"388_CR1","doi-asserted-by":"publisher","first-page":"4948","DOI":"10.3390\/en13184948","volume":"13","author":"M Abderrahim","year":"2020","unstructured":"Abderrahim M, Bekrar A, Trentesaux D, Aissani N, Bouamrane K (2020) Manufacturing 4.0 operations scheduling with AGV battery management constraints. Energies 13(18):4948","journal-title":"Energies"},{"key":"388_CR2","doi-asserted-by":"crossref","unstructured":"Aloul FA, Al\u00a0Rawi B, Aboelaze M (2006) Identifying the shortest path in large networks using boolean satisfiability. In: 2006 3rd international conference on electrical and electronics engineering, pp 1\u20134","DOI":"10.1109\/ICEEE.2006.251924"},{"key":"388_CR3","volume-title":"Handbook of Graph Theory, Combinatorial Optimization, and Algorithms","author":"S Arumugam","year":"2016","unstructured":"Arumugam S, Brandst\u00e4dt A, Nishizeki T, Thulasiraman K (2016) Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, vol 34. CRC Press, New York"},{"key":"388_CR4","first-page":"825","volume":"185","author":"CW Barrett","year":"2009","unstructured":"Barrett CW, Sebastiani R, Seshia SA, Tinelli C et al (2009) Satisfiability modulo theories. Handbook of Satisfiability 185:825\u2013885","journal-title":"Handbook of Satisfiability"},{"key":"388_CR5","doi-asserted-by":"crossref","unstructured":"Bj\u00f8rner N, Phan A-D, Fleckenstein L (2015) $$\\nu $$Z-an optimizing SMT solver. In: International conference on tools and algorithms for the construction and analysis of systems, pp 194\u2013199","DOI":"10.1007\/978-3-662-46681-0_14"},{"key":"388_CR6","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1613\/jair.3196","volume":"40","author":"A Cimatti","year":"2011","unstructured":"Cimatti A, Griggio A, Sebastiani R (2011) Computing small unsatisfiable cores in satisfiability modulo theories. J Artif Intell Res 40:701\u2013728","journal-title":"J Artif Intell Res"},{"key":"388_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-2196-8","volume-title":"Advanced Combinatorics: The Art of Finite and Infinite Expansions","author":"L Comtet","year":"1974","unstructured":"Comtet L (1974) Advanced Combinatorics: The Art of Finite and Infinite Expansions. Springer, Dordrecht"},{"issue":"6","key":"388_CR8","doi-asserted-by":"publisher","first-page":"1688","DOI":"10.1016\/j.cor.2005.07.004","volume":"34","author":"AI Corr\u00e9a","year":"2007","unstructured":"Corr\u00e9a AI, Langevin A, Rousseau L-M (2007) Scheduling and routing of automated guided vehicles: a hybrid approach. Comput Oper Res 34(6):1688\u20131707","journal-title":"Comput Oper Res"},{"key":"388_CR9","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.tre.2019.08.015","volume":"130","author":"DL Cort\u00e9s-Murcia","year":"2019","unstructured":"Cort\u00e9s-Murcia DL, Prodhon C, Afsar HM (2019) The electric vehicle routing problem with time windows, partial recharges and satellite customers. Transport Res Part E: Logistic Transport Rev 130:184\u2013206","journal-title":"Transport Res Part E: Logistic Transport Rev"},{"issue":"1","key":"388_CR10","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. Manage Sci 6(1):80\u201391","journal-title":"Manage Sci"},{"issue":"1","key":"388_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TASE.2018.2798630","volume":"16","author":"G Daugherty","year":"2018","unstructured":"Daugherty G, Reveliotis S, Mohler G (2018) Optimized multiagent routing for a class of guidepath-based transport systems. IEEE Trans Autom Sci Eng 16(1):363\u2013381","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"388_CR12","doi-asserted-by":"crossref","unstructured":"De Moura L, Bj\u00f8rner N (2011) Satisfiability modulo theories: introduction and applications. Commun ACM 54(9):69\u201377","DOI":"10.1145\/1995376.1995394"},{"key":"388_CR13","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.jmsy.2019.12.002","volume":"54","author":"M De Ryck","year":"2020","unstructured":"De Ryck M, Versteyhe M, Debrouwere F (2020) Automated guided vehicle systems, state-of-the-art control algorithms and techniques. J Manuf Syst 54:152\u2013173","journal-title":"J Manuf Syst"},{"key":"388_CR14","doi-asserted-by":"crossref","unstructured":"De\u00a0Moura L, Bj\u00f8rner N (2008) Z3: an efficient SMT solver. In: International conference on tools and algorithms for the construction and analysis of systems, Springer, Berlin, Heidelberg, pp 337\u2013340","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"388_CR15","doi-asserted-by":"crossref","unstructured":"Dershowitz N, Hanna Z, Nadel A (2006) A scalable algorithm for minimal unsatisfiable core extraction. In: International conference on theory and applications of satisfiability testing, pp 36\u201341","DOI":"10.1007\/11814948_5"},{"issue":"2","key":"388_CR16","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1287\/opre.40.2.342","volume":"40","author":"M Desrochers","year":"1992","unstructured":"Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper Res 40(2):342\u2013354","journal-title":"Oper Res"},{"issue":"1","key":"388_CR17","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"issue":"3","key":"388_CR18","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover F (1989) Tabu search\u2014part I. ORSA J Comput 1(3):190\u2013206","journal-title":"ORSA J Comput"},{"key":"388_CR19","unstructured":"Gurobi Optimization, LLC (2023) Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"388_CR20","doi-asserted-by":"crossref","unstructured":"Hansen P, Mladenovi\u0107 N (2005) In: Burke EK, Kendall G (eds) Variable Neighborhood Search, pp 211\u2013238. Springer, Boston, MA","DOI":"10.1007\/0-387-28356-0_8"},{"issue":"2","key":"388_CR21","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100\u2013107","journal-title":"IEEE Trans Syst Sci Cybern"},{"key":"388_CR22","doi-asserted-by":"crossref","unstructured":"Huang J (2005) MUP: a minimal unsatisfiability prover. In: Proceedings of the ASP-DAC 2005. Asia and South Pacific design automation conference, 2005, vol 1, pp 432\u2013437","DOI":"10.1145\/1120725.1120907"},{"key":"388_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.trc.2016.01.013","volume":"65","author":"M Keskin","year":"2016","unstructured":"Keskin M, \u00c7atay B (2016) Partial recharge strategies for the electric vehicle routing problem with time windows. Transport Res part C: Emerg Technol 65:111\u2013127","journal-title":"Transport Res part C: Emerg Technol"},{"issue":"2","key":"388_CR24","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0098-1354(93)80015-F","volume":"17","author":"E Kondili","year":"1993","unstructured":"Kondili E, Pantelides CC, Sargent RW (1993) A general algorithm for short-term scheduling of batch operations\u2014I. MILP formulation. Computers & Chemical Engineering 17(2):211\u2013227","journal-title":"MILP formulation. Computers & Chemical Engineering"},{"issue":"6","key":"388_CR25","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1287\/opre.41.6.1077","volume":"41","author":"NN Krishnamurthy","year":"1993","unstructured":"Krishnamurthy NN, Batta R, Karwan MH (1993) Developing conflict-free routes for automated guided vehicles. Oper Res 41(6):1077\u20131090","journal-title":"Oper Res"},{"key":"388_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-50497-0","volume-title":"Decision procedures-An Algorithmic Point of View","author":"D Kroening","year":"2016","unstructured":"Kroening D, Strichman O (2016) Decision procedures-An Algorithmic Point of View. Springer, Heidelberg"},{"key":"388_CR27","doi-asserted-by":"publisher","first-page":"107650","DOI":"10.1016\/j.cie.2021.107650","volume":"161","author":"I Kucukoglu","year":"2021","unstructured":"Kucukoglu I, Dewil R, Cattrysse D (2021) The electric vehicle routing problem and its variations: a literature review. Comput Industrial Eng 161:107650","journal-title":"Comput Industrial Eng"},{"key":"388_CR28","doi-asserted-by":"crossref","unstructured":"Lim A, Wang F (2005) Multi-depot vehicle routing problem: a one-stage approach. IEEE Trans Autom Sci Eng 2(4):397\u2013402","DOI":"10.1109\/TASE.2005.853472"},{"issue":"2","key":"388_CR29","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1287\/opre.8.2.219","volume":"8","author":"AS Manne","year":"1960","unstructured":"Manne AS (1960) On the job-shop scheduling problem. Oper Res 8(2):219\u2013223","journal-title":"Oper Res"},{"key":"388_CR30","doi-asserted-by":"publisher","first-page":"106270","DOI":"10.1016\/j.cie.2020.106270","volume":"141","author":"K Murakami","year":"2020","unstructured":"Murakami K (2020) Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system. Comput Ind Eng 141:106270","journal-title":"Comput Ind Eng"},{"key":"388_CR31","unstructured":"Nadel A (2010) Boosting minimal unsatisfiable core extraction. In: Formal methods in computer aided design, pp 221\u2013229"},{"key":"388_CR32","doi-asserted-by":"crossref","unstructured":"Nadel A, Ryvchin V, Strichman O (2013) Efficient MUS extraction with resolution. In: 2013 formal methods in computer-aided design, pp 197\u2013200","DOI":"10.1109\/FMCAD.2013.6679410"},{"key":"388_CR33","doi-asserted-by":"crossref","unstructured":"Pratissoli F, Brugioni R, Battilani N, Sabattini L (2023) Hierarchical traffic management of multi-AGV systems with deadlock prevention applied to industrial environments. IEEE Trans Autom Sci Eng:1\u201315","DOI":"10.1109\/TASE.2023.3276233"},{"key":"388_CR34","doi-asserted-by":"crossref","unstructured":"Roselli SF, Bengtsson K, \u00c5kesson K (2018) SMT solvers for job-shop scheduling problems: models comparison and performance evaluation. In: 2018 IEEE 14th international conference on automation science and engineering (CASE), pp 547\u2013552","DOI":"10.1109\/COASE.2018.8560344"},{"key":"388_CR35","doi-asserted-by":"crossref","unstructured":"Roselli SF, Fabian M, \u00c5kesson K (2021) Solving the conflict-free electric vehicle routing problem using SMT solvers. In: 2021 29th mediterranean conference on control and automation (MED), pp 542\u2013547","DOI":"10.1109\/MED51440.2021.9480202"},{"issue":"28","key":"388_CR36","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ifacol.2022.10.319","volume":"55","author":"SF Roselli","year":"2022","unstructured":"Roselli SF, Vader R, Fabian M, \u00c5kesson K (2022) Leveraging conflicting constraints in solving vehicle routing problems. IFAC-PapersOnLine 55(28):22\u201329","journal-title":"IFAC-PapersOnLine"},{"issue":"3","key":"388_CR37","doi-asserted-by":"publisher","first-page":"1405","DOI":"10.1109\/TASE.2022.3169949","volume":"19","author":"SF Roselli","year":"2022","unstructured":"Roselli SF, G\u00f6tvall P-L, Fabian M, \u00c5kesson K (2022) A compositional algorithm for the conflict-free electric vehicle routing problem. IEEE Trans Autom Sci Eng 19(3):1405\u20131421","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"388_CR38","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.cie.2015.01.003","volume":"86","author":"M Saidi-Mehrabad","year":"2015","unstructured":"Saidi-Mehrabad M, Dehnavi-Arani S, Evazabadian F, Mahmoodian V (2015) An ant colony algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs. Comput Ind Eng 86:2\u201313","journal-title":"Comput Ind Eng"},{"issue":"4","key":"388_CR39","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1287\/trsc.2013.0490","volume":"48","author":"M Schneider","year":"2014","unstructured":"Schneider M, Stenger A, Goeke D (2014) The electric vehicle-routing problem with time windows and recharging stations. Transp Sci 48(4):500\u2013520","journal-title":"Transp Sci"},{"key":"388_CR40","doi-asserted-by":"crossref","unstructured":"Selsam D, Bj\u00f8rner N (2019) Guiding high-performance SAT solvers with unsat-core predictions. In: International conference on theory and applications of satisfiability testing, pp 336\u2013353","DOI":"10.1007\/978-3-030-24258-9_24"},{"key":"388_CR41","doi-asserted-by":"crossref","unstructured":"Sinz C (2005) Towards an optimal CNF encoding of boolean cardinality constraints. In: International conference on principles and practice of constraint programming, pp 827\u2013831","DOI":"10.1007\/11564751_73"},{"key":"388_CR42","doi-asserted-by":"crossref","unstructured":"Thanos E, Wauters T, Vanden\u00a0Berghe G (2019) Dispatch and conflict-free routing of capacitated vehicles with storage stack allocation. J Oper Res Soc:1\u201314","DOI":"10.1080\/01605682.2019.1595191"},{"key":"388_CR43","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-94-009-0349-4_5","volume-title":"Frontiers of Combining Systems","author":"C Tinelli","year":"1996","unstructured":"Tinelli C, Harandi M (1996) A new correctness proof of the Nelson-Oppen combination procedure. In: Baader F, Schulz KU (eds) Frontiers of Combining Systems. Springer, Dordrecht, pp 103\u2013119"},{"key":"388_CR44","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.compchemeng.2015.02.013","volume":"76","author":"F Trespalacios","year":"2015","unstructured":"Trespalacios F, Grossmann IE (2015) Improved big-M reformulation for generalized disjunctive programs. Comput Chem Eng 76:98\u2013103","journal-title":"Comput Chem Eng"},{"issue":"21","key":"388_CR45","doi-asserted-by":"publisher","first-page":"6333","DOI":"10.3390\/s20216333","volume":"20","author":"F Yao","year":"2020","unstructured":"Yao F, Alkan B, Ahmad B, Harrison R (2020) Improving just-in-time delivery performance of IoT-enabled flexible manufacturing systems with agv based material transportation. Sensors 20(21):6333","journal-title":"Sensors"},{"issue":"6","key":"388_CR46","first-page":"442","volume":"6","author":"R Yuan","year":"2016","unstructured":"Yuan R, Dong T, Li J (2016) Research on the collision-free path planning of multi-AGVs system based on improved A* algorithm. Amer J Oper Res 6(6):442\u2013449","journal-title":"Amer J Oper Res"},{"key":"388_CR47","doi-asserted-by":"publisher","first-page":"106371","DOI":"10.1016\/j.cie.2020.106371","volume":"142","author":"M Zhong","year":"2020","unstructured":"Zhong M, Yang Y, Dessouky Y, Postolache O (2020) Multi-AGV scheduling for conflict-free path planning in automated container terminals. Comput Ind Eng 142:106371","journal-title":"Comput Ind Eng"}],"container-title":["Discrete Event Dynamic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-023-00388-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10626-023-00388-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-023-00388-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T09:12:17Z","timestamp":1707988337000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10626-023-00388-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,18]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["388"],"URL":"https:\/\/doi.org\/10.1007\/s10626-023-00388-6","relation":{},"ISSN":["0924-6703","1573-7594"],"issn-type":[{"value":"0924-6703","type":"print"},{"value":"1573-7594","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,18]]},"assertion":[{"value":"2 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2023","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 to have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interests"}}]}}