Deep Learning for Data-Driven Districting and Routing

The districting-and-routing problem is a strategic problem in which basic geographical units (e.g., zip codes) should be aggregated into delivery regions, and each delivery region is characterized by a routing cost estimated over an extended planning horizon. The objective is to minimize the expected routing costs while ensuring regional separability through the definition of the districts. We have proposed to rely on a graph neural network (GNN) trained on a set of demand scenarios, which is then used within an optimization approach to infer routing costs while solving the districting problem.

Full Paper : [SOON]

Organization of the Repository

• /Data contains the data necessary to solve the Districting-and-Routing Problem and the scripts to generate them:

  • /Data/Dataset contains the data related to each city with some test and training customers scenarios.
  • /Data/TSP-Scenarios contains the data related randomly generated districts and their expected cost calculated using the Sample Approximation Approach (SAA).

• /Evaluator contains scripts used to evaluate solutions

  • /Evaluator/Compatcness-Evaluation has the code to run a compactness evaluation of a given solution.
  • /Evaluator/Solution-Cost-Evaluation has the code to get the expected costs for a given solution using SAA in the test customers scenarios.

• /Solver contains scripts used to evaluate solutions

  • /Solver/GNN has the code related to the Graph Neural Network (GNN) and the trained models.
  • /Solver/CostEstimators has the code for the other cost estimators, namely BD, SNN, and FIG.
  • /Solver/ILS has the code for the Iterated Local Search (ILS) metaheuristic.
  • /Solver/ExactSolver has the code for a formulation to solve the set partitioning problem - able to get optimal in small instances.

Data Format

All datasets and solutions are written in GeoJSON format. The format specification is available at this URL: http://www.rfc-editor.org/info/rfc7946