Model checking is a fully-automatic formal verification method that has been extremely successful in validating and verifying safety-critical systems in the past three decades. In the past fifteen years, there has been a lot of work in extending many model checking algorithms over finite-state systems to finitely representable infinitestate systems. Unlike in the case of finite systems, decidability can easily become a problem in the case of infinite-state model checking. In this thesis, we present generic and specific techniques that can be used to derive decidability with near-optimal computational complexity for various model checking problems over infinite-state systems. Generic techniques and specific techniques primarily differ in the way in which a decidability result is derived. Generic techniques is a “top-down” approach wherein we start with a Turing-powerful formalismfor infinitestate systems (in the sense of being able to generate the computation graphs of Turing machines up to isomorphisms), and then impose semantic restrictions whereby the desired model checking problem becomes decidable. In other words, to show that a subclass of the infinite-state systems that is generated by this formalism is decidable with respect to the model checking problem under consideration, we will simply have to prove that this subclass satisfies the semantic restriction. On the other hand, specific techniques is a “bottom-up” approach in the sense that we restrict to a non-Turing powerful formalism of infinite-state systems at the outset. The main benefit of generic techniques is that they can be used as algorithmic metatheorems, i.e., they can give unified proofs of decidability of various model checking problems over infinite-state systems. Specific techniques are more flexible in the sense they can be used to derive decidability or optimal complexity when generic techniques fail. In the first part of the thesis, we adopt word/tree automatic transition systems as a generic formalism of infinite-state systems. Such formalisms can be used to generate many interesting classes of infinite-state systems that have been considered in the literature, e.g., the computation graphs of counter systems, Turing machines, pushdown systems, prefix-recognizable systems, regular ground-tree rewrite systems, PAprocesses, order-2 collapsible pushdown systems. Although the generality of these formalisms make most interesting model checking problems (even safety) undecidable, they are known to have nice closure and algorithmic properties. We use these nice properties to obtain several algorithmic metatheorems over word/tree automatic systems, e.g., for deriving decidability of various model checking problems including recurrent reachability, and Linear Temporal Logic (LTL) with complex fairness constraints. These algorithmic metatheorems can be used to uniformly prove decidability with optimal (or near-optimal) complexity of various model checking problems over many classes of infinite-state systems that have been considered in the literature. In fact, many of these decidability/complexity results were not previously known in the literature. In the second part of the thesis, we study various model checking problems over subclasses of counter systems that were already known to be decidable. In particular, we consider reversal-bounded counter systems (and their extensions with discrete clocks), one-counter processes, and networks of one-counter processes. We shall derive optimal complexity of various model checking problems including: model checking LTL, EF-logic, and first-order logic with reachability relations (and restrictions thereof). In most cases, we obtain a single/double exponential reduction in the previously known upper bounds on the complexity of the problems.

Message Passing Interface (MPI) is a standard library interface for writing parallel programs. The MPI specification is broadly used for solving engineering and scientific problems on parallel computers, and MPICH2 is a popular MPI implementation developed at Argonne National Laboratory. The scalability of MPI implementations is very important for building high performance parallel computing applications. The initial TCP (Transmission Control Protocol) network module developed for Nemesis communication sub-system in the MPICH2 library, however, was not scalable in how it established connections: pairwise connections between all of an application's processes were established during the initialization of the application (the library call to MPI_Init), regardless of whether the connections were eventually needed or not. In this work, we have developed a new TCP network module for Nemesis that establishes connections on-demand. The on-demand connection establishment scheme is designed to improve the scalability of the TCP network module in MPICH2 library, aiming to reduce the initialization time and the use of operating system resources of MPI applications. Our performance benchmark results show that MPI_Init in the on-demand connection establishment scheme becomes a fast constant time operation, and the additional cost of establishing connections later is negligible. The on-demand connection establishment between two processes, especially when two processes attempt to connect to each other simultaneously, is a complex task due to race-conditions and thus prone to hard-to-reproduce defects. To assure ourselves of the correctness of the TCP network module, we modeled its design using the SPIN model checker, and verified safety and liveness properties stated as Linear Temporal Logic claims.

This paper deals with the problem of shipping multiple commodities from a single vendor to a single buyer. Each commodity is assumed to be constantly consumed at the buyer, and periodically replenished from the vendor. Furthermore, these replenishments are restricted to happen at discrete time instants, e.g., a certain time of the day or a certain day of the week. At any such time instant, transportation cost depends on the shipment quantity according to certain discount scheme. Specifically, we consider two transportation quantity discount schemes: LTL (less-than-truckload) incremental discount and TL (truckload) discount. For each case, we develop MIP (mixed integer programming) mathematical model whose objective is to make an integrated replenishment and transportation decision such that the total system cost is minimized. We also derive optimal solution properties and give numerical studies to investigate the problem. / Singapore-MIT Alliance (SMA)

