Context-free vector assignment location problems

This dissertation deals with the location of public facilities on a network where all customers do not travel to their closest facility, but where customer travel is based solely upon the relative distance to the various facilities. Reasons for customer travel to nonclosest facilities include, but are not limited to, perceived differences in facilities, customer preference, convenience factors, and queue delays.

The concept of vector assignment of customer demand nodes to facilities is introduced and applied to the development of context-free facility location models which account for travel by customers to facilities other than the closest one. A generalization of the P-Median Problem is described and formulated where the assumption of travel to the closest facility is replaced by the assumption that fixed percentages of customers travel to their k^th closest facility. This generalization is called the Vector Assignment P-Median Problem (VAPMP). A proof is presented which shows that an optimal solution to the VAPMP exists which consists entirely of nodes of the graph; however, there may be more than one facility per node. Formulations of a number of other classical location problems are modified to account for the possibility of travel to other than the closest facility.

Three different procedures are developed for the solution of the VAPMP: (a) linear programming relaxation, (b) subgradient optimization of the Lagrangian dual, and (c) vertex substitution. The subgradient optimization of the Lagrangian dual is shown to be an efficient procedure

iii

iv which obtained and verified optimal solutions to almost all the problems tested. The subgradient procedure is modified and applied to the solution of two related generalized median location problems.

Constraints on the distance between customers and facilities and constraints on the utilization of facilities are developed and formulated. The impact on the solution procedures of various additional constraints is discussed.

The VAPMP is applied to the location of ambulance stations where the objective is the minimization of average response time. A procedure is developed to identify solutions to the ambulance location problem where response time to particular areas can be limited. Another procedure is developed to identify location configurations which have a more nearly balanced workload without increasing overall response time greatly.