A branch-and-cut algorithm for the inventory routing problem with pickups and deliveries
| Autor: | Claudia Archetti, Antonio Sforza, M. Grazia Speranza, Maurizio Boccia, Claudio Sterle |
|---|---|
| Přispěvatelé: | Archetti, C., Speranza, M. G., Boccia, M., Sforza, A., Sterle, C. |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Information Systems and Management
General Computer Science Discretization Computer science Commodity 0211 other engineering and technologies Time horizon 02 engineering and technology Interval (mathematics) Management Science and Operations Research Industrial and Manufacturing Engineering Set (abstract data type) Lot-sizing reformulation 0502 economics and business Vehicle routing problem Routing 050210 logistics & transportation 021103 operations research 05 social sciences Inventory management Branch-and-cut Modeling and Simulation Routing (electronic design automation) Branch and cut Algorithm Pickups and deliverie |
| Popis: | This paper addresses the Inventory Routing Problem with Pickups and Deliveries (IRP-PD). A single commodity has to be picked up from several origins and distributed to several destinations. The commodity is made available at the supplier depot and at the pickup customers, with known amounts in each period of a discretized time horizon. The commodity is consumed by the delivery customers, whose demand, in each period of the time horizon, is known. The vehicles start and end their routes at the supplier depot. The objective is to determine a collection and distribution plan minimizing the sum of routing and inventory costs, satisfying inventory and capacity constraints. A mixed integer linear programming model is presented for the IRP-PD. Valid inequalities are proposed that are adapted from the inventory routing, the vehicle routing and the lot-sizing problems literature. Moreover, a new set of valid inequalities, called interval inequalities, is presented. A branch-and-cut algorithm is designed and tested on a large set of instances. Computational results show that the proposed approach is able to solve to optimality 946 out of 1280 instances. Moreover, the approach outperforms the state-of-the art method for the single vehicle case, increasing the number of instances solved to optimality from 473 to 538 out of 640 instances tested, with 133 new best known solutions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|