References of "Crama, Yves"
     in
Bookmark and Share    
See detailQuadratization of pseudo-Boolean functions
Crama, Yves ULg; Anthony, Martin; Boros, Endre et al

Conference (2015, July)

Detailed reference viewed: 17 (0 ULg)
Full Text
Peer Reviewed
See detailMulti-period vehicle assignment problem with stochastic transportation order availability
Pironet, Thierry ULg; Crama, Yves ULg

Conference (2015, June 01)

This work investigates optimization techniques for a vehicle-load assignment problem. A company owning a limited fleet of vehicles wants to maximize its operational profit over an infinite horizon divided ... [more ▼]

This work investigates optimization techniques for a vehicle-load assignment problem. A company owning a limited fleet of vehicles wants to maximize its operational profit over an infinite horizon divided into periods. The profit stems from revenues for transporting full truckloads and costs derived from waiting idle and moving unladen. The stochastic component of the problem arises from projections on the realization of each transportation order, i.e. load. The methodology is based on optimizing decisions for deterministic scenarios. Several policies are generated in this way, from simple heuristics to more complex approaches, such as consensus and restricted expectation algorithms, up to policies derived from network flow models formulated over subtrees of scenarios. Myopic and a-posteriori deterministic optimizations models are used to compute bounds allowing for performance evaluation. Tests are performed on various instances featuring different number of loads, graph sizes, sparsity, and probability distributions. Performances are compared statistically over paired samples. The robustness of various policies with respect to erroneous évaluations of the probability distributions is also analyzed. [less ▲]

Detailed reference viewed: 24 (0 ULg)
Full Text
See detailProceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems
Marchetti-Spaccamela, Alberto; Crama, Yves ULg; Goossens, Dries et al

Book published by KU Leuven (2015)

This volume contains abstracts of talks presented at the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne ... [more ▼]

This volume contains abstracts of talks presented at the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne, Belgium. MAPSP is a biennial workshop dedicated to all theoretical and practical aspects of scheduling, planning, and timetabling. The abstracts in this volume include 5 invited talks by Onno Boxma, Michel Goemans, Willem-Jan van Hoeve, Rolf Niedermeier, and Stephan Westphal, plus 88 contributed talks. [less ▲]

Detailed reference viewed: 26 (3 ULg)
See detailFunctions of binary variables
Crama, Yves ULg

Conference (2015, April 29)

Detailed reference viewed: 12 (0 ULg)
Full Text
See detailQuand les maths nous transportent...
Crama, Yves ULg

Conference given outside the academic context (2015)

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter ... [more ▼]

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter deux fois le même pont. Leonhard Euler apporta en 1736 une démonstration élégante de cette affirmation. Il produisit ainsi l’une des premières applications des mathématiques à la construction d’itinéraires optimisés. Aujourd’hui, la modélisation mathématique est devenue un outil indispensable pour les décideurs dans le monde du transport et, plus généralement, pour la gestion et la planification des activités logistiques. Qu’il s’agisse de calculer l’itinéraire le plus rapide de Liège à Marbella, d’optimiser les tournées de livraison d’une chaîne de grande distribution, de charger des navires ou des avions en assurant leur stabilité, de réduire les stocks excédentaires d’une entreprise pharmaceutique, de fixer le prix de billets de TGV en fonction des places disponibles, dans chaque cas, les mathématiques, alliées à l’informatique, permettent de formuler de façon précise le problème rencontré et d’y apporter des réponses pertinentes. Cet exposé présentera quelques applications typiques des mathématiques dans le domaine de la logistique et fournira un aperçu des méthodes qui y sont mises en œuvre. [less ▲]

Detailed reference viewed: 19 (2 ULg)
Full Text
See detailExact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time
Michelini, Stefano ULg; Arda, Yasemin ULg; Crama, Yves ULg et al

Scientific conference (2015, February 05)

We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a ... [more ▼]

We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch-and-Price algorithm considering the pricing subproblem, an elementary shortest path problem with resource constraints (ESPPRC). We discuss research on this exact solution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲]

Detailed reference viewed: 12 (1 ULg)
Full Text
See detailA branch-and-price algorithm for 2-period vehicle routing problems
Crama, Yves ULg; Rezaei Sadrabadi, Mahmood ULg; Van Woensel, Tom

E-print/Working paper (2015)

We consider a Vehicle Routing Problem (VRP) with deterministic orders in two periods from a set of stores. Orders in period 1 (2) can be postponed (advanced) to the other period but any diversion from the ... [more ▼]

We consider a Vehicle Routing Problem (VRP) with deterministic orders in two periods from a set of stores. Orders in period 1 (2) can be postponed (advanced) to the other period but any diversion from the initial orders incurs a penalty. From the perspective of a Logistics Service Provider (LSP), such diversions could be beneficial if savings in the routing costs outweigh the penalties. So could they be from a store's view, as the store can set a high enough penalty to compensate the diversion from its own optimal orders. In this paper, we introduce a new model where we seek a better solution for the LSP, compared to solving two independent VRPs with fixed orders, by allowing orders to be fully postponed or advanced. We apply a branch-and-price algorithm to solve this model to optimality. Many cutting-edge techniques are implemented to have an efficient branch-and-price algorithm, and two ideas to possibly improve the upper bound are tested. We draw algorithmic and managerial insights based on our test instances. [less ▲]

