A Beam Search Heuristic for the Multi-commodity Capacitated Multi-facility Weber Problem


ÖNCAN T. , AKYÜZ M. H. , ALTINEL İ. K.

International MultiConference of Engineers and Computer Scientists (IMECS 2012), Hong Kong, PEOPLES R CHINA, 14 - 16 March 2012, pp.1617-1622 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • City: Hong Kong
  • Country: PEOPLES R CHINA
  • Page Numbers: pp.1617-1622

Abstract

The Multi-Commodity Capacitated Multi-facility Weber Problem (MCMWP) is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers for K commodities with the minimum total transportation cost. The MCMWP is a non-convex optimization problem. 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 present a branch and bound algorithm then we propose a beam search heuristic for the MCMWP. According to our computational experiments on randomly generated test instances, we can say that the proposed beam search heuristic yields comparable results with the previous best heuristics.