Bissan GHADDAR - Ivey Business School at Western University, United Kingdom

June 12th 2018

The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches

Abstract: We present a generalization of the vehicle routing problem which consists of intercepting non-stationary targets with a fleet of vehicles in order to bring them to a common destination. This problem models new applications in drone routing, ridesharing, and logistics where a vehicle agrees to meet another vehicle or a customer at a location that is away from the designated home location. We propose a Mixed Integer Second Order Cone Program formulation for the problem, along with valid inequalities for strengthening the continuous relaxation. We further exploit the problem structure using a Lagrangian decomposition and propose an exact branch-and-price algorithm. Computational results on instances with varying characteristics are presented and the results are compared to the solution of the full problem using CPLEX. The proposed valid inequalities reduce the computational time of CPLEX by up to 30% on average while the proposed branch-and-price is capable of solving instances where CPLEX fails in finding the optimal solution within the imposed time limit.

Video link: https://www.youtube.com/watch?v=p4TIEXDekSM

Fabio FURINI - LAMSADE / Paris-Dauphine University, France

June 1st 2018

Reformulation and Decompositions of Mixed Integer Linear Programs

Abstract: The talk will present basic and advanced techniques to identify and take advantage of innovative decomposition and reformulation methods for hard Combinatorial Optimisation Problems. Divide and conquer, from Latin divide et impera, is one of the key techniques for tackling combinatorial optimization problems. It relies on the idea of decomposing complex problems into a sequence of subproblems that are then easier to handle. Decomposition techniques (such as Dantzig-Wolfe, Lagrangian, or Benders decomposition) are extremely effective in a wide range of applications, including cutting & packing, production & scheduling, routing & logistics, telecommunications, transportation and many others. Moreover, decomposition techniques are playing an important role in many different fields of mixed-integer linear and non-linear optimization, multi objective optimization, optimization under uncertainty, bilevel optimization, etc. Despite the tremendous amount of research on these topics, the mathematical optimization community is constantly faced with new challenges coming from theoretical aspects and real world applications that require the development of new advanced tools.

Video link: https://www.youtube.com/watch?v=QsSgb1pePnk

Tom ARCHIBALD - University of Edinburgh / Business School, United Kingdom

February 22th 2018

Modelling transshipments in retail networks when demand is not fully observed

Abstract: Transshipments are a means to redistribute inventory in a retail network in order to better meet customer demand. Models of transshipments generally assume that customer demand is observed. This research relaxes this assumption and proposes a model that can be used to plan transshipments in a general setting. A numerical study shows that a proposed heuristic based on approximate dynamic programming can lead to substantial cost savings compared to commonly used policies.

Video link: https://www.youtube.com/watch?v=cJP0O3wPM-M

Herbert DAWID - Bielefeld University, Germany

January 26th 2018

Dynamic Investment Strategies and Leadership in Product Innovation

Abstract: We employ a dynamic market model with endogenous creation of submarkets tostudy the optimal product innovation strategies of incumbent firms. Firms invest in production capacity and R&D knowledge stock, where the latter determines the hazard rate of innovation. We find that under Markov Perfect Equilibrium behavior the firm with a larger market share on the established market is less likely to be the first innovator. Investment in R&D knowledge is negatively affected by the opponent’s production capacity on the established market if the opponent has not innovated yet. However, this effect is reversed after the opponent has successfully introduced the new product. The firm with higher costs of adjusting capacity for the established product has a larger incentive to engage in product innovation and might even achieve higher long run profit than its more efficient competitor. Joint work with Herbert Dawid, Michel Y. Keoula, Michael Kopel, Peter M. Kort.

Video link: https://www.youtube.com/watch?v=QI99w-F75Bo

Jean-François CORDEAU - HEC Montreal, Canada

December 13th 2017

A Unified Decomposition Matheuristic for Assembly, Production and Inventory Routing

Abstract: While the joint optimization of production and outbound distribution decisions in a manufacturing context has been intensively studied in the past decade, the integration of production, inventory and inbound transportation from suppliers has received much less attention despite its practical relevance. We aim to fill the gap by introducing a general model for the assembly routing problem (ARP), which consists of simultaneously planning the assembly of a finished product at a plant and the routing of vehicles collecting materials from suppliers to meet the inventory requirements imposed by the production. We formulate the problem as a mixed-integer linear program and we propose a three-phase decomposition matheuristic that relies on the iterative solution of different subproblems. The first phase determines a setup schedule while the second phase optimizes production quantities, supplier visit schedules and shipment quantities. The third phase solves a vehicle routing problem for each period in the planning horizon. The algorithm is flexible and we show how it can also be used to solve two well-known problems related to the ARP: the production routing problem (PRP) and the inventory routing problem (IRP). Using the same parameter setting for all problems and instances, we obtain 781 new best known solutions out of 2,628 standard IRP and PRP test instances. In particular, on large-scale multi-vehicle instances, the new algorithm outperforms specialized state-of-the-art heuristics for these two problems.

Laurent ALFANDARI - ESSEC Business School, France

October 23th 2017

Tighter Models for Barge Container Ship Routing

Abstract: This paper addresses the problem of optimal planning of a liner service for a barge container shipping company. Given estimated weekly demands between pairs of ports, our goal is to determine the subset of ports to be called and the amount of containers to be shipped between each pair of ports, so as to maximize the pro.t of the shipping company. In order to save possible leasing or storage costs of empty containers at the respective ports, our approach takes into account the repositioning of empty containers. The line has to follow the outbound-inbound principle, starting from the port at the river mouth. We propose a novel integrated approach in which the shipping company can simultaneously optimize the route (along with repositioning of empty containers), the choice of the .final port, length of the turnaround time and the size of its fleet. To solve this problem, a new mixed integer programming model is proposed. On the publicly available set of benchmark instances for barge container routing, we demonstrate that this model provides very tight dual bounds and signi.cantly outperforms the existing approaches from the literature for splittable demands. We also show how to further improve this model by projecting out arc variables for modeling the shipping of empty containers. Our numerical study indicates that the latter model improves the computing times for the challenging case of unsplittable demands. We also study the impact of the turnaround time optimization on the total pro.t of the company. Joint work with T. Damjanovic, F. Furini, I. Ljubic, V. Maras, S. Martin.

Video link: https://www.youtube.com/watch?v=sCRXfJAGw9U

Fabio D'ANDREAGIOVANNI - CRNS-Laboratory Heudiasyc / Université de Compiègne, France

September 27th 2017

Zero-price Energy Offering by (Multiband) Robust Optimization

Abstract: We consider the problem of a price-taker generating company that wants to select energy o ering strategies for its generation units, to maximize the pro t while considering the uncertainty of market price. First, we review central references available in literature about the use of Robust Optimization (RO) for price-uncertain energy o ering, pointing out how they can expose to the risk of suboptimal and even infeasible o ering. We then propose a new RO-based o ering method, which is characterized by making o ers at zero price and overcomes all the limits of the benchmark methods. We show the e ectiveness of the new method on realistic instances provided by our industrial partners, getting very high increases in pro t. Our method is based on Multiband Robustness (MR - Büsing, D'Andreagiovanni, 2012), an RO model that re nes the classical Bertsimas-Sim model, while maintaining its computational tractability and accessibility. MR is essentially based on the use of histogram-like uncertainty sets, which result particularly suitable to represent empirical distributions commonly available in uncertain real-world optimization problems.