共查询到20条相似文献,搜索用时 10 毫秒
1.
The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known
also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the
visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of
a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected
profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm
and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the
already known heuristics. Computational experiments are made on standard instances. 相似文献
2.
《European Journal of Operational Research》1996,88(3):464-474
In the team orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time for each of the M members of the team, the goal is to determine M paths from the start point to the end point through a subset of locations in order to maximize the total score. In this paper, a fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points. The computational results are presented in detail. 相似文献
3.
Liangjun Ke Zongben XuZuren Feng Ke ShangXueming Qian 《European Journal of Operational Research》2013
In this paper, a proportion-based robust optimization approach is developed to deal with uncertain combinatorial optimization problems. This approach assumes that a certain proportion of uncertain coefficients in each solution are allowed to change and optimizes a deterministic model so as to achieve a trade-off between optimality and feasibility when the coefficients change. We apply this approach on team orienteering problem with interval data (TOPID), a variant of vehicle routing problem, which has not yet been studied before. A branch and price algorithm is proposed to solve the robust counterpart by using two novel dominance relations. Finally, numerical study is performed. The results show the usefulness of the proposed robust optimization approach and the effectiveness of our algorithm. 相似文献
4.
Hermann Bouly Duc-Cuong Dang Aziz Moukrim 《4OR: A Quarterly Journal of Operations Research》2010,8(1):49-70
The team orienteering problem (TOP) is a generalization of the orienteering problem. A limited number of vehicles is available
to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated
profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid genetic algorithm
using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and
local search techniques for mutation. We have called this hybrid method a memetic algorithm for the TOP. Computational experiments
conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new
improved solutions in at least 5 instances. 相似文献
5.
The Team Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to maximize the profit gained from visiting customers without exceeding a travel cost/time limit. This paper proposes a new and fast evaluation process for TOP based on an interval graph model and a Particle Swarm Optimization inspired Algorithm (PSOiA) to solve the problem. Experiments conducted on the standard benchmark of TOP clearly show that our algorithm outperforms the existing solving methods. PSOiA reached a relative error of 0.0005% whereas the best known relative error in the literature is 0.0394%. Our algorithm detects all but one of the best known solutions. Moreover, a strict improvement was found for one instance of the benchmark and a new set of larger instances was introduced. 相似文献
6.
Pieter Vansteenwegen Wouter Souffriau Greet Vanden Berghe Dirk Van Oudheusden 《European Journal of Operational Research》2009
In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximise the sum of the collected scores. This paper describes an algorithm that combines different local search heuristics to solve the TOP. Guided local search (GLS) is used to improve two of the proposed heuristics. An extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space. The algorithm is compared with the best known heuristics of the literature and applied on a large problem set. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. Applying GLS to solve the TOP appears to be a very promising technique. Furthermore, the usefulness of exploring more areas of the solution space is clearly demonstrated. 相似文献
7.
A discrete particle swarm optimization for lot-streaming flowshop scheduling problem 总被引:1,自引:0,他引:1
We consider an n-job, m-machine lot-streaming problem in a flowshop with equal-size sublots where the objective is to minimize the total weighted earliness and tardiness. To solve this problem, we first propose a so-called net benefit of movement (NBM) algorithm, which is much more efficient than the existing linear programming model for obtaining the optimal starting and completion times of sublots for a given job sequence. A new discrete particle swarm optimization (DPSO) algorithm incorporating the NBM algorithm is then developed to search for the best sequence. The new DPSO improves the existing DPSO by introducing an inheritance scheme, inspired by a genetic algorithm, into particles construction. To verify the proposed DPSO algorithm, comparisons with the existing DPSO algorithm and a hybrid genetic algorithm (HGA) are made. Computational results show that the proposed DPSO algorithm with a two-point inheritance scheme is very competitive for the lot-streaming flowshop scheduling problem. 相似文献
8.
In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service. 相似文献
9.
Zhigang Lian 《Applied Mathematical Modelling》2010,34(11):3518-3526
The performance of a scheduling system, in practice, is not evaluated to satisfy a single objective, but to obtain a trade-off schedule regarding multiple objectives. Therefore, in this research, I make use of multiple objective decision-making method, a global criterion approach, to develop a multi-objective scheduling problem model with different due-dates on parallel machines processes, in which consider three performance measures, namely minimum run time of every machine, earlierness time (no tardiness) and process time of every job, simultaneously. According to this special multi-objective scheduling problem, the method of reverse order drawing GATT will be proposed, at the same time, bring forward a united search particle swarm optimization algorithm (USPSOA) solves this multi-objective scheduling problem. The validity and adaptability of the USPSOA is investigated through experimental results. 相似文献
10.
Shih-Wei LinVincent F. Yu 《European Journal of Operational Research》2012,217(1):94-107
This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature. 相似文献
11.
This paper studies the team orienteering problem with time windows, the aim of which is to maximize the total profit collected by visiting a set of customers with a limited number of vehicles. Each customer has a profit, a service time and a time window. A service provided to any customer must begin in his or her time window. We propose an iterative framework incorporating three components to solve this problem. The first two components are a local search procedure and a simulated annealing procedure. They explore the solution space and discover a set of routes. The third component recombines the routes to identify high quality solutions. Our computational results indicate that this heuristic outperforms the existing approaches in the literature in average performance by at least 0.41%. In addition, 35 new best solutions are found. 相似文献
12.
Memetic particle swarm optimization 总被引:2,自引:0,他引:2
We propose a new Memetic Particle Swarm Optimization scheme that incorporates local search techniques in the standard Particle
Swarm Optimization algorithm, resulting in an efficient and effective optimization method, which is analyzed theoretically.
The proposed algorithm is applied to different unconstrained, constrained, minimax and integer programming problems and the
obtained results are compared to that of the global and local variants of Particle Swarm Optimization, justifying the superiority
of the memetic approach. 相似文献
13.
In the capacitated team orienteering problem (CTOP), we are given a set of homogeneous vehicles and a set of customers each with a service demand value and a profit value. A vehicle can get the profit of a customer by satisfying its demand, but the total demand of all customers in its route cannot exceed the vehicle capacity and the length of the route must be within a specified maximum. The problem is to design a set of routes that maximizes the total profit collected by the vehicles. In this article, we propose a new heuristic algorithm for the CTOP using the ejection pool framework with an adaptive strategy and a diversification mechanism based on toggling between two priority rules. Experimental results show that our algorithm can match or improve all the best known results on the standard CTOP benchmark instances proposed by Archetti et al. (2008). 相似文献
14.
Amir Hossein Gandomi Gun Jin Yun Xin-She Yang Siamak Talatahari 《Communications in Nonlinear Science & Numerical Simulation》2013,18(2):327-340
There are more than two dozen variants of particle swarm optimization (PSO) algorithms in the literature. Recently, a new variant, called accelerated PSO (APSO), shows some extra advantages in convergence for global search. In the present study, we will introduce chaos into the APSO in order to further enhance its global search ability. Firstly, detailed studies are carried out on benchmark problems with twelve different chaotic maps to find out the most efficient one. Then the chaotic APSO (CAPSO) will be compared with some other chaotic PSO algorithms presented in the literature. The performance of the CAPSO algorithm is also validated using three engineering problems. The results show that the CAPSO with an appropriate chaotic map can clearly outperform standard APSO, with very good performance in comparison with other algorithms and in application to a complex problem. 相似文献
15.
Balanced fuzzy particle swarm optimization 总被引:1,自引:0,他引:1
Amir Robati Gholam Abbas BaraniHossein Nezam Abadi Pour Mohammad Javad FadaeeJavad Rahimi Pour Anaraki 《Applied Mathematical Modelling》2012,36(5):2169-2177
In the present study an extension of particle swarm optimization (PSO) algorithm which is in conformity with actual nature is introduced for solving combinatorial optimization problems. Development of this algorithm is essentially based on balanced fuzzy sets theory. The classical fuzzy sets theory cannot distinguish differences between positive and negative information of membership functions, while in the new method both kinds of information “positive and negative” about membership function are equally important. The balanced fuzzy particle swarm optimization algorithm is used for fundamental optimization problem entitled traveling salesman problem (TSP). For convergence inspecting of new algorithm, method was used for TSP problems. Convergence curves were represented fast convergence in restricted and low iterations for balanced fuzzy particle swarm optimization algorithm (BF-PSO) comparison with fuzzy particle swarm optimization algorithm (F-PSO). 相似文献
16.
An exact algorithm for team orienteering problems 总被引:1,自引:1,他引:0
Sylvain Boussier Dominique Feillet Michel Gendreau 《4OR: A Quarterly Journal of Operations Research》2007,5(3):211-230
Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the
optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles
are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with
classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based
on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary
work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale
Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100
customers.
相似文献
17.
《Journal of computational science》2014,5(2):258-268
This paper proposes a new co-swarm PSO (CSHPSO) for constrained optimization problems, which is obtained by hybridizing the recently proposed shrinking hypersphere PSO (SHPSO) with the differential evolution (DE) approach. The total swarm is subdivided into two sub swarms in such a way that the first sub swarms uses SHPSO and second sub swarms uses DE. Experiments are performed on a state-of-the-art problems proposed in IEEE CEC 2006. The results of the CSHPSO is compared with SHPSO and DE in a variety of fashions. A statistical approach is applied to provide the significance of the numerical experiments. In order to further test the efficacy of the proposed CSHPSO, an economic dispatch (ED) problem with valve points effects for 40 generating units is solved. The results of the problem using CSHPSO is compared with SHPSO, DE and the existing solutions in the literature. It is concluded that CSHPSO is able to give the minimal cost for the ED problem in comparison with the other algorithms considered. Hence, CSHPSO is a promising new co-swarm PSO which can be used to solve any real constrained optimization problem. 相似文献
18.
Self-adaptive velocity particle swarm optimization for solving constrained optimization problems 总被引:4,自引:0,他引:4
Particle swarm optimization (PSO) is originally developed as an unconstrained optimization technique, therefore lacks an explicit
mechanism for handling constraints. When solving constrained optimization problems (COPs) with PSO, the existing research
mainly focuses on how to handle constraints, and the impact of constraints on the inherent search mechanism of PSO has been
scarcely explored. Motivated by this fact, in this paper we mainly investigate how to utilize the impact of constraints (or
the knowledge about the feasible region) to improve the optimization ability of the particles. Based on these investigations,
we present a modified PSO, called self-adaptive velocity particle swarm optimization (SAVPSO), for solving COPs. To handle
constraints, in SAVPSO we adopt our recently proposed dynamic-objective constraint-handling method (DOCHM), which is essentially
a constituent part of the inherent search mechanism of the integrated SAVPSO, i.e., DOCHM + SAVPSO. The performance of the
integrated SAVPSO is tested on a well-known benchmark suite and the experimental results show that appropriately utilizing
the knowledge about the feasible region can substantially improve the performance of the underlying algorithm in solving COPs. 相似文献
19.
This paper presents a co-evolutionary particle swarm optimization (PSO) algorithm, hybridized with noising metaheuristics,
for solving the delay constrained least cost (DCLC) path problem, i.e., shortest-path problem with a delay constraint on the
total “cost” of the optimal path. The proposed algorithm uses the principle of Lagrange relaxation based aggregated cost.
It essentially consists of two concurrent PSOs for solving the resulting minimization-maximization problem. The main PSO is
designed as a hybrid PSO-noising metaheuristics algorithm for efficient global search to solve the minimization part of the
DCLC-Lagrangian relaxation by finding multiple shortest paths between a source-destination pair. The auxiliary/second PSO
is a co-evolutionary PSO to obtain the optimal Lagrangian multiplier for solving the maximization part of the Lagrangian relaxation
problem. For the main PSO, a novel heuristics-based path encoding/decoding scheme has been devised for representation of network
paths as particles. The simulation results on several networks with random topologies illustrate the efficiency of the proposed
hybrid algorithm for the constrained shortest path computation problems. 相似文献
20.
The performance of PSO algorithm depends greatly on the appropriate parameter selection strategies for fine tuning its parameters. This paper proposes three new nonlinear strategies for selecting inertia weight which plays a significant role in particle’s foraging behaviour. The PSO variants implying these strategies are named as: fine grained inertia weight PSO (FGIWPSO); Double Exponential Self Adaptive IWPSO (DESIWPSO) and Double Exponential Dynamic IWPSO (DEDIWPSO). In FGIWPSO, inertia weight is obtained adaptively, depending on particle’s iteration wise performance and decreases exponentially. DESIWPSO and DEDIWPSO employ Gompertz function, a double exponential function for selecting inertia weight. In DESIWPSO the particles’ iteration wise performance is fed as input to the Gompertz function. On the other hand DEDIWPSO evaluates the inertia weight for whole swarm iteratively using Gompertz function where relative iteration is fed as input. The efficacy and efficiency of proposed approaches is validated on a suite of benchmark functions. The proposed variants are compared with non linear inertia weight and exponential inertia weight strategies. Experimental results assert that the proposed modifications help in improving PSO performance in terms of solution quality as well as convergence rate. 相似文献