Accession Number : ADA100992


Title :   A Generalized Assignment Heuristic for Vehicle Routing


Corporate Author : WHARTON SCHOOL PHILADELPHIA PA DEPT OF DECISION SCIENCES


Personal Author(s) : Fisher, Marshall L ; Jaikumar, Ramchandran


Full Text : http://www.dtic.mil/dtic/tr/fulltext/u2/a100992.pdf


Report Date : Aug 1979


Pagination or Media Count : 34


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.


Descriptors :   *ROUTING , *HEURISTIC METHODS , DECISION MAKING , COST ANALYSIS , LOGISTICS MANAGEMENT , RANDOM VARIABLES , SUPPLY DEPOTS , SCHEDULING , RESOURCE MANAGEMENT , VEHICLES , INVENTORY CONTROL , DECOMPOSITION , NETWORK FLOWS , ALGORITHMS , PARAMETRIC ANALYSIS


Subject Categories : Administration and Management
      Operations Research
      Military Operations, Strategy and Tactics


Distribution Statement : APPROVED FOR PUBLIC RELEASE