Corridor Location — The Multi-Gateway Shortest Path

The Problem

One of the most difficult aspects of corridor location is to achieve consensus around a good decision.  There are constituencies with different interests and emphases (e.g. economic, environmental), and invariably some who are directly impacted by deleterious effects of the proposed facility.

Corridor location software traditionally has two components:

Decision support systems should generate alternatives for consideration that are not only very similar to other paths under consideration, but also some that are very different spatially, while achieving comparable goals in terms of cost minimization.  Proposed paths that have generated conflict and strong emotions can then be reconfigured completely, without significantly sacrificing their logistical benefits.

The Solution


Figure 1.  Existing solution approaches employing optimization models usually find alternative paths (blue line) which are only small perturbations of the shortest path (red line). The result is a small area difference between paths as shown by the arrow.
Figure 2.  Gateway path (blue line) found using GSPP  constrained to pass through the gateway cell indicated by the arrow. The area between the two paths (A) is significantly greater than in traditional optimization methods.

Researchers at the University of California, Santa Barbara developed the Gateway Shortest Path Problem (GSPP) approach, which finds spatially different alternatives by selecting “gateway” cells and computing shortest paths that pass through those gateways (Figures 1,2). The further the gateway cells are from the optimal path, the more likely it is that the gateway path will be significantly spatially different from the optimal path. The result is usually a good alternative in terms of cost since it is after all a shortest path, albeit constrained.

Multiple Gateways

Figure 3.  Single-gateway solutions.

The above approach for generating spatially different alternatives only considered paths that travel through a single gateway cell. However, by considering paths that travel through multiple gateway cells, a much larger variety of distinct alignments can be produced. This is better shown in Figures 3 and 4, which display the solutions obtained for a 20 by 20 cell region by considering a single gateway and three gateways, respectively. The two graphs highlight the tradeoffs between the economic and environmental impact associated to each solution, and the spatial dissimilarity as measured by enclosed areas.

Figure 4.  Three-gateway solutions.

It is clear that the range of solutions produced by the multi-gateway approach encompasses a much larger set of alignments than those generated by the single-gateway approach (20,798 distinct alignments vs. 292).

Theoretically, the multiple-gateway path model can be used with all possible combinations and orderings of gateway cells. However, some sets and orderings are not considered consistent within the context of planning objectives. Given this property, a methodology has been developed that involves progressively selecting gateway cells, so that resulting pathways are considered consistent and reasonable. Together progressive selection and the multi-gateway model is designed to generate virtually all consistent, but spatially different alternatives for corridor alignment.

The objective of this research also includes the design of a graphical user interface to support spatial exploration of alignment alternatives.

Additional resources

PDF handout