Beam search heuristics for the single and multi-commodity capacitated Multi-facility Weber Problems

M. Hakan Akyüz, Temel Öncan, I. Kuban Altinel

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)

Abstract

The Multi-facility Weber Problem (MWP) is concerned with locating I uncapacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. It is a non-convex optimization problem and difficult to solve. In this work, we focus on the capacitated extensions of the MWP which are Capacitated MWP (CMWP) and multi-commodity CMWP (MCMWP). Both the CMWP and MCMWP impose capacity restrictions on facilities. Indeed, the MCMWP is a natural extension of the CMWP and considers the situation where K distinct commodities are shipped subject to limitations on the total amount of goods sent from facilities to the customers. Customer locations, demands and capacities for each commodity are known a priori. The transportation costs, which depend on the commodity type, are proportional to the distance between customers and facilities. We first introduce branch and bound algorithms for both the CMWP and the MCMWP then we propose beam search heuristics for these problems. According to our computational experiments on standard and randomly generated test instances, we can say that the new heuristics perform very well.

Original languageEnglish
Pages (from-to)3056-3068
Number of pages13
JournalComputers & Operations Research
Volume40
Issue number12
DOIs
Publication statusPublished - 13 Aug 2013
Externally publishedYes

Keywords

  • Beam search
  • Branch and bound
  • Location-allocation
  • Transportation

Fingerprint Dive into the research topics of 'Beam search heuristics for the single and multi-commodity capacitated Multi-facility Weber Problems'. Together they form a unique fingerprint.

  • Cite this