LOCATING DISCRETIONARY SERVICE FACILITIES .2. MAXIMIZING MARKET-SIZE,MINIMIZING INCONVENIENCE

Discretionary service facilities are providers of products and/or serv ices that are purchased by customers who are traveling on otherwise pr eplanned trips such as the daily commute. Optimum location of such fac ilities requires them to be at or near points in the transportation ne twork having sizable flows of different potential customers. N. Fouska (1988) and O. Berman, R. Larson and N. Fouska (ELF 1992) formulate a first version of this problem, assuming that customers would make no d eviations, no matter how small, from the preplanned route to visit a d iscretionary service facility. Here the model is generalized in a numb er of directions, all sharing the property that the customer may devia te from the preplanned route to visit a discretionary service facility . Three different generalizations are offered, two of which can be sol ved approximately by greedy heuristics and the third by any approximat e or exact method used to solve the p-median problem. We show for thos e formulations yielding to a greedy heuristic approximate solution, in cluding the formulation in ELF, that the problems are examples of opti mizing submodular functions for which the G. Nemhauser, L. Wolsey and M. Fisher (1978) bound on the performance of a greedy algorithm holds. In particular, the greedy solution is always within 37% of optimal, a nd for one of the formulations we prove that the bound is tight.