This article describes the application of soft computing methods for solving the problem of locating garbage accumulation points in urban scenarios. This is a relevant problem in modern smart cities, in order to reduce negative environmental and social impacts in the waste management process, and also to optimize the available budget from the city administration to install waste bins. A specific problem model is presented, which accounts for reducing the investment costs, enhance the number of citizens served by the installed bins, and the accessibility to the system. A family of single- and multi-objective heuristics based on the PageRank method and two mutiobjective evolutionary algorithms are proposed. Experimental evaluation performed on real scenarios on the cities of Montevideo (Uruguay) and Bahia Blanca (Argentina) demonstrates the effectiveness of the proposed approaches. The methods allow computing plannings with different trade-off between the problem objectives. The computed results improve over the current planning in Montevideo and provide a reasonable budget cost and quality of service for Bahia Blanca.
Several articles have presented heuristics and soft computing methods for solving problems that are similar to the GAPs location problem. Bautista and Pereira @cite_15 modeled the GAPs location problem as a minimal set covering maximum satisfiability problem, and proposed a genetic algorithm and a GRASP metaheuristic for solving real instances in Barcelona, Spain. Other authors have applied integral approaches to solve the bins location problem and the routing collection problem simultaneously. For example, Chang and Wei @cite_32 used a fuzzy evolutionary search to solve the problem for a scenario in Kaohsiung, Taiwan. The model considered the percentage of population served, the average walking distance between users and their assigned GAP, and the approximate length of the routes of collecting vehicles as objectives. Explicit costs were not taken into account. @cite_8 introduced the Waste Bin Allocation and Routing Problem, which was solved applying different methodologies that combine sequential and simultaneous strategies; the allocation was solved either with an exact or an heuristic method, while the routing was solved using Variable Neighborhood Search.
@cite_15 @cite_32 @cite_8
2115083197 2015462215 2047612779 2024061864
The efficient organization of waste collection systems based on bins located along the streets involves the solution of several tactical optimization problems. In particular, the bin configuration and sizing at each collection site as well as the service frequency over a given planning horizon have to be decided. In this context, a higher service frequency leads to higher routing costs, but at the same time less or smaller bins are required, which leads to lower bin allocation investment costs. The bins used have different types and different costs and there is a limit on the space at each collection site as well as a limit on the total number of bins of each type that can be used. In this paper we consider the problem of designing a collection system consisting of the combination of a vehicle routing and a bin allocation problem in which the trade-off between the associated costs has to be considered. The solution approach combines an effective variable neighborhood search metaheuristic for the routing part with a mixed integer linear programming-based exact method for the solution of the bin allocation part. We propose hierarchical solution procedures where the two decision problems are solved in sequence, as well as an integrated approach where the two problems are considered simultaneously. Extensive computational testing on synthetic and real-world instances with hundreds of collection sites shows the benefit of the integrated approaches with respect to the hierarchical ones. Abstract The problem of locating hub facilities and allocating non-hub nodes to those hubs arises frequently in the design of communication networks, airline passenger flow and parcel delivery networks. In this paper we consider uncapacitated multiple and single allocation p -hub median problems. We develop new mixed 0 1 linear formulations with tight linear programming relaxations. The approach is tested on a well known and heavily used benchmark data set of real-world problems with resulting LP relaxations ranging from 10010 to 391 250 variables and from 2 101 to 31 901 constraints, which proved to be difficult linear programs. Yet, this approach proved to be very effective: in almost all instances the linear programming solution was integer. In cases with fractional solutions, the integrality was achieved by adding a small partial set of integrality constraints. Therefore, we extended the range of optimally solvable instances of these NP-hard hub location problems, which have defied researchers for the last ten years. As an additional result for the single allocation case we were able to establish optimality of all heuristic solutions obtained via tabu search algorithm from a previous study. For the more difficult single allocation p -hub median problem we also used the best known heuristic solution as a guidance in adding integrality constraints. This novel linkage between optimal and heuristic solutions has a potential impact in a number of other problem settings, where efficient heuristic solutions exist and are probably, but not provably optimal. This paper considers a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands. A tabu search heuristic is developed for this problem. Comparisons with known optimal solutions on problems whose sizes vary from 6 to 46 customers indicate that the heuristic produces an optimal solution in 89.45 of cases, with an average deviation of 0.38 from optimality. We present a new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows. The algorithm combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. More precisely, guided local search is used to regulate a composite local search in the first stage and the neighborhood of the evolution strategies algorithm in the second stage. The vehicle routing problem with time windows is a classical problem in operations research, where the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified time windows. The presented algorithm is specifically designed for large-scale problems. The computational experiments were carried out on an extended set of 302 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 86 of all test instances within reasonable computing times. The power of the algorithm is confirmed by the results obtained on 23 capacitated vehicle routing problems from the literature.