Recent supply chain literature and practice recognize that significant cost savings can be achieved by coordinating inventory and transportation decisions. Although the existing literature on analytical models for these decisions is very broad, there are still some challenging issues. In particular, the uncertainty of demand in a dynamic system and the structure of various practical transportation cost functions remain unexplored in detail. Taking these motivations into account, this dissertation focuses on the analytical investigation of the impact of transportation-related costs and practices on inventory decisions, as well as the integrated inventory and transportation decisions, under stochastic dynamic demand. Considering complicated, yet realistic, transportation-related costs and practices, we develop and solve three classes of models: (1) Pure inbound inventory model impacted by transportation cost; (2) Pure outbound transportation models concerning shipment consolidation strategy; (3) Integrated inbound inventory and outbound transportation models. In broad terms, we investigate the modeling framework of vendor-customer systems for integrated inventory and transportation decisions, and we identify the optimal inbound and outbound policies for stochastic dynamic supply chain systems. This dissertation contributes to the previous literature by exploring the impact of realistic transportation costs and practices on stochastic dynamic supply chain systems while identifying the structural properties of the corresponding optimal inventory and/or transportation policies. Placing an emphasis on the cases of stochastic demand and dynamic planning, this research has roots in applied probability, optimal control, and stochastic dynamic programming.

Tracking multiple targets in a high cluttered environment where multiple receivers are used is a challenging task due to the high level of false alarms and uncertainty in the track hypothesis. The multi-static active sonar scenario is an example for such systems where multiple source-receiver combinations are deployed. Due to the nature of the underwater environment and sound propagation characteristics, tracking targets in the underwater environment becomes a complex operation. Conventional tracking approaches (such as the Kalman and particle filter) require a predetermined kinematic model of the target. Moreover, tracking an unknown and changing number of targets within a certain search area requires complex mathematical association filters to identify the number of targets and associate measurements to different target tracks. As the number of false detections increases, the computational complexity of conventional tracking system grows introducing further challenges for real-time target tracking situations. The methodology presented in this thesis provides a rapid and reliable tracking system capable of tracking multiple targets without depending on a kinematic model of the target movement. In this algorithm, Self Organizing Maps, Dynamic Programming and the Hough transform are combined to produce tracks of possible targets’ paths and estimate of targets’ locations. Evaluation of the performance of the tracking algorithm is performed using three types of simulations and a set of real data obtained from a sea trial. This research documents the results of experimental testing and analysis of the tracking system. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-08-07 13:21:06.869

This thesis deals with sequence alignment algorithms. The sequence alignment is a mutual arrange of two or more sequences in order to study their similarity and dissimilarity. Four decades after the seminal work by Needleman and Wunsch in 1970, these methods still need more explorations. We start out with a review of a sequence alignment, and its generalization to multiple alignments, although the focus of this thesis is on the evaluation of the new alignment algorithms. The research presented here in has stepped into the different algorithms that are in terms of the dynamic programming. In the study of sequence alignment algorithms, two powerful techniques have been invented. According to the simulations, the new algorithms are shown to be extremely efficient for the comparing DNA sequences. All the sequence alignment algorithmsare compared in terms of the distance. We use the programming language R for the implementation and simulation of the algorithms discussed in this thesis.

No description available.

