ORBi Collection: Quantitative methods in economics & management
http://hdl.handle.net/2268/71
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
Iterated local search for the capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints
http://hdl.handle.net/2268/208310
Title: Iterated local search for the capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints
<br/>
<br/>Author, co-author: Pollaris, Hanne; Braekers, Kris; Caris, An; Janssens, Gerrit, K.; Limbourg, Sabine
<br/>
<br/>Abstract: In this article an Iterated Local Search algorithm for the capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints is presented. Axle weight limits impose a great challenge for transportation companies. Yet, the literature on the incorporation of axle weight constraints in vehicle routing models is very scarce. The effect of introducing axle weight constraints in a CVRP on total routing cost is analyzed. Results show that integrating axle weight constraints does not lead to a large cost increase. However, not including axle weight constraints in the planning process may induce major axle weight violations.Sat, 18 Mar 2017 10:49:48 GMTA tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints
http://hdl.handle.net/2268/207751
Title: A tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints
<br/>
<br/>Author, co-author: Paquay, Célia; Limbourg, Sabine; Schyns, Michael
<br/>
<br/>Abstract: This paper considers the three-dimensional Multiple Bin Size Bin Packing Problem which
consists in packing a set of cuboid boxes into containers of various shapes with minimising
unused space. The problem is extended to air cargo where bins are Unit Load Devices,
especially designed for fitting in aircraft. We developed a fast constructive heuristic able to
manage the different constraints met in transportation. The heuristic is split into two distinct
phases. The first phase deals with the packing of boxes into identical bins using an extension
of the Extreme Points. During this phase, the fragility, stability and orientations of the boxes
are taken into account as well as the special shape of the bins and their weight capacity.
The second phase takes into account the multiple types of available bins. If necessary, the
best found loading pattern is finally enhanced with respect to weight distribution in a post
processing. After parametrisation, computational experiments have been performed on data
sets especially designed for this application. The heuristic requires really short computational
times to achieve promising results.Thu, 02 Mar 2017 14:26:35 GMTRoad and intermodal transport performance: the impact of operational costs and air pollution external costs
http://hdl.handle.net/2268/207580
Title: Road and intermodal transport performance: the impact of operational costs and air pollution external costs
<br/>
<br/>Author, co-author: Mostert, Martine; Caris, An; Limbourg, Sabine
<br/>
<br/>Abstract: The transportation of goods is essential for the economy, but it also contributes to air pollution which, in turn, affects human health. These negative impacts generate additional costs for society that are not necessarily taken into account in public transportation policies and in private transportation decisions of companies and individuals. This leads to inefficient transportation systems where the social equilibrium is not reached. Intermodal transport is promoted by the European Commission to reduce these negative externalities. The objective of this paper is to analyze at a strategic level the effect on modal split between road, intermodal rail and intermodal inland waterway transport of several economic or environmental policies. An intermodal allocation model is applied to the Belgian case in order to identify the modal split changes between the single minimization of costs (operational or health-related external) and the introduction of additional road taxes.Wed, 22 Feb 2017 14:50:14 GMTInstances for the 3D Multiple Bin Size Bin Packing Problem
http://hdl.handle.net/2268/206856
Title: Instances for the 3D Multiple Bin Size Bin Packing Problem
<br/>
<br/>Author, co-author: Paquay, Célia; Limbourg, Sabine; Schyns, Michael
<br/>
<br/>Abstract: The subject of this work is to solve the problem of packing a set of shipments (various cuboid boxes) into containers of various shapes without wasting loading space. All the boxes have to be loaded and few are identical. As it is the case for all the packing problems, the packing has to satisfy geometry constraints: the items cannot overlap and have to lie entirely inside the bins. The richness of our application is to manage additional and common constraints: the bin weight capacity, the rotations of the boxes, the stability and the fragility of the boxes and the uniformity of the weight distribution inside the ULDs. The last constraint is crucial in air transportation: when ULDs are packed inside the airplane, the centre of gravity is computed assuming each ULD has a centre of gravity close to the geometrical centre of its basis. This type of constraints can be adapted to road transportation for the axle weight limits, which plays a key role since the weigh-in-motion systems become more common.Sun, 05 Feb 2017 16:48:02 GMTA bi-objective model for intermodal transport
http://hdl.handle.net/2268/205453
Title: A bi-objective model for intermodal transport
<br/>
<br/>Author, co-author: Mostert, Martine; Limbourg, SabineTue, 17 Jan 2017 13:52:22 GMTIntermodal network design: a three-mode bi-objective model applied to the case of Belgium
http://hdl.handle.net/2268/205111
Title: Intermodal network design: a three-mode bi-objective model applied to the case of Belgium
<br/>
<br/>Author, co-author: Mostert, Martine; Caris, An; Limbourg, Sabine
<br/>
<br/>Abstract: Freight transport planning is nowadays encouraged to align with environmental objectives. Among those, climate change is of particular interest for many countries. In its White Paper on Transport, the European Commission considers intermodal transport as a potential solution for reducing environmental impacts. In order to make good strategic transport decisions, realistic decision support models for freight transport networks must be developed, so that insights can be derived for the different stakeholders of the transportation chain. This research proposes a bi-objective mathematical formulation which takes into account economic and environmental objectives, on a road and intermodal network with three modes of transport (road, intermodal rail, and intermodal inland waterways), and in which economies of scale of intermodal transport can be considered. With this model better fitting reality, an application to the Belgian case study provides practical information on how flows, terminal types and locations vary depending on the chosen policy, on the integration or not of economies of scale, on costs or emissions modifications and on the number of terminals to locate. Results show that the chosen policy influences the terminal type and the intermodal market share. The study also highlights the interest of intermodal transport on short distances, and the risk of flow exchanges inside the intermodal market share, rather than between road and intermodal transport.Tue, 10 Jan 2017 13:25:56 GMTA class of valid inequalities for multilinear 0-1 optimization problems
http://hdl.handle.net/2268/204587
Title: A class of valid inequalities for multilinear 0-1 optimization problems
<br/>
<br/>Author, co-author: Rodriguez Heck, Elisabeth; Crama, YvesWed, 21 Dec 2016 09:47:56 GMTQuadratic reformulations of nonlinear binary optimization problems
http://hdl.handle.net/2268/204497
Title: Quadratic reformulations of nonlinear binary optimization problems
<br/>
<br/>Author, co-author: Crama, YvesMon, 19 Dec 2016 08:47:42 GMTA column generation approach to job grouping for flexible manufacturing systems
http://hdl.handle.net/2268/204061
Title: A column generation approach to job grouping for flexible manufacturing systems
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.
<br/>
<br/>Abstract: A flexible manufacturing system consists of a number of NC-machines, linked by automated material handling devices, that perform the various operations required to manufacture parts. Each operation requires different tools. These tools are stored in a limited capacity tool magazine attached to each machine. When it becomes necessary to add or remove tools from the tool magazine, the machine may have to be shut down for a setup. In this paper, we study a model which aims at minimizing the number of setups. We assume that N jobs must be processed on a machine. Each job requires a certain set of tools, which have to be present in the tool magazine of the machine when the job is executed. The magazine has a total capacity of C tools. We say that a group (subset, batch) of jobs is feasible if, together, these jobs do not require more than C tools. The job grouping problem is to partition the jobs into a minimum number of feasible groups. The problem can be formulated as a set covering problem. We solve the linear relaxation of this formulation in order to obtain tight lower bounds. Since the number of variables is potentially huge, we use a column generation approach. The column generation subproblem turns out to be NP-hard; we solve it by enumeration. We also describe some fast and simple heuristics for the job grouping problem. The result of our computational experiments is that the lower bound is extremely strong. The quality of the heuristic solutions is in general very good too. We also investigate a more general multiple-machine model in which each tool may occupy several slots in the tool magazines.Mon, 05 Dec 2016 20:56:09 GMTOn the strength of relaxations of multidimensional knapsack problems
http://hdl.handle.net/2268/204060
Title: On the strength of relaxations of multidimensional knapsack problems
<br/>
<br/>Author, co-author: Crama, Yves; Mazzola, Joseph B.
<br/>
<br/>Abstract: Branch-and-bound algorithms for integer programming problems typically employ bounds derived from well-known relaxations, such as the Lagrangian, surrogate, or composite relaxations. Although the bounds derived from these relaxations are stronger than the bound obtained from the linear programming relaxation (LPR), in the case of multidimensional knapsack problems, i.e., integer programming problems with nonnegative objective-function and constraint coefficients, the improvement in the bound that can be realized using these relaxations is limited. In particular, we show that the improvement in the quality of the bound using any of these relaxations cannot exceed the magnitude of the largest coefficient in the objective function, nor can it exceed one-half of the optimal objective-function value of LPR. This implies, for example, that for those problem classes in which all of the objective-function coefficients are equal to 1, the bound derived from the surrogate relaxation cannot be better than the bound obtained by simply rounding the LPR bound. Awareness of these properties is important in the development of algorithms, since this class of problems subsumes many well-known integer programming problems.Mon, 05 Dec 2016 20:46:48 GMTBerge-acyclic multilinear 0-1 optimization problems
http://hdl.handle.net/2268/204059
Title: Berge-acyclic multilinear 0-1 optimization problems
<br/>
<br/>Author, co-author: Buchheim, Christoph; Crama, Yves; Rodriguez Heck, ElisabethMon, 05 Dec 2016 18:58:16 GMTLes problèmes “riches” de tournées de véhicules
http://hdl.handle.net/2268/203869
Title: Les problèmes “riches” de tournées de véhicules
<br/>
<br/>Author, co-author: Limbourg, SabineTue, 29 Nov 2016 13:39:50 GMTLa compétitivité du transport intermodal
http://hdl.handle.net/2268/203868
Title: La compétitivité du transport intermodal
<br/>
<br/>Author, co-author: Limbourg, SabineTue, 29 Nov 2016 13:36:58 GMTApproximation algorithms for integer covering problems via greedy column generation
http://hdl.handle.net/2268/203417
Title: Approximation algorithms for integer covering problems via greedy column generation
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: Many combinatorial optimization problems can be formulated as covering problems. In some cases, this covering formulation is not polynomial in the input size of the original problem. In order to solve the problem approximately one can apply the greedy algorithm to the covering formulation. In this case, the column generation subproblem is to determine which column the greedy algorithm chooses. This problem might be NP-hard in itself. We propose a modification of the greedy algorithm in which the column generation subproblem is solved approximately, within a factor α. We derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithms.Mon, 14 Nov 2016 20:05:41 GMTComplexity of product positioning and ball intersection problems
http://hdl.handle.net/2268/203415
Title: Complexity of product positioning and ball intersection problems
<br/>
<br/>Author, co-author: Crama, Yves; Hansen, Pierre; Jaumard, Brigitte
<br/>
<br/>Abstract: The product positioning problem consists in choosing the attributes of a new product in such a way as to maximize its market share, i.e., to attract a maximum number of customers. Mathematically, the problem can be formulated as follows: given a set of balls (with respect to some norm) and a weight associated to each ball, find a point which maximizes the sum of the weights of the balls containing it. The complexity of this problem is investigated in the case of the L∞ and of the Euclidean norms. In both cases, the problem is proved to be NP-hard, but to be polynomially solvable when the dimension of the space is fixed.Mon, 14 Nov 2016 19:50:23 GMTValid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
http://hdl.handle.net/2268/203414
Title: Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
<br/>
<br/>Author, co-author: Crama, Yves; Mazzola, Joseph B.
<br/>
<br/>Abstract: This paper defines the dense subhypergraph problem (DSP), which provides a modelling framework for the nonlinear knapsack problem and other well-known problems arising in areas such as capital budgeting, flexible manufacturing system production planning, repair-kit selection, and compiler construction. We define several families of valid inequalities and state conditions under which these inequalities are facet-defining for DSP. We also explore the polyhedral structure of the cardinality-constrained DSP. Finally, we examine a special case of this problem that arises, for example, within the context of Lagrangian decomposition. For this case, we present a complete description of the convex hull of the feasible region.Mon, 14 Nov 2016 19:42:43 GMTModels for machine-part grouping in cellular manufacturing
http://hdl.handle.net/2268/203079
Title: Models for machine-part grouping in cellular manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: For cellular manufacturing strategies to succeed, the productive system first has to be divided into highly independent cells. This means that a partition of the machines into machine groups, a partition of the parts into part families, and a matching between the machine groups and the part families have to be simultaneously determined. Mathematically, this question can be expressed as the problem of finding a near block diagonal permutation of the machine-part incidence matrix. Research on such grouping problems has primarily concentrated on the design of heuristics. Different grouping efficiency criteria have been proposed to express the quality of the groupings proposed by these heuristics. This paper is concerned with mathematical programming approaches to the formation of production cells. Existing models are reviewed and their features are briefly discussed. An alternative model is proposed, which allows for the formulation of various constraints and grouping efficiency criteria. Finally, some test problems are used to support the claim that this model may be adequate for the solution to optimality of the cell formation problem.Wed, 02 Nov 2016 20:28:50 GMTThe component retrieval problem in printed circuit board assembly
http://hdl.handle.net/2268/203078
Title: The component retrieval problem in printed circuit board assembly
<br/>
<br/>Author, co-author: Crama, Yves; Flippo, Olaf E.; Van de Klundert, Joris; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board, and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, then the additional problem emerges of selecting, for each placement on the board, the feeder slot from which the related component type is to be retrieved. In this paper, we consider this Component Retrieval Problem for placement machines that operate in a similar way as the Fuji CP II. We explain why a simple forward dynamic programming scheme cannot provide an efficient solution to this problem, thereby invalidating the correctness of an earlier published approach. We then present a polynomial algorithm that solves the problem to optimality. The analysis of the Component Retrieval Problem is greatly facilitated by its reformulation as a longest path problem in a PERT/CPM network with design aspects. Finding the minimal makespan of the assembly process thus amounts to identifying a design for which the longest path in the induced network is shortest. As an alternative interpretation, the Component Retrieval Problem can be viewed as a shortest path problem with side-constraints. The complexity of these network problems is analysed, and it is proven that the polynomial solvability of the Component Retrieval Problem is caused by the specific structure it inflicts on the arc lengths in the network. In the absence of this structure, the network problems are shown to be NP- hard in general.Wed, 02 Nov 2016 20:19:22 GMTScheduling jobs of equal length: complexity, facets and computational results
http://hdl.handle.net/2268/202812
Title: Scheduling jobs of equal length: complexity, facets and computational results
<br/>
<br/>Author, co-author: Crama, Yves; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed timespan [0,T], subdivided into T unit-length subperiods. The processing time (or length) of each job equals p,p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs.
This problem is proved to be NP-hard, already for p=2 and 0–1 processing costs. On the other hand, when T=np+c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions.
Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.Mon, 24 Oct 2016 07:02:47 GMTProduction Planning in Automated Manufacturing
http://hdl.handle.net/2268/202760
Title: Production Planning in Automated Manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.; Spieksma, Frits C.R.Fri, 21 Oct 2016 08:17:53 GMT