We analyze spatio-temporal routing under various constraints specific to multi-robot applications. Spatio-temporal routing requires multiple robots to visit spatial locations at specified time instants, while optimizing certain criteria like the total distance traveled, or the total energy consumed. Such a spatio-temporal concept is intuitively demonstrable through music (e.g. a musician routes multiple fingers to play a series of notes on an instrument at specified time instants). As such, we showcase much of our work on routing through this medium. Particular to robotic applications, we analyze constraints like maximum velocities that the robots cannot exceed, and information-exchange networks that must remain connected. Furthermore, we consider a notion of heterogeneity where robots and spatial locations are associated with multiple skills, and a robot can visit a location only if it has at least one skill in common with the skill set of that location. To extend the scope of our work, we analyze spatio-temporal routing in the context of a distributed framework, and a dynamic environment.

The research reported in this thesis considers the classical combinatorial optimization problem known as the Generalized Assignment Problem (GAP). Since the mid 1970's researchers have been developing solution approaches for this particular type of problem due to its importance both in practical and theoretical terms. Early attempts at solving GAP tended to use exact integer programming techniques such as Branch and Bound. Although these tended to be reasonably successful on small problem instances they struggle to cope with the increase in computational effort required to solve larger instances. The increase in available computing power during the 1980's and 1990's coincided with the development of some highly efficient heuristic approaches such as Tabu Search (TS), Genetic Algorithms (GA) and Simulated Annealing (SA). Heuristic approaches were subsequently developed that were able to obtain high quality solutions to larger and more complex instances of GAP. Most of these heuristic approaches were able to outperform highly sophisticated commercial mathematical programming software since the heuristics tend to be tailored to the problem and therefore exploit its structure. A new approach for solving GAP has been developed during this research that combines the exact Branch and Bound approach and the heuristic strategy of Tabu Search to produce a hybrid algorithm for solving GAP. This approach utilizes the mathematical programming software Xpress-MP as a Branch and Bound solver in order to solve sub-problems that are generated by the Tabu Search guiding heuristic. Tabu Search makes use of memory structures that record information about attributes of solutions visited during the search. This information is used to guide the search and in the case of the hybrid algorithm to generate sub problems to pass to the Branch and Bound solver. The new algorithm has been developed, imp lemented and tested on benchmark test problems that are extremely challenging and a comprehensive report and analysis of the experimentation is reported in this thesis.

This thesis compares actual and perceived travel times and presents a model for predicting traffic flows when there is a network disruption. The goal of this research is to demonstrate the necessity of accounting for possible differences in travel time perception and actual travel times, and also to show trends in how the route choices change based on the transformation of the perceived travel times. A pilot test was done to determine actual travel time perceptions, and the results provided the foundation for the tests presented in this thesis and the model framework. The model is separated into three phases: equilibrium assignment, link travel time transform, and logit assignment. The transform of the link travel times is best represented by an inverse cumulative Normal distribution, and the corresponding values provide quantifiable measure of the severity of a traffic network disruption. The methodology is presented and applied to two test networks to demonstrate the resulting route choice patterns. Both networks are tested for three severity levels and three levels of demand. / text

The transportation routing map is increasingly used in various transportation network modeling applications such as vehicle navigation and traffic assignment modeling. A typical navigation GIS map contains all detailed road facility layers and may not be as computationally efficient as a lower-resolution map for path finding. A lower-resolution transportation routing map retains only route-finding related roadways and is efficient for path finding but may result in sub-optimal routes because of misclassification links. With the goal in balancing the traffic analysis requirement of intended application and computation requirements of transportation navigation and traffic assignment, the systematic abstraction of the lower-resolution transportation routing map from high resolution map is an important and non-trivial task. For vehicle navigation applications, the traffic analysis requirement is the shortest path quality. An innovative transportation routing map abstraction method or Connectivity Enhancement Algorithm (CEA) is proposed to deal with vehicle navigation application routing map abstraction. The algorithm starts from a low-resolution network and keeps updating the map by adding links and nodes when it processes each search set. The outcome of the algorithm is an abstract map that retains the original detailed map's hierarchical structure with quality topological connectivity at a significant computations saving. With the development of traffic assignment modeling, a detailed network is desired to describe the real world traffic network. It is the consensus that one should not directly apply a GIS map blind-sight without a systematic approach and unnecessarily overuse the network details causes excessive run time. The traffic analysis requirement of those applications is the dynamic user equilibrium (DUE) condition network performance is identical or near-identical with high resolution network. The lowest network resolution level that meets the requirements of emerging traffic analysis is not easy to determine. The proposed traffic analysis network abstraction method gives a solution for this problem. It is an iterative network abstraction approach and considers the link travel time with DUE traffic condition. The case study and numerical analysis prove that the two network abstraction methods are sound and promising. The transportation routing map abstraction method could detect most misclassification links and is robust for different network scales. The abstracted navigation map provides the identical or near-identical SP cost/travel time for any OD pair while the computation burden is much lighter than that on original map. In another hand, the case studies about the traffic analysis network abstraction tell that the method converges very quick and the rendered the abstracted network that has lowest resolution of network or least links and nodes but the DUE condition network performance or trips cost/travel time is much closer to that on the original map.

The cell transmission model (CTM) based single destination system optimal dynamic traffic assignment (SD-SO-DTA) model has been widely applied to situations such as mass evacuations on a transportation network. Although formulated as a linear programming (LP) model, embedded multi-period cell network representation yields an extremely large model for real-size networks. As a result, most of these models are not solvable using existing LP solvers. Solutions obtained by LP also involve holding vehicles at certain locations, violating CTM flow dynamics. This doctoral research is aimed at developing innovative algorithms that overcome both computational efficiency and solution realism issues. We first prove that the LP formulation of the SD-SO-DTA problem is equivalent to the earliest arrival flow (EAF), and then develop efficient algorithms to solve EAF. Two variants of the algorithm are developed under different model assumptions and network operating conditions. For the case of time-varying network parameters, we develop a network flow algorithm on a time-expanded network. The main challenge in this approach is to address the issue of having backward wave speed lower than forward wave speed. This situation leads to non-typical constraints involving coefficients with value of less than 1. In this dissertation we develop a new network algorithm to solve this problem in optimal, even with coefficients of value less than 1. Additionally, the developed approach solves for optimal flows that exhibit non-vehicle-holding properties, which is a major breakthrough compared to all existing solution techniques for SD-SODTA. For the case of time-invariant network parameters, we reduce the SD-SO-DTA to a standard EAF problem on a dynamic network, which is constructed on the original roadway network without dividing it into cells. We prove that the EAF under free flow status is one of the optimal solutions of SD-SO-DTA, if cell properties follow a trapezoidal/triangular fundamental diagram. We use chain flows obtained on a static network to induce dynamic flows, an approach applicable to large-scale networks. Another contribution of this research is to provide a simple and practical algorithm solving the EAF with multiple sources, which has been an active research area for many years. Most existing studies involve submodular function optimization as subroutines, and thus are not practical for real-life implementation. This study’s contribution in this regard is the development of a practical algorithm that avoids submodular function optimization. The main body of the given method is comprised of |S⁺| iterations of earliest arrival s - t flow computations, where |S⁺| is the number of sources. Numerical results show that our multi-source EAF algorithm solves the SD-SO-DTA problem with time-invariant parameters to optimum.

Changed governance increased the freedom of schools but also their responsibility, with more scope for interpreting the assignment. Two models of school development were studied to see how they affect school actors’ understanding of assignment and responsibility, the relationship between the commissioner’s exaction of responsibility and the contractor’s assumption of responsibility. Two case studies examine conceptual dimensions of assumption of responsibility. These models and resulting measures shape actors’ understanding of assignment and responsibility, emphasizing different parts of the control system. The Scope for Action Model stresses the role of the local school with a bottom-up strategy for assumption of responsibility. It uses culture analysis to clarify responsibility relations by making actors aware of their accountability and the potential in their assignment. The Effective Schools Model stresses the political level in a top-down strategy. It shows organizational deficiencies in relation to the assignment and the responsibility. The models increased cooperation between professionals, exposing the organization and its boundaries, management, and occupational roles. Activities became more pupil-oriented, highlighting the task of upbringing and teaching. Lack of time, poor organizational structures, and increased administration obstructed the fulfilment of the assignment. The models led to the exposure and creation of responsibility structures for organization, management, communication and cooperation. Responsibility structures were created through firmer cooperation. These measures furthered individual and collective learning processes and (re)shaped the professionals’ understanding of assignment and responsibility. Professional autonomy is essential for commitment, motivation, and understanding. It is concluded that knowledge of the school’s responsibility reduces the discrepancy and helps professionals to improve their competence and develop school.

Civilinės teisinės apyvartos dalyviai neretai savo teises ir pareigas realizuoja, taikydami asmenų pasikeitimo prievolėje institutą, tačiau netinkamas minėtą institutą reglamentuojančių teisės normų aiškinimas gali tapti kliūtimi įgyvendinant ir vykdant asmenų teises bei pareigas. Todėl darbe keliama problema: kaip turi būti aiškinami kai kurie asmenų pasikeitimo prievolėje aspektai ir kokių reikalavimų turi būti laikomasi, siekiant tinkamai realizuoti kreditoriaus ir skolininko pasikeitimo sutartinėje prievolėje institutus. Siekiant išspręsti iškeltą problemą šiame darbe atskleidžiama asmenų pasikeitimo sutartinėje prievolėje samprata, apžvelgiami reikalavimo perleidimo, faktoringo, subrogacijos skolos perkėlimo reglamentavimo ypatumai pagal romėnų teisę, kai kurių užsienio valstybių teisę, būsimąjį Europos civilinį kodeksą, reikalavimo perleidimas ir skolos perkėlimas atskiriami nuo į juos panašių institutų. Darbe taip pat atskleidžiami esminiai reikalavimo perleidimo ir faktoringo teoriniai ir praktiniai aspektai: atvejai, kai draudžiama ar ribojama perleisti reikalavimo teisę, skolininko padėtis perleidžiant reikalavimą, cesijos ir faktoringo sutarties samprata, forma, turinys, pradinio kreditoriaus atsakomybės ypatumai. Parodant kai kuriuos skolininko pasikeitimo sutartinėje prievolėje aspektus, atkreipiamas dėmesys į draudimus perkelti skolą, skolos perkėlimo būdus, skolos perkėlimo sutarties sampratą, formą bei turinį, analizuojama kreditoriaus sutikimo reikšmė, skolos... [to full text] / The participants of civil legal turnover often use the institute of a change of persons to implement their rights and obligations. However, inaccurate interpretation of legal norms regulating this institute may hamper the realization of the rights and obligations. Therefore, the problem arises - how some aspects of a change of persons in an obligation should be interpreted and what particular requirements should be followed in pursuance of appropriate realization of institutes of a change of creditor or debtor in a contractual obligation. In order to solve the problem pointed out this work reveals the concept of a change of persons in a contractual obligation, analyses peculiarities of regulation of the assignment of claims, factoring, subrogation and delegation of debts upon Roman law, law of some of the foreign countries and the future European Civil Code, as well as distinguishes the assignment of claims and delegation of debts from similar institutes. The work also covers the essential theoretical and practical aspects of the assignment of claims and factoring: the injunctions and restrictions to assign a claim, the status of the debtor of the assignment of the claim, the conception of the cessio and factoring agreements, its form, content, and undertakings of an assignor. While analysing some aspects of the change of a debtor in a contractual obligation the analysis of restrictions to delegate a debt, the ways of delegation, the conception of the agreement to delegate a... [to full text]

