skip to main content

Title: Identifying Critical Links in Transportation Network Design Problems for Maximizing Network Accessibility
A significant amount of research has been performed on network accessibility evaluation, but studies on incorporating accessibility maximization into network design problems have been relatively scarce. This study aimed to bridge the gap by proposing an integer programming model that explicitly maximizes the number of accessible opportunities within a given travel time budget. We adopted the Lagrangian relaxation method for decomposing the main problem into three subproblems that can be solved more efficiently using dynamic programming. The proposed method was applied to several case studies, which identified critical links for maximizing network accessibility with limited construction budget, and also illustrated the accuracy and efficiency of the algorithm. This method is promisingly scalable as a solution algorithm for large-scale accessibility-oriented network design problems.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
Transportation Research Record: Journal of the Transportation Research Board
Page Range / eLocation ID:
237 to 251
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In many biomedical and social science studies, it is important to identify and predict the dynamic changes of associations among network data over time. We propose a varying-coefficient model to incorporate time-varying network data, and impose a piecewise penalty function to capture local features of the network associations. The proposed approach is semi-parametric, and therefore flexible in modeling dynamic changes of association in network data problems. Furthermore, the approach can identify the time regions when dynamic changes of associations occur. To achieve a sparse network estimation at local time intervals, we implement a group penalization strategy involving parameters that overlap between groups. However, this makes the optimization process challenging for large-dimensional network data observed at many time points. We develop a fast algorithm, based on the smoothing proximal-gradient method, that is computationally efficient and accurate. We illustrate the proposed method through simulation studies and children's attention deficit hyperactivity disorder fMRI data, showing that the proposed method and algorithm recover dynamic network changes over time efficiently. 
    more » « less
  2. Parsons problems are drag-and-drop computer programming puzzles that require learners to place code blocks in the correct order and sometimes indentation. Introductory computer programming instructors use them to teach novice programmers how to code while optimizing problem-solving efficiency and cognitive load. While there is research on the design of Parsons problems for programmers without disabilities and programmers with visual or motor impairments, research regarding their accessibility for programmers with cognitive disabilities is scant. To identify the accessibility barriers and benefits of Parsons problems for neurodiverse programmers, an exploratory multiple-case study was conducted. Participants were asked to read eight chapters of an interactive eBook on Python and to solve Parsons problems. Within-case analyses of 15 retrospective think-aloud interviews with five novice programmers with disabilities led to four recommendations for improving the cognitive accessibility of Parsons problems. For example, programmers with seizure disorders may experience seizures when solving programming problems that require numeric calculations. Hence, creating a range of Parsons problems that do not require mental arithmetic could improve the learning experience for programmers with seizure disorders and those who struggle with mental calculations by lowering their cognitive load. Given this study's qualitative and exploratory approach, it does not offer conclusive, broadly generalizable results. Yet, it reveals detailed and promising avenues for exploration in computing education research that might elude many quantitative techniques. 
    more » « less
  3. Crowdsourcing has become an efficient paradigm to utilize human intelligence to perform tasks that are challenging for machines. Many incentive mechanisms for crowdsourcing systems have been proposed. However, most of existing incentive mechanisms assume that there are sufficient participants to perform crowdsourcing tasks. In large-scale crowdsourcing scenarios, this assumption may be not applicable. To address this issue, we diffuse the crowdsourcing tasks in social network to increase the number of participants. To make the task diffusion more applicable to crowdsourcing system, we enhance the classic Independent Cascade model so the influence is strongly connected with both the types and topics of tasks. Based on the tailored task diffusion model, we formulate the Budget Feasible Task Diffusion ( BFTD ) problem for maximizing the value function of platform with constrained budget. We design a parameter estimation algorithm based on Expectation Maximization algorithm to estimate the parameters in proposed task diffusion model. Benefitting from the submodular property of the objective function, we apply the budget-feasible incentive mechanism, which satisfies desirable properties of computational efficiency, individual rationality, budget-feasible, truthfulness, and guaranteed approximation, to stimulate the task diffusers. The simulation results based on two real-world datasets show that our incentive mechanism can improve the number of active users and the task completion rate by 9.8% and 11%, on average. 
    more » « less
  4. Network disaster recovery is one of the greatest concerns for Mobile Network Operators (MNOs) and first responders during large-scale natural disasters such as earth- quakes. In many recent studies, wireless multi-hop networking has been demonstrated as an effective technique to quickly and efficiently extend the network coverage during disasters. In this paper, we specifically address the network deployment problem by proposing the Population-Aware Relay Placement (PARP) solution, which seeks the efficient deployment of a limited number of relays such that population coverage is maximized in the scenario of network disaster recovery. We provide a graph-based modeling and prove its NP-hardness accordingly. In order to efficiently solve this problem, we propose a heuristic solution, which is constructed in two steps. We first design a simple algorithm based on a disk graph to determine the Steiner locations, which is the biggest challenge in this problem. Then, we formulate the problem as an integer programming problem, which is inspired by the formulation of Prize-Collecting Steiner Tree (PCST). Thus, the integer problem is solved by exploring the similarity of the existing algorithm for PCST. To evaluate the proposed solution extensively, we present numerical results on both real-world and random scenarios, which validate the effectiveness of the proposed solution and show substantial improvement by comparing to the previous one. 
    more » « less
  5. While the networking community has extensively tackled network design problems using optimization or other techniques (e.g., in areas such as traffic-engineering, and resource allocation), much of this work focuses on efficiently generating designs assuming well-defined objectives. In this paper, we argue that in practice, the objectives of a network design task may not be easy to specify for an architect. We argue for, and present a structured approach where the objectives of a network design task are learnt through iterative interactions with the architect. Our approach is inspired by a programming-by-examples approach that has seen success in the programming languages community. However, conventional program synthesis techniques do not apply because in our context a user can only provide a relative comparison between multiple choices on which one is more desirable, rather than provide an exact output for a given input. We propose a novel comparative synthesis approach to tackle these challenges. We sketch the approach, present promising preliminary results, and discuss future research questions. 
    more » « less