Deep Learning for Data-Driven Districting-and-Routing

References

• Ahmed C , Forel A , Parmentier A , Vidal T (2024) DistrictNet: Decision-aware learning for geographical districting. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds. Proc. 38th Internat. Conf. Neural Inform. Processing Systems , vol. 37 (Curran Associates Inc., Red Hook, NY), 128574–128602.Google Scholar
• Akkerman F , Mes M (2025) Distance approximation to support customer selection in vehicle routing problems. Ann. Oper. Res. 350(1):269–297.Crossref, Google Scholar
• Ansari S , Basdere M , Li X , Ouyang Y , Smilowitz K (2018) Advancements in continuous approximation models for logistics and transportation systems: 1996-2016. Transportation Res. Part B Methodological 107:229–252.Crossref, Google Scholar
• Baddeley A (2006) Spatial point processes and their applications. Weil W , ed. Stochastic Geometry , Volume 1892 of Lecture Notes in Mathematics (Springer Berlin Heidelberg, Berlin, Heidelberg), 1–75.Google Scholar
• Beardwood J , Halton JH , Hammersley JM (1959) The shortest path through many points. Math. Proc. Cambridge Philosophical Soc. 55(9):299–327.Crossref, Google Scholar
• Benzarti E , Sahin E , Dallery Y (2013) Operations management applied to home care services: Analysis of the districting problem. Decision Support Systems 55(2):587–598.Crossref, Google Scholar
• Bozkaya B , Erkut E , Laporte G (2003) A tabu search heuristic and adaptive memory procedure for political districting. Eur. J. Oper. Res. 144(1):12–26.Crossref, Google Scholar
• Bruno G , Cavola M , Diglio A , Laporte G , Piccolo C (2021) Reorganizing postal collection operations in urban areas as a result of declining mail volumes: A case study in Bologna. J. Oper. Res. Soc. 72(7):1591–1606.Crossref, Google Scholar
• Cappart Q , Chételat D , Khalil EB , Lodi A , Morris C , Velickovic P (2023) Combinatorial optimization and reasoning with graph neural networks. J. Machine Learn. Res. 24(130):1–61.Google Scholar
• Çavdar B , Sokol J (2015) A distribution-free TSP tour length estimation model for random graphs. Eur. J. Oper. Res. 243(2):588–598.Crossref, Google Scholar
• Chien TW (1992) Operational estimators for the length of a traveling salesman tour. Comput. Oper. Res. 19(6):469–478.Crossref, Google Scholar
• Daganzo CF (1984) The distance traveled to visit N points with a maximum of C stops per vehicle: An analytic model and an application. Transportation Sci. 18(4):331–350.Link, Google Scholar
• Dai H , Dai B , Song L (2016) Discriminative embeddings of latent variable models for structured data. Proc. 33rd Internat. Conf. Machine Learn., 2702–2711.Google Scholar
• Dai H , Khalil EB , Zhang Y , Dilkina B , Song L (2017) Learning combinatorial optimization algorithms over graphs. Proc. 31st Internat. Conf. Neural Inform. Processing Systems , 6351–6361.Google Scholar
• Dalle G , Baty L , Bouvier L , Parmentier A (2022) Learning with combinatorial optimization layers: A probabilistic approach. Preprint, submitted July 27, https://arxiv.org/abs/2207.13513.Google Scholar
• Dibbelt J , Strasser B , Wagner D (2016) Customizable contraction hierarchies. ACM J. Experiment. Algorithmics 21:1–49.Crossref, Google Scholar
• Drakulić D , Michel S , Andreoli JM (2025) GOAL: A generalist combinatorial optimization agent learner. Thirteenth Internat. Conf. Learn. Representations , 52465–52488.Google Scholar
• Drexl M , Schneider M (2015) A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 241(2):283–308.Crossref, Google Scholar
• Dyer M , Frieze A (1985) On the complexity of partitioning graphs into connected subgraphs. Discrete Appl. Math. (1979) 10(2):139–153.Crossref, Google Scholar
• Fey M , Lenssen JE (2019) Fast graph representation learning with PyTorch Geometric. Proc. ICLR Workshop Representation Learn. Graphs Manifolds. Google Scholar
• Figliozzi MA (2007) Analysis of the efficiency of urban commercial vehicle tours: Data collection, methodology, and policy implications. Transportation Res. Part B Methodological 41(9):1014–1032.Crossref, Google Scholar
• Franceschetti A , Jabali O , Laporte G (2017) Continuous approximation models in freight distribution management. Trans. Oper. Res. 25(3):413–433.Google Scholar
• Galvão LC , Novaes AG , Souza De Cursi JE , Souza JC (2006) A multiplicatively-weighted Voronoi diagram approach to logistics districting. Comput. Oper. Res. 33(1):93–114.Crossref, Google Scholar
• García-Ayala G , González-Velarde JL , Ríos-Mercado RZ , Fernández E (2016) A novel model for arc territory design: Promoting Eulerian districts. Internat. Trans. Oper. Res. 23(3):433–458.Crossref, Google Scholar
• Geisberger R , Sanders P , Schultes D , Vetter C (2012) Exact routing in large road networks using contraction hierarchies. Transportation Sci. 46(3):388–404.Link, Google Scholar
• Glorot X , Bordes A , Bengio Y (2011) Deep sparse rectifier neural networks. Gordon G, Dunson D, Dudík M, eds. Proc. 14th Internat. Conf. Artificial Intelligence Statist. Proceedings of Machine Learning Research, vol. 15 (PMLR, New York), 315–323.Google Scholar
• Hamilton WL , Ying R , Leskovec J (2017) Inductive representation learning on large graphs. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems , vol. 30 (Curran Associates Inc., Red Hook, NY), 1025–1035.Google Scholar
• Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1):106–130.Crossref, Google Scholar
• Holland C , Levis J , Nuggehalli R , Santilli B , Winters J (2017) UPS optimizes delivery routes. Interfaces (Providence) 47(1):8–23.Link, Google Scholar
• Horn DL , Hampton CR , Vandenberg AJ (1993) Practical application of district compactness. Political Geography 12(2):103–120.Crossref, Google Scholar
• Joshi CK , Laurent T , Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. Preprint, submitted June 4, https://arxiv.org/abs/1906.01227.Google Scholar
• Joshi CK , Cappart Q , Rousseau LM , Laurent T (2022) Learning the travelling salesperson problem requires rethinking generalization. Constraints 22:1–29.Google Scholar
• Kalcsics J , Ríos-Mercado RZ (2019) Districting problems. Location Science, Springer Books, 2nd ed. (Springer), 705–743.Google Scholar
• Kingma DP , Ba J (2014) Adam: A method for stochastic optimization. Preprint, submitted December 22, https://arxiv.org/abs/1412.6980.Google Scholar
• Kipf TN , Welling M (2017) Semi-supervised classification with graph convolutional networks. Proc. Internat. Conf. Learn. Representation (OpenReview.net).Google Scholar
• Kool W , van Hoof H , Welling M (2019) Attention, learn to solve routing problems! Proc. Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Kou S , Golden B , Bertazzi L (2024) An improved model for estimating optimal VRP solution values. Optim. Lett. 18(3):697–703.Crossref, Google Scholar
• Kou S , Golden B , Poikonen S (2022) Optimal TSP tour length estimation using standard deviation as a predictor. Comput. Oper. Res. 148:105993.Crossref, Google Scholar
• Kovacs A , Golden B , Hartl R , Parragh S (2014) Vehicle routing problems in which consistency considerations are important: A survey. Networks 64(3):192–213.Crossref, Google Scholar
• Kwon O , Golden B , Wasil E (1995) Estimating the length of the optimal TSP tour: An empirical study using regression and neural networks. Comput. Oper. Res. 22(10):1039–1046.Crossref, Google Scholar
• Kwon YD , Choo J , Kim B , Yoon I , Gwon Y , Min S (2020) POMO: Policy optimization with multiple optima for reinforcement learning. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates Inc., Red Hook, NY), 21188–21198.Google Scholar
• Lei H , Laporte G , Guo B (2012) Districting for routing with stochastic customers. EURO J. Transportation Logist. 1(1):67–85.Crossref, Google Scholar
• Lei H , Laporte G , Liu Y , Zhang T (2015) Dynamic design of sales territories. Comput. Oper. Res. 56:84–92.Crossref, Google Scholar
• Levy-Kramer J (2018) k-means-constrained. https://github.com/joshlk/k-means-constrained.Google Scholar
• Li Y , Tarlow D , Brockschmidt M , Zemel R (2016) Gated graph sequence neural networks. Proc. Internat. Conf. Learn. Representation. Google Scholar
• Lin S , Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2):498–516.Link, Google Scholar
• Lourenço HR , Martin OC , Stützle T (2019) Iterated local search: Framework and applications. Gendreau M, Potvin J-Y, eds. Handbook of Metaheuristics (Springer International Publishing, Cham, Switzerland), 129–168.Crossref, Google Scholar
• Miyazawa FK , Moura PFS , Ota MJ , Wakabayashi Y (2020) Cut and flow formulations for the balanced connected k-partition problem. Baïou M , Gendron B , Günlük O , Mahjoub AR , eds. Combin. Optim.: 6th Internat. Sympos. ISCO 2020 (Springer-Verlag, Berlin, Heidelberg), 128–139.Crossref, Google Scholar
• Novaes A , de Cursi J , Graciolli O (2000) A continuous approach to the design of physical distribution systems. Comput. Oper. Res. 27(9):877–893.Crossref, Google Scholar
• 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.Google Scholar
• Scarselli F , Gori M , Tsoi AC , Hagenbuchner M , Monfardini G (2009) The graph neural network model. IEEE Trans. Neural Networks 20(1):61–80.Crossref, Google Scholar
• Sun Z , Yang Y (2023) DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Adv. Neural Inform. Processing Systems , vol. 36 (Curran Associates Inc., Red Hook, NY), 3706–3731.Crossref, Google Scholar
• Uchoa E , Pecin D , Pessoa A , Poggi M , Vidal T , Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Varol T , Özener O , Albey E (2024) Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions. Transportation Sci. 58(1):45–66.Link, Google Scholar
• Veličković P , Cucurull G , Casanova A , Romero A , Liò P , Bengio Y (2018) Graph attention networks. Proc. Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Verweij B , Ahmed S , Kleywegt AJ , Nemhauser G , Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: A computational study. Comput. Optim. Appl. 24(2–3):289–333.Crossref, Google Scholar
• Wang MY (2019) Deep graph library: Towards efficient and scalable deep learning on graphs. Proc. ICLR Workshop Representation Learn. Graphs Manifolds. Google Scholar
• Webster GR (2013) Reflections on current criteria to evaluate redistricting plans. Political Geography 32(1):3–14.Crossref, Google Scholar
• Young HP (1988) Measuring the compactness of legislative districts. Legislative Stud. Quart. 13(1):105.Crossref, Google Scholar
• Zhong H , Hall RW , Dessouky M (2007) Territory planning and vehicle dispatching with driver learning. Transportation Sci. 41(1):74–89.Link, Google Scholar
• Zoltners AA , Sinha P (2005) Sales territory design: Thirty years of modeling and implementation. Marketing Sci. 24(3):313–331.Link, Google Scholar