共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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. 相似文献
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.
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.
相似文献
5.
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). 相似文献
6.
The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP. 相似文献
7.
Nenad Mladenović Dragan Urošević Saı¨d Hanafi Aleksandar Ilić 《European Journal of Operational Research》2012
We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers. 相似文献
8.
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. 相似文献
9.
This paper presents a General Variable Neighborhood Search (GVNS) heuristic for the Traveling Salesman Problem with Time Windows (TSPTW). The heuristic is composed by both constructive and optimization stages. In the first stage, the heuristic constructs a feasible solution using VNS, and in the optimization stage the heuristic improves the feasible solution with a General VNS heuristic. Both constructive and optimization stages take advantage of elimination tests, partial neighbor evaluation and neighborhood partitioning techniques. Experimental results show that this approach is efficient, reducing significantly the computation time and improving some best known results from the literature. 相似文献
10.
We introduce a new extension of Punnen's exponential neighborhood for the traveling salesman problem (TSP). In contrast to
an interesting generalization of Punnen's neighborhood by De Franceschi, Fischetti, and Toth (2005), our neighborhood is searchable
in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related
problems, including those of De Franceschi, Fischetti, and Toth (2005) for the vehicle routing problem.
Research of GG was partially supported by Leverhulme Trust and by the IST Programme of the European Community, under the PASCAL
Network of Excellence, IST-2002–506778. 相似文献
11.
We consider constant-performance, polynomial-time, nonexact algorithms for the minimax or bottleneck version of the Travelling Salesman Problem. It is first shown that no such algorithm can exist for problems with arbitrary costs unless P = NP. However, when costs are positive and satisfy the triangle inequality, we use results pertaining to the squares of biconnected graphs to produce a polynomial-time algorithm with worst-case bound 2 and show further that, unless P = NP, no polynomial alternative can improve on this value. 相似文献
12.
The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem
and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of
complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally
compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes
with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature. 相似文献
13.
The solution of the aircrew-scheduling problem is represented by a set of rotations developed from a given set of flight segments.
Once the set of rotations to be made by aircrew members has been determined, the air carrier must solve the aircrew rostering
problem that entails the monthly assignment of aircrew members to planned rotations. This paper attempts to solve the aircrew
rostering problem, thus constructing personalized monthly schedules using Simulated Annealing, Genetic Algorithms, and Tabu
Search techniques. The developed models are tested on numerical examples that consist of constructing schedules for pilots.
Dimensions of the considered examples are characteristic of small and medium-sized airlines. 相似文献
14.
The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most
significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers
need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable.
In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood
Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP
has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm
is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP
algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number
of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm
gives a new best solution. 相似文献
15.
Justo Puerto Dionisio Pérez-Brito Carlos G. García-González 《European Journal of Operational Research》2014
This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found. 相似文献
16.
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. 相似文献
17.
This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework. 相似文献
18.
The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. 相似文献
19.
The clustered traveling salesman problem is an extension of the classical traveling salesman problem where the set of vertices is partitioned into clusters. The objective is to find a least cost Hamiltonian cycle such that the vertices of each cluster are visited contiguously and the clusters are visited in a prespecified order. A tabu search heuristic is proposed to solve this problem. This algorithm periodically restarts its search by merging two elite solutions to form a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics. 相似文献