Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints

Electric bus scheduling problem can be defined as vehicle scheduling problem with route and fueling time constraints (VSPRFTC). Every vehicle’s travel miles (route time) after charging is limited, thus the vehicle must be recharged after taking several trips and the minimal charging time (fueling time) must be satisfied. A multiple ant colony algorithm (ACA) was presented to solve VSPRFTC based on ACA used to solve traveling salesman problem (TSP), a new metaheuristic approach inspired by the foraging behavior of real colonies of ants. The VSPRFTC considered in this paper minimizes a multiple, hierarchical objective function: the first objective is to minimize the number of tours (or vehicles) and the second is to minimize the total deadhead time. New improvement of ACA as well as detailed operating steps was provided on the basis of former algorithm. Then in order to settle contradiction between accelerating convergence and avoiding prematurity or stagnation, improvement on route construction rule and Pheromone updating rule was adopted. A group feasible trip sets (blocks) had been produced after the process of applying ACA. In dealing with the fueling time constraint a bipartite graphic model and its optimization algorithm are developed for trip set connecting in a hub and spoke network system to minimize the number of vehicle required. The maximum matching of the bipartite graph is obtained by calculating the maximum inflow with the Ford–Fulkerson algorithm. At last, an example was analyzed to demonstrate the correctness of the application of this algorithm. It proved to be more efficient and robust in solving this problem.     

Higher order optimization and adaptive numerical solution for optimal control of monodomain equations in cardiac electrophysiology

In this work adaptive and high resolution numerical discretization techniques are demonstrated for solving optimal control of the monodomain equations in cardiac electrophysiology. A monodomain model, which is a well established model for describing the wave propagation of the action potential in the cardiac tissue, will be employed for the numerical experiments. The optimal control problem is considered as a PDE constrained optimization problem. We present an optimal control formulation for the monodomain equations with an extra-cellular current as the control variable which must be determined in such a way that excitations of the transmembrane voltage are damped in an optimal manner.The focus of this work is on the development and implementation of an efficient numerical technique to solve an optimal control problem related to a reaction-diffusions system arising in cardiac electrophysiology. Specifically a Newton-type method for the monodomain model is developed. The numerical treatment is enhanced by using a second order time stepping method and adaptive grid refinement techniques. The numerical results clearly show that super-linear convergence is achieved in practice.     

Dynamic evolution of economically preferred facilities

In a sustained development scenario, it is often the case that an investment is to be made over time in facilities that generate benefits. The benefits result from joint synergies between the facilities expressed as positive utilities specific to some subsets of facilities. As incremental budgets to finance fixed facility costs become available over time, additional facilities can be opened. The question is which facilities should be opened in order to guarantee that the overall benefit return over time is on the highest possible trajectory. This problem is common in situations such as ramping up a communication or transportation network where the facilities are hubs or service stations, or when introducing new technologies such as alternative fuels for cars and the facilities are fueling stations, or when expanding the production capacity with new machines, or when facilities are functions in a developing organization that is forced to make choices of where to invest limited funding.     

A numerical method for an optimal control problem with minimum sensitivity on coefficient variation

In this paper, we consider a class of optimal control problem involving an impulsive systems in which some of its coefficients are subject to variation. We formulate this optimal control problem as a two-stage optimal control problem. We first formulate the optimal impulsive control problem with all its coefficients assigned to their nominal values. This becomes a standard optimal impulsive control problem and it can be solved by many existing optimal control computational techniques, such as the control parameterizations technique used in conjunction with the time scaling transform. The optimal control software package, MISER 3.3, is applicable. Then, we formulate the second optimal impulsive control problem, where the sensitivity of the variation of coefficients is minimized subject to an additional constraint indicating the allowable reduction in the optimal cost. The gradient formulae of the cost functional for the second optimal control problem are obtained. On this basis, a gradient-based computational method is established, and the optimal control software, MISER 3.3, can be applied. For illustration, two numerical examples are solved by using the proposed method.     

A flexible flowshop problem with total flow time minimization

In this study, we consider total flow time problem in a flexible flowshop environment. We develop a branch and bound algorithm to find the optimal schedule. The efficiency of the algorithm is enhanced by upper and lower bounds and a dominance criterion. Computational experience reveals that the algorithm solves moderate sized problems in reasonable solution times.     

A semidefinite programming approach for solving fractional optimal control problems

This paper presents a numerical scheme for solving fractional optimal control. The fractional derivative in this problem is in the Riemann–Liouville sense. The proposed method, based upon the method of moments, converts the fractional optimal control problem to a semidefinite optimization problem; namely, the nonlinear optimal control problem is converted to a convex optimization problem. The Grunwald–Letnikov formula is also used as an approximation for fractional derivative. The solution of fractional optimal control problem is found by solving the semidefinite optimization problem. Finally, numerical examples are presented to show the performance of the method.     

Interval optimal control problem in a Hilbert space

An optimal control problem for a system involving an interval parameter is considered. The concepts of a universal optimal state and a universal optimal control are introduced. The existence and uniqueness of a universal solution to the interval optimal control problem is proved, and an algorithm for its determination is presented. The interval optimal control problem for a system described by the boundary value problem for a second-order ordinary differential equation is solved as an example.     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

A filled function method for optimal discrete-valued control problems

In this paper, we present a new approach to solve a class of optimal discrete-valued control problems. This type of problem is first transformed into an equivalent two-level optimization problem involving a combination of a discrete optimization problem and a standard optimal control problem. The standard optimal control problem can be solved by existing optimal control software packages such as MISER 3.2. For the discrete optimization problem, a discrete filled function method is developed to solve it. A numerical example is solved to illustrate the efficiency of our method.     

均值-方差准则下的多期最优保险投资(英文)

近年来,最优保险投资问题吸引了越来越多的注意。一般这个问题是在连续时间框架下来研究的。本文针对这一问题建立离散时间的最优控制模型。应用动态规划原理求解模型对应的近似问题,得到了最优投资策略和投资有效边界的解析表达形式。本文得到的最优投资策略和投资有效边界均依赖于承保参数。通过数值例子分析了承保参数对最优投资策略和有效边界的影响。     

A class of optimal state-delay control problems

We consider a general nonlinear time-delay system with state-delays as control variables. The problem of determining optimal values for the state-delays to minimize overall system cost is a non-standard optimal control problem–called an optimal state-delay control problem–that cannot be solved using existing optimal control techniques. We show that this optimal control problem can be formulated as a nonlinear programming problem in which the cost function is an implicit function of the decision variables. We then develop an efficient numerical method for determining the cost function’s gradient. This method, which involves integrating an auxiliary impulsive system backwards in time, can be combined with any standard gradient-based optimization method to solve the optimal state-delay control problem effectively. We conclude the paper by discussing applications of our approach to parameter identification and delayed feedback control.     

Nonlinear optimal feedback control for lunar module soft landing

In this paper, the task of achieving the soft landing of a lunar module such that the fuel consumption and the flight time are minimized is formulated as an optimal control problem. The motion of the lunar module is described in a three dimensional coordinate system. We obtain the form of the optimal closed loop control law, where a feedback gain matrix is involved. It is then shown that this feedback gain matrix satisfies a Riccati-like matrix differential equation. The optimal control problem is first solved as an open loop optimal control problem by using a time scaling transform and the control parameterization method. Then, by virtue of the relationship between the optimal open loop control and the optimal closed loop control along the optimal trajectory, we present a practical method to calculate an approximate optimal feedback gain matrix, without having to solve an optimal control problem involving the complex Riccati-like matrix differential equation coupled with the original system dynamics. Simulation results show that the proposed approach is highly effective.     

A large neighbourhood search approach to the multi-activity shift scheduling problem

The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this paper, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive specialized graph structures that can be searched efficiently. The overall shift scheduling problem can then be solved using a Large Neighbourhood Search. These approaches are able to return near optimal solution on traditional single activity problems and they scale well on large instances containing up to 10 activities.     

Mean–variance optimal trading problem subject to stochastic dominance constraints with second order autoregressive price dynamics

