Given a group of people traveling from the same origin to multiple destinations, the Taxi Sharing Problem consists in assigning taxis to each person such that the total cost spent by the group of people is minimized. ...
详细信息
ISBN:
(数字)9783319395951
ISBN:
(纸本)9783319395944;9783319395951
Given a group of people traveling from the same origin to multiple destinations, the Taxi Sharing Problem consists in assigning taxis to each person such that the total cost spent by the group of people is minimized. This problem arises in the context of Smart Mobility, where the resources of a city must be optimized to save costs and pollution while the mobility services are improved for the citizens. We propose a mixed integer linear programming formulation as an accurate way to solve the problem of taxi sharing. We empirically analyze our formulation solving different real-like instances of the problem with 9 to 69 people.
Many problems of interest for cyber-physical network systems can be formulated as mixedintegerlinear Programs in which the constraints are distributed among the agents. In this paper we propose a distributed algorit...
详细信息
Many problems of interest for cyber-physical network systems can be formulated as mixedintegerlinear Programs in which the constraints are distributed among the agents. In this paper we propose a distributed algorithm to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. In the proposed algorithm, at each communication round, agents solve locally a small LP, generate suitable cutting planes, namely intersection cuts and cost-based cuts, and communicate a fixed number of active constraints, i.e., a candidate optimal basis. We prove that, if the cost is integer, the algorithm converges to the lexicographically minimal optimal solution in a finite number of communication rounds. Finally, through numerical computations, we analyze the algorithm convergence as a function of the network size.
Consideration was given to the two-step problem of stochastic optimization with a bilinear model which describes the problem of forming the securities portfolio consisting of some risk assets and one riskless asset. T...
详细信息
Consideration was given to the two-step problem of stochastic optimization with a bilinear model which describes the problem of forming the securities portfolio consisting of some risk assets and one riskless asset. The probability of exceeding the given threshold of capital is used as the optimality criterion. At the second step, the piecewise constant control is used as the capital control. Determined were the upper and lower estimates of the probability functional. The problems of maximizing the upper and lower estimates of the probability functional were reduced to the problems of mixed integer linear programming by means of discretizing the probabilistic measure. An algorithm to seek an approximate solution to the original problem was proposed, and an example was considered.
Square-based fiducial markers are one of the most popular approaches for camera pose estimation due to its fast detection and robustness. In order to maximize their error correction capabilities, it is required to use...
详细信息
Square-based fiducial markers are one of the most popular approaches for camera pose estimation due to its fast detection and robustness. In order to maximize their error correction capabilities, it is required to use an inner binary codification with a large inter-marker distance. This paper proposes two mixed integer linear programming (MILP) approaches to generate configurable square-based fiducial marker dictionaries maximizing their inter-marker distance. The first approach guarantees the optimal solution, however, it can only be applied to relatively small dictionaries and number of bits since the computing times are too long for many situations. The second approach is an alternative formulation to obtain suboptimal dictionaries within restricted time, achieving results that still surpass significantly the current state of the art methods. (C) 2015 Elsevier Ltd. All rights reserved.
Unmanned air vehicles (UAVs), which have been popular in military context, have recently attracted attention of many researchers because of their potential civilian applications. However, before the UAVs can be used f...
详细信息
Unmanned air vehicles (UAVs), which have been popular in military context, have recently attracted attention of many researchers because of their potential civilian applications. However, before the UAVs can be used for civilian applications, a systematic integration of UAVs in the National Airspace System (NAS) is needed that can allow safe operation of UAVs along with other manned aircrafts. One of the critical capabilities needed for safe operation of the UAVs in the NAS is the ability of UAV to carry out sense and avoid task which would allow the UAV to amend its path to avoid collision with other aircrafts. Despite recent technological advances, such as availability of automatic dependent surveillance broadcast that can transmit position of an aircraft to others in the vicinity, planning a collision-free path autonomously is still challenging in a dynamic environment. The objective of this paper is to develop a methodology for discovering a path for the UAV that meets mission goals, avoids collision, is optimal in terms of path length and, more importantly, is feasible. The paper formulates the problem of path planning using the mathematical paradigm of mixed integer linear programming and provides a solution strategy for solving this problem in the dynamic sense. The tasks of avoidance of obstacles and waypoint navigation are incorporated as constraints in the MILP problem. The paper presents the solution of the MILP problem and verifies the performance of the proposed methodology with regard to optimality of the solution and computational time requirement via several simulated scenarios of different complexities.
When operating a compressor station, given its mass flow rate, inlet pressure and temperature, and discharge pressure, dispatchers need to decide which compressors to run and at what flow rates, i.e., the operating sc...
详细信息
When operating a compressor station, given its mass flow rate, inlet pressure and temperature, and discharge pressure, dispatchers need to decide which compressors to run and at what flow rates, i.e., the operating scheme of the station, to cut its energy costs. This paper addresses this problem under unsteady states. This means that at least one of the four given operating parameters is time-dependent, and therefore so is the operating scheme. The key constraints of the problem are the minimum uptime and downtime of each compressor, which interconnect the operating schemes at each time step and complicate the problem. The energy cost of a compressor unit is almost a linear function of its flow rate for a given inlet pressure, inlet temperature, and discharge pressure. Therefore, the optimization problem was formulated as a mixed integer linear programming (MILP) model, which was solved by CPLEX. The optimal operating schemes given by CPLEX were simulated to reevaluate the objective function, and the error of the linearized energy cost model was shown to be within 5%. The recalculated objective function values were 0.22%-1.18% higher than those of the true optimum. However, the MILP method was 0.49-64.95 times faster than the dynamic programming approach yielding global optimal solutions. (C) 2016 Elsevier B.V. All rights reserved.
In this paper, we develop mixed-integerlinearprogramming models for assigning the most appropriate teaching assistants to the tutorials in a department. The objective is to maximize the number of tutorials that are ...
详细信息
In this paper, we develop mixed-integerlinearprogramming models for assigning the most appropriate teaching assistants to the tutorials in a department. The objective is to maximize the number of tutorials that are taught by the most suitable teaching assistants, accounting for the fact that different teaching assistants have different capabilities and each teaching assistant's teaching load cannot exceed a maximum value. Moreover, with optimization models, the teaching load allocation, a time-consuming process, does not need to be carried out in a manual manner. We have further presented a number of extensions that capture more practical considerations. Extensive numerical experiments show that the optimization models can be solved by an off-the-shelf solver and used by departments in universities.
An appropriate design of work-rest schedule is recognized as an efficient way in providing betterergonomicenvironment, improving labor productivity as well as safety. Construction workers usually undertake physically ...
详细信息
An appropriate design of work-rest schedule is recognized as an efficient way in providing betterergonomicenvironment, improving labor productivity as well as safety. Construction workers usually undertake physically demanding tasks in an outdoor environment, with awkward postures and repetitive motions. This study proposes a mixed-integerlinearprogramming approach to optimize the work-rest schedule for construction workers in hot weather for the objective of maximizing the total productive time. The model takes into consideration the physical and physiological conditions of the workers, the working environment, the nature of the jobs and the minimum rest duration of the government regulation. The results of numerical experiments show that the proposed model outperforms a default work-rest schedule by up to 10% in terms of total productive time. This implies considerable cost savings for the construction industry.
In a recent article (Goncalves et al., AIChE J. 2017. DOI: 10.1002/aic.15556), we presented a mixed-integerlinearprogramming formulation for the detailed design of shell and tube heat exchangers based on the Kern ap...
详细信息
In a recent article (Goncalves et al., AIChE J. 2017. DOI: 10.1002/aic.15556), we presented a mixed-integerlinearprogramming formulation for the detailed design of shell and tube heat exchangers based on the Kern approach (Kern, D. Q Process Heat Transfer;McGraw Hill, 1950). The formulation relies on the use of standardized values for several mechanical parts, which we express in terms of discrete choices. Because we aim at having this model used as part of more complex models (i.e., heat exchanger networks synthesis), we identified a need to improve its computational efficiency. In this article, we explore several different modeling options to speed up solutions. These options are based on different alternatives of aggregation of the discrete values in relation to the set of binary variables. Numerical results show that these procedures allow large computational effort reductions.
This paper deals with the Event Scheduling Problem with Consumption and Production of Resources (ESPCPR). ESPCPR is an extension of the Resource Constrained Project Scheduling Problem (RCPSP), where activities requiri...
详细信息
暂无评论