The Transit Route Arc-Node Service Maximization problem

This article presents a new method for determining optimal transit routes. The Transit Route Arc-Node Service Maximization model is a mathematical model that maximizes the service value of a route, rather than minimizing cost. Cost (distance) is considered as a budget constraint on the extent of the route. The mathematical formulation modifies and exploits the structure of linear programming problems designed for the traveling salesman problem. An innovative divide-and-conquer solution procedure is presented that not only makes the transit routing problem tractable, but also provides a range of high-quality alternate routes for consideration, some of which have substantially varying geometries. Variant formulations are provided for several common transit route types. The model is tested through its application to an existing street network in Richardson, TX. Optimal numeric results are obtained for several problem instances, and these results demonstrate that increased route cost is not correlated with increased service provision.