A multiobjective model for locating undesirable facilities

In this paper, we develop a multiobjective model to depict the tradeoffs involved when locating one or more undesirable facilities to service a region. We assume that the region requires a certain capacity of service, and that this capacity can be met by building a combination of different-sized facilities. Examples could include sanitary landfills, incinerators, and power-generating stations. Our objectives are to minimize the total cost of the facilities located, the total opposition to the facilities, and the maximum disutility imposed on any individual. Opposition and disutility are assumed to be nonlinearly decreasing functions of distance, and increasing functions of facility size. We formulate our model as a multiobjective mixed-integer program, and generate the set of efficient solutions using an enumeration algorithm. Our code can solve realistically sized problems on a microcomputer. We give an example to illustrate the tradeoffs between the three objectives, which are inevitable in such a location problem.This research was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada (OGP 25481), and by the Nova Fellowship of the Faculty of Business, University of Alberta.     

Computing the Pareto frontier of a bi-objective bi-level linear problem using a multiobjective mixed-integer programming algorithm

In this article, we study the bi-level linear programming problem with multiple objective functions on the upper level (with particular focus on the bi-objective case) and a single objective function on the lower level. We have restricted our attention to this type of problem because the consideration of several objectives at the lower level raises additional issues for the bi-level decision process resulting from the difficulty of anticipating a decision from the lower level decision maker. We examine some properties of the problem and propose a methodological approach based on the reformulation of the problem as a multiobjective mixed 0–1 linear programming problem. The basic idea consists in applying a reference point algorithm that has been originally developed as an interactive procedure for multiobjective mixed-integer programming. This approach further enables characterization of the whole Pareto frontier in the bi-objective case. Two illustrative numerical examples are included to show the viability of the proposed methodology.     

Stochastic Multiobjective Optimization: Sample Average Approximation and Applications

We investigate one stage stochastic multiobjective optimization problems where the objectives are the expected values of random functions. Assuming that the closed form of the expected values is difficult to obtain, we apply the well known Sample Average Approximation (SAA) method to solve it. We propose a smoothing infinity norm scalarization approach to solve the SAA problem and analyse the convergence of efficient solution of the SAA problem to the original problem as sample sizes increase. Under some moderate conditions, we show that, with probability approaching one exponentially fast with the increase of sample size, an ϵ-optimal solution to the SAA problem becomes an ϵ-optimal solution to its true counterpart. Moreover, under second order growth conditions, we show that an efficient point of the smoothed problem approximates an efficient solution of the true problem at a linear rate. Finally, we describe some numerical experiments on some stochastic multiobjective optimization problems and report preliminary results.     

Bi-criteria dynamic location-routing problem for patrol coverage

In this paper, we address the problem of dynamic patrol routing for state troopers for effective coverage of highways. Specifically, a number of state troopers start their routes at temporary stations (TS), patrol critical locations with high crash frequencies, and end their shifts at other (or the same) TS so the starting points for the next period are also optimized. We determine the number of state troopers, their assigned routes, and the locations of the TS where they start and end their routes. The TS are selected from a given set of potential locations. The problem, therefore, is a multi-period dynamic location-routing problem in the context of public service. Our objective is to maximize the critical location coverage benefit while minimizing the costs of TS selections, vehicle utilizations, and routing/travel. The multi-objective nature of the problem is handled using an ?-constraint approach. We formulate the problem as a mixed integer linear programming model and solve it using both off-the-shelf optimization software and a custom-built, efficient heuristic algorithm. The heuristic, utilizing the hierarchical structure of the problem, is built on the decomposition of location and routing problems. By allowing routing to start from multiple locations, our model improves the coverage by as much as 12% compared with the single-depot coverage model.     

A mathematical programming model for the bus deviation route problem

In small towns, or in those peripherical metropolitan areas in which the demand for public transportation is relatively low, the objectives of the bus route planner are different from those faced in highly congested networks. Some towns, also in Italy, are experimenting with urban public transportation systems where regular bus routes are designed which allow users located at specific points outside the main line to signal their presence to the bus driver, who then deviates from the main route to satisfy this demand. This way the bus line is a mixture between a regular line and a dial-a-ride system. The bus deviation route problem is concerned with the design problem which arises in planning the location of the demand points outside the line. A model is presented which takes into account both the advantage of passengers served by this deviation device and the disadvantage suffered by passengers on the bus, whose travel time increases during deviations, and by passengers downstream of the deviation whose waiting time also increases. Through some modeling assumption we are able to represent this problem as a mixed integer linear programming problem, whose relatively low dimension allows for exact solution through standard simplex-based branch and bound code. The proposed model has been applied to a real case and some results of this are presented and discussed.     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

无约束多目标规划的信赖域方法

本文将信赖域方法应用于多目标规划,提出了一类解多目标问题的新算法,并证明了全局收敛性。     

Consequences of dropping nonessential objectives for the application of MCDM methods

In this article we consider the problem of nonessential objectives for multiobjective optimization problems (MOP) with linear objective functions. In 1977 an approach based on the reduction of size of the matrix of objective functions has been worked out by one of the present authors (Gal, T., Leberling, H., 1977. European Journal of Operations Research 1, 176–184). Although this method for dropping nonessential objectives leads to a mathematically equivalent MOP, problems concerning the application of MOP methods may arise. For instance, dropping some (or all) of the nonessential objectives the question is, how to ensure obtaining the same solution as with all objectives involved. We consider the problem of adapting the parameters of multiobjective optimization methods. For the case of weighting methods a simple procedure for adapting the weights is analyzed. For other methods, e.g. reference point approaches, such a simple possibility for adapting the parameters is not given.     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

垃圾填埋场选址问题的模糊数学模型研究

为有助于在环境和经济框架内评价垃圾填埋场选址决策,本文建立了关于该问题的多目标模型,模型中既考虑了安置和运营设施需要的固定成本和可变成本,也考虑了居民区承受的风险,以及各居民区承担风险的公平性。并进一步讨论了用模糊方法处理的一般多目标规划模型的模糊最优解与有效解及弱有效解之间的关系。最后使用两种模糊目标规划方法求解数值例子以分析所建模型的适用性,结果表明,加权模糊方法可以为决策者提供更接近期望值的满意方案。     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

在闭凸集上连续型多场址的最优选择

本文考虑带有约束的连续型多场址问题(CEMFLC).对于连续型多场址问题(CEMFLC),我们给出了在闭集上选择最优场址的算法,证明了该算法是全局收敛的,最后,我们指出这一算法可用于解有约束或无约束的的高离散型多场址问题(EMFL),而且简化了(EMFL)问题现有的一些算法.     

Hybrid biobjective evolutionary algorithms for the design of a hospital waste management network

Colombian environmental authorities are exploring new alternatives for improving the disposal of hospital waste generated in the Department of Boyacá (Colombia). To design this hospital waste management network we propose a biobjective obnoxious facility location problem (BOOFLP) that deals with the existing tradeoff between a low-cost operating network and the negative effect on the population living near the waste management facilities. To solve the BOOFLP we propose a hybrid approach that combines a multiobjective evolutionary algorithm (NSGA II) with a mixed-integer program. The algorithms are compared against the Noninferior Set Estimation (NISE) method and tested on data from Boyacá’s hospital waste management network and publicly available instances.     

Solution of a possibilistic multiobjective linear programming problem

The estimate of the parameters which define a conventional multiobjective decision making model is a difficult task. Normally they are either given by the Decision Maker who has imprecise information and/or expresses his considerations subjectively, or by statistical inference from the past data and their stability is doubtful. Therefore, it is reasonable to construct a model reflecting imprecise data or ambiguity in terms of fuzzy sets and several fuzzy approaches to multiobjective programming have been developed 1, 9, 10, 11. The fuzziness of the parameters gives rise to a problem whose solution will also be fuzzy, see 2, 3, and which is defined by its possibility distribution. Once the possibility distribution of the solution has been obtained, if the decision maker wants more precise information with respect to the decision vector, then we can pose and solve a new problem. In this case we try to find a decision vector, which approximates as much as possible the fuzzy objectives to the fuzzy solution previously obtained. In order to solve this problem we shall develop two different models from the initial solution and based on Goal Programming: an Interval Goal Programming Problem if we define the relation “as accurate as possible” based on the expected intervals of fuzzy numbers, as we showed in [4], and an ordinary Goal Programming based on the expected values of the fuzzy numbers that defined the goals. Finally, we construct algorithms that implement the above mentioned solution method. Our approach will be illustrated by means of a numerical example.     