Public transit is considered a cost-effective alternative to mitigate the effects of traffic gridlock through the implementation of innovative service designs, and deploying new smart systems for operations control and traveller information. Public transport planners use transit assignment models to predict passenger loads and levels of service. Existing transit assignment approaches have limitations in evaluating the effects of information technologies, since they are neither sensitive to the types of information that may be provided to travellers nor to the traveller’s response to that information. Moreover, they are not adequate for evaluating the impacts of Intelligent Transportation Systems (ITS) deployments on service reliability, which in turn affect passengers’ behaviour. This dissertation presents an innovative transit assignment framework, namely the MIcrosimulation Learning-based Approach to TRansit ASsignment – MILATRAS. MILATRAS uses learning and adaptation to represent the dynamic feedback of passengers’ trip choices and their adaptation to service performance. Individual passengers adjust their behaviour (i.e. trip choices) according to their experience with the transit system performance. MILATRAS introduces the concept of ‘mental model’ to maintain and distinguish between the individual’s experience with service performance and the information provided about system conditions. A dynamic transit path choice model is developed using concepts of Markovian Decision Process (MDP) and Reinforcement Learning (RL). It addresses the departure time and path choices with and without information provision. A parameter-calibration procedure using a generic optimization technique (Genetic Algorithms) is also proposed. A proof-of-concept prototype has been implemented; it investigates the impact of different traveller information provision scenarios on departure time and path choices, and network performance. A large-scale application, including parameter calibration, is conducted for the Toronto Transit Commission (TTC) network. MILATRAS implements a microsimulation, stochastic (nonequilibrium-based) approach for modelling within-day and day-to-day variations in the transit assignment process, where aggregate travel patterns can be extracted from individual choices. MILATRAS addresses many limitations of existing transit assignment models by exploiting methodologies already established in the areas of traffic assignment and travel behaviour modeling. Such approaches include the microsimulation of transportation systems, learning-based algorithms for modelling travel behaviour, agent-based representation for travellers, and the adoption of Geographical Information Systems (GIS). This thesis presents a significant step towards the advancement of the modelling for the transit assignment problem by providing a detailed operational specification for an integrated dynamic modelling framework – MILATRAS.

Public transit is considered a cost-effective alternative to mitigate the effects of traffic gridlock through the implementation of innovative service designs, and deploying new smart systems for operations control and traveller information. Public transport planners use transit assignment models to predict passenger loads and levels of service. Existing transit assignment approaches have limitations in evaluating the effects of information technologies, since they are neither sensitive to the types of information that may be provided to travellers nor to the traveller’s response to that information. Moreover, they are not adequate for evaluating the impacts of Intelligent Transportation Systems (ITS) deployments on service reliability, which in turn affect passengers’ behaviour. This dissertation presents an innovative transit assignment framework, namely the MIcrosimulation Learning-based Approach to TRansit ASsignment – MILATRAS. MILATRAS uses learning and adaptation to represent the dynamic feedback of passengers’ trip choices and their adaptation to service performance. Individual passengers adjust their behaviour (i.e. trip choices) according to their experience with the transit system performance. MILATRAS introduces the concept of ‘mental model’ to maintain and distinguish between the individual’s experience with service performance and the information provided about system conditions. A dynamic transit path choice model is developed using concepts of Markovian Decision Process (MDP) and Reinforcement Learning (RL). It addresses the departure time and path choices with and without information provision. A parameter-calibration procedure using a generic optimization technique (Genetic Algorithms) is also proposed. A proof-of-concept prototype has been implemented; it investigates the impact of different traveller information provision scenarios on departure time and path choices, and network performance. A large-scale application, including parameter calibration, is conducted for the Toronto Transit Commission (TTC) network. MILATRAS implements a microsimulation, stochastic (nonequilibrium-based) approach for modelling within-day and day-to-day variations in the transit assignment process, where aggregate travel patterns can be extracted from individual choices. MILATRAS addresses many limitations of existing transit assignment models by exploiting methodologies already established in the areas of traffic assignment and travel behaviour modeling. Such approaches include the microsimulation of transportation systems, learning-based algorithms for modelling travel behaviour, agent-based representation for travellers, and the adoption of Geographical Information Systems (GIS). This thesis presents a significant step towards the advancement of the modelling for the transit assignment problem by providing a detailed operational specification for an integrated dynamic modelling framework – MILATRAS.

Tabu search based algorithms are among the widely used heuristic algorithms for combinatorial optimization problems. In this project, we propose an improved enhanced tabu search algorithm for the well-known combinatorial optimization problem, the quadratic assignment problem (QAP). The new algorithm was tested on a number of instances from the library of the QAP instances  QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to the earlier "pure" tabu search algorithms on many instances of the QAP.