共查询到20条相似文献,搜索用时 15 毫秒
1.
This paper presents a tabu search based method for finding good solutions to a real-life vehicle routing problem. The problem considered deals with some new features beyond those normally associated with the classical problems of the literature: in addition to capacity constraints for vehicles and time windows for deliveries, it takes the heterogeneous character of the fleet into account, in the sense that utilization costs are vehicle-dependent and that some accessibility restrictions have to be fulfilled. It also deals with the use of trailers. In spite of the intricacy of the problem, the proposed tabu search approach is easy to implement and can be easily adapted to many other applications. An emphasis is placed on means that have to be used to speed up the search. In a few minutes of computation on a personal workstation, our approach obtains solutions that are significantly better than those previously developed and implemented in practice. 相似文献
2.
Guido Perboli Ferdinando Pezzella Roberto Tadei 《Mathematical Methods of Operations Research》2008,68(2):361-382
This paper presents EVE-OPT, a Hybrid Algorithm based on Genetic Algorithms and Taboo Search for solving the Capacitated Vehicle
Routing Problem. Several hybrid algorithms have been proposed in recent years for solving this problem. Despite good results,
they usually make use of highly problem-dependent neighbourhoods and complex genetic operators. This makes their application
to real instances difficult, as a number of additional constraints need to be considered. The algorithm described here hybridizes
two very simple heuristics and introduces a new genetic operator, the Chain Mutation, as well as a new mutation scheme. We
also apply a procedure, the k-chain-moves, able to increase the neighbourhood size, thereby improving the quality of the solution with negligible computational
effort. Despite its simplicity, EVE-OPT is able to achieve the same results as very complex state-of-the art algorithms. 相似文献
3.
Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem 总被引:37,自引:0,他引:37
Ibrahim Hassan Osman 《Annals of Operations Research》1993,41(4):421-451
The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature. 相似文献
4.
This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found. 相似文献
5.
We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time. 相似文献
6.
The tour partitioning heuristic for the vehicle routing problem assumes an unlimited supply of vehicles. If the number of vehicles is fixed, this heuristic may produce infeasible solutions. We modify the heuristic to guarantee feasibility in this situation and we analyze the worst-case performance of the modified heuristic. 相似文献
7.
8.
Frédéric Semet 《Annals of Operations Research》1995,61(1):45-65
In the partial accessibility constrained vehicle routing problem, a route can be covered by two types of vehicles, i.e. truck or truck + trailer. Some customers are accessible by both vehicle types, whereas others solely by trucks. After introducing an integer programming formulation for the problem, we describe a two-phase heuristic method which extends a classical vehicle routing algorithm. Since it is necessary to solve a combinatorial problem that has some similarities with the generalized assignment problem, we propose an enumerative procedure in which bounds are obtained from a Lagrangian relaxation. The routine provides very encouraging results on a set of test problems. 相似文献
9.
Heuristic Procedures for the Capacitated Vehicle Routing Problem 总被引:6,自引:0,他引:6
In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given. 相似文献
10.
Arild Hoff Irina Gribkovskaia Gilbert Laporte Arne Løkketangen 《European Journal of Operational Research》2009
This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing a pickup when delivering at a customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked up from the first visited customers. These customers are revisited in reverse order, thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times on the same route, giving rise to a general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution on the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost, their computation can be time consuming. The best lasso solution generated within a given time limit is generally better than the best general solution produced with the same computing effort. 相似文献
11.
This article addresses an extension of the multi-depot vehicle routing problem in which vehicles may be replenished at intermediate depots along their route. It proposes a heuristic combining the adaptative memory principle, a tabu search method for the solution of subproblems, and integer programming. Tests are conducted on randomly generated instances. 相似文献
12.
In this paper we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available. 相似文献
13.
István Borgulya 《Central European Journal of Operations Research》2008,16(4):331-343
In this paper, we present a multi-objective evolutionary algorithm for the capacitated vehicle routing problem with route
balancing. The algorithm is based on a formerly developed multi-objective algorithm using an explicit collective memory method,
namely the extended virtual loser (EVL). We adapted and improved the algorithm and the EVL method for this problem. We achieved
good results with this simple technique. In case of this problem the quality of the results of the algorithm is similar to
that of other evolutionary algorithms. 相似文献
14.
15.
The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (Fv) and a secondary objective of minimizing the total cost (Fc). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective Fc while attaining all the known optimal values regarding the objective of the number of vehicles Fv. To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance. 相似文献
16.
The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495. 相似文献
17.
Daniel Palhazi Cuervo Peter Goos Kenneth Sörensen Emely Arráiz 《European Journal of Operational Research》2014
The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a broad neighborhood structure at each iteration. This is efficiently done using a data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible portions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. These results show that the performance of existing metaheuristic algorithms can be considerably improved by carrying out a thorough statistical analysis of their components. In particular, it shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained. 相似文献
18.
19.
Path relinking for the vehicle routing problem 总被引:3,自引:0,他引:3
This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search
method that explores the solution space more thoroughly than other local search based methods by overcoming local optima.
Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect
previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu
search on the vehicle routing problem. 相似文献
20.
A variable neighborhood search for the capacitated arc routing problem with intermediate facilities 总被引:2,自引:0,他引:2
Michael Polacek Karl F. Doerner Richard F. Hartl Vittorio Maniezzo 《Journal of Heuristics》2008,14(5):405-423
The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications
like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of
the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length
restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the
basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for
all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved. 相似文献