The efficient modeling of execution price path of an asset to be traded is an important aspect of the optimal trading problem. In this paper an execution price path based on the second order autoregressive process is proposed. The proposed price path is a generalization of the existing first order autoregressive price path in literature. Using dynamic programming method the analytical closed form solution of unconstrained optimal trading problem under the second order autoregressive process is derived. However in order to incorporate non-negativity constraints in the problem formulation, the optimal static trading problems under second order autoregressive price process are formulated. For a risk neutral investor, the optimal static trading problem of minimizing expected execution cost subject to non-negativity constraints is formulated as a quadratic programming problem. Whereas, for a risk averse investor the variance of execution cost is considered as a measure for the timing risk, and the mean–variance problem is formulated. Moreover, the optimal static trading problem subject to stochastic dominance constraints with mean–variance static trading strategy as the reference strategy is studied. Using Static approximation method the algorithm to solve proposed optimal static trading problems is presented. With numerical illustrations conducted on simulated data and the real market data, the significance of second order autoregressive price path, and the optimal static trading problems is presented.     

Optimization of Algorithmic Parameters using a Meta-Control Approach*

Optimization algorithms usually rely on the setting of parameters, such as barrier coefficients. We have developed a generic meta-control procedure to optimize the behavior of given iterative optimization algorithms. In this procedure, an optimal continuous control problem is defined to compute the parameters of an iterative algorithm as control variables to achieve a desired behavior of the algorithm (e.g., convergence time, memory resources, and quality of solution). The procedure is illustrated with an interior point algorithm to control barrier coefficients for constrained nonlinear optimization. Three numerical examples are included to demonstrate the enhanced performance of this method. This work was primarily done when Z. Zabinsky was visiting Clearsight Systems Inc.     

A computational method for free terminal time optimal control problem governed by nonlinear time delayed systems

This paper considers a free terminal time optimal control problem governed by nonlinear time delayed system, where both the terminal time and the control are required to be determined such that a cost function is minimized subject to continuous inequality state constraints. To solve this free terminal time optimal control problem, the control parameterization technique is applied to approximate the control function as a piecewise constant control function, where both the heights and the switching times are regarded as decision variables. In this way, the free terminal time optimal control problem is approximated as a sequence of optimal parameter selection problems governed by nonlinear time delayed systems, each of which can be viewed as a nonlinear optimization problem. Then, a fully informed particle swarm optimization method is adopted to solve the approximate problem. Finally, two free terminal time optimal control problems, including an optimal fishery control problem, are solved by using the proposed method so as to demonstrate its applicability.     

A Common Regularization for Three Reservoir Optimal Control Problems

Four optimal control problems of reservoir release are investigated. The first problem is to minimize the peak release in order to prevent flood and to reduce the flood height. The second problem is to maximize the lowest release in order to ensure irrigation, water supply, shipping and environment downstream. The third problem is to minimize the flooding duration in order to reduce damage to goods, possessions, plants, levees, etc. It is shown that these three problems may possess infinitely many different optimal solutions, but they all have a common optimal solution, which is the unique optimal solution of the fourth problem. Since this unique optimal solution depends continuously on the input data, the fourth problem is well-posed and it can be considered as a common regularization of the three ill-posed problems.     

Nonlinear Periodic Optimal Control: A Pseudospectral Fourier Approach

Abstract

A pseudospectral method for generating optimal trajectories of the class of periodic optimal control problems is proposed. The method consists of representing the solution of the periodic optimal control problem by an mth degree trigonometric interpolating polynomial, using Fourier nodes as grid points, and then discretizing the problem using the trapezoidal rule as the quadrature formula for smoothly differentiable periodic functions. The periodic optimal control problem is thereby transformed into an algebraic nonlinear programming problem. Due to its dynamic nature, the pseudospectral Fourier approach avoids many of the numerical difficulties typically encountered in solving standard periodic optimal control problems. An illustrative example is provided to demonstrate the applicability of the proposed method.     

Numerical Solution of Optimal Control Problems with Discrete-Valued System Parameters

In this paper, we propose a new approach to solve a class of optimal control problems involving discrete-valued system parameters. The basic idea is to formulate a problem of this type as a combination of a discrete global optimization problem and a standard optimal control problem, and then solve it using a two-level approach. Numerical results show that the proposed method is efficient and capable of finding optimal or near optimal solutions.