Titre :

A Branch-Price-and-Cut algorithm for the Multi-Commodity two-echelon Distribution Problem

Auteur(s) :

Petris, Matteo [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Archetti, Claudia [Auteur]
ESSEC Business School
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Semet, Frédéric [Auteur]
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

EURO Journal on Transportation and Logistics

Pagination :

100139

Éditeur :

Springer

Date de publication :

2024

ISSN :

2192-4376

Mot(s)-clé(s) en anglais :

Two echelon routing problems Multiple commodities Split delivery Branch-Price-and-Cut
Two echelon routing problems
Multiple commodities
Split delivery
Branch-Price-and-Cut

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

In the Multi-Commodity two-echelon Distribution Problem (MC2DP), multiple commodities are distributed in a two-echelon distribution system involving suppliers, distribution centres and customers. Each supplier may provide ...
Lire la suite >In the Multi-Commodity two-echelon Distribution Problem (MC2DP), multiple commodities are distributed in a two-echelon distribution system involving suppliers, distribution centres and customers. Each supplier may provide different commodities and each customer may request several commodities as well. In the first echelon, capacitated vehicles perform direct trips to transport the commodities from the suppliers to the distribution centres for consolidation purposes. In the second echelon, each distribution centre owns a fleet of capacitated vehicles to deliver the commodities to the customers through multi-stop routes. Commodities are compatible, i.e., they can be mixed in the vehicles. Finally, customer requests can be split by commodities, that is, a customer can be visited by several vehicles, but the total amount of each commodity has to be delivered by a single vehicle. The aim of the MC2DP is to minimise the total transportation cost to satisfy customer demands. We propose a set covering formulation for the MC2DP where the exponential number of variables relates to the routes in the delivery echelon. We develop a Branch-Price-and-Cut algorithm (BPC) to solve the problem. The pricing problem results in solving an Elementary Shortest Path Problem with Resource Constraints (ESPPRC) per distribution centre. We tackle the ESPPRC with a label setting dynamic programming algorithm which incorporates ng-path relaxation and a bidirectional labelling search. Pricing heuristics are invoked to speed up the procedure. In addition, the formulation is strengthened by integrating capacity cuts and two families of valid inequalities specific for the multiple commodities aspect of the problem.<p>Our approach solves to optimality 439 over the 736 benchmark instances from the literature. The optimality gap of the unsolved instances is 2.1%, on average.</p>Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL