121 |
Optimizing ride matches for dynamic ride-sharing systemsWang, Xing 05 April 2013 (has links)
Ride-share systems, which aim to bring together travelers with similar itineraries and time schedules, may provide significant societal and environmental benefits by reducing the number of cars used for personal travel and improving the utilization of available seat capacity. Effective and efficient optimization technology that matches drivers and riders in real-time is one of the necessary components for a successful ride-share system. The research conducted in this dissertation formally defines dynamic or real-time ride-sharing, identifies optimization problems for finding best sets of ride-share matches in a number of operational scenarios, develops approaches for solving ride-share optimization problems, and tests the concepts via a simulation study of work trips in the Atlanta metropolitan area.
The first chapter introduces the motivation of the ride-sharing problem and briefly defines the dynamic ride-sharing system.
In Chapter 2, we systematically outline the optimization challenges that arise when developing technology to support ride-sharing and survey the related operations research models in academic literature.
In Chapter 3, we develop optimization-based approaches for finding ride-share matches in a standard problem setting, with the goal of minimizing the total system-wide vehicle miles incurred by system users. To assess the merits of our methods we present a simulation study based on 2008 travel demand data from metropolitan Atlanta. The simulation results indicate that the use of sophisticated optimization methods instead of simple greedy matching rules substantially improves the performance of ride-sharing systems. Furthermore, even with relatively low participation rates, it appears that sustainable populations of dynamic ride-sharing participants may be possible even in relatively sprawling urban areas with many employment centers.
In Chapter 4, we consider a more sophisticated ride-share setting where participants may be unlikely to accept ride-share matches if they are not stable. Generically, a set of matches between riders and drivers is defined as stable if no rider and driver, currently matched to others, would prefer to be matched together. This notion of stability is similar to that of the stable marriage problem. We develop notions of stable ride-share matching in a variety of settings, and develop approaches for finding stable (or nearly-stable) solutions. Computational results are used to compare system performance under various levels of matching stability. A system with unstable matching assignments is simulated over two months in which participants are likely to reject the system's assignment if a private arrangement between individuals could bring better benefits. The simulation results indicate that the total savings generated by a ride-sharing system deteriorate with unstable matching assignments and that enforcing stability constraints in matching models is beneficial.
In Chapter 5, we consider another set of more sophisticated ride-share matching settings where participants are not assumed to accept each match to which they are assigned. In such settings, it may be useful to present users with a menu of possible ride-share matches from which they can choose. We develop models and solution approaches to jointly present multiple options to participants based on a complete bipartite graph structure. This research could serve as a building block for future work on the dynamic ride-sharing problem.
|
122 |
On the stability and efficiency of decentralized matching processesBurani, Nadia 14 January 2002 (has links)
No description available.
|
123 |
Incentives in Random Matching MarketsPais, Joana 12 July 2005 (has links)
El objetivo de esta tesis es estudiar el funcionamiento de los mercados de trabajo dónde los trabajadores son asignados a las empresas por procesos aleatorios usando modelos de asignación bilateral. En estos modelos, los agentes pertenecen a uno de dos conjuntos disjuntos -empresas y trabajadores- y cada agente tiene preferencias ordinales sobre el otro lado del mercado. El problema se reduce a una asignación de los miembros de estos dos conjuntos el uno al otro.En el segundo capítulo, titulado "On Random Matching Markets: Properties and Equilibria," se describe un algoritmo que empieza desde una asignación cualquiera y continua creando, a cada paso, una asignación provisional. En cada momento del tiempo, una empresa es elegida al azar y se considera el mejor trabajador en su lista de preferencias. Si este trabajador ya está asignado a una empresa mejor, la asignación no se altera. En caso contrario, el trabajador y la empresa quedan temporalmente juntos hasta que el trabajador reciba una propuesta de trabajo mejor. Seguidamente, se exploran algunas propiedades del algoritmo; por ejemplo, el algoritmo generaliza el famoso algoritmo de "deferred-acceptance" de Gale y Shapley. Luego se analizan los incentivos que los agentes enfrentan en el juego de revelación inducido por el algoritmo. El hecho de que las empresas son seleccionadas al azar introduce incertidumbre en el resultado final. Una vez que las preferencias de los agentes son ordinales, se utiliza un concepto de equilibrio ordinal, basado en la dominancia estocastica de primer orden.En el tercer capítulo, "Incentives in Decentralized Random Matching Markets," se considera un juego secuencial dónde los agentes actúan de acuerdo con las reglas generales del algoritmo. En este capítulo, las estrategias de los agentes pueden tomar una forma cualquiera y no tienen que coincidir con una lista de preferencias. El primer jugador es la Naturaleza, que elige una secuencia de empresas , que representa la incertidumbre existente en un mercado descentralizado. Luego, las empresas son elegidas de acuerdo con la sequencia y les es dada la oportunidad de hacer una propuesta. Ya que el juego es dinamico, se analizan los equilibrios de Nash ordinales perfectos en subjuegos.En "Random Stable Mechanisms in the College Admissions Problem," se considera el juego inducido por un mecanismo aleatorio estable. En este capítulo, se caracterizan los equilibrios de Nash ordinales. En particular, puede obtenerse una asignación en un equilibrio dónde las empresas revelan sus verdaderas preferencias si y sólo si la asignación es estable con respecto a las verdaderas preferencias.Por fin, en el último capítulo, se caracterizan los equilibrios perfectos ordinales en el juego inducido por un mecanismo aleatorio estable. / The purpose of this thesis is to explore the functioning of labor markets where workers are assigned to firms by means of random processes using two-sided matching models. In these models, agents belong to one of two disjoint sets -firms and workers- and each agent has ordinal preferences over the other side of the market. Matching reduces to assigning the members of these two sets to one another.In the second chapter, entitled "On Random Matching Markets: Properties and Equilibria," I describe an algorithm that starts with any matching situation and proceeds by creating, at each step, a provisional matching. At each moment in time, a firm is randomly chosen and the best worker on its list of preferences is considered. If this worker is already holding a firm he prefers, the matching goes unchanged. Otherwise, they are (temporarily) matched, pending the possible draw of even better firms willing to match this worker. Some features of this algorithm are explored; namely, it encompasses other algorithms in the literature, as Gale and Shapley's famous deferred-acceptance algorithm. I then analyze the incentives facing agents in the revelation game induced by the proposed algorithm. The random order in which firms are selected when the algorithm is run introduces some uncertainty in the output reached. Since agents' preferences are ordinal in nature, I use ordinal Nash equilibria, based on first-order stochastic dominance.In the third chapter, "Incentives in Decentralized Random Matching Markets," I take a step further by considering a sequential game where agents act according to the general rules of the algorithm. The original feature is that available strategies exhaust all possible forms of behavior: agents act in what they perceive to be their own best interest throughout the game, not necessarily according to a list of possible matches. The game starts with a move by Nature that determines the order of play, reflecting the inherently uncertain features of a decentralized market. Then, firms are selected according to the drawn order and given the opportunity to offer their positions. In order to account for the dynamic nature of the game, I characterize subgame perfect ordinal Nash equilibria.Following a different approach, in "Random Stable Mechanisms in the College Admissions Problem," I consider the game induced by a random stable matching mechanism. In this paper, I characterize ordinal Nash equilibria, providing simultaneously some results that extend to deterministic mechanisms. In particular, a matching can be obtained as the outcome of a play of the game where firms reveal their true preferences if and only if it is stable with respect to the true preferences.In closing, in the last chapter I characterize perfect equilibria in the game induced by a random stable mechanism.
|
124 |
Three Essays on Experimental EconomicsPintér, Ágnes 18 September 2006 (has links)
There was a time when the conventional wisdom was that, because economics is a science concerned with complex, naturally occuring systems, laboratory experiments had little to offer economists. But experimental economics has now become a well-established tool that plays an important role in helping game theory bridge the gap between the study of ideally rational behavior modeled in theory and the study of actual "real-world" behavior of agents. Although it has older antecedents, experimental economics is a fairly new line of work, having originiated more or less contemporaneously with game theory. As economist focused on microeconomic models which depend on the preferences of the agents, the fact that these are dificult to observe in natural environments made it increasingly attractive to look to the laboratory to see -in a controlled environment- whether the assumptions made about individuals were descriptive of their behavior. But game theory is the part of economic theory that does not focus solely on the strategic behavior of individuals in economic environments, but also other issues that will be critical in the design of economic institutions, such as how information is distributed, the influence of agents' expectations and beliefs, and the tension between equilibrium and efficiency. Game theory has already achieved important insights into issues sucs as the design of contracts and allocation mechanisms that take into account the sometimes counterintuitive ways in which individual incentives operate in environments with decision makers that have different information and objectives.This thesis is divided into three chapters that present self-contained studies of economic situations where experiments may help game theory to explain field observations. In deriving the results, besides the game theory literature, rigorous statistical and econometric methods are used.
|
125 |
Structure from Infrared Stereo ImagesHajebi, Kiana January 2007 (has links)
With the rapid growth in infrared sensor technology and its drastic cost reduction, the potential of application of these imaging technologies in computer vision systems has increased. One potential application for IR imaging is depth from stereo. Discerning depth from stereopsis is difficult because the quality of un-cooled sensors is not sufficient for generating dense depth maps. In this thesis, we investigate the production of sparse disparity maps from un-calibrated infrared stereo images and agree that a dense depth field may not be attained directly from IR stereo images, but perhaps a sparse depth field may be obtained that can be interpolated to produce a dense/semi-dense depth field.
In our proposed technique, the sparse disparity map is produced by a robust features-based stereo matching method capable of dealing with the problems of infrared images, such as low resolution and high noise; initially, a set of stable features are extracted from stereo pairs
using the phase congruency model, which contrary to the gradient-based feature detectors, provides features that are invariant to geometric transformations. Then, a set of Log-Gabor wavelet coefficients at different orientations and frequencies is used to analyze and describe
the extracted features for matching. The resulted sparse disparity map is then refined by triangular and epipolar geometrical constraints. In densifying the sparse map, a watershed transformation is applied to divide the image into several segments, where the disparity inside
each segment is assumed to vary smoothly. The surface of each segment is then reconstructed independently by fitting a spline to its known disparities;
Experiments on a set of indoor and outdoor IR stereo pairs lend credibility to the
robustness of our IR stereo matching and surface reconstruction techniques and hold promise for low-resolution stereo images which don’t have a large amount of texture and local details.
|
126 |
Approximation of antenna patterns by means of a combination of Gaussian beamsHaydar Lazem Al-Saadi, Adel January 2012 (has links)
Modeling of electromagnetic wave propagation in terms of Gaussian beams (GBs) has been considered in recent years. The incident radiation is expanded in terms of GBs by means of the point matching method. The simultaneous equations can be solved directly to produce excitation coefficients that generate the approximate pattern of a known antenna. Two different types of antenna patterns have been approximated in terms of GBs: a truncated antenna pattern and a hyperbolic antenna pattern. The influence of the Gaussian beam parameters on the approximation process is clarified.
|
127 |
Multi-Object Shape Retrieval Using Curvature TreesAlajlan, Naif January 2006 (has links)
This work presents a geometry-based image retrieval approach for multi-object images. We commence with developing an effective shape matching method for closed boundaries. Then, a structured representation, called curvature tree (CT), is introduced to extend the shape matching approach to handle images containing multiple objects with possible holes. We also propose an algorithm, based on Gestalt principles, to detect and extract high-level boundaries (or envelopes), which may evolve as a result of the spatial arrangement of a group of image objects.
At first, a shape retrieval method using triangle-area representation (TAR) is presented for non-rigid shapes with closed
boundaries. This representation is effective in capturing both local and global characteristics of a shape, invariant to translation, rotation, scaling and shear, and robust against noise and moderate amounts of occlusion. For matching, two algorithms are introduced.
The first algorithm matches concavity maxima points extracted from TAR image obtained by thresholding the TAR. In the second matching algorithm, dynamic space warping (DSW) is employed to search efficiently for the optimal (least cost) correspondence between the points of two shapes. Experimental results using the MPEG-7 CE-1 database of 1400 shapes show the superiority of our method over other recent methods.
Then, a geometry-based image retrieval system is developed for multi-object images. We model both shape and topology of image objects including holes using a structured representation called curvature tree (CT). To facilitate shape-based matching, the TAR of each object and hole is stored at the corresponding node in the CT. The similarity between two CTs is measured based on the maximum similarity subtree isomorphism (MSSI) where a one-to-one correspondence is established between the nodes of the two trees. Our matching scheme agrees with many recent findings in psychology about the human perception of multi-object images. Two algorithms are introduced to solve the MSSI problem: an approximate and an exact. Both algorithms have polynomial-time computational complexity and use the DSW as the similarity measure between the attributed
nodes. Experiments on a database of 13500 medical images and a database of 1580 logo images have shown the effectiveness of the proposed method.
The purpose of the last part is to allow for high-level shape retrieval in multi-object images by detecting and extracting the envelope of high-level object groupings in the image. Motivated by studies in Gestalt theory, a new algorithm for the envelope extraction is proposed that works in two stages. The first stage detects the envelope (if exists) and groups its objects using hierarchical clustering. In the second stage, each grouping is merged using morphological operations and then further refined using concavity tree reconstruction to eliminate odd concavities in the extracted envelope. Experiment on a set of 110 logo images demonstrates the feasibility of our approach.
|
128 |
Structure from Infrared Stereo ImagesHajebi, Kiana January 2007 (has links)
With the rapid growth in infrared sensor technology and its drastic cost reduction, the potential of application of these imaging technologies in computer vision systems has increased. One potential application for IR imaging is depth from stereo. Discerning depth from stereopsis is difficult because the quality of un-cooled sensors is not sufficient for generating dense depth maps. In this thesis, we investigate the production of sparse disparity maps from un-calibrated infrared stereo images and agree that a dense depth field may not be attained directly from IR stereo images, but perhaps a sparse depth field may be obtained that can be interpolated to produce a dense/semi-dense depth field.
In our proposed technique, the sparse disparity map is produced by a robust features-based stereo matching method capable of dealing with the problems of infrared images, such as low resolution and high noise; initially, a set of stable features are extracted from stereo pairs
using the phase congruency model, which contrary to the gradient-based feature detectors, provides features that are invariant to geometric transformations. Then, a set of Log-Gabor wavelet coefficients at different orientations and frequencies is used to analyze and describe
the extracted features for matching. The resulted sparse disparity map is then refined by triangular and epipolar geometrical constraints. In densifying the sparse map, a watershed transformation is applied to divide the image into several segments, where the disparity inside
each segment is assumed to vary smoothly. The surface of each segment is then reconstructed independently by fitting a spline to its known disparities;
Experiments on a set of indoor and outdoor IR stereo pairs lend credibility to the
robustness of our IR stereo matching and surface reconstruction techniques and hold promise for low-resolution stereo images which don’t have a large amount of texture and local details.
|
129 |
Betting on the Unexpected: The Effect of Expectation Matching on Choice Strategies in a Binary Choice TaskJames, Greta January 2012 (has links)
Probability matching is the tendency to predict outcomes in accordance with their actual contingencies in a binary choice task. It is, however, a suboptimal response if the aim is to maximize correct predictions. I review two theories that attempt to explain why probability matching occurs: the pattern-search hypothesis and dual-systems theory. These theories are tested in two studies which suggest that dual-systems theory provides a better account of probability matching behavior. Studies 3, 4, and 5 then provide evidence for an extension of the dual-systems theory, called expectation matching, which is intended to explain why probability matching is the intuitive response to a binary choice problem.
|
130 |
Design and Characterization of RFID Modules in Multilayer ConfigurationsBasat, Sabri S. 05 January 2007 (has links)
Radio Frequency IDentification (RFID) Tags have become quite widespread in many services in the industry such as access control, parcel and document tracking, distribution logistics, automotive systems, and livestock or pet tracking. In these applications, a wireless communication link is provided between a remote transponder (antenna and integrated circuit (IC)) and an interrogator or reader. A suitable antenna for these tags must have low cost, low profile and especially small size whereas the bandwidth requirement (few kilohertz to megahertz) is less critical.
In this document, methods to reduce tag size, the performance optimization of the tag by using novel antenna matching techniques for increased operational bandwidth and gain/radiation pattern/radiation efficiency improvement are introduced for 13.56 MHz HF and 915 MHz UHF RFID tags.In addition, an evaluation of an active 915 MHz UHF RFID field study for container tracking at the port of Savannah, GA is also presented.
|
Page generated in 0.036 seconds