Unexpected disruptions in urban rail transit systems cause the infeasibility of the initial train schedule and delays or cancelations of a lot of trains. Even though some recent studies begun to address the rolling stock and timetable optimization problem (RSTO), there is still a large gap between theoretical models and practical applications due to the real-time requirements of train rescheduling decisions. In this work, we first model RSTO using a path-based formulation, in which each path refers to a spatial-temporal trajectory of a rescheduled train in the considered network. The optimal set of paths can minimize the expected cost of train cancelation and train delay time. Our formulation also considers a series of operational constraints, such as train headway constraints, short-turning constraints and rolling stock constraints. We develop an efficient branch-and-price framework that decomposes the problem into a restricted master problem and a set of pricing subproblems, where we iteratively generate promising paths with negative reduce costs. We show that each subproblem is a resource-constrained shortest path problem and can be solved efficiently by an improved label setting algorithm by proving its optimality conditions. We compare the tightness of our new path-based formulation with state-of-art formulations and test our branch-and-price approach on real-world instances from Beijing rail transit. The results show that our approach can generate near-optimal solutions in less than three minutes with small duality gap, which evidently outperforms existing formulations and fulfills the requirement of rail managers in practical applications. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72288101 and 72322022]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0391 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0391 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The coupled lot-sizing and cutting-stock problem has been a challenging and significant problem for industry, and has therefore received sustained research attention. The quality of the solution is a major determinant of cost performance in related production and inventory management systems, and therefore there is intense pressure to develop effective practical solutions. In the literature, a number of heuristics have been proposed for solving the problem. However, the heuristics are limited in obtaining high solution qualities. This paper proposes a new progressive selection algorithm that hybridizes heuristic search and extended reformulation into a single framework. The method has the advantage of generating a strong bound using the extended reformulation, which can provide good guidelines on partitioning and sampling in the heuristic search procedure to ensure an efficient solution process. We also analyze per-item and per-period Dantzig–Wolfe decompositions of the problem and present theoretical comparisons. The master problem of the per period Dantzig–Wolfe decomposition is often degenerate, which results in a tailing-off effect for column generation. We apply a hybridization of Lagrangian relaxation and stabilization techniques to improve the convergence. The discussion is followed by extensive computational tests, where we also perform detailed statistical analyses on various parameters. Comparisons with other methods indicate that our approach is computationally tractable and is able to obtain improved results. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0746 .

Establishing family relationships, such as parentage and sibling relationships, is fundamental in biological research, especially in wild species, as they are often important to understanding evolutionary, ecological, and behavioral processes. Because it is commonly impossible to determine familial relationships from field observations alone, the reconstruction of sibling relationships often depends on informative genetic markers coupled with accurate sibling reconstruction algorithms. Most studies in the literature reconstruct sibling relationships using methods that are based on either statistical analyses (i.e., likelihood estimation) or combinatorial concepts (i.e., Mendelian inheritance laws) of genetic data. We present a novel computational framework that integrates both combinatorial concepts and statistical analyses into one sibling reconstruction optimization model. To solve this integrated model, we propose a column-generation approach with a branch-and-price method. Under the assumption of parsimonious reconstruction, the master problem is to find the minimum set of sibling groups to cover the tested population. Pricing subproblems, which include both statistical similarity and combinatorial concepts of genetic data, are iteratively solved to generate high-quality sibling group candidates. Tested on real biological data sets, our approach efficiently provides reconstruction results that are more accurate than those provided by other state-of-the-art reconstruction algorithms.

This study focuses on the information extraction from reported sensor data in the communication system of wide-area-search munitions (WASMs). Such sensor data could be erroneous and inconsistent. For example, two WASMs might detect the same target, but associate it with two different targets and tracks. Similarly, two WASMs might detect two distinct targets, but recognize them as the same target. The research challenge is how to fuse both accurate and inaccurate information broadcasted from WASMs, and reconstruct the battle space for accurate target tracking. For each of the detected target points, WASMs provide its location information, detection time, and directional velocity. We, herein, propose a target clustering approach to group target points detected by WASMs and identify the track of individual targets. Our approach differs from traditional clustering techniques as it performs clustering using the time and orientation information, in addition to the distance in the Euclidean space. Our approach employs a network modeling technique to reconstruct all target points and their feasible movement, and a new optimization technique to find the most probable target tracks. Our approach can also determine the optimal number of clusters (targets) automatically from the input data. In this study, distributed interactive simulation, a real-time simulation of a network's information exchange, is used to generate battle space test instances that are used in evaluating the proposed framework. Based on seven realistically simulated instances, the computational results show that our approach provides extremely accurate target-tracking results in a timely fashion. We also compare our results with those obtained using the k-means clustering technique. On average, our approach reconstructs the real target tracks with about 95% accuracy in less than 10 s, while the k-means clustering results yields about 80% accuracy in a similar computational time.

As electronic records (e.g., medical records and technical defect records) accumulate, the retrieval of a record from a past instance with the same or similar circumstances, has become extremely valuable. This is because a past record may contain the correct diagnosis or correct solution to the current circumstance. We refer to the two records of the same or similar circumstances asmasterandduplicaterecords. Current record retrieval techniques are lacking when applied to this special master defect record retrieval problem. In this study, we propose a new paradigm for master defect record retrieval using network-based feature association (NBFA). We train the master record retrieval process by constructing feature associations to limit the search space. The retrieval paradigm was employed and tested on a real-world large-scale defect record database from a telecommunications company. The empirical results suggest that the NBFA was able to significantly improve the performance of master record retrieval, and should be implemented in practice. This paper presents an overview of technical aspects of the master defect record retrieval problem, describes general methodologies for retrieval of master defect records, proposes a new feature association paradigm, provides performance assessments on real data from a telecommunications company, and highlights difficulties and challenges in this line of research that should be addressed in the future.

In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon's benchmark test cases for VRPTW. Experimental results show that our approach yields very good solutions when compared with the benchmarking solutions.