Search

This paper proposes an exact algorithm to solve the one-to-one multiobjective shortest path problem. The solution involves determining a set of nondominated paths between two given nodes in a graph that minimizes several objective functions. This study is motivated by the application of this solution method to determine cycling itineraries. The proposed algorithm improves upon a label-correcting algorithm to rapidly solve the problem on large graphs (i.e., up to millions of nodes and edges). To verify the performance of the proposed algorithm, we use computational experiments to compare it with the best-known methods in the literature. The numerical results confirm the efficiency of the proposed algorithm. Summary of Contribution: The paper deals with a classic operations research problem (the one-to-one multiobjective shortest path problem) and is motivated by a real application for cycling itineraries. An efficient method is proposed and is based on a label-correcting algorithm into which several additional improvement techniques are integrated. Computational experiments compare this algorithm with the best-known methods in the literature to validate the performance on large-size graphs (Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) instances from the ninth DIMACS challenge). New instances from the context of cycling itineraries are also proposed. [ABSTRACT FROM AUTHOR]

We describe an algorithm to position a rigid surface so as to make its cross-section by a given plane match a given curve in that plane, a problem relevant to model-based medical imaging. After building an atlas of cross-sections of the surface and searching it for a best position to start from, each iteration of the algorithm (1) determines a vector field along the intersection curve that will improve its matching with the target curve, and (2) computes and applies a small displacement of the surface whose effect on the intersection will approximate best the required vector field. Computations use least-square techniques, an exponential formula for Lie groups of transformations, and generic properties of cross-sections. Experiments with an implementation are reported and theoretical tools for justifying and improving the algorithm, some of them based on Catastrophe Theory, are outlined. [Copyright &y& Elsevier]

To limit greenhouse gas emissions in the public transportation sector, transit authorities are constantly increasing the proportion of electric buses (EBs) in their fleets. Due to space and budget constraints, more often than not, the number of chargers that can be installed at the depots is less than the number of EBs in the fleet. Moreover, even if there is one charger for each EB, it is virtually impossible to use all the chargers at the same time due to maximum power grid constraints. Thus, there is a need to devise optimization techniques that help to recharge the buses in an efficient and acute way, taking into account these charging infrastructure capacity constraints. In this study, we consider a multi-day electric bus assignment and overnight recharge scheduling problem that can be briefly stated as follows. Given a set of vehicle blocks (sequences of timetabled bus trips performed by the same bus on a given day) to be operated over several days, a set of identical EBs, and a set of chargers available at the depot whose charging function is a piecewise linear function, the problem consists in assigning an EB to each block and to schedule the overnight recharging operations at the depot such that the EBs never run out of energy when performing their blocks and the depot charging capacity is never exceeded. The objective is twofold: minimizing the total charging costs and minimizing the impact of the charging decisions in the long-term health of the batteries. We first model this problem as a mixed integer linear program (MILP) that can be solved with a commercial solver. Then, to yield faster computational times, we develop two multi-phase matheuristics based on the MILP. To show the interest of considering a multiple-day horizon, we introduce two other matheuristics that mimic current industrial practices and solve the problem sequentially, one day at a time. To evaluate all these algorithms, we use a set of 264 instances generated from data of an EB operator. • We introduce the multi-day electric bus assignment and overnight recharge scheduling problem. • We provide a (non-trivial) mixed integer programming formulation. • We introduce two matheuristics based on mathematical programming. • We report experiments on real-world instances provided by an industrial partner. [ABSTRACT FROM AUTHOR]

A gene expression atlas is an essential resource to quantify and understand the multiscale processes of embryogenesis in time and space. The automated reconstruction of a prototypic 4D atlas for vertebrate early embryos, using multicolor fluorescence in situ hybridization with nuclear counterstain, requires dedicated computational strategies. To this goal, we designed an original methodological framework implemented in a software tool called Match-IT. With only minimal human supervision, our system is able to gather gene expression patterns observed in different analyzed embryos with phenotypic variability and map them onto a series of common 3D templates over time, creating a 4D atlas. This framework was used to construct an atlas composed of 6 gene expression templates from a cohort of zebrafish early embryos spanning 6 developmental stages from 4 to 6.3 hpf (hours post fertilization). They included 53 specimens, 181,415 detected cell nuclei and the segmentation of 98 gene expression patterns observed in 3D for 9 different genes. In addition, an interactive visualization software, Atlas-IT, was developed to inspect, supervise and analyze the atlas. Match-IT and Atlas-IT, including user manuals, representative datasets and video tutorials, are publicly and freely available online. We also propose computational methods and tools for the quantitative assessment of the gene expression templates at the cellular scale, with the identification, visualization and analysis of coexpression patterns, synexpression groups and their dynamics through developmental stages. [ABSTRACT FROM AUTHOR]