共查询到20条相似文献,搜索用时 31 毫秒
1.
In the single vehicle routing allocation problem (SVRAP) we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem. In this paper, we present a tabu search algorithm for the SVRAP. Our tabu search algorithm includes aspiration, path relinking and frequency-based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others. 相似文献
2.
Ilfat Ghamlouche Teodor Gabriel Crainic Michel Gendreau 《Annals of Operations Research》2004,131(1-4):109-133
In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems. 相似文献
3.
Alireza Rahimi-Vahed Teodor Gabriel Crainic Michel Gendreau Walter Rei 《Journal of Heuristics》2013,19(3):497-524
In this paper, we consider a multi-depot periodic vehicle routing problem which is characterized by the presence of a homogeneous fleet of vehicles, multiple depots, multiple periods, and two types of constraints that are often found in reality, i.e., vehicle capacity and route duration constraints. The objective is to minimize total travel costs. To tackle the problem, we propose an efficient path relinking algorithm whose exploration and exploitation strategies enable the algorithm to address the problem in two different settings: (1) As a stand-alone algorithm, and (2) As a part of a co-operative search algorithm called integrative co-operative search. The performance of the proposed path relinking algorithm is evaluated, in each of the above ways, based on standard benchmark instances. The computational results show that the developed PRA performs well, in both solution quality and computational efficiency. 相似文献
4.
Solving the flight perturbation problem with meta heuristics 总被引:1,自引:0,他引:1
Tobias Andersson 《Journal of Heuristics》2006,12(1-2):37-53
When there is a perturbation in a carefully constructed aircraft schedule, e.g. an aircraft breakdown, it is important to
minimize the negative consequences of this disturbance. Here, a tabu search and a simulated annealing approach to the flight
perturbation problem are presented. The heuristics use a tree-search algorithm to find new schedules for the aircraft, and
utilize a path relinking strategy to explore paths between structurally different solutions. The computational results indicate
that the solution strategies, especially the tabu search, can be successfully used to solve the flight perturbation problem. 相似文献
5.
The integrated operational transportation planning problem extends the traditional vehicle routing and scheduling problem by the possibility of outsourcing a part of the requests by involving subcontractors. The purpose of this paper is to present the integrated planning problem and to propose an approach for solving it by a tabu search heuristic. Existing approaches from literature which discuss vehicle routing combined with outsourcing regard only one specific type of subcontracting. This paper describes and explores the complex situation where an own fleet and several types of subcontracting are used for request fulfillment. As the approach contains new aspects, unknown to the literature so far, tabu search is extended to special types of moves. On the basis of computational results the cost structure is analyzed in order to investigate the long-term planning question whether and to what extend it is profitable to maintain an own fleet. 相似文献
6.
Probabilistic diversification and intensification in local search for vehicle routing 总被引:18,自引:0,他引:18
This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving
vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches.
It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this
technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented
in this article, too. The solutions of nearly forty problem instances of the literature have been improved. 相似文献
7.
《European Journal of Operational Research》2006,169(2):606-622
In this paper we use a scatter search framework to solve the vehicle routing problem with time windows (VRPTW). Our objective is to achieve effective solutions and to investigate the effects of reference set design parameters pertaining to size, quality and diversity. Both a common arc method and an optimization-based set covering model are used to combine vehicle routing solutions. A reactive tabu search metaheuristic and a tabu search with an advanced recovery feature, together with a set covering procedure are used for solution improvement. Our approach led to a robust solution method, generating solution quality that is competitive with the current best metaheuristics. 相似文献
8.
F Alonso M J Alvarez J E Beasley 《The Journal of the Operational Research Society》2008,59(7):963-976
In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented. 相似文献
9.
10.
In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements. 相似文献
11.
《European Journal of Operational Research》2006,169(2):359-372
Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems.This paper provides the main principles and ideas of scatter search and its generalized form path relinking. We first describe a basic design to give the reader the tools to create relatively simple implementations. More advanced designs derive from the fact that scatter search and path relinking are also intimately related to the tabu search (TS) metaheuristic, and gain additional advantage by making use of TS adaptive memory and associated memory-exploiting mechanisms capable of being tailored to particular contexts. These and other advanced processes described in the paper facilitate the creation of sophisticated implementations for hard problems that often arise in practical settings. Due to their flexibility and proven effectiveness, scatter search and path relinking can be successfully adapted to tackle optimization problems spanning a wide range of applications and a diverse collection of structures, as shown in the papers of this volume. 相似文献
12.
根据第三方库存-路线问题的特点,以车辆租赁费用和运行费用之和为目标函数,不限制客户每次的配送量小于车辆容量,建立了满载运输和非满载运输混合的整数规划模型.针对第三方库存-路线问题的复杂性,本文设计嵌入禁忌搜索的遗传算法来同时决策库存和路线问题.首先对配送间隔进行编码,然后用禁忌搜索法计算每天需要配送的车辆路线问题.最后与其下界值进行比较,结果表明该算法是一个有效的算法,不但第三方能取得较低的运营总成本和较高的车辆利用率,而且也能为客户节约库存空间. 相似文献
13.
《European Journal of Operational Research》2006,169(2):508-519
Artificial neural networks (ANN) have been widely used for both classification and prediction. This paper is focused on the prediction problem in which an unknown function is approximated. ANNs can be viewed as models of real systems, built by tuning parameters known as weights. In training the net, the problem is to find the weights that optimize its performance (i.e., to minimize the error over the training set). Although the most popular method for training these networks is back propagation, other optimization methods such as tabu search or scatter search have been successfully applied to solve this problem. In this paper we propose a path relinking implementation to solve the neural network training problem. Our method uses GRG, a gradient-based local NLP solver, as an improvement phase, while previous approaches used simpler local optimizers. The experimentation shows that the proposed procedure can compete with the best-known algorithms in terms of solution quality, consuming a reasonable computational effort. 相似文献
14.
The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP. 相似文献
15.
Multi-objective optimization problems deal with the presence of different conflicting objectives. Given that it is not possible to obtain a single solution by optimizing all the objectives simultaneously, a common way to face these problems is to obtain a set of efficient solutions called the non-dominated frontier. In this paper, we address the problem of routing school buses with two objectives: minimize the number of buses, and minimize the longest time a student would have to stay in the bus. The trade-off in this problem is between service level, which is represented by the maximum route length, and operational cost, which is represented by the number of buses in the solution. We present different constructive solution methods and a tabu search procedure to obtain non-dominated solutions. The procedure is coupled with an intensification phase based on the path relinking methodology: a strategy proposed several years ago, which has been rarely used in actual implementations. Computational experiments with real data, in the context of routing school buses in a rural area, establish the effectiveness of our procedure in relation to the approach previously identified to be the best. 相似文献
16.
In this paper, we present a solution method for a bi-objective vehicle routing problem, called the vehicle routing problem
with route balancing (VRPRB), in which the total length and balance of the route lengths are the objectives under consideration.
The method, called Target Aiming Pareto Search, is defined to hybridize a multi-objective genetic algorithm for the VRPRB
using local searches. The method is based on repeated local searches with their own appropriate goals. We also propose an
implementation of the Target Aiming Pareto Search using tabu searches, which are efficient meta-heuristics for the vehicle
routing problem. Assessments with standard metrics on classical benchmarks demonstrate the importance of hybridization as
well as the efficiency of the Target Aiming Pareto Search. 相似文献
17.
The open vehicle routing problem (VRP) is an immediate variant of the standard vehicle routing problem where the vehicle need not return to the depot after servicing its last customer. In this paper, we present results on an implementation of the attribute-based hill climber heuristic to the open VRP. The attribute-based hill climber heuristic is a parameter-free variant of the tabu search principle and has shown to be highly effective for the standard vehicle routing problem. 相似文献
18.
Y H Lee J I Kim K H Kang K H Kim 《The Journal of the Operational Research Society》2008,59(6):833-841
The vehicle fleet mix problem is a special case of the vehicle routing problem where customers are served by a heterogeneous fleet of vehicles with various capacities. An efficient heuristic for determining the composition of a vehicle fleet and travelling routes was developed using tabu search and by solving set partitioning problems. Two kinds of problems have appeared in the literature, concerning fixed cost and variable cost, and these were tested for evaluation. Initial solutions were found using the modified sweeping method. Whenever a new solution in an iteration of the tabu search was obtained, optimal vehicle allocation was performed for the set of routes, which are constructed from the current solution by making a giant tour. Experiments were performed for the benchmark problems that appeared in the literature and new best-known solutions were found. 相似文献
19.
We consider a multi-product two-stage production/distribution system design problem (PDSD) where a fixed number of capacitated distribution centers are to be located with respect to capacitated suppliers (plants) and retail locations (customers) while minimizing the total costs in the system. We present a mixed-integer problem formulation that facilitates the development of efficient heuristic procedures. We provide meta-heuristic procedures, including a population-based scatter search with path relinking and trajectory-based local and tabu search, for the solution of the problem. We also develop efficient construction heuristics and transshipment heuristics that are incorporated into the heuristic procedures for the solution of subproblems. We present extensive computational results that show the high performance of the solution approaches. We obtain smaller than 1.0% average optimality gaps with acceptable runtimes, even for relatively large problems. The computational results also demonstrate the effectiveness of the construction and transshipment heuristics that impact the solution quality and overall runtimes. 相似文献
20.
This paper presents a unified tabu search heuristic for the vehicle routing problem with time windows and for two important generalizations: the periodic and the multi-depot vehicle routing problems with time windows. The major benefits of the approach are its speed, simplicity and flexibility. The performance of the heuristic is assessed by comparing it to alternative methods on benchmark instances of the vehicle routing problem with time windows. Computational experiments are also reported on new randomly generated instances for each of the two generalizations. 相似文献