Note: The minimax model for finding the k best differentiated paths between origins and destinations is a very important submodel for getting good results from the mixed-integer network design model.

A Railway Network Design Model with Multiple Project Stages and Time Sequencing by Michael Kuby* Xu Zhongyi** Xie Xiaodong*** 2001 Journal of Geographical Systems 3:25–47. *Department of Geography, Arizona State University, Tempe, AZ 85287-0104 **Planning Bureau, Ministry of Railways, People's Republic of China ***Computer Center, Economic Planning and Research Institute, Ministry of Railways, PRC  Abstract.  This paper presents a methodology for solving network design problems in which different kinds of projects can be built in stages over time. The innovations presented here are motivated by one of the key decisions faced by China's Ministry of Railways, which developed the decision support system with World Bank assistance to aid in investment planning. China needs to expand its overtaxed railway system, and can do so by building brand new corridors, or by double- or triple-tracking or electrifying existing or new lines. Double-track electrified lines can be built all at once or in stages. We developed a mixed-integer programming formulation to solve the single time period network design problem with multiple project types. For solving the multi-time period problem, we developed a backwards time sequencing procedure that takes into account the extra investment costs that come from building a project in stages, and also the interest savings that accrue from putting off unnecessary capacity until it is needed. Other features of the DSS include a preloading routine for handling large O-D traffic matrices, and the incorporation of unsatisfied demand in the model.

A Minimax Method for Finding the k Best "Differentiated" Paths  by  Michael Kuby*  Xu Zhongyi**  Xie Xiaodong*** 1997 Geographical Analysis, Vol. 29, No. 4, 298-313. *Department of Geography, Arizona State University, Tempe, AZ 85287-0104 **Planning Bureau, Ministry of Railways, People's Republic of China ***Computer Center, Economic Planning and Research Institute, Ministry of Railways, PRC Abstract. In real-world applications, the k shortest paths between a pair of nodes on a network will often be slight variations of one another. This could be a problem for many path-based models, particularly those on capacitated networks where different routing alternatives are needed that are less likely to encounter the same capacity constraints. This paper develops a method to generate k differentiated paths that are relatively short and yet relatively different from one another, but not necessarily disjoint. Our method utilizes the sum of a path's distance plus some fraction of its shared distance with each other path. A minimax algorithm is used to select the path whose largest sum of length, plus shared length vis-à-vis each previously selected path, is as small as possible. We present computational results for the Chinese railway system, comparing the paths generated by a standard k shortest path algorithm with those from our new model. Key Words: shortest path, differentiated path, route, disjoint, different, network, transportation, minimax.