排序方式: 共有67条查询结果,搜索用时 31 毫秒
61.
Solving the maximum clique problem using a tabu search approach 总被引:3,自引:0,他引:3
We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the
-generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support. 相似文献
62.
This paper surveys the research on evolutionary algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from a single depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. The main types of evolutionary algorithms for the VRPTW are genetic algorithms and evolution strategies. In addition to describing the basic features of each method, experimental results for the benchmark test problems of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed. 相似文献
63.
Jawad?AbracheEmail author Teodor?Gabriel?Crainic Michel?Gendreau 《4OR: A Quarterly Journal of Operations Research》2004,2(1):1-33
Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research.Received: April 2003, Revised: July 2003, AMS classification:
91B26, 90BXX, 90C27All correspondence to:Jawad Abrache 相似文献
64.
R Séguin J-Y Potvin M Gendreau T G Crainic P Marcotte 《The Journal of the Operational Research Society》1997,48(2):162-174
This paper is concerned with a class of dynamic and stochastic problems known as real-time decision problems. The objective is to provide responses of a required quality in a continuously evolving environment, within a prescribed time frame, using limited resources and information that is often incomplete or uncertain. Furthermore, the outcome of any particular decision may also be uncertain. This paper provides an overview of this class of problems, reviews the relevant Artificial Intelligence literature, proposes a dynamic programming framework, and assesses the potential usefulness of Operational Research approaches for their solution. Throughout the paper, a vehicle dispatching application illustrates the relevant concepts. 相似文献
65.
66.
This paper develops an efficient heuristic to solve the non-homogeneous redundancy allocation problem for multi-state series-parallel systems. Non identical components can be used in parallel to
improve the system availability by providing redundancy in subsystems. Multiple component choices are available for each subsystem.
The components are binary and chosen from a list of products available on the market, and are characterized in terms of their
cost, performance and availability. The objective is to determine the minimal-cost series-parallel system structure subject
to a multi-state availability constraint. System availability is represented by a multi-state availability function, which
extends the binary-state availability. This function is defined as the ability to satisfy consumer demand that is represented
as a piecewise cumulative load curve. A fast procedure is used, based on universal generating function, to evaluate the multi-state
system availability. The proposed heuristic approach is based on a combination of space partitioning, genetic algorithms (GA)
and tabu search (TS). After dividing the search space into a set of disjoint subsets, this approach uses GA to select the
subspaces, and applies TS to each selected subspace. The design problem, solved in this study, has been previously analyzed
using GA. Numerical results for the test problems from previous research are reported, and larger test problems are randomly
generated. These results show that the proposed approach is efficient both in terms of both of solution quality and computational
time, as compared to existing approaches. 相似文献
67.
El Hachemi Nizar El Hallaoui Issmail Gendreau Michel Rousseau Louis-Martin 《Annals of Operations Research》2015,230(1):87-104
Annals of Operations Research - In this paper we present the solution to a weekly log-truck scheduling problem (LTSP) integrating the routing and scheduling of trucks where all goods are... 相似文献