http://hdl.handle.net/2268/64 Search this channel search http://orbi.ulg.ac.be/simple-search http://hdl.handle.net/2268/147885 Title: Branch-and-price: principles and its application to a 2-period vehicle routing problem <br/> <br/>Author, co-author: Rezaei Sadrabadi, Mahmood <br/> <br/>Abstract: We review branch-and-price as an efficient algorithm to solve integer programming problems with huge number of variables. In particular, we discuss column generation algorithm as the main engine in branch-and-price. Implementation of branch-and-price to solve the most basic version of the well-known vehicle routing problem (VRP) is investigated, and some common tricks are introduced. Then, a new extension of VRP is introduced and exploitation of branch-and-price to solve it is discussed. We consider a 2-period vehicle routing problem where each vertex of the network has a positive demand for period 1, 2, or both. Each demand on period 1 can be postponed to period 2 in order to decrease sum of the routing costs on two periods, but it is penalized in the objective function. Similarly, each demand on period 2 can be advanced to period 1, and yet penalized, with the hope of reducing routing costs. We have used many of the classic tricks to implement branch-and-price for solving our 2-period VRP. We have also used new tricks to (1) possibly improve the upper bound during the course of column generation in each node and (2) decrease the computations time to solve pricing problem in column generation. http://hdl.handle.net/2268/147884 Title: Branch-and-price: principles and its application to a 2-period vehicle routing problem <br/> <br/>Author, co-author: Rezaei Sadrabadi, Mahmood <br/> <br/>Abstract: We review branch-and-price as an efficient algorithm to solve integer programming problems with huge number of variables. In particular, we discuss column generation algorithm as the main engine in branch-and-price. Implementation of branch-and-price to solve the most basic version of the well-known vehicle routing problem (VRP) is investigated, and some common tricks are introduced. Then, a new extension of VRP is introduced and exploitation of branch-and-price to solve it is discussed. We consider a 2-period vehicle routing problem where each vertex of the network has a positive demand for period 1, 2, or both. Each demand on period 1 can be postponed to period 2 in order to decrease sum of the routing costs on two periods, but it is penalized in the objective function. Similarly, each demand on period 2 can be advanced to period 1, and yet penalized, with the hope of reducing routing costs. We have used many of the classic tricks to implement branch-and-price for solving our 2-period VRP. We have also used new tricks to (1) possibly improve the upper bound during the course of column generation in each node and (2) decrease the computations time to solve pricing problem in column generation. http://hdl.handle.net/2268/147883 Title: Branch-and-price: principles and its application to a 2-period vehicle routing problem <br/> <br/>Author, co-author: Rezaei Sadrabadi, Mahmood <br/> <br/>Abstract: We review branch-and-price as an efficient algorithm to solve integer programming problems with huge number of variables. In particular, we discuss column generation algorithm as the main engine in branch-and-price. Implementation of branch-and-price to solve the most basic version of the well-known vehicle routing problem (VRP) is investigated, and some common tricks are introduced. Then, a new extension of VRP is introduced and exploitation of branch-and-price to solve it is discussed. We consider a 2-period vehicle routing problem where each vertex of the network has a positive demand for period 1, 2, or both. Each demand on period 1 can be postponed to period 2 in order to decrease sum of the routing costs on two periods, but it is penalized in the objective function. Similarly, each demand on period 2 can be advanced to period 1, and yet penalized, with the hope of reducing routing costs. We have used many of the classic tricks to implement branch-and-price for solving our 2-period VRP. We have also used new tricks to (1) possibly improve the upper bound during the course of column generation in each node and (2) decrease the computations time to solve pricing problem in column generation. http://hdl.handle.net/2268/146900 Title: Multiperiod vehicle loading with stochastic release dates <br/> <br/>Author, co-author: Arda, Yasemin; Crama, Yves; Kronus, David; Pironet, Thierry; Van Hentenryck, Pascal <br/> <br/>Abstract: Production scheduling and vehicle routing problems are well-known topics in operations management. Although these tasks are consecutive in the supply chain, few optimization models tackle the associated issues. A most common situation, in practice, is actually that transportation management is disconnected from production planning: when production items or batches have been completely processed by the manufacturing plant, they become available for shipping, and they are consequently handled by the transportation managers. From a global managerial perspective, and with a view towards coordination of the product flows and customer satisfaction, this is not an ideal process. It is by far preferable, indeed, to set up an integrated production-transportation plan taking into account, among other constraints, the capacity of the plants and the customer due-dates. The present research proposes a methodology to investigate a multi-period vehicle loading problem with deterministic or stochastic information concerning items arrivals from production. Results from related optimization techniques are statistically compared and the benefits of the multi-period and stochastic modeling is demonstrated. Finally, an efficient heuristic is highlighted and is shown to be robust to the deviation from item arrival forecasts. http://hdl.handle.net/2268/143679 Title: An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts <br/> <br/>Author, co-author: Arda, Yasemin; Crama, Yves; François, Véronique <br/> <br/>Abstract: This study analyzes a rich vehicle routing problem with multiple trips and driver shifts. The considered problem features are inspired from the practical case of a Belgian distribution company. Along with the multi-trip component, characteristics of this particular problem include time windows, pickup and delivery customers, and site-vehicle dependencies. Internal and external fleets are considered with different cost structures and driver shifts constraints. An adpative large neighborhood search is used to treat the problem. http://hdl.handle.net/2268/143678 Title: An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts <br/> <br/>Author, co-author: Arda, Yasemin; Crama, Yves; François, Véronique http://hdl.handle.net/2268/143176 Title: Monitoring delivery chains using multivariate control charts <br/> <br/>Author, co-author: Faraz, Alireza; Heuchenne, Cédric; Saniga, Erwin; Foster, Earnest <br/> <br/>Abstract: Delivery chains are concerned with the delivery of goods and services to customers within a specific time interval; this time constraint is added to the usual consumer demand for product or service quality. In this context, we address the idea of using process control tools to monitor this key variable of delivery time. In applications, there are usually several production and delivery sites and a variety of different ways to transport, treat and provide goods and services; that makes the problem multivariate in nature. We therefore propose to control the process using multivariate T2 control charts economically designed with the addition of statistical constraints, a design method called economic-statistical design. We illustrate the application in general through an illustrative example. http://hdl.handle.net/2268/142576 Title: Optimization model for empty container repositioning <br/> <br/>Author, co-author: Salmon, Frédéric; Limbourg, Sabine <br/> <br/>Abstract: Empty container management is a transportation issue relating to the imbalance of container demand and supply. This project aims at minimizing the overall cost of empty container management. It takes account of transit time, shipping cost, the carrying capacity of the various modes of transport, the stochastic demand and supply of each terminal and port as well as other parameters such as substitution or holding costs, plus the intermodality with road transportation. http://hdl.handle.net/2268/142535 Title: A general lot-sizing problem in a closed-loop supply chain with returns <br/> <br/>Author, co-author: Amand, Guillaume; Arda, Yasemin <br/> <br/>Abstract: We consider a stochastic version of the multi-product multi-level capacitated lotsizing and scheduling problem with sequence-dependent setups. A bottler needs to determine its production schedule over a finite horizon in order to satisfy a deterministic demand. The raw materials are supplied through two different sources: uncapacitated reserves of new bottles and the uncertain returns of used bottles. We present results for the single-item case. http://hdl.handle.net/2268/138900 Title: Hybrid Tabu Search Heuristics for a Bilevel Competitive Facility Location Model <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban http://hdl.handle.net/2268/138893 Title: A Bilevel Competitive Facility Location Model with Competitor’s Response <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban <br/> <br/>Abstract: We are concerned with a problem in which a new entrant leader firm aims at finding the location and attractiveness of each new facility to maximize its profit where there are existing facilities belonging to a competitor. The competitor reacts to the leader by adjusting the attractiveness levels of its existing facilities to maximize its profit. We first formulate a bilevel mixed-integer nonlinear programming model. Then, we convert it into an equivalent single level mixed-integer nonlinear program and solve it using global optimization methods. http://hdl.handle.net/2268/138888 Title: A discrete competitive facility location model with variable attractiveness <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban <br/> <br/>Abstract: We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant to compete against already existing ones that may belong to one or more competitors. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels to maximize the profit. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, two branch-and-bound methods using Lagrangean and nonlinear programming relaxations. http://hdl.handle.net/2268/138861 Title: The complexity of scheduling short tasks with few starting times <br/> <br/>Author, co-author: Crama, Yves; Spieksma, Frits C.R. <br/> <br/>Abstract: The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for these tasks on a single processor? This result establishes a sharp borderline between NP-complete and polynomially solvable versions of this problem with respect to the parameters \tau and k. http://hdl.handle.net/2268/138860 Title: Optimally Locating Facilities with Variable Characteristics <br/> <br/>Author, co-author: Kucukaydin, Hande; Altinel, I. Kuban; Aras, Necati <br/> <br/>Abstract: The main focus of this study is on competitive facility location problems which constitute a special family of facility location problems. In such a problem, a firm or franchise is concerned with installing new facilities to serve customers in a market where existing facilities with known locations and attractiveness levels compete for increasing their market share and profit. We can classify these problems into two groups: those with non-reactive competition and those with reactive competition. In this study, three different types of competitive facility location models are proposed in order to determine the locations and attractiveness levels of the new facilities to maximize the profit. The first one belongs to the former class, where the last two models fall into the latter one and therefore bring us to the area of the bilevel programming. Finally, a different facility location problem which takes the customer preferences into account is considered, where the facilities are not necessarily identical and customers visit different types of facilities according to some given probability distribution and the maximum distance which they are willing to travel. http://hdl.handle.net/2268/138834 Title: Ciftduzeyli Bir Rekabetci Tesis Yer Secimi Problemi Icin Tabu Arama Sezgiseli <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban <br/> <br/>Abstract: In this study, the problem of a firm is considered where the firm tries to open new facilities in a market where there are already existing facilities belonging to a competitor. The new entrant firm wishes to find the optimal location and attractiveness levels of its facilities to maximize its profit. On the other hand, the competitor can react to the new entrant by changing the attractiveness levels of its existing facilities, closing them and/or opening new facilities. The gravity-based rule is employed in order to model the customer behavior. According to this rule, the probability that a customer patronizes a facility is proportional to the attractiveness level of the facility and inversely proportional to the distance between the customer and the facility. To this end, a bilevel mixed-integer nonlinear programming problem in discrete space is formulated. The new entrant firm is the leader of the game and the competitor is the follower. In order to find feasible solutions to the model, two tabu search heuristic methods are proposed. Two exact methods are utilized as subroutines of the proposed methods: a gradient ascent algorithm and a branch-and-bound algorithm that uses nonlinear programming relaxation. http://hdl.handle.net/2268/138825 Title: A leader-follower game in competitive facility location <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban <br/> <br/>Abstract: We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. We propose heuristics that combine tabu search with exact solution methods. http://hdl.handle.net/2268/138804 Title: Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban <br/> <br/>Abstract: We are concerned with a problem in which a firm or franchise enters a market by locating new facilities where there are existing facilities belonging to a competitor. The firm aims at finding the location and attractiveness of each facility to be opened so as to maximize its profit. The competitor, on the other hand, can react by adjusting the attractiveness of its existing facilities with the objective of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the facilities of the firm can be located at predetermined candidate sites. We employ Huff's gravity-based rule in modeling the behavior of the customers where the fraction of customers at a demand point that visit a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. In order to find the optimal solution of this model, we convert it into an equivalent one-level mixed-integer nonlinear program so that it can be solved by global optimization methods. Apart from reporting computational results obtained on a set of randomly generated instances, we also compute the benefit the leader firm derives from anticipating the competitor's reaction of adjusting the attractiveness levels of its facilities. The results on the test instances indicate that the benefit is 58.33% on the average. http://hdl.handle.net/2268/138700 Title: A discrete competitive facility location model with variable attractiveness <br/> <br/>Author, co-author: Kucukaydin, Hande; Aras, Necati; Altinel, I. Kuban <br/> <br/>Abstract: We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant firm to compete against already existing facilities that may belong to one or more competitors. The demand is assumed to be aggregated at certain points in the plane and the new facilities can be located at predetermined candidate sites. We employ Huff’s gravity-based rule in modelling the behaviour of the customers where the probability that customers at a demand point patronize a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels so as to maximize the profit, which is calculated as the revenue from the customers less the fixed cost of opening the facilities and variable cost of setting their attractiveness levels. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and another branch-and-bound method with nonlinear programming relaxation. Computational results obtained on a set of randomly generated instances show that the last method outperforms the others in terms of accuracy and efficiency and can provide an optimal solution in a reasonable amount of time. http://hdl.handle.net/2268/134402 Title: Multi-period vehicle loading with stochastic release dates <br/> <br/>Author, co-author: Arda, Yasemin; Crama, Yves; Kronus, David; Pironet, Thierry; Van Hentenryck, Pascal <br/> <br/>Abstract: 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. http://hdl.handle.net/2268/128949 Title: Procédé opératoire nouveau pour l’étude physiologique des organes thoraciques <br/> <br/>Author, co-author: Fredericq, Léon <br/> <br/>Commentary: 1885 Certaines informations, telles que la pagination, la tomaison et l'année de publication, peuvent comporter des erreurs.