Detailed reference viewed: 77 (3 ULg)
Full Text
See detailQuadratizations of pseudo-Boolean functions
Rodriguez Heck, Elisabeth ULg; Crama, Yves ULg

Scientific conference (2014, December 04)

Detailed reference viewed: 17 (4 ULg)
See detailBoolean Functions for Classification: Logical Analysis of Data
Crama, Yves ULg

Conference (2014, November 20)

Detailed reference viewed: 13 (0 ULg)
Full Text
See detailQuand les maths nous transportent...
Crama, Yves ULg

Conference given outside the academic context (2014)

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter ... [more ▼]

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter deux fois le même pont. Leonhard Euler apporta en 1736 une démonstration élégante de cette affirmation. Il produisit ainsi l’une des premières applications des mathématiques à la construction d’itinéraires optimisés. Aujourd’hui, la modélisation mathématique est devenue un outil indispensable pour les décideurs dans le monde du transport et, plus généralement, pour la gestion et la planification des activités logistiques. Qu’il s’agisse de calculer l’itinéraire le plus rapide de Liège à Marbella, d’optimiser les tournées de livraison d’une chaîne de grande distribution, de charger des navires ou des avions en assurant leur stabilité, de réduire les stocks excédentaires d’une entreprise pharmaceutique, de fixer le prix de billets de TGV en fonction des places disponibles, dans chaque cas, les mathématiques, alliées à l’informatique, permettent de formuler de façon précise le problème rencontré et d’y apporter des réponses pertinentes. Cet exposé présentera quelques applications typiques des mathématiques dans le domaine de la logistique et fournira un aperçu des méthodes qui y sont mises en œuvre. [less ▲]

Detailed reference viewed: 26 (2 ULg)
See detailRevealed preference tests of collectively rational consumption behavior
Crama, Yves ULg

Conference (2014, October 28)

To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests that can be applied to real-world data. These tests check whether the observed ... [more ▼]

To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests that can be applied to real-world data. These tests check whether the observed household behavior is "rational", in the sense that it is consistent with the predictions of the model. In this talk, we present different approaches based on revealed preferences to test collective models of household consumption. Testing collective rationality is computationally difficult (NP-hard). In order to overcome this negative result, we introduce mixed-integer programming formulations which can be used for medium-sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model on large data sets. We present the results of computational experiments using our approaches. [less ▲]

Detailed reference viewed: 20 (1 ULg)
Full Text
See detailMulti-period vehicle assignment problem with stochastic load availability
Crama, Yves ULg; Pironet, Thierry ULg

E-print/Working paper (2014)

In this research, we want to investigate optimization techniques for a generic load assignment problem including a limited fleet of vehicles within a full-truck-load (FTL) multi-period setting including ... [more ▼]

In this research, we want to investigate optimization techniques for a generic load assignment problem including a limited fleet of vehicles within a full-truck-load (FTL) multi-period setting including forecasts on load availability. Several policies are generated from simple heuristics through state of the art approaches such as consensus and restricted expectation algorithms up to the optimization of a subtree of scenarios. Moreover, myopic and a-posteriori deterministic optimizations (including no or fully revealed information) set bounds for policies performance comparisons. Tests are performed for different graphs sizes and sparsity, several distribution laws and number of loads. Performances are compared statistically over paired samples. The robustness of performing policies against a false valuation of the probability distribution is also analyzed. [less ▲]

Detailed reference viewed: 64 (8 ULg)
Full Text
Peer Reviewed
See detailMulti-period vehicle loading with stochastic release dates
Arda, Yasemin ULg; Crama, Yves ULg; Kronus, David ULg et al

in EURO Journal on Transportation and Logistics (2014), 3(2), 93-119

This paper investigates a multi-period vehicle loading problem with stochastic information regarding the release dates of items to be transported. The deterministic version of the problem can be ... [more ▼]

This paper investigates a multi-period vehicle loading problem with stochastic information regarding the release dates of items to be transported. The deterministic version of the problem can be formulated as a large-scale set covering problem. Several heuristic algorithms are proposed to generate decision policies for the stochastic optimization model over a long rolling horizon. The resulting policies have been extensively tested on instances which display the main characteristics of the industrial case-study that motivated the research. The tests demonstrate the benefits of the multi-period stochastic model over simple myopic strategies. A simple and efficient heuristic is shown to deliver good policies and to be robust against errors in the estimation of the probability distribution of the release dates. [less ▲]

Detailed reference viewed: 181 (42 ULg)
Full Text
See detailShort Prime Quadratizations of Cubic Negative Monomials
Crama, Yves ULg; Rodriguez Heck, Elisabeth ULg

E-print/Working paper (2014)

Pseudo-Boolean functions naturally model problems in a number of different areas such as computer science, statistics, economics, operations research or computer vision, among others. Pseudo-Boolean ... [more ▼]

Pseudo-Boolean functions naturally model problems in a number of different areas such as computer science, statistics, economics, operations research or computer vision, among others. Pseudo-Boolean optimization (PBO) is NP-hard, even for quadratic polynomial objective functions. However, much progress has been done in finding exact and heuristic algorithms for the quadratic case. Quadratizations are techniques aimed at reducing a general PBO problem to a quadratic polynomial one. Quadratizing single monomials is particularly interesting because it allows quadratizing any pseudo-Boolean function by termwise quadratization. A characterization of short quadratizations for negative monomials has been provided. In this report we present a proof of this characterization for the case of cubic monomials, which requires a different analysis than the case of higher degree. [less ▲]

Detailed reference viewed: 37 (17 ULg)
Full Text
Peer Reviewed
See detailSpecific Multi-trip Operators for Vehicle Routing Problems
Arda, Yasemin ULg; Crama, Yves ULg; François, Véronique ULg et al

Conference (2014, July 17)

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem use existing VRP ... [more ▼]

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem use existing VRP heuristics to create trips, together with bin packing methods aimed at assigning these trips to the available vehicles. In this work, specific local search operators for the VRPM are proposed. Heuristics using these operators are compared with classical solution techniques mentioned above. [less ▲]

Detailed reference viewed: 16 (2 ULg)
Full Text
See detailOptimization of the service start time for an elementary shortest path problem with time windows
Arda, Yasemin ULg; Crama, Yves ULg; Kucukaydin, Hande ULg

E-print/Working paper (2014)

We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their ... [more ▼]

We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their individual time windows. When the vehicle visits a customer, it delivers the customer's demand and collects a revenue in return for the delivery. The vehicle can start its trip at any desired time. The transportation cost is a function of both the total distance traveled and the duration of the assigned trip. The objective is to determine the service start time from the depot, the subset of customers to be served, and the trip to be performed so as to minimize the total loss, which is calculated as the di erence between the transportation cost and the revenue collected from the customers. We develop two exact dynamic programming algorithms which can deal with an in nite number of Pareto-optimal states arising from the fact that the starting time and the duration of the trip act like continuous decision variables. We report computational results obtained with these algorithms and with a faster heuristic for the elementary shortest path problem. We also examine the performance of these algorithms when they are used to solve the pricing subproblem arising in the framework of a column generation algorithm for a related vehicle routing problem with time windows. [less ▲]

Detailed reference viewed: 219 (9 ULg)
See detailApproximation algorithms for multi-dimensional vector assignment problems
Crama, Yves ULg

Conference (2014, July 09)

Detailed reference viewed: 10 (1 ULg)
See detailVehicle routing problems with multiple trips: using specific local search operators
Arda, Yasemin ULg; Crama, Yves ULg; François, Véronique ULg et al

Conference (2014, June 25)

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem make use of existing ... [more ▼]

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem make use of existing VRP heuristics to create trips, together with bin packing methods aimed at assigning these trips to the available vehicles. The first contribution of this work is to propose specific local search operators for the VRPM. The operators directly integrate the multi-trip structure of the problem within well-known VRP operators. As a second contribution, heuristics using these operators are compared with classical solution techniques mentioned above. The comparison is performed by using the adaptive large neighborhood search metaheuristic as a common basis for both methods. The most classical version of the problem is studied as well as a variant involving time windows [less ▲]

Detailed reference viewed: 78 (8 ULg)
Full Text
See detailService Start Time Optimization in Elementary Shortest Path Problems with Resource Constraints
Arda, Yasemin ULg; Kucukaydin, Hande; Crama, Yves ULg

Scientific conference (2014, June 12)

Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and ... [more ▼]

Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and branch-and-price. We consider an elementary shortest path problem with resource constraints, where there is a capacitated single vehicle at the depot for serving a set of customers by respecting their associated time windows. The vehicle can start serving the customers at any desired time and can be used for a fixed amount of time. The total transportation cost is defined as a function of the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. Every time the vehicle visits a customer, it delivers the required load and collects a revenue in return for the delivery. The objective is to determine the trip to be performed and the service start time from the depot so as to minimize the total loss, which is calculated as the total transportation cost minus the collected revenues. In this study, we develop two exact dynamic programming algorithms which can deal with an infinite number of Pareto-optimal states arising from the fact that the vehicle can depart from the depot at any point in time and charges depending on the amount of time it spends for serving customers. Apart from reporting computational results for our elementary shortest path problem, we also embed it into a column generation framework for the corresponding capacitated vehicle routing problem with time windows. Recent results for the developed branch-and-price algorithm are also reported. [less ▲]

Detailed reference viewed: 12 (0 ULg)
See detailAbout almost periodic sequences of integers and related concepts
Crama, Yves ULg

Scientific conference (2014, May 07)

Detailed reference viewed: 16 (4 ULg)