A generalized assignment heuristic for vehicle routing

Networks - Tập 11 Số 2 - Trang 109-124 - 1981
Marshall L. Fisher1, Ramchandran Jaikumar2
1The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania, 19104
2Graduate School of Business Administration, Harvard University, Boston, Massachusetts 02163

Tóm tắt

AbstractWe 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.

Từ khóa


Tài liệu tham khảo

10.1007/BF01386316

10.1057/jors.1969.75

Christofides N.“The Traveling Salesman Problem and Its Applications” ORSA/TIMS/AIIE Distribution Conference Feb.1978.

N.Christofides A.Mingozzi andP.Toth “The Vehicle Routing Problem” Urbino Working Paper July 1978.

10.1287/opre.12.4.568

10.1287/mnsc.27.1.1

M. L.FisherandR.Jaikumar “A Decomposition Algorithm for Large‐Scale Vehicle Routing” Decision Sciences Working Paper 78–11–05 University of Pennsylvania July1978.

M. L.Fisher R.Jaikumar andL.van Wassenhove “A Multiplier Adjustment Method for the Generalized Assignment Problem” Decision Sciences Working Paper University of Pennsylvania March 1981.

10.1057/jors.1967.44

10.1287/opre.22.2.340

10.1002/net.3230070203

P.KrolakandJ.Nelson “A Family of Truck Load Clustering Heuristics for Solving Vehicle Scheduling Problems” Working Paper Vanderbilt University (1978).

10.1002/j.1538-7305.1965.tb04146.x

10.1287/opre.21.2.498

P.Miliotis “Combining Cutting‐Plane and Branch and Bound Methods to Solve Integer Programming Problems” London School of Economics working paper (1977).

10.1007/BF01580682

U. R.Rau private communication.

10.1007/BF01580430

10.1287/opre.25.3.517

Shuster K. A., 1972, A Heuristic Approach to Routing Solid Waste Collection Vehicles

Tyagi M., 1968, A Practical Method for the Truck Dispatching Problem, J. Oper. Res. Soc. Jpn., 10, 76

10.1057/jors.1970.52

Thông tin
Thông tin xuất bản

Networks

Tập 11 Số 2

109-124

Thông tin tác giả