Deep Learning for Data-Driven Districting-and-Routing

Ferraz, Arthur;Ahmed, Cheikh;Cappart, Quentin;Vidal, Thibaut
(2026) Transportation Science — Vol. 60, n° 3, p. 424-444 (2026)

Files

2402.06040v2.pdf
  • Open Access
  • Adobe PDF
  • 3.14 MB
Download

Details

Authors
  • Ferraz, ArthurDepartment of Computer Science, Pontifical Catholic University of Rio de Janeiro, 22451-900 Rio de Janeiro, Brazil
    Author
  • Ahmed, CheikhInterdisciplinary Research Center on Enterprise Networks, Logistics and Transportation, Montréal, Quebec H3T 1N8, Canada; and Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Quebec H3T 1J4, Canada
    Author
  • Cappart, Quentinorcid-logoUCLouvain
    Author
  • Vidal, Thibautorcid-logoInterdisciplinary Research Center on Enterprise Networks, Logistics and Transportation, Montréal, Quebec H3T 1N8, Canada; and Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Quebec H3T 1J4, Canada
    Author
Abstract
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 since 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 Beardwood-Halton-Hammersley and Daganzo's work. 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Ferraz, A., Ahmed, C., Cappart, Q., & Vidal, T. (2026). Deep Learning for Data-Driven Districting-and-Routing. Transportation Science, 60(3), 424-444. https://doi.org/10.1287/trsc.2024.0581 (Original work published 2026)