Search results for "Operations Research"
showing 10 items of 1297 documents
A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems
2013
The three-dimensional multiple bin-size bin packing problem, MBSBPP, is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considere…
A cutting plane algorithm for the capacitated arc routing problem
2003
The Capacitated Arc Routing Problem (CARP) consists of finding a set of minimum cost routes that service all the positive-demand edges of a given graph, subject to capacity restrictions.In this paper, we introduce some new valid inequalities for the CARP. We have designed and implemented a cutting plane algorithm for this problem based on these new inequalities and some other which were already known. Several identification algorithms have been developed for all these valid inequalities. This cutting plane algorithm has been applied to three sets of instances taken from the literature as well as to a new set of instances with real data, and the resulting lower bound was optimal in 47 out of…
On Randomness and Structure in Euclidean TSP Instances: A Study With Heuristic Methods
2021
Prediction of the quality of the result provided by a specific solving method is an important factor when choosing how to solve a given problem. The more accurate the prediction, the more appropriate the decision on what to choose when several solving applications are available. In this article, we study the impact of the structure of a Traveling Salesman Problem instance on the quality of the solution when using two representative heuristics: the population-based Ant Colony Optimization (ACO) and the local search Lin-Kernighan (LK) algorithm. The quality of the result for a solving method is measured by the computation accuracy, which is expressed using the percent error between its soluti…
Heuristics for the Mixed Rural Postman Problem
2000
Abstract The Rural Postman Problem on a mixed graph (MRPP) consists of finding a minimum cost tour which traverses, at least once, the arcs and edges of a given subset of the arcs and edges of the graph. This problem is known to be NP-hard. This paper presents two heuristic approaches to solve it. An approximate algorithm based on the resolution of some flow and matching problems and a tabu search implementation is presented. The tabu search algorithm seeks high-quality tours by means of a switching mechanism in an intensification phase and two levels of diversification. Computational results are presented to assess the merits of the method. Scope and purpose Routing Problems arise in sever…
Solving a continuous periodic review inventory-location allocation problem in vendor-buyer supply chain under uncertainty
2019
In this work, a mixed-integer binary non-linear two-echelon inventory problem is formulated for a vendor-buyer supply chain network in which lead times are constant and the demands of buyers follow a normal distribution. In this formulation, the problem is a combination of an (r, Q) and periodic review policies based on which an order of size Q is placed by a buyer in each fixed period once his/her on hand inventory reaches the reorder point r in that period. The constraints are the vendors’ warehouse spaces, production restrictions, and total budget. The aim is to find the optimal order quantities of the buyers placed for each vendor in each period alongside the optimal placement of the ve…
A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems
2002
Abstract In this paper we develop several heuristic algorithms for the two-dimensional cutting problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximising the value of the pieces cut. They can be considered to be general purpose algorithms because they solve the four versions of the TDC: weighted and unweighted, constrained and unconstrained. We begin by proposing two constructive procedures based on simple bounds obtained by solving one-dimensional knapsack problems. We then use these constructive algorithms as building blocks for more complex procedures. We have developed a greedy randomised adaptive search procedure (GRASP) which is very fast an…
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
2007
In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are use…
GRASP for the uncapacitated r-allocation p-hub median problem
2014
In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman [19], in which every node is assigned to r of the p selected hubs (r@?p) and we are restricted to route the traffic of the nodes through their associated r hubs. As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on t…
Best compromise solution for a new multiobjective scheduling problem
2006
In future wireless networks, a mobile terminal will be able to communicate with a service provider using several network connections. These connections to networks will have different properties and they will be priced separately. In order to minimize the total communication time and the total transmission costs, an automatic method for selecting the network connections is needed. Here, we describe the network connection selection problem and formulate it mathematically. We discuss solving the problem and analyse different multiobjective optimization approaches for it.
A branch-and-cut algorithm for the pallet loading problem
2005
We propose a branch-and-cut algorithm for the pallet loading problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes).