Doctoral Research

Finding a low-cost road network from one starting point to several destinations.

Why it matters

Access to several destinations creates opportunities to share connections. Modeling the combined network makes those tradeoffs explicit; paired experiments test whether reducing the search area preserves cost in the configurations examined.

My contribution

For my PhD, I formulated and implemented an integer-programming model in Python and R that charges shared links once when minimizing total network cost. I compared full and convex-hull-reduced networks to test when restricting the search retained the selected-edge cost.

Result

All 72 archived full/reduced comparisons produced matching selected-edge costs. This finding applies to the tested configurations, not every network.

Tools

Python
R
Integer programming
MIP
OMPR

Results depend on the network, solver settings, and assumptions used to reduce the search area.

Project gallery

Historical portfolio screenshots. 3 images. Select an image to view it full size.

Blue connections run from a green central origin to three red targets across a hexagonal grid. The full-network solution is labeled cost 12. — Full network: the archived solution connects a central origin to three targets at a selected-edge cost of 12.

A blue triangle encloses 31 red-circled nodes within a larger 91-node hexagonal network, showing the retained search area. — Convex-hull reduction retains 31 of 91 nodes inside the triangle defined by the three targets in this example.

Blue connections join the central origin and three red targets after convex-hull reduction. The solution is labeled cost 12, matching the full-network example. — Reduced network: the archived solution connects the same origin and targets with the same selected-edge cost of 12.

Testing when a smaller search area helps

The R implementation uses a multi-commodity flow formulation to compare full networks with convex-hull-reduced networks. Paired configurations test whether reducing the search area changes selected-edge cost, while varying target placement tests when useful reduction is possible. The experiments span six hexagonal grid sizes, three target layouts, and four target counts.

All 72 saved full/reduced comparisons have matching selected-edge costs. This supports cost preservation for those tested configurations. It does not establish that a convex-hull restriction preserves the best solution on every network.

Design of the network experiments — Six grid sizes, three target layouts, and four target counts produce 72 paired configurations. Each compares the full network with a convex-hull-reduced network. Scroll horizontally to explore the diagram.

Target placement determines the benefit

These representative saved observations use a 271-cell grid with 12 targets. Concentrated radial targets leave a much smaller model. Targets near the corners can span the whole grid, leaving no nodes to remove and adding preprocessing overhead.

For radial targets, the recorded times cover model construction and solving; hull preprocessing happened before the timer. The reduced near-corner and random timings also include hull computation. Each row is one saved run pair, so the times describe these experiments rather than a general performance guarantee.

Archived 271-cell, 12-target comparisons. Each value pair is full network / reduced network.
Target layout	Nodes retained	Selected-edge cost	Recorded time (seconds)
Radial arms	271 / 31	12 / 12	71.83 / 6.60
Near corners	271 / 271	54 / 54	38.04 / 42.46
Seeded random	271 / 99	32 / 32	37.81 / 13.92

Implementation and validation scope

The model assigns one flow to each target while charging shared edges once. It also supports targets that must be endpoints, instead of allowing every target to serve as a waypoint.

The repository includes checks against Dijkstra for single-target cases, comparisons between HiGHS and GLPK, and scenarios with barriers, narrow corridors, and different target layouts. The figures and table here summarize archived results; the solver and test suite were not rerun for this presentation.

Technical details

The University of Texas at Dallas · Doctoral research

Choosing a separate shortest route to each destination can miss opportunities to share parts of the network.

Represent roads and connections as a vector network.
Use integer programming in Python and R to choose connections with low total cost.
Use convex-hull preprocessing to reduce the search area.

Dissertation: Modeling Integer Programming To Multiple Target Access Problem. The University of Texas at Dallas, 2024.

← Back to projects