Search

Mobility-on-demand (MoD) systems consist of a fleet of shared vehicles that can be hailed for one-way point-to-point trips. The total distance driven by the vehicles and the fleet size can be reduced by employing ridesharing, i.e., by assigning multiple passengers to one vehicle. However, finding the optimal passenger-vehicle assignment in an MoD system is a hard combinatorial problem. In this work, we demonstrate how the VGA method, a recently proposed systematic method for ridesharing, can be used to compute the optimal passenger-vehicle assignments and corresponding vehicle routes in a massive-scale MoD system. In contrast to existing works, we solve all passenger-vehicle assignment problems to optimality, regularly dealing with instances containing thousands of vehicles and passengers. Moreover, to examine the impact of using optimal ridesharing assignments, we compare the performance of an MoD system that uses optimal assignments against an MoD system that uses assignments computed using insertion heuristic and against an MoD system that uses no ridesharing. We found that the system that uses optimal ridesharing assignments subject to the maximum travel delay of 4 minutes reduces the vehicle distance driven by 57 % compared to an MoD system without ridesharing. Furthermore, we found that the optimal assignments result in a 20 % reduction in vehicle distance driven and 5 % lower average passenger travel delay compared to a system that uses insertion heuristic., Comment: Non-revised version (before first submission). Currently published online in the Journal of Intelligent Transportation Systems

Colonies of Saccharomyces cerevisiae laboratory strains pass through specific developmental phases when growing on solid respiratory medium. During entry into the so-called alkali phase, in which ammonia signaling is initiated, 2 prominent cell types are formed within the colonies: U cells in upper colony regions, which have a longevity phenotype and activate the expression of a large number of metabolic genes, and L cells in lower regions, which die more quickly and exhibit a starvation phenotype. Here, we performed a detailed analysis of the activities of enzymes of central carbon metabolism in lysates of both cell types and determined several fermentation end products, showing that previously reported expression differences are reflected in the different enzymatic capabilities of each cell type. Hence, U cells, despite being grown on respiratory medium, behave as fermenting cells, whereas L cells rely on respiratory metabolism and possess active gluconeogenesis. Using a spectrum of different inhibitors, we showed that glycolysis is essential for the formation, and particularly, the survival of U cells. We also showed that β-1,3-glucans that are released from the cell walls of L cells are the most likely source of carbohydrates for U cells.

We consider a system consisting of multiple mobile robots in which the user can at any time issue relocation tasks ordering one of the robots to move from its current location to a given destination location. In this paper, we deal with the problem of finding a trajectory for each such relocation task that avoids collisions with other robots. The chosen robot plans its trajectory so as to avoid collision with other robots executing tasks that were issued earlier. We prove that if the destination of each task is an endpoint in a so-called well-formed infrastructure, then this mechanism is guaranteed to always succeed and provide a trajectory for the robot that reaches the destination without any collisions. The time-complexity of the approach is only quadratic in the number of robots. We demonstrate the applicability of the presented method on several real-world maps and compare its performance against a popular reactive approach that attempts to solve the collisions locally. Besides being dead-lock free, the presented approach generates trajectories that reach the goal significantly faster (up to 48% improvement) than the trajectories resulting from local collision avoidance.

Nutrient sensing and metabolic reprogramming are crucial for metazoan cell aging and tumor growth. Here, we identify metabolic and regulatory parallels between a layered, multicellular yeast colony and a tumor-affected organism. During development, a yeast colony stratifies into U and L cells occupying the upper and lower colony regions, respectively. U cells activate a unique metabolism controlled by the glutamine-induced TOR pathway, amino acid-sensing systems (SPS and Gcn4p) and signaling from mitochondria with lowered respiration. These systems jointly modulate U cell physiology, which adapts to nutrient limitations and utilize the nutrients released from L cells. Stress-resistant U cells share metabolic pathways and other similar characteristics with tumor cells, including the ability to proliferate. L cells behave similarly to stressed and starving cells, which activate degradative mechanisms to provide nutrients to U cells. Our data suggest a nutrient flow between both cell types, resembling the Cori cycle and glutamine-NH(4)(+) shuttle between tumor and healthy metazoan cells.

When growing on solid surfaces, yeast, like other microorganisms, develops organized multicellular populations (colonies and biofilms) that are composed of differentiated cells with specialized functions. Life within these populations is a prevalent form of microbial existence in natural settings that provides the cells with capabilities to effectively defend against environmental attacks as well as efficiently adapt and survive long periods of starvation and other stresses. Under such circumstances, the fate of an individual yeast cell is subordinated to the profit of the whole population. In the past decade, yeast colonies, with their complicated structure and high complexity that are also developed under laboratory conditions, have become an excellent model for studies of various basic cellular processes such as cell interaction, signaling, and differentiation. In this paper, we summarize current knowledge on the processes related to chronological aging, adaptation, and longevity of a colony cell population and of its differentiated cell constituents. These processes contribute to the colony ability to survive long periods of starvation and mostly differ from the survival strategies of individual yeast cells.

During their development and aging on solid substrates, yeast giant colonies produce ammonia, which acts as a quorum sensing molecule. Ammonia production is connected with alkalization of the surrounding medium and with extensive reprogramming of cell metabolism. In addition, ammonia signaling is important for both horizontal (colony centre versus colony margin) and vertical (upper versus lower cell layers) colony differentiations. The centre of an aging differentiated giant colony is thus composed of two major cell subpopulations, the subpopulation of long-living, metabolically active and stress-resistant cells that form the upper layers of the colony and the subpopulation of stress-sensitive starving cells in the colony interior. Here, we show that microcolonies originating from one cell pass through similar developmental phases as giant colonies. Microcolony differentiation is linked to ammonia signaling, and cells similar to the upper and lower cells of aged giant colonies are formed even in relatively young microcolonies. A comparison of the properties of these cells revealed a number of features that are similar in microcolonies and giant colonies as well as a few that are only typical of chronologically aged giant colonies. These findings show that colony ageper seis not crucial for colony differentiation.

Enzymes scavenging reactive oxygen species (ROS) are important for cell protection during stress and aging. A deficiency in these enzymes leads to ROS imbalance, causing various disorders in many organisms, including yeast. In contrast to liquid cultures, where fitness of the yeast population depends on its ROS scavenging capability, the present study suggests that Saccharomyces cerevisiae cells growing in colonies capable of ammonia signaling use a broader protective strategy. Instead of maintaining high levels of antioxidant enzymes for ROS detoxification, colonies activate an alternative metabolism that prevents ROS production. Colonies of the strain deficient in cytosolic superoxide dismutase Sod1p thus developed the same way as wild type colonies. They produced comparable levels of ammonia and underwent similar developmental changes (expression of genes of alternative metabolism and center margin differentiation in ROS production, cell death occurrence, and activities of stress defense enzymes) and did not accumulate stress-resistant suppressants. An absence of cytosolic catalase Ctt1p, however, brought colonies developmental problems, which were even more prominent in the absence of mitochondrial Sod2p. sod2Delta and ctt1Delta colonies failed in ammonia production and sufficient activation of the alternative metabolism and were incapable of center margin differentiation, but they did not increase ROS levels. These new data indicate that colony disorders are not accompanied by ROS burst but could be a consequence of metabolic defects, which, however, could be elicited by imbalance in ROS produced in early developmental phases. Sod2p and homeostasis of ROS may participate in regulatory events leading to ammonia signaling.