The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a fleet of homogeneous vehicles to purchase different products at the selected suppliers so that all product demands are fulfilled and traveling and purchasing costs are minimized. We consider variants of the MVTPP in which the capacity of the vehicles can become binding and the demand for each product is one unit. Corresponding solution algorithms from the literature are either branch-and-cut or branch-and-price algorithms, where in the latter case the route-generation subproblem is solved on an expanded graph by applying standard dynamic-programming techniques. Our branch-price-and-cut algorithm employs a novel labeling algorithm that works directly on the original network and postpones the purchasing decisions until the route has been completely defined. Moreover, we define a new branching rule generally applicable in case of unitary product demands, introduce a new family of valid inequalities to apply when suppliers can be visited at most once, and show how product incompatibilities can be handled without considering additional resources in the pricing problem. In comprehensive computational experiments with standard benchmark sets we prove that the new branch-price-and-cut approach is highly competitive.

A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand / N. Bianchessi, S. Irnich, C. Tilk. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 288:(2021 Jan 15), pp. 152-170. [10.1016/j.dam.2020.08.014]

A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand

N. Bianchessi
Primo
;
2021

Abstract

The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a fleet of homogeneous vehicles to purchase different products at the selected suppliers so that all product demands are fulfilled and traveling and purchasing costs are minimized. We consider variants of the MVTPP in which the capacity of the vehicles can become binding and the demand for each product is one unit. Corresponding solution algorithms from the literature are either branch-and-cut or branch-and-price algorithms, where in the latter case the route-generation subproblem is solved on an expanded graph by applying standard dynamic-programming techniques. Our branch-price-and-cut algorithm employs a novel labeling algorithm that works directly on the original network and postpones the purchasing decisions until the route has been completely defined. Moreover, we define a new branching rule generally applicable in case of unitary product demands, introduce a new family of valid inequalities to apply when suppliers can be visited at most once, and show how product incompatibilities can be handled without considering additional resources in the pricing problem. In comprehensive computational experiments with standard benchmark sets we prove that the new branch-price-and-cut approach is highly competitive.
vehicle routing; multiple vehicle traveling purchaser problem; unitary demand; incompatible products; column generation; dynamic-programming labeling algorithm
Settore MAT/09 - Ricerca Operativa
   Advanced Cosmetic Manifacturing (AD-COM)
   AD-COM
   REGIONE LOMBARDIA
   ID 214632
15-gen-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
LM-2020-02.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 448.42 kB
Formato Adobe PDF
448.42 kB Adobe PDF Visualizza/Apri
DA11755-R1-POSTPRINT.pdf

Open Access dal 16/01/2023

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 492.49 kB
Formato Adobe PDF
492.49 kB Adobe PDF Visualizza/Apri
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: https://hdl.handle.net/2434/707058
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact