Abstract We consider a common variant of the vehicle routing problem in which a vehicle fleet delivers products stored at a central depot to satisfy customer orders. Each vehicle has a fixed capacity, and each order uses a fixed portion of vehicle capacity. The routing decision involves determining which of the demands will be satisfied by each vehicle and what route each vehicle will follow in servicing its assigned demand in order to minimize total delivery cost. We present a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost. This heuristic has many attractive features. It has outperformed the best existing heuristics on a sample of standard test problems. It will always find a feasible solution if one exists, something no other existing heuristic can guarantee. It can be easily adapted to accommodate many additional problem complexities. By parametrically varying the number of vehicles in the fleet, our method can be used to optimally solve the problem of finding the minimum size fleet that can feasibly service the specified demand.

Recent years have wRnessed an increasing number of systems of computers that are distributed geographically and connected by high-capacRy commumcauons channels in designing and managing such a network one must decide where to place copies of the various databases available to the users of the system This decision must trade off the cost of accessing a database, which ~s reduced by additional copies, against the cost of storing and updating the additional copies An optimizing algorithm for a general model of this problem ms described, and successful computational experience with large real examples is reported KEY WORDS AND PHRASES database location, mathematical programming models CR CATEGORIES 3 72, 4 33 IntroducuonRecent years have witnessed an increasing number of systems of computers that are distributed geographically and connected by high-capacity commumcations channels.The best known example is the network developed under the sponsorship of the Advanced Research Projects Agency (ARPA).These computer networks provide a number of benefits.They make possible the sharing of expensive specialized hardware, software, and databases, and they facilitate collaboration between geographically separated researchers studying the same problem.A number of difficult location problems arise in the design and management of such networks, including the problem of where to place copies of the various databases available to the users of the system.This decision must trade off the cost of accessing a database, which is reduced by additional copies, against the cost of storing and updating the additional copies.Other performance characteristics of the system are also affected by the positioning of database copies, including reliability of the system and opportumties for the parallel processing of requests against the database in order to reduce response time.This problem has received substantial attention.Previous literature (see Elam and Stutz [4] and Levin [13] for critical reviews) has been principally concerned with formulating appropriate models of the problem.Virtually all of these models are integer or mixedinteger linear programs.The more realistic models also belong to the notoriously difficult class of NP-hard problems, so we would expect the computation of an optimal solution to be a challenging task.Nevertheless, there has been little attention given to algorithm development in previous research.Computational experience with the few simple algorithms that have been proposed has been scant and limited to very small problems.This paper is intended to correct this gap in previous research.We describe an opumizing