Drivers are essential factors affecting the efficiency and management level of a carrier. In this thesis, the driver assignment problem is investigated and methods for obtaining lower total operational costs are introduced for small and medium-sized truck freight transportation companies. Three interrelated research topics, including the following, have been systematically studied. Firstly, extending the traditional costing and Activity-Based Costing (ABC) method, the new Time-Driven Activity-Based Costing (TDABC) method, TDABC-FTC, has been introduced for truck freight companies. Detailed implementation process flow has been designed to streamline the easy incorporation of overhead cost. Fuel costs hold about one-third of the total operational costs of truck freight transportation, and drivers’ driving behaviors heavily influence the fuel consumption rate. In this work, the On-Board Diagnostics (OBD) Ⅱ, GPS tracker and Controller Area Network (CAN) bus are used to retrieve related truck operation data and transfer these data to a central database for later processing to obtain driving behavior parameters. An artificial neural network (ANN) model, built using MATLAB toolbox, is introduced to capture the relations between driving behavior and fuel consumption rate. The fuel consumption indicators for different drivers are then developed to reflect their relative fuel consumption rate quantitatively. The driver assignment problem is modeled as an optimization problem for minimizing the total operational cost of the truck, and the NP-hard problem is solved as a mixed integer programming problem. Two solution methods, Branch and Bound, and the Hungarian algorithm, are used to solve the formulated driver assignment problem. The Hungarian algorithm has been modified to address two particular situations in the driver assignment problem. Numerical experiments are conducted to validate the effectiveness of the newly introduced TDABC model, the fuel saving oriented optimal driver assignment method associating driver behavior to truck fuel consumption rate for different transportation tasks, and the solution methods for the special optimization problems formulated in this work. The newly introduced methods were tested using real truck fleet data, showing considerable benefit of the optimal scheduling techniques, and forming the foundation for further research in this area. / Graduate

abstract: Linear Temporal Logic is gaining increasing popularity as a high level specification language for robot motion planning due to its expressive power and scalability of LTL control synthesis algorithms. This formalism, however, requires expert knowledge and makes it inaccessible to non-expert users. This thesis introduces a graphical specification environment to create high level motion plans to control robots in the field by converting a visual representation of the motion/task plan into a Linear Temporal Logic (LTL) specification. The visual interface is built on the Android tablet platform and provides functionality to create task plans through a set of well defined gestures and on screen controls. It uses the notion of waypoints to quickly and efficiently describe the motion plan and enables a variety of complex Linear Temporal Logic specifications to be described succinctly and intuitively by the user without the need for the knowledge and understanding of LTL specification. Thus, it opens avenues for its use by personnel in military, warehouse management, and search and rescue missions. This thesis describes the construction of LTL for various scenarios used for robot navigation using the visual interface developed and leverages the use of existing LTL based motion planners to carry out the task plan by a robot. / Dissertation/Thesis / M.S. Computer Science 2013

