The literature on k-splittable flows, see Baier et al. (2002), provides evidence on how controlling the number of used paths enables practical applications of flows optimization in many real-world contexts. Such a modeling feature has never been integrated so far in Quickest Flows, a class of optimization problems suitable to cope with situations such as emergency evacuations, transportation planning and telecommunication systems, where one aims to minimize the makespan, i.e. the overall time needed to complete all the operations, see Pascoal et al. (2006). In order to bridge this gap, a novel optimization problem, the Quickest Multicommodity k-Splittable Flow Problem (QMCkSFP) is introduced in this paper. The problem seeks to minimize the makespan of transshipment operations for given demands of multiple commodities, while imposing restrictions on the maximum number of paths for each single commodity. The computational complexity of this problem is analyzed, showing its NP-hardness in the strong sense, and an original Mixed-Integer Programming formulation is detailed. We propose a matheuristic algorithm based on a hybridized Very Large-Scale Neighborhood Search that, utilizing the presented mathematical formulation, explores multiple search spaces to solve efficiently large instances of the QMCkSFP. High quality computational results obtained on benchmark test sets are presented and discussed, showing how the proposed matheuristic largely outperforms a state-of-the-art heuristic scheme frequently adopted in path-restricted flow problems.

A matheuristic approach for the Quickest Multicommodity k-Splittable Flow Problem / Melchiori, Anna; Sgalambro, Antonino. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 92:(2018), pp. 111-129. [10.1016/j.cor.2017.12.012]

A matheuristic approach for the Quickest Multicommodity k-Splittable Flow Problem

Anna Melchiori;
2018

Abstract

The literature on k-splittable flows, see Baier et al. (2002), provides evidence on how controlling the number of used paths enables practical applications of flows optimization in many real-world contexts. Such a modeling feature has never been integrated so far in Quickest Flows, a class of optimization problems suitable to cope with situations such as emergency evacuations, transportation planning and telecommunication systems, where one aims to minimize the makespan, i.e. the overall time needed to complete all the operations, see Pascoal et al. (2006). In order to bridge this gap, a novel optimization problem, the Quickest Multicommodity k-Splittable Flow Problem (QMCkSFP) is introduced in this paper. The problem seeks to minimize the makespan of transshipment operations for given demands of multiple commodities, while imposing restrictions on the maximum number of paths for each single commodity. The computational complexity of this problem is analyzed, showing its NP-hardness in the strong sense, and an original Mixed-Integer Programming formulation is detailed. We propose a matheuristic algorithm based on a hybridized Very Large-Scale Neighborhood Search that, utilizing the presented mathematical formulation, explores multiple search spaces to solve efficiently large instances of the QMCkSFP. High quality computational results obtained on benchmark test sets are presented and discussed, showing how the proposed matheuristic largely outperforms a state-of-the-art heuristic scheme frequently adopted in path-restricted flow problems.
2018
Quickest flow; k-splittable flow; Matheuristics; Flows over time; Multicommodity
01 Pubblicazione su rivista::01a Articolo in rivista
A matheuristic approach for the Quickest Multicommodity k-Splittable Flow Problem / Melchiori, Anna; Sgalambro, Antonino. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 92:(2018), pp. 111-129. [10.1016/j.cor.2017.12.012]
File allegati a questo prodotto
File Dimensione Formato  
Melchiori_Preprint_A-matheuristic-approach_2018.pdf

accesso aperto

Note: https://www.sciencedirect.com/science/article/pii/S030505481730312X?via%3Dihub
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Creative commons
Dimensione 365.14 kB
Formato Adobe PDF
365.14 kB Adobe PDF
Melchiori_A-matheuristic-approach_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 741.93 kB
Formato Adobe PDF
741.93 kB Adobe PDF   Contatta l'autore

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/11573/1187847
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact