Dept. of Industrial and Enterprise Systems Engineering
http://hdl.handle.net/2142/16358
Tue, 24 Nov 2015 22:09:04 GMT2015-11-24T22:09:04ZA large-scale neighborhood search approach to vehicle routing pick-up and delivery problem with time windows under uncertainty
http://hdl.handle.net/2142/88233
A large-scale neighborhood search approach to vehicle routing pick-up and delivery problem with time windows under uncertainty
Tumuluri, Praveen
The vehicle routing problem with shipment pick-up and delivery with time windows (VRPPDTW) is one of the core problems that is addressed by a package delivery company in its operations. Most often, this problem has been addressed from the point of view of cost-cutting, to achieve the lowest cost possible under a given/predicted demand and service time scenario. This thesis aims to study a real-world VRPPDTW problem with side-constraints and build solutions that are cost-effective as well as robust to stochasticity in demands and service times. Even without the additional side constraints, the VRPPDTW is NP-hard. In particular, we consider the solution of VRPPDTW with side-constraints adopted by a carrier. Because of the nature as well as the size of the problem and the network, we demonstrate that the problem is combinatorially explosive. We therefore develop a large-scale neighbourhood search heuristic combined with a break-and-join heuristic and a clustering heuristic. We use this heuristic to build a set of schedules with far lower operating costs than the existing solution and effectively decrease the costs by 15% by reducing the number of routes needed to serve the shipments. We then build a framework to evaluate the performance of the solutions under stochasticity, and present results related to under stochasticity in service times.
vehicle routing; large-scale neighbourhood search
Fri, 24 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/882332015-07-24T00:00:00ZTumuluri, PraveenOn the convexity of right-closed sets and its application to liveness enforcement in Petri Nets
http://hdl.handle.net/2142/88056
On the convexity of right-closed sets and its application to liveness enforcement in Petri Nets
Salimi, Ehsan
A set of n-dimensional integral vectors,
Nn, is said to be right-closed if for any x 2
, any
vector y x also belongs to it. An integral-set
Nn is convex if and only if there is a convex set
C Rn such that
= Int(C), where Int( ) denotes the integral points in the set argument. In this
dissertation, we show that the problem of verifying convexity of a right-closed set is decidable. Following
this, we present a polynomial time, LP-based algorithm, for verifying the convexity of a right-closed
set of integral vectors, when the dimension n is xed. This result is to be viewed against the backdrop
of the fact that checking the convexity of a real-valued, geometric set can only be accomplished in an
approximate sense; and, the fact that most algorithms involving sets of real-valued vectors do not apply
directly to their integral counterparts. Also, we discuss a grid-search based algorithm for verifying the
convexity of such a set, although not a polynomial time procedure, it is a method that veri es the
convexity of right-closed sets in a reasonable time complexity.
On the application side, right-closed sets feature in the synthesis of Liveness Enforcing Supervisory
Policies (LESPs) for a large family of Petri Nets (PNs). For any PN structure N from this family,
the set of initial markings, (N), for which there is a LESP, is right-closed. A LESP determines the
transitions of a PN that are to be permitted to re at any marking in such a manner that, irrespective
of the past, every transition can be red at some marking in the future. A system that is modeled by a
live PN does not experience livelocks, which serves as the motivation for investigating implementation
paradigms for LESPs in practice.
If a transition is prevented from ring at a marking by a LESP, and all LESPs, irrespective of
the implementation-paradigm that is chosen, prescribe the same control for the marking, then it is a
minimally restrictive LESP. It is possible to synthesize the minimally restrictive LESP for any instance N of the aforementioned family that uses the right-closed set of markings (N). The literature also
contains an implementation paradigm called invariant-based monitors for liveness enforcement in PNs.
This paradigm is popular due to the fact that the resulting supervisor can be directly incorporated
into the semantics of the PN model of the controlled system. In this work, we show that there is an
invariant-based monitor that is equivalent to the minimally restrictive LESP that uses the right-closed
set (N) if and only if (N) is convex. This result serves as the motivation behind exploring the
convexity of right-closed sets.
Right-closed set; convexity; integer convexity; polyhedral theory; Petri Nets; Liveness
Thu, 16 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/880562015-07-16T00:00:00ZSalimi, EhsanEmpirical investigations of properties of robust aircraft routing models
http://hdl.handle.net/2142/88051
Empirical investigations of properties of robust aircraft routing models
Li, Guanqun
The airline schedule planning process is an important component of airline operations, and it involves considerably complex problems. This research focuses on the aircraft routing phase. We introduce the concept of robustness in aircraft routing problems, and find solutions that can stand uncertainty.
We categorize the delays in flight operations into two components – independent delay and propagated delay. In the data driven approach, independent delay can be regarded as constant, but propagated delay can be worked on. An example of aircraft swap is given to show that aircraft routing can potentially reduce the flight delays. To solve robust aircraft routing problems, we propose a list of formulations. They are in three categories – Lan, Clarke, Barnhart’s approach, chance-constrained programming approach, and extreme value approach.
We conduct experiments with two airline networks – a 50-flight network and a 165-flight network. The K-fold cross validation approach is incorporated into aircraft routing problems to eliminate overfitting. According to the three evaluation metrics – on time performance, average total propagated delay and passenger disruptions, several good formulations are identified, which are recommended for airline schedule planners. We also explain the reasons behind the solution differences.
airline scheduling; optimization; aircraft routing; propagated delay
Wed, 15 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/880512015-07-15T00:00:00ZLi, GuanqunEffects of asphalt rejuvenator on thermal and mechanical properties of oxidized hot mixed asphalt
http://hdl.handle.net/2142/88046
Effects of asphalt rejuvenator on thermal and mechanical properties of oxidized hot mixed asphalt
Farace, Nicholas Anthony
The utilization of asphalt rejuvenator, and its effectiveness for restoring thermal and mechanical properties was investigated via Disk-shaped Compact Tension (DC(T)) testing and acoustic emission (AE) testing for determining the embrittlement temperature of the mixtures. During the DC(T) testing the fracture energies and peak loads were used to measure the resistance of the rejuvenated asphalt to low temperature cracking. The AE testing monitored the emissions generated while the specimens were cooled from room temperature to -40°C to estimate the temperature at which thermal cracking began (i.e. the embrittlement temperature). The purpose of this research was to determine if the rejuvenator restored the low temperature performance of highly oxidized hot mixed asphalt (HMA).
The study was divided into three parts. Part 1 set a baseline for comparison of the low temperature performance by using DC(T) testing and AE testing on virgin HMA samples and HMA samples that had been aged and oxidized for 36 hours at 135°C. The results showed the virgin samples had much higher peak loads and fracture energies than the 36 hours aged samples. Acoustic Emission showed similar results with the virgin samples having embrittlement temperatures 10°C cooler than the 36 hours aged specimens. Part 2 of the study evaluated the effect of varying amounts of rejuvenator (10%, 15%, and 20% by weight of binder content) on HMA mixtures when left for different dwell times. The dwell times were varied from 1 week to 8 weeks. The testing was done at 0°C instead of the standard -12°C as the standard was too close to the original 36 hours aged embrittlement temperature, and could have caused variance in the results. It was found that the rejuvenator lowered peak loads, and kept the fracture energies near the same level from the DC(T) testing. The AE results showed an improvement of embrittlement temperature, with increasing improvement with the dwell times. The 8 weeks specimens had cooler embrittlement temperatures than the virgin specimens. Part 3 of the study investigated lower temperature effects on fracture energy and peak load of the rejuvenated asphalt. Rejuvenator was applied (10% by weight of binder) to specimens aged 36 hours at 135°C, and the dwell time was varied from 1 to 4 weeks. The results from this testing showed the peak loads being restored to levels of the virgin specimens, and the fracture energies improved to a level beyond that of the virgin specimens. The results showed a general trend of improvement for the AE testing of the embrittlement temperature, but further testing at different rejuvenator levels and dwell times would be required to ensure the mechanical results.
Asphalt Rejuvenator; Acoustic Emission
Tue, 14 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/880462015-07-14T00:00:00ZFarace, Nicholas AnthonyDynamic pricing with reference price effects
http://hdl.handle.net/2142/87956
Dynamic pricing with reference price effects
Hu, Zhenyu
This dissertation mainly focuses on the models and the corresponding dynamic pricing problems that incorporate reference price effects, a concept developed in economics and marketing literature that try to capture the dependency of consumers purchasing behavior on past prices.
Conceptually, reference price is a price expectation consumers develop from their observations of historical prices. Since it can not be physically observed, various models have been proposed to operationalize its formation. We empirically compare some of the models in the literature and extend the literature by proposing a new reference price model. In addition, we present analysis on the dynamic pricing problems under these models assuming consumers are loss/gain neutral or loss-averse. We find that constant pricing strategies are a robust solution to the problem regardless of which reference price models one may choose.
Empirical evidences, however, indicate that loss/gain neutral or loss-averse behavior may not be a universal phenomenon. We analyze the dynamic pricing problem when consumers exhibit gain-seeking behavior. In sharp contrast to the loss-averse case, even myopic pricing strategies can result in complicated cyclic price paths. We show for a special case that a cyclic skimming pricing strategy is optimal and provide conditions to guarantee the optimality of high-low pricing strategies.
With the understanding of the qualitative behavior of the optimal pricing strategies under various settings, we develop efficient algorithms to compute the optimal prices in both loss-averse and gain-seeking case. We demonstrate the efficiency and robustness of our algorithms by applying them to a practical problem with real data.
Finally, we extend the above considered single-product setting to multi-product setting and analyze the corresponding dynamic pricing problems.
dynamic pricing; reference price effects
Thu, 04 Jun 2015 00:00:00 GMThttp://hdl.handle.net/2142/879562015-06-04T00:00:00ZHu, ZhenyuStrategic Planning Under Uncertainty: Stochastic Integer Programming Approaches
http://hdl.handle.net/2142/87108
Strategic Planning Under Uncertainty: Stochastic Integer Programming Approaches
Ahmed, Shabbir
In the final part of this thesis, we address a class of stochastic programs with discrete first stage decisions and decision-dependent uncertainties. These problems are formulated as 0--1 hyperbolic programs for which we use the theory of convex extensions to develop a reformulation scheme and an exact solution strategy. The proposed methods are used in a case study for locating restaurant franchises.
Operations Research
Sat, 01 Jan 2000 00:00:00 GMThttp://hdl.handle.net/2142/871082000-01-01T00:00:00ZAhmed, ShabbirFinite Algorithms for Global Optimization of Concave Programs and General Quadratic Programs
http://hdl.handle.net/2142/87106
Finite Algorithms for Global Optimization of Concave Programs and General Quadratic Programs
Shectman, Joseph Parker
This document examines finiteness issues in the context of structured global optimization problems. Specific aspects of this research include: (1) Development of finite algorithms, (2) Analysis of the algorithms' computational complexity, (3) Demonstrating the efficiency of the algorithms in applications; the applications coming from several engineering disciplines and from finance.
Computer Science
Fri, 01 Jan 1999 00:00:00 GMThttp://hdl.handle.net/2142/871061999-01-01T00:00:00ZShectman, Joseph ParkerGlobal Optimization of Multiplicative Programs: Theory, Algorithms, and Applications
http://hdl.handle.net/2142/87104
Global Optimization of Multiplicative Programs: Theory, Algorithms, and Applications
Ryoo, Hong Seo
Finally, we provide computational results on a real-world medical database pattern recognition problem. These results reveal that the Wisconsin Breast Cancer Database is bilinearly inseparable.
Engineering, Industrial
Fri, 01 Jan 1999 00:00:00 GMThttp://hdl.handle.net/2142/871041999-01-01T00:00:00ZRyoo, Hong SeoFlexible Computer Support for Collaboration in Civil Infrastructure Management
http://hdl.handle.net/2142/87105
Flexible Computer Support for Collaboration in Civil Infrastructure Management
Lucenti, Martin Joseph, Jr
This thesis also presents CityCollab and its evaluation by a community of users. CityCollab is a collaborative system, which supports the processing of Requests for Work in the context of civil infrastructure management. CityCollab represents an instantiation of the more general FLECS architecture/framework.
Engineering, Civil
Fri, 01 Jan 1999 00:00:00 GMThttp://hdl.handle.net/2142/871051999-01-01T00:00:00ZLucenti, Martin Joseph, JrMicrofiltration of Synthetic Metal Working Fluids Using Aluminum Oxide Membranes
http://hdl.handle.net/2142/87107
Microfiltration of Synthetic Metal Working Fluids Using Aluminum Oxide Membranes
Skerlos, Steven John
The design of membrane filtration systems is also influenced by the rate of contaminant build-up in the MWF. Microbiological population growth can grow to potentially hazardous levels in extremely short time-scales. Membrane filtration systems designed to control microbial populations must remove microbes from the MWF at a rate faster than population growth. A model is developed to relate microbiological parameters such as growth rate, yield, and substrate consumption to membrane filtration system design parameters. The model is used to determine if microbial growth control is possible for a given metalworking fluid, membrane filtration system, and membrane cleaning schedule.
Engineering, Environmental
Sat, 01 Jan 2000 00:00:00 GMThttp://hdl.handle.net/2142/871072000-01-01T00:00:00ZSkerlos, Steven John