Solving a concrete sleepers production scheduling by genetic algorithms

PRECON S.A. is a manufacturing company devoted to produce prefabricated concrete parts for several industries as railway transportation and agricultural industries. Recently, PRECON S.A. signed a contract with RENFE, the Spanish National Railway Company, to manufacture pre-stressed concrete sleepers for the sidings of the new railways of the high speed train (AVE). The scheduling problem associated with the manufacturing process of the sleepers is very complex, since this involves several constraints and objectives. These constraints are related to production capacity, the quantity of available moulds, demand satisfaction and other operational constraints. The two main objectives are related to the way to maximize the utilization of manufacturing resources and minimize mould movements. We developed a deterministic crowding genetic algorithm for this multiobjective problem. The algorithm has proved to be a powerful and flexible tool to solve large-scale instances of this real and complex scheduling problem.     

Heuristic for a new multiobjective scheduling problem

We consider a telecommunication problem in which the objective is to schedule data transmission to be as fast and as cheap as possible. The main characteristic and restriction in solving this multiobjective optimization problem is the very limited computational capacity available. We describe a simple but efficient local search heuristic to solve this problem and provide some encouraging numerical test results. They demonstrate that we can develop a computationally inexpensive heuristic without sacrificing too much in the solution quality.     

A meta-model for multiobjective routing in MPLS networks

MPLS (Multiprotocol Label Switching) enables the utilisation of explicit routes and other advanced routing mechanisms in multiservice packet networks, capable of dealing with multiple and heterogeneous QoS (Quality of Service) parameters. Firstly the paper presents a discussion of conceptual and methodological issues raised by multiobjective routing optimisation models for MPLS networks. The major contribution is the proposal of a multiobjective routing optimisation framework for MPLS networks. The major features of this modelling framework are: the formulation of a three-level hierarchical routing optimisation problem including network and service performance objectives, the inclusion of fairness objectives in the different levels of optimisation and a two-level stochastic representation of the traffic in the network (traffic flow and packet stream levels). A variant of the general model for two classes of traffic flows, QoS traffic and Best Effort traffic, is also presented. Finally a stochastic teletraffic modelling approach, underlying the optimisation model, is fully described. Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

A path following method for box-constrained multiobjective optimization with applications to goal programming problems

We propose a path following method to find the Pareto optimal solutions of a box-constrained multiobjective optimization problem. Under the assumption that the objective functions are Lipschitz continuously differentiable we prove some necessary conditions for Pareto optimal points and we give a necessary condition for the existence of a feasible point that minimizes all given objective functions at once. We develop a method that looks for the Pareto optimal points as limit points of the trajectories solutions of suitable initial value problems for a system of ordinary differential equations. These trajectories belong to the feasible region and their computation is well suited for a parallel implementation. Moreover the method does not use any scalarization of the multiobjective optimization problem and does not require any ordering information for the components of the vector objective function. We show a numerical experience on some test problems and we apply the method to solve a goal programming problem.     

Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning

In this paper, we propose a modification of Benson’s algorithm for solving multiobjective linear programmes in objective space in order to approximate the true nondominated set. We first summarize Benson’s original algorithm and propose some small changes to improve computational performance. We then introduce our approximation version of the algorithm, which computes an inner and an outer approximation of the nondominated set. We prove that the inner approximation provides a set of -nondominated points. This work is motivated by an application, the beam intensity optimization problem of radiotherapy treatment planning. This problem can be formulated as a multiobjective linear programme with three objectives. The constraint matrix of the problem relies on the calculation of dose deposited in tissue. Since this calculation is always imprecise solving the MOLP exactly is not necessary in practice. With our algorithm we solve the problem approximately within a specified accuracy in objective space. We present results on four clinical cancer cases that clearly illustrate the advantages of our method.