Vérification Formelle et Incrémentale de Spécifications SysML pour la Conception de Systèmes à Base de ComposantsLe travail présenté dans cette thèse est une contribution à la spécification et la vérification des Systèmes à Base de Composants (SBC) modélisé avec le langage SysML. Les SBC sont largement utilisés dans le domaine industrielet ils sont construits en assemblant différents composants réutilisables, permettant ainsi le développement de systèmes complexes en réduisant leur coût de développement. Malgré le succès de l'utilisation des SBC, leur conception est une étape de plus en plus complexe qui nécessite la mise en {\oe}uvre d'approches plus rigoureuses.Pour faciliter la communication entre les différentes parties impliquées dans le développement d'un SBC, un des langages largement utilisé est SysML, qui permet de modéliser, en plus de la structure et le comportement du système, aussi ses exigences. Il offre un standard de modélisation, spécification et documentation de systèmes, dans lequel il est possible de développer un système, partant d'un niveau abstrait, vers des niveaux plus détaillés pouvant aboutir à une implémentation. %Généralement ces systèmes sont faits plus grands parce qu'ils sont développés avec des cadres logiciels.Dans ce contexte nous avons traité principalement deux problématiques.La première est liée au développement par raffinement d'un SBC modélisé uniquement par ses interfaces SysML. Notre contribution permet au concepteur des SBC de garantir formellement qu'une composition d'un ensemble de composants élémentaires et réutilisables raffine une spécification abstraite d'un SBC. Dans cette contribution, nous exploitons les outils: Ptolemy pour la vérification de la compatibilité des composants assemblés, et l'outil MIO Workbench pour la vérification du raffinementLa deuxième problématique traitée concerne la difficulté de déterminer quoi construire et comment le construire, en considérant seulement les exigences du système et des composants réutilisables, donc la question qui en découle est la suivante: comment spécifier une architecture SBC qui satisfait toutes les exigences du système? Nous proposons une approche de vérification formelle incrémentale basée sur des modèles SysML et des automates d'interface pour guider, par les exigences, le concepteur SBC afin de définir une architecture de système cohérente, qui satisfait toutes les exigences SysML proposées. Dans cette approche nous exploitons le model-checker SPIN et la LTL pour spécifier et vérifier les exigences.Mots clés: {Modélisation, Spécifications SysML, Architecture SBC, Raffinement, Compatibilité, Exigences, Propriétés LTL, Promela/SPIN, Ptolemy, MIO Workbench} / Formal and Incremental Verification of SysML Specifications for the Design of Component-Based SystemsThe work presented in this thesis is a contribution to the specification and verification of Component-Based Systems (CBS) modeled in SysML. CBS are widely used on the industrial field, and they are built by assembling various reusable components, allowing developing complex systems at lower cost.Despite the success of the use of CBS, their design is an increasingly complex step that requires the implementation of more rigorous approaches.To ease the communication between the various stakeholders in a CBS development project, one of the widely used modeling languages is SysML, which besides allowing modeling of structure and behavior, it has capabilities to model requirements. It offers a standard for modeling, specifying and documenting systems, wherein it is possible to develop a system, starting from an abstract level, to more detailed levels that may lead to an implementation.In this context, we have dealt mainly two issues. The first one concerns the development by refinement of a CBS, which is described only by its SysML interfaces and behavior protocols. Our contribution allows the designer of CBS to formally ensure that a composition of a set of elementary and reusable components refines an abstract specification of a CBS. In this contribution, we use the tools: Ptolemy for the verification of compatibility of the assembled components and MIO Workbench for refinement verification.The second one concerns the difficulty to decide what to build and how to build it, considering only system requirements and reusable components. Therefore, the question that arises is: how to specify a CBS architecture, which satisfies all system requirements? We propose a formal and incremental verification approach based on SysML models and interface automata to guide, by the requirements, the CBS designer to define a coherent system architecture that satisfies all proposed SysML requirements. In this approach we use the SPIN model-checker and LTL properties to specify and verify requirements.Keywords: {Modeling, SysML specifications, CBS architecture, Refinement, Compatibility, Requirements, LTL properties, Promela/SPIN, Ptolemy, MIO Workbench}

As localizações dos terminais e as rotas de entrega que partem desses terminais são decisões importantes que surgem na concepção de redes de transporte de carga fracionada. Nesses casos, dois problemas independentes precisam ser tratados: o problema da localização de instalações (LAP) e o problema da roteirização dos veículos (VRP). Este trabalho apresenta um modelo matemático para resolver o LAP e o VRP de forma integrada, ou seja, para a resolução do problema de Localização/Roteirização (Location Routing Problem - LRP). De acordo com a literatura, a abordagem integrada do LRP fornece melhores resultados do que a solução do LAP e do VRP separadamente. O modelo foi testado e aplicado em um caso real de Many-to-Many com Multiplos elos LRP, respeitou as restrições e o nível de serviço exigido e propiciou melhoria nos resultados para a empresa de transporte no qual foi aplicado. Os resultados do modelo também foram melhores do que os resultados apresentados por um software líder de mercado. / In the Less Than Truck Load (LTL) operations both the location of facilities and the routing of vehicles are important decisions for the optimal design of the related logistics network. Two interdependent problems arise: the Location Allocation Problem (LAP) and the Vehicle Routing Problem (VRP). This paper presents a mathematical model to solve the LAP and the VRP simultaneously on an integrated way, such as the so-called Location-Routing Problem (LRP). According to the literature the LRP integrated approach provides better results than considering the LAP and the VRP separately. The model was tested and applied to a real case of Many-to-Many with Multi-Echelons LTL Location-Routing Problem respecting the constraints and the required service level standard and provided better results for the company in which it was tested. The model results also were better than the results presented by market-leading software.

