This article addresses a street sweeping problem that extends the class of multi-depot arc routing problem by integrating a flexible assignment of end depot for each working shift. A unique team of specialized vehicle...
详细信息
This article addresses a street sweeping problem that extends the class of multi-depot arc routing problem by integrating a flexible assignment of end depot for each working shift. A unique team of specialized vehicles starts each shift from a depot, visits the required arcs and returns at the end of each shift to a depot. The service in the next shift should start from the end depot of the previous one. An additional new constraint imposes that the highway arcs must be serviced during a night shift while all others arcs (boulevard, street, etc.) can be swept during both day and night. The aim of this arc routing problem is to find optimal shifts that satisfy these two practical aspects, along with other constraints such as maximum shift duration. The problem is motivated by a real-world application that has not been previously studied in the literature. A mixed integer linear programming model is formulated with the objective of minimizing the total travel time and tested on newly generated instances based on Cordeau's multi-depot vehicle routing problem instances. The results show a generation of total travel time savings up to 12 % compared to the single depot arc routing problem.
This paper describes a method for solving task planning and motion planning problems simultaneously. We target a fetch-and-carry of a small item by a single-arm mobile manipulator and introduce a method that can gener...
详细信息
ISBN:
(数字)9798331531614
ISBN:
(纸本)9798331531621
This paper describes a method for solving task planning and motion planning problems simultaneously. We target a fetch-and-carry of a small item by a single-arm mobile manipulator and introduce a method that can generate a sequence of actions and motions required for each action, even in environments with narrow open spaces such as corridors. In addition, to deal with a case where another object is already placed at the target location, we introduce a push-aside action and extend the previous method to include this action. As our method is formulated using mixed integer linear programming (MILP), the calculation time is relatively short, irrespective of the complexity of the target problem. To verify the efficiency of the proposed method, we performed a quantitative evaluation through simulation and conducted experiments on an actual mobile manipulator to verify feasibility of the methods.
A wide range of problems can be modeled as mixed integer linear programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effe...
详细信息
A wide range of problems can be modeled as mixed integer linear programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effectively solved by state of the art solvers. In this survey we review advanced MIP formulation techniques that result in stronger and/or smaller formulations for a wide class of problems.
The traditional strategy for ground-level ozone control is to apply emission reductions across the board throughout certain time periods and locations. In this paper, we study various mixed integer linear programming ...
详细信息
The traditional strategy for ground-level ozone control is to apply emission reductions across the board throughout certain time periods and locations. In this paper, we study various mixed integer linear programming (MILP) models that seek to select targeted control strategies for the Dallas Fort-Worth (DFW) region to reduce emissions, in order to achieve the State Implementation Plan (SIP) requirements with minimum cost. Statistics and optimization methods are used to determine a potential set of cost-effective control strategies for reducing ozone. These targeted control strategies are specified for different types of emission sources in various time periods and locations. Three MILP models, a static model, a sequential model, and a dynamic model, are studied in this research. These different MILP models allow decision makers to study how the targeted control strategies change under different circumstances. Meanwhile, two types of auxiliary variables are considered as supplemental control strategies in the optimization if the current set of control strategies is unable to reduce ozone to complywith the 8-h ozone standard. Results fromthe differentmodels can provide decisionmakers with information concerning how the effectiveness of the control strategies varies with daily emission patterns and meteorology.
We introduce two new formulations for probabilistic constraints based on extended disjunctive formulations. Their strength results from considering multiple rows of the probabilistic constraints together. The properti...
详细信息
We introduce two new formulations for probabilistic constraints based on extended disjunctive formulations. Their strength results from considering multiple rows of the probabilistic constraints together. The properties of the first can be used to construct hierarchies of relaxations for probabilistic constraints, while the second provides computational advantages over other formulations. (C) 2012 Elsevier B.V. All rights reserved.
In this paper, we propose the modeling of a real-case problem where a farmer has to optimize the use of his/her land by selecting the best mix of crops to cultivate. Complexity of the problem is due to the several fac...
详细信息
In this paper, we propose the modeling of a real-case problem where a farmer has to optimize the use of his/her land by selecting the best mix of crops to cultivate. Complexity of the problem is due to the several factors that have to be considered simultaneously. These include the market prices variability of harvested products, the specific resource requests for each crop, the restrictions caused by limited machines availability, and the timing of operations required to complete each crop cultivation. We provide two different mathematical formulations for the analyzed problem. The first one represents a natural integerprogramming formulation looking for the crop-mix that maximizes the farmer's expected profit measured as the difference between revenues obtained by selling the harvested products and the production costs. Since the revenue of each crop depends on the price as quoted at the exchange market and the yield per hectare of harvested product, we define it as a random variable. Then, the second model uses the maximization of the Conditional Value-at-Risk (CVaR) as objective function and looks for the crop-mix that allows to maximize the average expected profit under a predefined quantile of worst realizations. To test and compare the proposed models with the cultivation choice made by the farmer, we use Italian historical data represented by monthly returns of different crops over a time period of 16 years. Computational results emphasize the advantage of using the CVaR model for a risk-averse farmer and provide interesting insights for farmers involved in similar problems. (C) 2016 Elsevier Ltd. All rights reserved.
The bi-objective double-floor corridor allocation problem (bDFCAP) investigated here explores the effective placement of given departments in a double-floor space to minimise the overall flow cost and the corridor len...
详细信息
The bi-objective double-floor corridor allocation problem (bDFCAP) investigated here explores the effective placement of given departments in a double-floor space to minimise the overall flow cost and the corridor length objectives. Within each floor, departments are arranged in two parallel rows on opposite sides along a central corridor without overlapping. In this study, the bDFCAP is formulated as a mixed integer linear programming model, which has improved the performance over the previous one. Thereafter, a genetic algorithm with a variable neighbourhood search technique is designed and employed to solve the bDFCAP in a more effective manner. This technique is utilized to improve the local search capability by adaptively transforming between a deep-searching strategy and broad-searching strategy, and the superior performance of the proposed method is proven through comparisons with two other algorithms in current literature. Besides, the state-of-the-art lower bounds of several benchmark instances are updated.
This work proposes a methodology for directional overcurrent protection coordination in interconnected transmission systems considering a possible network contingency state. The methodology uses the short-circuit data...
详细信息
This work proposes a methodology for directional overcurrent protection coordination in interconnected transmission systems considering a possible network contingency state. The methodology uses the short-circuit data of the current network topology;however, the maximum load current data in the protection section of each relay is obtained considering the n-1 criterion, already foreseeing the disconnection of some network line. Thus, if a line gets disconnected, other protective devices will not improperly actuate by the redistribution of load currents in the network. The objective is to propose an adaptive protection scheme to redo the coordination for each topological change in the network. To this end, this work considers a smart grid environment with a supervisory system with communication capability between this and the remote devices. To obtain the optimal performance, the coordination problem, originally non-linear and non-convex, is linearized, allowing its formulation as a mixed integer linear programming problem. The methodology is applied to the 8-bus test system in 3 different cases and the 30-bus test system. Results show that the optimal coordination is obtained in a fast computational processing time, showing the suitability of the methodology for real-time application.
The analysis of the Quality of Service (QoS) level in a Cloud Computing environment becomes an attractive research domain as the utilization rate is daily higher and higher. Its management has a huge impact on the per...
详细信息
The analysis of the Quality of Service (QoS) level in a Cloud Computing environment becomes an attractive research domain as the utilization rate is daily higher and higher. Its management has a huge impact on the performance of both services and global Cloud infrastructures. Thus, in order to find a good trade-off, a Cloud provider has to take into account many QoS objectives, and also the manner to optimize them during the virtual machines allocation process. To tackle this complex challenge, this article proposed a multiobjective optimization of four relevant Cloud QoS objectives, using two different optimization methods: a Genetic Algorithm (GA) and a mixed integer linear programming (MILP) approach. The complexity of the virtual machine allocation problem is increased by the modeling of Dynamic Voltage and Frequency Scaling (DVFS) for energy saving on hosts. A global mixed-integer non linearprogramming formulation is presented and a MILP formulation is derived by linearization. A heuristic decomposition method, which uses the MILP to optimize intermediate objectives, is proposed. Numerous experimental results show the complementarity of the two heuristics to obtain various trade-offs between the different QoS objectives. (C) 2017 Elsevier B.V. All rights reserved.
Sprawl has a detrimental effect on quality of life and the environment. With dwindling resources and increasing populations, we must manage sprawl. Ewing et al. (2000) defined factors to measure sprawl in the present ...
详细信息
Sprawl has a detrimental effect on quality of life and the environment. With dwindling resources and increasing populations, we must manage sprawl. Ewing et al. (2000) defined factors to measure sprawl in the present urban structure. The measures are divided into four broad categories, which are density factors, mixed use factors, street factors, and center factors, and can be used in future planning of metro areas. In this research, we develop a mixedintegerprogramming model to optimize land usage subject to sprawl constraints, which are based upon the aforementioned sprawl measures. Due to the large size of the problem, we employ a combination of heuristics and Benders' decomposition similar to one described by Bazaraa and Sherali (1982) to provide an urban planner with suitable land use assignments. We show examples demonstrating how the planner can use this approach to analyze how various factors that affect land use and sprawl measures. Finally, we discuss topics of future research. (C) 2016 Elsevier Ltd. All rights reserved.
暂无评论