We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.
This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.
This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips. 相似文献
The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times. 相似文献
This paper presents modeling and solution method improvements for the Multi-Resource Routing Problem (MRRP) with flexible tasks. The MRRP with flexible tasks is used to model routing and scheduling problems for intermodal drayage operations in which two resources (tractors and trailers) perform tasks to transport loaded and empty equipment. Tasks may be either well defined, in which both the origin and the destination of a movement are given, or flexible, in which the origin or the destination is chosen by the model. This paper proposes methods to effectively manage the number of options considered for flexible tasks (either feasible origins for a known destination or feasible destinations for a known origin). This modeling change generates sufficient options to allow for low-cost solutions while maintaining reasonable computational effort. We also propose a new solution method that uses randomized route generation. Computational results from test cases show that these changes improve the quality of solutions by at least 5% in the test cases as compared to methods from previous studies. 相似文献
In this paper we consider some properties on prices under flow control in a network that is to be shared by noncooperative users. Each user is faced with an optimization problem which is formulated as the minimization of its own criterion subject to constraint on the flows of the other users. The operating points of the network are the Nash equilibria of the underlying routing game. Our objective is to study the behavior of prices of all users when the network designer needs to allocate capacities to network links. For parallel links topologies, we show that degradation of the performances such as prices will not take place, as well as the users may find it beneficial to improve their requests 相似文献
In this paper, we argue that vehicle routing solutions are often tactical decisions, that should not be changed too often
or too much. For marketing or other reasons, vehicle routing solutions should be stable, i.e. a new solution (when e.g. new customers require service) should be as similar as possible to a solution already in
use. Simultaneously however, this new solution should still have a good quality in the traditional sense (e.g. small total
travel cost). In this paper, we develop a way to measure the difference between two vehicle routing solutions. We use this
distance measure to create a metaheuristic approach that will find solutions that are “close” (in the solution space) to a
given baseline solution and at the same time have a high quality in the sense that their total distance traveled is small.
By using this approach, the dispatcher is offered a choice of Pareto-optimal solutions, allowing him to make a trade-off between
changing his existing solution and allowing a longer travel distance. Some experiments are performed to show the effectiveness
of the approach. 相似文献
Let F be a function field of characteristic p > 2, finitely generated over a field C algebraic over a finite field Cp and such that it has an extension of degree p. Then Hilbert's Tenth Problem is not decidable over F. 相似文献