As localizações dos terminais e as rotas de entrega que partem desses terminais são decisões importantes que surgem na concepção de redes de transporte de carga fracionada. Nesses casos, dois problemas independentes precisam ser tratados: o problema da localização de instalações (LAP) e o problema da roteirização dos veículos (VRP). Este trabalho apresenta um modelo matemático para resolver o LAP e o VRP de forma integrada, ou seja, para a resolução do problema de Localização/Roteirização (Location Routing Problem - LRP). De acordo com a literatura, a abordagem integrada do LRP fornece melhores resultados do que a solução do LAP e do VRP separadamente. O modelo foi testado e aplicado em um caso real de Many-to-Many com Multiplos elos LRP, respeitou as restrições e o nível de serviço exigido e propiciou melhoria nos resultados para a empresa de transporte no qual foi aplicado. Os resultados do modelo também foram melhores do que os resultados apresentados por um software líder de mercado. / In the Less Than Truck Load (LTL) operations both the location of facilities and the routing of vehicles are important decisions for the optimal design of the related logistics network. Two interdependent problems arise: the Location Allocation Problem (LAP) and the Vehicle Routing Problem (VRP). This paper presents a mathematical model to solve the LAP and the VRP simultaneously on an integrated way, such as the so-called Location-Routing Problem (LRP). According to the literature the LRP integrated approach provides better results than considering the LAP and the VRP separately. The model was tested and applied to a real case of Many-to-Many with Multi-Echelons LTL Location-Routing Problem respecting the constraints and the required service level standard and provided better results for the company in which it was tested. The model results also were better than the results presented by market-leading software.

A less-than-truckload (LTL) carrier typically delivers shipments less than 10,000 pounds (classified as LTL shipment). The size of the shipment in LTL networks provides ample opportunities for consolidation. LTL carriers have focused on hub-and-spoke based consolidation to realize economies of scale. Generally, hub-and-spoke systems work as follows: the shipment is picked up from the shipper and brought to an origin terminal, which is the entry point into the hub-and-spoke system. From the terminal, the freight is sent to the first hub, where it is sorted and consolidated with other shipments, and then sent on to a second hub. It is finally sent from the second hub to the destination terminal, which is the exit point of the hub-and-spoke system. However, the flow of shipments is often more complicated in practice. In an attempt to reduce sorting costs, load planners sometimes take this hub-and-spoke infrastructure and modify it considerably to maximize their truck utilization while satisfying service constraints. Decisions made by a load planner may have a cascading effect on load building throughout the network. As a result, decentralized load planning may result in expensive global solutions. Academic as well as industrial researchers have adapted a hierarchical approach to design the hub-and-spoke networks: generate the hub-and-spoke network, route shipments within this hub-and-spoke network (generate a load plan) and finally, balance the empty trailers. We present mathematical models and heuristics for each of the steps involved in the design of the hub-and-spoke network. The heuristics are implemented in a user-friendly graphical tool that can help understand patterns of freight flow and provide insights into the design of the hub-and-spoke network. We also solved the load planning sub-problem in a parallel computation environment to achieve significant speed-ups. Because of the quick solution times, the tool lays the foundation to address pressing further research questions such as deciding location and number of hubs. We have used data provided by Roadway Parcel Services, Inc. (RPS), now FedEx Ground, as a case-study for the heuristics. Our solutions rival the existing industry solutions which have been a product of expensive commercial software and knowledge acquired by the network designers in the industry.

The trucking industry is vitally important to the economy, providing an essential service by transporting goods between businesses and consumers. The less-than-truckload (LTL) industry is an important segment, serving businesses that ship quantities between 150 lbs and 10,000 lbs. Large LTL carriers use thousands of drivers to move loads between terminals in their network, and each driver may be used for multiple dispatches between rest periods. Driver wages are a major component of transportation costs. Consequently, cost-effective driver management is of crucial importance for the profitability of LTL carriers. This thesis investigates a variety of issues related to driver management. In this thesis, we describe a dynamic driver scheduling scheme developed for a large U.S. LTL carrier. Dynamic driver scheduling is challenging because drivers must abide by a complex set of rules, including government and union regulations, and trucking moves are not pre-scheduled. The technology developed combines greedy search with enumeration of time-feasible driver duties, and is capable of generating cost-effective schedules covering 15,000 20,000 loads in minutes. One of the key tactical questions faced by an LTL carrier is how many drivers to locate at each terminal. Unionized carriers have bid drivers that can only move loads between their domicile and a designated region. The developed allocation technology determines the number of drivers to allocate to each terminal as well as the designated region for bid drivers. Computational experiments based on real-life dispatch data demonstrate the effectiveness of our domiciling methodology, and show that union rules may result in substantially larger driver fleets, in some cases up to 50% larger. Finally, we investigate a fundamental question related to driver management in order to obtain some fundamental insights: determining the minimum number of drivers required to cover a set of loaded moves. The problem is shown to be polynomially solvable without any restrictions on driver schedules. For variants with restrictions, several easily computable lower bounds are derived, integer programming formulations are presented, and fast heuristics are designed and analyzed. A computational study provides insights into the quality of the lower bounds and heuristic solutions.