Search

Transportation problems involving routing and loading at the same time are currently a hot topic in combinatorial optimization. The interest of researchers and practitioners is motivated by the intrinsic difficulty of this research area, which combines two computationally hard problems, and by its practical relevance in important real world applications. This annotated bibliography aims at collecting, in a systematic way, the most relevant results obtained in the area of vehicle routing with loading constraints, with the objective of stimulating further research in this promising area. [ABSTRACT FROM AUTHOR]

A relevant logistic issue in the organization of a fair is to determine how stands have to be placed in the exhibition space so as to satisfy all constraints on security, ease of access, services, and so on, while maximizing the revenues coming from the exhibitors. We consider in particular the problem of allocating the maximum number of stands by satisfying all the constraints required by practical implementations. We examine a number of real-world cases, and show how basic mathematical programming models can be improved to handle specific requests from the organizers. We report the solutions obtained through an original decision support system, that embeds a number of algorithms to solve the various cases by reduction to one or more linear programs. [ABSTRACT FROM AUTHOR]

The article focuses on the proceedings of the second joint conference ECCO XXIII-CO 2010 organised by International Symposium on Combinatorial Optimization and European Chapter on Combinatorial Optimization (ECCO) held at the facilities of the University of Málaga, Spain from May 27 to May 29, 2010. It includes information on conferences held by ECCO, its plan for future conferences and their present coordinator Silvano Martello.

This volume collects all eleven survey papers that appeared in volumes 7-10 (2009-2011) of the journal 4OR: A Quarterly Journal of Operations Research. We briefly introduce the collected surveys and those that were included in the first two volumes of this series. [ABSTRACT FROM AUTHOR]

A recent paper (Davidović et al., J. Heuristics, 18:549-569, ) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution. [ABSTRACT FROM AUTHOR]

The purpose of this note is to give the readers of 4OR information on the state of the journal and its future, abiding by a triennial tradition which started with Bouyssou et al. (4OR 1(1):1-6, ) and continued with Bouyssou et al. (4OR 4(1):1-9, ) and Bouyssou et al. (4OR Q J Oper Res 7(1):15, ). In the 3 years that have passed since the last editorial note, three volumes of the journal have been published, each containing four issues: vol. 7 (2009), vol. 8 (2010) and vol. 9 (2011). [ABSTRACT FROM AUTHOR]

We present the result of research, developed within Nokia Siemens Networks, to solve the downlink subframe allocation problem in Mobile WiMAX (IEEE 802.16) technology in its full complexity, while simultaneously fulfilling real-life constraints on processing power and delay. We describe the IEEE 802.16 standard,and introduce two system models. A theoretical analysis of the two-dimensional packing problems originated by such models shows that they are both NP-hard in the strong sense. From a practical point of view, the processing budget for scheduling in the base station was estimated to be 1 ms on a state-of-the-art PC. Thus,we introduce two highly efficient heuristics that were developed to handle the system practically. A thorough computational analysis of their optimization characteristics and a system-level evaluation in realistic scenarios proved that the algorithms offer significant capacity gain in Mobile WiMAX systems that translate to increased operator revenues. [ABSTRACT FROM AUTHOR]

Given a non-convex two-dimensional area and identical rectangular stands, we consider the problem of placing the maximum number of stands in the area, by satisfying a number of operational constraints. We present linear programming models and show the total unimodularity of the matrices associated with their constraint sets. We then give computational results obtained by applying the models to the real-world case of the Beira Mar handcraft fair of Fortaleza (Brazil). [ABSTRACT FROM AUTHOR]

This volume of the Annals of Operations Research collects all eleven survey papers that appeared in volumes 4–6 (2006–2008) of the journal 4OR: A Quarterly Journal of Operations Research. This is the second volume of this type, after the one published in 2007. We briefly introduce the collected surveys. [ABSTRACT FROM AUTHOR]

We discuss some relevant results obtained by Egerváry in the early Thirties, whose importance has been recognized several years later. We start with a quite well-known historical fact: the first modern polynomial-time algorithm for the assignment problem, invented by Harold W. Kuhn half a century ago, was christened the “Hungarian method” to highlight that it derives from two older results, by Kőnig (Math Ann 77:453–465, 1916) and Egerváry (Mat Fiz Lapok 38:16–28, 1931) (A recently discovered posthumous paper by Jacobi (1804–1851) contains however a solution method that appears to be equivalent to the Hungarian algorithm). Our second topic concerns a combinatorial optimization problem, independently defined in satellite communication and in scheduling theory, for which the same polynomial-time algorithm was independently published 30 years ago by various authors. It can be shown that such algorithm directly implements another result contained in the same 1931 paper by Egerváry. We finally observe that the latter result also implies the famous Birkhoff-von Neumann theorem on doubly stochastic matrices. [ABSTRACT FROM AUTHOR]

The paper deals with a unit commitment problem of a generation company whose aim is to find the optimal scheduling of a multiunit pump-storage hydro power station, for a short term period in which the electricity prices are forecasted. The problem has a mixed-integer nonlinear structure, which makes very hard to handle the corresponding mathematical models. However, modern mixed-integer linear programming (MILP) software tools have reached a high efficiency, both in terms of solution accuracy and computing time. Hence we introduce MILP models of increasing complexity, which allow to accurately represent most of the hydroelectric system characteristics, and turn out to be computationally solvable. In particular we present a model that takes into account the head effects on power production through an enhanced linearization technique, and turns out to be more general and efficient than those available in the literature. The practical behavior of the models is analyzed through computational experiments on real-world data. [ABSTRACT FROM AUTHOR]

The article discusses various reports published within the issue, including one about the Lagrangian relaxation and another on dial-a-ride services.

Abstract: We address the problem of packing a given set of rectangles into the minimum size square. We consider three versions of the problem, arising when the rectangles (i) are squares; (ii) have a fixed orientation; (iii) can be rotated by 90∘. For each case we study lower bounds, and analyze their worst-case performance ratio. In addition, we evaluate through computational experiments their average performance on instances from the literature. [Copyright &y& Elsevier]

This article considers a combination of capacitated vehicle routing and three-dimensional loading, with additional constraints frequently encountered in freight transportation. It proposes a tabu search algorithm that iteratively invokes an inner tabu search procedure for the solution of the loading subproblem. The algorithm is experimentally evaluated both on instances adapted from vehicle routing instances from the literature and on new real-world instances. [ABSTRACT FROM AUTHOR]

We present a computer code that implements a general Tabu Search technique for the solution of two- and three-dimensional bin packing problems, as well as virtually any of their variants requiring the minimization of the number of bins. The user is only requested to provide a procedure that gives an approximate solution to the actual variant to be solved. [ABSTRACT FROM AUTHOR]

We consider a knapsack problem in which each item has two types of weight and the container has two types of capacity. We discuss the surrogate, Lagrangian, and continuous relaxations, and give an effective method to determine the optimal Lagrangian and surrogate multipliers associated with the continuous relaxation of the problem. These results are used to obtain an exact branch-and-bound algorithm, which also includes heuristic procedures and a reduction technique. The performance of bounds and algorithms is evaluated through extensive computational experiments. [ABSTRACT FROM AUTHOR]

We consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items. [ABSTRACT FROM AUTHOR]

Crew and vehicle scheduling are fundamental issues in public transit management. Informally, they can be described as the problem of determining the optimal duties for a set of crews (e.g., bus drivers) or vehicles (e.g., buses) so as to cover a given set of timetabled trips, satisfying a number of constraints laid down by the union contract and company regulations. We consider the simplified but still NP-hard case in which several depots are specified, and limits on both the total time between the start and the end of any duty (spread time) and the total duty operational time (working time) are imposed. We give a 0-1 linear programming formulation based on binary variables associated with trip transitions, which applies to both crew and vehicle scheduling. The model is enhanced by means of new families of valid inequalities, for which exact and heuristic separation procedures are proposed. These techniques are embedded into an exact branch-and-cut algorithm, which also incorporates heuristic procedures. The performance of two implementations of the method (for vehicle scheduling and crew scheduling, respectively) are evaluated through computational testing on both random and real-world test problem from the literature. [ABSTRACT FROM AUTHOR]

The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular bins. The problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 1/8. An exact algorithm for filling a single bin is developed, leading to the definition of an exact brand-and-bound algorithm for the three-dimensional bin packing problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable time limit. [ABSTRACT FROM AUTHOR]

We introduce this volume of the Annals of Operations Research that collects updated versions of the invited surveys that appeared in the journal 4OR—A Quarterly Journal of Operations Research. [ABSTRACT FROM AUTHOR]

We consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimize the maximum completion time of a task. We introduce lower bounds, approximation algorithms and a branch-and-bound procedure for the exact solution of the problem. Extensive computational results show that, in many cases, large-size instances of the problem can be solved exactly. [ABSTRACT FROM AUTHOR]

We consider a generalization of the fixed job schedule problem where a bound is imposed on the total working time of each processor. It is shown that the problem is NP-hard but polynomially solvable in the preemptive case. We introduce several lower bounds. One is determined through definition of a special class of graphs, for which the maximum clique problem is shown to be polynomial. Lower bounds and dominance criteria are exploited in a branch-and-bound algorithm for optimal solution of the problem. The effectiveness of the algorithm is analyzed through computational experiments. [ABSTRACT FROM AUTHOR]

We consider a generalization of the fixed job schedule problem in which each processor is available only for a prefixed time interval from the release time of the earliest task assigned to it. The problem can arise in bus driver scheduling. We show that the problem is NP-hard, and introduce polynomial procedures to determine lower bounds, dominance criteria and reductions. We also develop a branch-and-bound algorithm for obtaining the optimal solution of the problem and analyze the algorithm's average performance in a series of computational experiments. Finally, we investigate the preemptive case and other polynomial special cases. [ABSTRACT FROM AUTHOR]

Given a graph with arc costs, the Bottleneck Traveling Salesman Problem is to find a Hamiltonian circuit that minimizes the largest cost of any of its arcs. Lower bounds for the problem (bottleneck assignment problem, bottleneck paths, bottleneck arborescence, cuts) are analyzed and combined to obtain a bounding procedure for a breadth-first branch and bound algorithm. At each node of the branch-decision tree, the algorithm uses a heuristic search to find a Hamiltonian circuit containing only arcs whose cost is not greater than the current lower bound, the aim being to reduce the number of nodes explored. Extensive computational results are discussed. These show that, unlike the classical Traveling Salesmen Problem, the same algorithm can be used successfully for large numbers of vertices both in symmetric and in asymmetric cases. Results for Euclidean graphs are also presented. [ABSTRACT FROM AUTHOR]

The problem of finding the kth smallest of n elements can be solved either with O(n) algorithms or with O(n²) algorithms. Although they require a higher number of operations in the worst case, O(n²) algorithms are generally preferred to O(n) algorithms because of their better average performance. We present a hybrid algorithm which is O(n) in the worst case and efficient in the average case. [ABSTRACT FROM AUTHOR]