An exact method for the Multi-Trip Batch Delivery Problem
| Autor: | Robbes, Alexis, Kergosien, Yannick, Billaut, Jean-Charles |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Recherche Opérationnelle, Ordonnancement, Transport ERL 7002 (ROOT), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Robbes, Alexis |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | EURO 2021 EURO 2021, Jul 2021, Athènes, Greece |
| Popis: | International audience; We consider a Multi-Trip Batch Delivery Problem: we have a set of batches, each batch is composed of a predefined set of products and each product has to be delivered at a specific location before a given due date. A set of vehicles is carrying out deliveries, batch by batch. They leave from a common depot, deliver all products of their batch and come back to the depot to take charge of the next batch. The problem consists of assigning the batches to vehicles, determining the routes associated with each batch, and minimizing the total tardiness. This problem can be seen as a variant of a Multi-trip Vehicle Routing Problem with soft due dates. We also assume that each batch is associated with a release date (date from which the products of a batch are ready to leave the depot) and the delivery batch sequence of each vehicle is sorted in increasing order of release dates. This study is motivated by real-world applications where the delivery problem takes into account the production stage and the batch composition is imposed. To solve the problem, we propose an exact method based on a tree exploration in three phases. The method uses branch-and-bound algorithm technics with upper/lower bounds, dominance properties, symmetry cuts, and external memory. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|