Going the extra mile — By design: Generating road networks with target values of travel impedance via bi-level optimization

The inherent characteristics of a road network impact transportation system design, performance, and user behavior. However, systematically evaluating their impacts on vehicle routing, facility location, and other transportation decisions is challenging. In this work, we propose a methodology to generate stylized road networks that satisfy user-defined values of average network circuity and inefficiency, two graph characteristics that, respectively, describe the closeness of spatial locations in terms of shortest travel distance and time. We refine an exact solution approach consisting of two novel bi-level mixed-integer Road Network Design Problems solved in succession. We concoct a suite of test instances to evaluate their computational performance and demonstrate that our proposed linearizations, valid inequalities, and warm start heuristics significantly improve model tractability. The resulting method enables the generation of road networks with prescribed values of average travel impedance. As such, it lays a groundwork for future research on the impacts of road network structure and connectivity on transportation systems.