{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:09:22Z","timestamp":1778663362694,"version":"3.51.4"},"reference-count":61,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>Districting-and-routing is a strategic problem aiming to aggregate basic geographical units (e.g., zip codes) into delivery districts. Its goal is to minimize the expected long-term routing cost of performing deliveries in each district separately. Solving this stochastic problem poses critical challenges because repeatedly evaluating routing costs on a set of scenarios while searching for optimal districts takes considerable time. Consequently, solution approaches usually replace the true cost estimation with continuous cost approximation formulas extending the work of Beardwood-Halton-Hammersley and Daganzo. These formulas commit errors that can be magnified during the optimization step. To reconcile speed and solution quality, we introduce a supervised learning and optimization methodology leveraging a graph neural network for delivery cost estimation. This network is trained to imitate known costs generated on a limited subset of training districts. It is used within an iterated local search procedure to produce high-quality districting plans. Our computational experiments, conducted on five metropolitan areas in the United Kingdom, demonstrate that the graph neural network predicts long-term district cost operations more accurately and that optimizing over this oracle permits large economic gains (10.12% on average) over baseline methods that use continuous approximation formulas or shallow neural networks. Finally, we observe that having compact districts alone does not guarantee high-quality solutions and that other learnable geometrical features of the districts play an essential role.<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendix is available at https:\/\/doi.org\/10.1287\/trsc.2024.0581 .<\/jats:p>","DOI":"10.1287\/trsc.2024.0581","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T15:01:21Z","timestamp":1773846081000},"page":"424-444","source":"Crossref","is-referenced-by-count":0,"title":["Deep Learning for Data-Driven Districting-and-Routing"],"prefix":"10.1287","volume":"60","author":[{"given":"Arthur","family":"Ferraz","sequence":"first","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Rio de Janeiro, 22451-900 Rio de Janeiro, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheikh","family":"Ahmed","sequence":"additional","affiliation":[{"name":"Interdisciplinary Research Center on Enterprise Networks, Logistics and Transportation, Montr\u00e9al, Quebec H3T 1N8, Canada; and Department of Mathematics and Industrial Engineering, Polytechnique Montr\u00e9al, Montr\u00e9al, Quebec H3T 1J4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8742-0774","authenticated-orcid":false,"given":"Quentin","family":"Cappart","sequence":"additional","affiliation":[{"name":"Interdisciplinary Research Center on Enterprise Networks, Logistics and Transportation, Montr\u00e9al, Quebec H3T 1N8, Canada; and Department of Computer and Software Engineering, Polytechnique Montr\u00e9al, Montr\u00e9al, Quebec H3T 1J4, Canada; and UCLouvain, 1348 Louvain-la-Neuve, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5183-8485","authenticated-orcid":false,"given":"Thibaut","family":"Vidal","sequence":"additional","affiliation":[{"name":"Interdisciplinary Research Center on Enterprise Networks, Logistics and Transportation, Montr\u00e9al, Quebec H3T 1N8, Canada; and Department of Mathematics and Industrial Engineering, Polytechnique Montr\u00e9al, Montr\u00e9al, Quebec H3T 1J4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"crossref","unstructured":"Ahmed C , \nForel A , \nParmentier A , \nVidal T   (2024) DistrictNet: Decision-aware learning for geographical districting. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds.\n                      Proc. 38th Internat. Conf. Neural Inform. Processing Systems\n                      , vol. 37 (Curran Associates Inc., Red Hook, NY), 128574\u2013128602.","DOI":"10.52202\/079017-4084"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-022-04674-8"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2017.09.019"},{"key":"B4","first-page":"1","volume-title":"Stochastic Geometry","author":"Baddeley A","year":"2006"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2012.10.015"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00380-0"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1080\/01605682.2020.1736446"},{"issue":"130","key":"B9","first-page":"1","volume":"24","author":"Cappart Q","year":"2023","journal-title":"J. Machine Learn. Res."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.12.020"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(92)90002-M"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.4.331"},{"key":"B13","unstructured":"Dai H , \nDai B , \nSong L   (2016) Discriminative embeddings of latent variable models for structured data.\n                      Proc. 33rd Internat. Conf. Machine Learn\n                      ., 2702\u20132711."},{"key":"B14","unstructured":"Dai H , \nKhalil EB , \nZhang Y , \nDilkina B , \nSong L   (2017) Learning combinatorial optimization algorithms over graphs.\n                      Proc. 31st Internat. Conf. Neural Inform. Processing Systems\n                      , 6351\u20136361."},{"key":"B15","unstructured":"Dalle G , \nBaty L , \nBouvier L , \nParmentier A   (2022) Learning with combinatorial optimization layers: A probabilistic approach. Preprint, submitted July 27, https:\/\/arxiv.org\/abs\/2207.13513."},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1145\/2886843"},{"key":"B17","unstructured":"Drakuli\u0107 D , \nMichel S , \nAndreoli JM   (2025) GOAL: A generalist combinatorial optimization agent learner.\n                      Thirteenth Internat. Conf. Learn. Representations\n                      , 52465\u201352488."},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.08.030"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90008-3"},{"key":"B20","unstructured":"Fey M , \nLenssen JE   (2019) Fast graph representation learning with PyTorch Geometric.\n                      Proc. ICLR Workshop Representation Learn. Graphs Manifolds."},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2007.04.006"},{"issue":"3","key":"B22","first-page":"413","volume":"25","author":"Franceschetti A","year":"2017","journal-title":"Trans. Oper. Res."},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.07.001"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12219"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"B26","unstructured":"Glorot X , \nBordes A , \nBengio Y   (2011) Deep sparse rectifier neural networks. Gordon G, Dunson D, Dud\u00edk M, eds.\n                      Proc. 14th Internat. Conf. Artificial Intelligence Statist\n                      . Proceedings of Machine Learning Research, vol. 15 (PMLR, New York), 315\u2013323."},{"key":"B27","unstructured":"Hamilton WL , \nYing R , \nLeskovec J   (2017) Inductive representation learning on large graphs. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds.\n                      Adv. Neural Inform. Processing Systems\n                      , vol. 30 (Curran Associates Inc., Red Hook, NY), 1025\u20131035."},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/inte.2016.0875"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/0962-6298(93)90031-2"},{"key":"B31","unstructured":"Joshi CK , \nLaurent T , \nBresson X   (2019) An efficient graph convolutional network technique for the travelling salesman problem. Preprint, submitted June 4, https:\/\/arxiv.org\/abs\/1906.01227."},{"key":"B32","first-page":"1","volume":"22","author":"Joshi CK","year":"2022","journal-title":"Constraints"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Kalcsics J , \nR\u00edos-Mercado RZ   (2019) Districting problems.\n                      Location Science\n                      , Springer Books, 2nd ed. (Springer), 705\u2013743.","DOI":"10.1007\/978-3-030-32177-2_25"},{"key":"B34","unstructured":"Kingma DP , \nBa J   (2014) Adam: A method for stochastic optimization. Preprint, submitted December 22, https:\/\/arxiv.org\/abs\/1412.6980."},{"key":"B35","unstructured":"Kipf TN , \nWelling M   (2017) Semi-supervised classification with graph convolutional networks.\n                      Proc. Internat. Conf. Learn. Representation\n                      (OpenReview.net)."},{"key":"B36","unstructured":"Kool W , \nvan Hoof H , \nWelling M   (2019) Attention, learn to solve routing problems!\n                      Proc. Internat. Conf. Learn. Representations\n                      (OpenReview.net)."},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-023-02082-w"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105993"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1002\/net.21565"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(94)00093-N"},{"key":"B41","unstructured":"Kwon YD , \nChoo J , \nKim B , \nYoon I , \nGwon Y , \nMin S   (2020) POMO: Policy optimization with multiple optima for reinforcement learning. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds.\n                      Adv. Neural Inform. Processing Systems\n                      , vol. 33 (Curran Associates Inc., Red Hook, NY), 21188\u201321198."},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1007\/s13676-012-0005-x"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.11.008"},{"key":"B44","unstructured":"Levy-Kramer J   (2018) k-means-constrained. https:\/\/github.com\/joshlk\/k-means-constrained."},{"key":"B45","unstructured":"Li Y , \nTarlow D , \nBrockschmidt M , \nZemel R   (2016) Gated graph sequence neural networks.\n                      Proc. Internat. Conf. Learn. Representation."},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91086-4_5"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53262-8_11"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(99)00063-5"},{"key":"B50","unstructured":"Park N   (2018) Middle super output area population estimates: Mid-2018: Sape21dt3a edition. Accessed November 27, 2021, https:\/\/www.ons.gov.uk\/peoplepopulationandcommunity\/populationandmigration\/populationestimates\/datasets\/middlesuperoutputareamidyearpopulationestimates."},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.52202\/075280-0164"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.08.012"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2022.0015"},{"key":"B55","unstructured":"Veli\u010dkovi\u0107 P , \nCucurull G , \nCasanova A , \nRomero A , \nLi\u00f2 P , \nBengio Y   (2018) Graph attention networks.\n                      Proc. Internat. Conf. Learn. Representations\n                      (OpenReview.net)."},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021814225969"},{"key":"B57","unstructured":"Wang MY   (2019) Deep graph library: Towards efficient and scalable deep learning on graphs.\n                      Proc. ICLR Workshop Representation Learn. Graphs Manifolds."},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1016\/j.polgeo.2012.10.004"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.2307\/439947"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1060.0167"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1287\/mksc.1050.0133"}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.2024.0581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T08:15:10Z","timestamp":1778660110000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/trsc.2024.0581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/trsc.2024.0581"],"URL":"https:\/\/doi.org\/10.1287\/trsc.2024.0581","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}