Groupe d’études et de recherche en analyse des décisions

G-2000-26

Weber's Problem with Forbidden Regions for Location and Transportation

, , et

Weber's problem is to locate a facility in the Euclidean plane in order to minimize total transportation costs from that facility to a given set of users with a fixed demand. We consider the case where location in some regions is forbidden as well as transportation through the same or other regions. An exact branch-and-bound algorithm is proposed in two versions to solve this problem. In the first, transportation costs are only assumed to be non-decreasing in the distance traveled from the facility. In the second, they are assumed to be proportional to that distance, which leads to more precise bounds and new tests. Computational experience is reported: problems with up to 1000 users are solved exactly for the first time.

, 20 pages