skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Fast heuristics for the time‐constrained immobile server problem
Abstract We propose easy‐to‐implement heuristics for time‐constrained applications of a problem referred to in the literature as the facility location problem with immobile servers, stochastic demand, and congestion, the service system design problem, or the immobile server problem (ISP). The problem is typically posed as one of allocating capacity to a set of M/M/1 queues to which customers with stochastic demand are assigned with the objective of minimizing a cost function composed of a fixed capacity‐acquisition cost, a variable customer‐assignment cost, and an expected‐waiting‐time cost. The expected‐waiting‐time cost results in a nonlinear term in the objective function of the standard binary programming formulation of the problem. Thus, the solution approaches proposed in the literature are either sophisticated linearization or relaxation schemes, or metaheuristics. In this study, we demonstrate that an ensemble of straightforward, greedy heuristics can rapidly find high‐quality solutions. In addition to filling a gap in the literature on ISP heuristics, new stopping criteria for an existing cutting plane algorithm are proposed and tested, and a new mixed‐integer linear model requiring no iterating algorithm is developed. In many cases, our heuristic approach finds solutions of the same or better quality than those found by exact methods implemented with expensive, state‐of‐the‐art mathematical programming software, in particular a commercial nonlinear mixed‐integer linear programming solver, given a five‐minute time limit.  more » « less
Award ID(s):
2227548
PAR ID:
10547735
Author(s) / Creator(s):
;
Publisher / Repository:
Wiley
Date Published:
Journal Name:
International Transactions in Operational Research
ISSN:
0969-6016
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Transportation Research Record: Journal of the Transportation Research Board)
    null (Ed.)
    Since passenger demand in urban transit systems is asymmetrically distributed across different periods in a day and different geographic locations across the cities, the tradeoff between vehicle operating costs and service quality has been a persistent problem in transit operational design. The emerging modular vehicle technology offers us a new perspective to solve this problem. Based on this concept, we propose a variable-capacity operation approach with modular transits for shared-use corridors, in which both dispatch headway and vehicle capacity are decision variables. This problem is rigorously formulated as a mixed integer linear programming model that aims to minimize the overall system cost, including passenger waiting time costs and vehicle operating costs. Because the proposed model is linear, the state-of-the-art commercial solvers (e.g., Gurobi) can be used to obtain the optimal solution of the investigated problem. With numerical experiments, we demonstrate the feasibility of the mathematical model, verify the effectiveness of the proposed model in reducing overall system costs in transit systems, as well as the robustness of the proposed model with different parameter settings. 
    more » « less
  2. ; (, AIAA AVIATION FORUM AND ASCEND 2024)
    As we strive to establish a long-term presence in space, it is crucial to plan large-scale space missions and campaigns with future uncertainties in mind. However, integrated space mission planning, which simultaneously considers mission planning and spacecraft design, faces significant challenges when dealing with uncertainties; this problem is formulated as a stochastic mixed integer nonlinear program (MINLP), and solving it using the conventional method would be computationally prohibitive for realistic applications. Extending a deterministic decomposition method from our previous work, we propose a novel and computationally efficient approach for integrated space mission planning under uncertainty. The proposed method effectively combines the Alternating Direction Method of Multipliers (ADMM)-based decomposition framework from our previous work, robust optimization, and two-stage stochastic programming (TSSP).This hybrid approach first solves the integrated problem deterministically, assuming the worst scenario, to precompute the robust spacecraft design. Subsequently, the two-stage stochastic program is solved for mission planning, effectively transforming the problem into a more manageable mixed-integer linear program (MILP). This approach significantly reduces computational costs compared to the exact method, but may potentially miss solutions that the exact method might find. We examine this balance through a case study of staged infrastructure deployment on the lunar surface under future demand uncertainty. When comparing the proposed method with a fully coupled benchmark, the results indicate that our approach can achieve nearly identical objective values (no worse than 1% in solved problems) while drastically reducing computational costs. 
    more » « less
  3. ; ; ; ; (, IEEE Industry Applications Society Annual Meeting)
    null (Ed.)
    This paper presents a multi-objective (MO) optimization for economic/emission dispatch (EED) problem incorporating hydrothermal plants, wind power generation, energy storage systems (ESSs) and responsive loads. The uncertain behavior of wind turbines and electric loads is modeled by scenarios. Stochastic programming is proposed to achieve the expected cost and emission production. Moreover, the carbon capture systems are considered to lower the level of carbon emission produced by conventional thermal units. The proposed optimization problem is tested on the IEEE 24-bus case study using DC power flow calculation. The optimal Pareto frontier is obtained, and a fuzzy decision-making tool determined the best solution among obtained Pareto points. The problem is modeled as mixed-integer non-linear programming in the General Algebraic Modelling System (GAMS) and solved using DICOPT solver. 
    more » « less
  4. ; (, IEEE Conference on Decision and Control)
    In this paper, we consider the problem of dynamic programming when supremum terms appear in the objective function. Such terms can represent overhead costs associated with the underlying state variables. Specifically, this form of optimization problem can be used to represent optimal scheduling of batteries such as the Tesla Powerwall for electrical consumers subject to demand charges - a charge based on the maximum rate of electricity consumption. These demand charges reflect the cost to the utility of building and maintaining generating capacity. Unfortunately, we show that dynamic programming problems with supremum terms do not satisfy the principle of optimality. However, we also show that the supremum is a special case of the class of forward separable objective functions. To solve the dynamic programming problem, we propose a general class of optimization problems with forward separable objectives. We then show that for any problem in this class, there exists an augmented-state dynamic programming problem which satisfies the principle of optimality and the solutions to which yield solutions to the original forward separable problem. We further generalize this approach to stochastic dynamic programming problems and apply the results to the problem of optimal battery scheduling with demand charges using a data-based stochastic model for electricity usage and solar generation by the consumer. 
    more » « less
  5. ; (, Proceedings of the 2019 Institute of Industrial and Systems Engineers Annual Conference)
    This study develops a multi-objective optimization model that considers the preferences of stakeholders in a vehicle-to-grid system. The optimization problem is formulated using a mixed integer linear programming (MILP) model with objectives to meet the requirements of the aggregator and electric vehicle owners. The first objective aims to minimize the customer’s charging cost while also maximizing the earnings of the customer from discharging to the grid during periods of peak demand while the second objective ensures that the aggregator’s profit is maximized. Simulations using time series over a 48-hour period show the results of the two objectives solved together as a multi-objective problem. Pareto front is used to show the relationship between the two conflicting objectives and for selecting a solution depending on the decision maker’s preferences. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email