Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

A branch-and-price algorithm for 2-period vehicle routing problems Crama, Yves ; Rezaei Sadrabadi, Mahmood ; 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: 116 (7 ULg)Quadratizations of pseudo-Boolean functions Rodriguez Heck, Elisabeth ; Crama, Yves Scientific conference (2014, December 04) Detailed reference viewed: 31 (14 ULg)Boolean Functions for Classification: Logical Analysis of Data Crama, Yves Conference (2014, November 20) Detailed reference viewed: 24 (0 ULg)Quand les maths nous transportent... Crama, Yves 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: 53 (3 ULg)Revealed preference tests of collectively rational consumption behavior Crama, Yves 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: 24 (1 ULg)Multi-period vehicle loading with stochastic release dates Arda, Yasemin ; Crama, Yves ; Kronus, David 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: 206 (53 ULg)Short Prime Quadratizations of Cubic Negative Monomials Crama, Yves ; Rodriguez Heck, Elisabeth 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: 57 (28 ULg)Specific Multi-trip Operators for Vehicle Routing Problems Arda, Yasemin ; Crama, Yves ; François, Véronique 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: 50 (4 ULg)Optimization of the service start time for an elementary shortest path problem with time windows Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande 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: 237 (13 ULg)Approximation algorithms for multi-dimensional vector assignment problems Crama, Yves Conference (2014, July 09) Detailed reference viewed: 12 (1 ULg)Vehicle routing problems with multiple trips: using specific local search operators Arda, Yasemin ; Crama, Yves ; François, Véronique 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: 111 (10 ULg)Service Start Time Optimization in Elementary Shortest Path Problems with Resource Constraints Arda, Yasemin ; ; Crama, Yves 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: 21 (0 ULg)About almost periodic sequences of integers and related concepts Crama, Yves Scientific conference (2014, May 07) Detailed reference viewed: 20 (6 ULg)Compact quadratizations of nonlinear binary optimization problems Crama, Yves ; Rodriguez Heck, Elisabeth Conference (2014, March 25) Detailed reference viewed: 54 (23 ULg)An exact bi-directional dynamic programming algorithm for an elementary shortest path problem with variable service start time Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande Conference (2014, January 31) We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start ... [more ▼] We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start servicing the customers at any desired time, but it can be used for a fixed amount of time. The total transportation cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. On the other hand, each served customer yields a revenue. Thus, the aim is to identify the path to be followed and the start time of the vehicle from the depot that minimize the total transportation cost minus the gained revenues. This kind of a problem can be encountered as a pricing subproblem when a branch-and-price algorithm is applied to solve vehicle routing problems with additional constraints. In such a case, the revenues correspond to the dual prices of the visited vertices. It is known that the classical ESPPRC can be solved to optimality by implementing a dynamic programming (DP) algorithm. However, our problem has to take an infinite number of Pareto-optimal states into consideration, since the vehicle can leave the depot at any point in time and charges depending on the total traveling and waiting time. We propose an exact DP algorithm which can deal with an infinite number of Pareto-optimal states by representing total traveling and waiting time as a piecewise linear function of the service start time at the depot and develop suitable dominance rules. Furthermore, a column generation algorithm is devised for solving the relaxed set covering formulation of the related vehicle routing problem where new columns are determined by the proposed DP algorithm. Finally, computational results are presented. [less ▲] Detailed reference viewed: 143 (1 ULg)Quadratic reformulations of nonlinear binary optimization problems Crama, Yves Conference (2014, January 30) Detailed reference viewed: 28 (1 ULg)Quadratic reformulations of nonlinear binary optimization problems Crama, Yves Conference (2014, January 06) Detailed reference viewed: 22 (2 ULg)Multi-Dimensional Vector Assignment Problems ; Crama, Yves ; in Discrete Optimization (2014), 14 We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of ... [more ▼] We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of which contains the same number n of p-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the m sets of vectors into n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case m = 3 and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension p. [less ▲] Detailed reference viewed: 38 (9 ULg)Optimization of Service Start Time for an Elementary Shortest Path Problem Kucukaydin, Hande ; Arda, Yasemin ; Crama, Yves Conference (2013, July 08) We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers ... [more ▼] We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers with a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where the delivery and backhaul customers are considered to be two disjoint sets. Split deliveries and pick-ups are not allowed. In this problem, the vehicle may be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. Namely, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the objective is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the total of the distance and time costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices. In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, computational results are presented. [less ▲] Detailed reference viewed: 92 (14 ULg)Neighborhood Search Approaches for a Vehicle Routing Problem with Multiple Trips and Driver Shifts Arda, Yasemin ; Crama, Yves ; François, Véronique Conference (2013, July 08) Detailed reference viewed: 49 (16 ULg) |
||