This paper investigates optimal portfolio strategies in a market with partial information on the drift. The drift is modelled as a function of a continuous-time Markov chain with finitely many states which is not directly observable. Information on the drift is obtained from the observation of stock prices. Moreover, expert opinions in the form of signals at random discrete time points are included in the analysis. We derive the filtering equation for the return process and incorporate the filter into the state variables of the optimization problem. This problem is studied with dynamic programming methods. In particular, we propose a policy improvement method to obtain computable approximations of the optimal strategy. Numerical results are presented at the end. (author's abstract)

Commercially available Hybrid Electric Vehicles (HEVs) have been around for more than ten years. However, their market share remains small. Focusing only on the improvement of fuel economy, the design tends to reduce the size of the internal combustion engine in the HEV, and uses the electrical drive to compensate for the power gap between the load demand and the engine capacity. Unfortunately, the low power density and the high cost of the combined electric motor drive and battery packs dictate that the HEV has either worse performance or much higher price than the conventional vehicle. In this research, a new design philosophy for parallel HEV is proposed, which uses a full size engine to guarantee the vehicle performance at least as good as the conventional vehicle, and hybridizes with an electrical drive in parallel to improve the fuel economy and performance beyond the conventional cars. By analyzing the HEV fuel economy versus the increasing of the electrical drive power on typical driving conditions, the optimal hybridization electric power capacity is determined. Thus, the full size engine HEV shows significant improvement in fuel economy and performance, with relatively short cost recovery period. A new control strategy, which optimizes the fuel economy of parallel configured charge sustained hybrid electric vehicles, is proposed in the second part of this dissertation. This new approach is a constrained engine on-off strategy, which has been developed from the two extreme control strategies of maximum SOC and engine on-off, by taking their advantages and overcoming their disadvantages. A system optimization program using dynamic programming algorithm has been developed to calibrate the control parameters used in the developed control strategy, so that the control performance can be as close to the optimal solution as possible. In order to determine the sensitivity of the new control strategy to different driving conditions, a passenger car is simulated on different driving cycles. The performances of the vehicle with the new control strategy are compared with the optimal solution obtained on each driving condition with the dynamic programming optimization. The simulation result shows that the new control strategy always keeps its performance close to the optimal one, as the driving condition changes.

Multi-homing is a technology used by Internet Service Provider (ISP) to connect to the Internet via multiple networks. This connectivity enhances the network reliability and service quality of the ISP. However, using multi-networks may imply multiple costs on the ISP. To make full use of the underlying networks with minimum cost, a routing strategy is requested by ISPs. Of course, this optimal routing strategy depends on the pricing regime used by network providers. In this study we investigate a relatively new pricing regime – top-percentile pricing. Under top-percentile pricing, network providers divide the charging period into several fixed length time intervals and calculate their cost according to the traffic volume that has been shipped during the θ-th highest time interval. Unlike traditional pricing regimes, the network design under top-percentile pricing has not been fully studied. This paper investigates the optimal routing strategy in case where network providers charge ISPs according to top-percentile pricing. We call this problem the Top-percentile Traffic Routing Problem (TpTRP). As the ISP cannot predict next time interval’s traffic volume in real world application, in our setting up the TpTRP is a multi-stage stochastic optimisation problem. Routing decisions should be made at the beginning of every time period before knowing the amount of traffic that is to be sent. The stochastic nature of the TpTRP forms the critical difficulty of this study. In this paper several approaches are investigated in either the modelling or solving steps of the problem. We begin by exploring several simplifications of the original TpTRP to get an insight of the features of the problem. Some of these allow analytical solutions which lead to bounds on the achievable optimal solution. We also establish bounds by investigating several “naive” routing policies. In the second part of this work, we build the multi-stage stochastic programming model of the TpTRP, which is hard to solve due to the integer variables introduced in the calculation of the top-percentile traffic. A lift-and-project based cutting plane method is investigated in solving the SMIP for very small examples of TpTRP. Nevertheless it is too inefficient to be applicable on large sized instances. As an alternative, we explore the solution of the TpTRP as a Stochastic Dynamic Programming (SDP) problem by a discretization of the state space. This SDP model gives us achievable routing policies on small size instances of the TpTRP, which of course improve the naive routing policies. However, the solution approach based on SDP suffers from the curse of dimensionality which restricts its applicability. To overcome this we suggest using Approximate Dynamic Programming (ADP) which largely avoids the curse of dimensionality by exploiting the structure of the problem to construct parameterized approximations of the value function in SDP and train the model iteratively to get a converged set of parameters. The resulting ADP model with discrete parameter for every time interval works well for medium size instances of TpTRP, though it still requires too long to be trained for large size instances. To make the realistically sized TpTRP problem solvable, we improve on the ADP model by using Bezier Curves/Surfaces to do the aggregation over time. This modification accelerates the efficiency of parameter training in the solution of the ADP model, which makes the realistically sized TpTRP tractable.

This work deals with building a program system for solving dynamic programming problems on a computer. The theoretical part describes dynamic programming as a tool used for optimizing multistage decision processes and dynamic programming problems implemented in the program system. The practical part describes the design and implementation of the program system and verification of its functionality.

The areas of machine learning, data mining, and knowledge representation have many different formats used to represent information. Decision rules, amongst these formats, are the most expressive and easily-understood by humans. In this thesis, we use dynamic programming to design decision rules and analyze them. The use of dynamic programming allows us to work with decision rules in ways that were previously only possible for brute force methods. Our algorithms allow us to describe the set of all rules for a given decision table. Further, we can perform multi-stage optimization by repeatedly reducing this set to only contain rules that are optimal with respect to selected criteria. One way that we apply this study is to generate small systems with short rules by simulating a greedy algorithm for the set cover problem. We also compare maximum path lengths (depth) of deterministic and non-deterministic decision trees (a non-deterministic decision tree is effectively a complete system of decision rules) with regards to Boolean functions. Another area of advancement is the presentation of algorithms for constructing Pareto optimal points for rules and rule systems. This allows us to study the existence of “totally optimal” decision rules (rules that are simultaneously optimal with regards to multiple criteria). We also utilize Pareto optimal points to compare and rate greedy heuristics with regards to two criteria at once. Another application of Pareto optimal points is the study of trade-offs between cost and uncertainty which allows us to find reasonable systems of decision rules that strike a balance between length and accuracy.

We propose a new approach to optimize operations of hydro storage systems with multiple connected reservoirs whose operators participate in wholesale electricity markets. Our formulation integrates short-term intraday with long-term interday decisions. The intraday problem considers bidding decisions as well as storage operation during the day and is formulated as a stochastic program. The interday problem is modeled as a Markov decision process of managing storage operation over time, for which we propose integrating stochastic dual dynamic programming with approximate dynamic programming. We show that the approximate solution converges towards an upper bound of the optimal solution. To demonstrate the efficiency of the solution approach, we fit an econometric model to actual price and in inflow data and apply the approach to a case study of an existing hydro storage system. Our results indicate that the approach is tractable for a real-world application and that the gap between theoretical upper and a simulated lower bound decreases sufficiently fast. (authors' abstract)