Road pavement upgrade scheduling accounting for minimizing congestion.

Road pavement maintenance and upgrades (RPU) need to be scheduled in a way that minimises congestion across the road network and matches the schedule with the availability of equipment and skilled labourers to ensure that they are completed on time. RPU should not introduce unbearable congestion around blocked lanes or roads, and increased traffic due to ongoing road upgrades needs to be transferred to alternative routes. In situations where multiple upgrades are planned together, the scheduled road closures should be coordinated to not block alternative routes. While extensive studies have been conducted separately on scheduling and routing, limited research has linked these processes together, and only in restricted scenarios. In this paper, we investigate how to minimise the disruption of a set of road maintenance tasks based on their interaction with other tasks. We propose a new approach for scheduling a set of road maintenance tasks, some at the same time and others at different times, to minimise overall disruption. The proposed approach has two phases: (1) identify the local area affected by the RPU, and (2) determine which upgrades can be planned together to minimise congestion. The comparison of the results shows how the novel optimized approach identifies a better schedule to minimise congestion.

High-Quality Ultra-Compact Grid Layout of Grouped Networks.

Prior research into network layout has focused on fast heuristic techniques for layout of large networks, or complex multi-stage pipelines for higher quality layout of small graphs. Improvements to these pipeline techniques, especially for orthogonal-style layout, are difficult and practical results have been slight in recent years. Yet, as discussed in this paper, there remain significant issues in the quality of the layouts produced by these techniques, even for quite small networks. This is especially true when layout with additional grouping constraints is required. The first contribution of this paper is to investigate an ultra-compact, grid-like network layout aesthetic that is motivated by the grid arrangements that are used almost universally by designers in typographical layout. Since the time when these heuristic and pipeline-based graph-layout methods were conceived, generic technologies (MIP, CP and SAT) for solving combinatorial and mixed-integer optimization problems have improved massively. The second contribution of this paper is to reassess whether these techniques can be used for high-quality layout of small graphs. While they are fast enough for graphs of up to 50 nodes we found these methods do not scale up. Our third contribution is a large-neighborhood search meta-heuristic approach that is scalable to larger networks.

BetaSearch: a new method for querying ß-residue motifs.

BACKGROUND: Searching for structural motifs across known protein structures can be useful for identifying unrelated proteins with similar function and characterising secondary structures such as ß-sheets. This is infeasible using conventional sequence alignment because linear protein sequences do not contain spatial information. ß-residue motifs are ß-sheet substructures that can be represented as graphs and queried using existing graph indexing methods, however, these approaches are designed for general graphs that do not incorporate the inherent structural constraints of ß-sheets and require computationally-expensive filtering and verification procedures. 3D substructure search methods, on the other hand, allow ß-residue motifs to be queried in a three-dimensional context but at significant computational costs. FINDINGS: We developed a new method for querying ß-residue motifs, called BetaSearch, which leverages the natural planar constraints of ß-sheets by indexing them as 2D matrices, thus avoiding much of the computational complexities involved with structural and graph querying. BetaSearch exhibits faster filtering, verification, and overall query time than existing graph indexing approaches whilst producing comparable index sizes. Compared to 3D substructure search methods, BetaSearch achieves 33 and 240 times speedups over index-based and pairwise alignment-based approaches, respectively. Furthermore, we have presented case-studies to demonstrate its capability of motif matching in sequentially dissimilar proteins and described a method for using BetaSearch to predict ß-strand pairing. CONCLUSIONS: We have demonstrated that BetaSearch is a fast method for querying substructure motifs. The improvements in speed over existing approaches make it useful for efficiently performing high-volume exploratory querying of possible protein substructural motifs or conformations. BetaSearch was used to identify a nearly identical ß-residue motif between an entirely synthetic (Top7) and a naturally-occurring protein (Charcot-Leyden crystal protein), as well as identifying structural similarities between biotin-binding domains of avidin, streptavidin and the lipocalin gamma subunit of human C8.