The fixed-charge transportation problem (FCTP) is a generalization of the transportation problem where an additional fixed cost is paid for sending a flow from an origin to a destination. We propose an iterated local search heuristic based on the utilization of reduced costs for guiding the restart phase. The reduced costs are obtained by applying a lower bounding procedure that computes a sequence of nondecreasing lower bounds by solving a three-index mathematical formulation of the problem strengthened with valid inequalities. The proposed method was tested on two sets of benchmark instances from the literature. The first set was used to evaluate the state-of-the-art heuristics for the problem; the proposed heuristic was able to provide new best-knownupper bounds on all 124 open instances. On the second set of instances, which was recently introduced for testing the currently best exact method for the problem, the new heuristic was able to provide provably good upper bounds within short computing times.

A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem / Erika Buson;Roberto Roberti;Paolo Toth. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 62:(2014), pp. 1095-1106. [10.1287/opre.2014.1288]

A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem

ROBERTI, ROBERTO;TOTH, PAOLO
2014

Abstract

The fixed-charge transportation problem (FCTP) is a generalization of the transportation problem where an additional fixed cost is paid for sending a flow from an origin to a destination. We propose an iterated local search heuristic based on the utilization of reduced costs for guiding the restart phase. The reduced costs are obtained by applying a lower bounding procedure that computes a sequence of nondecreasing lower bounds by solving a three-index mathematical formulation of the problem strengthened with valid inequalities. The proposed method was tested on two sets of benchmark instances from the literature. The first set was used to evaluate the state-of-the-art heuristics for the problem; the proposed heuristic was able to provide new best-knownupper bounds on all 124 open instances. On the second set of instances, which was recently introduced for testing the currently best exact method for the problem, the new heuristic was able to provide provably good upper bounds within short computing times.
2014
A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem / Erika Buson;Roberto Roberti;Paolo Toth. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 62:(2014), pp. 1095-1106. [10.1287/opre.2014.1288]
Erika Buson;Roberto Roberti;Paolo Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/402968
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 18
social impact