Search results for "Integer programming"

The Multi-period Multi-trip Container Drayage Problem with Release and Due Dates

2021

Abstract The Container Drayage Problem (CDP) aims at routing a fleet of trucks, based at a common terminal, to serve customers while minimizing the total travel distance. Each trip starts from and ends at the terminal, and handles a subset of customers. Each customer requires either that a container is picked up or delivered. We introduce a more realistic variant, i.e., the Multi-trip Multi-period CDP with Release and Due Dates (MM-CDP-RDD), in which the planning horizon is composed of several periods (days). On each day, each truck may perform more than one trip respecting the Release and Due Dates (RDD) associated with customer services, corresponding to the first and the last day on whic…

Min-max control of uncertain multi-inventory systems with multiplicative uncertainties

2001

In this note, we consider production-distribution systems with buffer and capacity constraints. For such systems, we assume that the model is not known exactly. More precisely, the entries of the matrix representing the system structure may be affine functions of some uncertain time-varying parameters that take values within assigned bounds. We give stabilizability conditions that can be checked, in principle, by solving a min-max problem on the surface of the state-space (buffer level space) unit ball. Then, we consider a special case in which each uncertain parameter affects a single column of the system matrix and is independent of all the other ones. In this case, we propose a mixed int…

Dual Inequalities for Stabilized Column Generation Revisited

2014

Column generation (CG) models have several advantages over compact formulations: they provide better linear program bounds, may eliminate symmetry, and can hide nonlinearities in their subproblems. However, users also encounter drawbacks in the form of slow convergence, also known as the tailing-off effect, and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize th…

Field testing of repurposed electric vehicle batteries for price-driven grid balancing

2019

Abstract As electric cars become more widespread, the disposal and recycling of used batteries will become an important challenge. Typically, vehicle batteries are replaced if their capacity drops to 70–80% of initial capacity. However, they may still be useful for stationary applications. In this paper, results from a field test of a molten salt high-temperature electric vehicle battery repurposed as stationary storage for grid balancing are presented. In a previous study, we have shown that a mixed integer linear programming control strategy driven by a spot-market price for electricity is best suited for an implementation on hardware with limited computational resources. A 14-day experim…

A decomposition approach for multidimensional knapsacks with family-split penalties

2022

The optimization of Multidimensional Knapsacks with Family-Split Penalties has been introduced in the literature as a variant of the more classical Multidimensional Knapsack and Multi-Knapsack problems. This problem deals with a set of items partitioned in families, and when a single item is picked to maximize the utility, then all items in its family must be picked. Items from the same family can be assigned to different knapsacks, and in this situation split penalties are paid. This problem arises in real applications in various fields. This paper proposes a new exact and fast algorithm based on a specific Combinatorial Benders Cuts scheme. An extensive experimental campaign computational…

ADAPT - Advanced Prediction Models for Trajectory-Based Operations (TBO)

2018

Nesting Problems : Exact and Heuristic Algorithms

2013

Nesting problems are two-dimensional cutting and packing problems involving irregular shapes. This thesis is focused on real applications on Nesting problems such as the garment industry or the glass cutting. The aim is to study different mathematical methodologies to obtain good lower bounds by exact procedures and upper bounds by heuristic algorithms. The core of the thesis is a mathematical model, a Mixed Integer Programming model, which is adapted in each one of the parts of the thesis. This study has three main parts: first, an exact algorithm for Nesting problems when rotation for the pieces is not allowed; second, an Iterated Greedy algorithm to deal with more complex Nesting problem…

Landowner preferences and conservation prioritization : response to Nielsen et al

2017

Minimizing fleet operating costs for a container transportation company

2006

Abstract This paper focuses on a fleet management problem that arises in container trucking industry. From the container transportation company perspective, the present and future operating costs to minimize can be divided in three components: the routing costs, the resource (i.e., driver and truck) assignment costs and the container repositioning costs (i.e., the costs of restoring a given container fleet distribution over the serviced territory, as requested by the shippers that own the containers). This real-world problem has been modeled as an integer programming problem. The proposed solution approach is based on the decomposition of this problem in three simpler sub-problems associate…