In this work we study a suppliers selection and routing problem where a fleet of homogeneous vehicles with a predefined capacity is available for procuring different products from different suppliers with the aim to minimize both the traveling and the purchasing costs. Decisions are further complicated by the presence of pairwise incompatibility constraints among products, implying the impossibility of loading two incompatible products on the same vehicle. The problemis known as the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints.We study a variant in which products demand is unitary and propose a column generation approach based on a Dantzig-Wolfe reformulation of the problem, where each column represents a feasible vehicle route associated with a compatible purchasing plan.Two different procedures are introduced to solve the pricing problem, namely a labeling algorithm solving a Resource-Constrained Elementary Shortest Path Problem on an expanded graph, and a tailored branch-and-cut algorithm. Due to the integrality request on variables, we embed the column generation in a branch-and-bound framework and propose different branching rules, thus obtaining a branch-and-price procedure. Extensive tests, carried out on a large set of instances, show that our branch-and-price method performs well, improving on average, both in quality and in computational time, solutions obtained by a branch-and-cut approach existing in the literature that relies on a three-index connectivity constraints based formulation.

The Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints and Unitary Demands: A Branch-and-Price Approach / Manerba, Daniele; Gendreau, M; Mansini, R.. - (2014).

The Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints and Unitary Demands: A Branch-and-Price Approach

MANERBA, DANIELE;
2014

Abstract

In this work we study a suppliers selection and routing problem where a fleet of homogeneous vehicles with a predefined capacity is available for procuring different products from different suppliers with the aim to minimize both the traveling and the purchasing costs. Decisions are further complicated by the presence of pairwise incompatibility constraints among products, implying the impossibility of loading two incompatible products on the same vehicle. The problemis known as the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints.We study a variant in which products demand is unitary and propose a column generation approach based on a Dantzig-Wolfe reformulation of the problem, where each column represents a feasible vehicle route associated with a compatible purchasing plan.Two different procedures are introduced to solve the pricing problem, namely a labeling algorithm solving a Resource-Constrained Elementary Shortest Path Problem on an expanded graph, and a tailored branch-and-cut algorithm. Due to the integrality request on variables, we embed the column generation in a branch-and-bound framework and propose different branching rules, thus obtaining a branch-and-price procedure. Extensive tests, carried out on a large set of instances, show that our branch-and-price method performs well, improving on average, both in quality and in computational time, solutions obtained by a branch-and-cut approach existing in the literature that relies on a three-index connectivity constraints based formulation.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11583/2663713
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo