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

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

9 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)3056-3068
Aantal pagina's13
TijdschriftComputers & Operations Research
Volume40
Nummer van het tijdschrift12
DOI's
StatusGepubliceerd - 13 aug 2013
Extern gepubliceerdJa

Vingerafdruk

Duik in de onderzoeksthema's van 'Beam search heuristics for the single and multi-commodity capacitated Multi-facility Weber Problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit