Multi-terminal vehicle-dispatch algorithm

OmegaPublished 1 January 1976

Billy E. Gillett, Jerry G. Johnson

DOI10.1016/0305-0483(76)90097-9

Source URL

Citations171

SJR quartileQ1

SJR score2.31

SNIP2.20

TL;DR

Application of the Multi-Terminal Sweep Algorithm to eleven multiple terminal vehicle-dispatch problems shows that near-optimal solutions to large-scale problems can be found in a reasonable amount of computer time.

Abstract

This paper introduces the Multi-Terminal Sweep Algorithm, a heuristic algorithm for obtaining an approximate solution to the multiple terminal vehicle-dispatch problem. The procedure determines a set of routes by which vehicles from two or more terminals can service a collection of demand points so that the total distance traveled is kept near to the minimum. This solution also satisfies constraints on the vehicle load and on the length of each route. Application of the algorithm to eleven multiple terminal vehicle-dispatch problems shows that near-optimal solutions to large-scale problems can be found in a reasonable amount of computer time.

Keywords

Engineering

Management ScienceThe Truck Dispatching Problem

4,873 Citations1959George B. Dantzig, J. H. Ramser

A procedure based on a linear programming formulation is given for obtaining a near optimal solution to the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal.

Operations ResearchA Heuristic Algorithm for the Vehicle-Dispatch Problem

1,157 Citations1974Billy E. Gillett, Leland R. Miller

The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell’s and is slightly less so than Christ ofides andEilon's.

Journal of the Operational Research SocietyAn Algorithm for the Vehicle-dispatching Problem

699 Citations1969N.D. Christofides, Samuel Eilon

The vehicle-scheduling problem involves the design of several vehicle tours to meet a given set of requirements for customers with known locations, subject to a capacity constraint for the vehicles and a distance constraint for vehicles.

NetworksImplementing vehicle routing algorithms

332 Citations1977B. L. Golden, Thomas L. Magnanti +1 more

This work considers heuristic algorithms for vehicle routing, comparing techniques of Clarke and Wright, Gillett and Miller, and Tyagi, and presenting modifications and extensions which permit problems involving hundreds of demand points to be solved in a matter of seconds.

Journal of the Operational Research SocietyComputer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points

242 Citations1972Anthony Wren, A. C. HOLLIDAY

A new algorithm is presented that allows routes from several depots to be constructed simultaneously, subject to restrictions on numbers of vehicles at individual depots, and a flexible priority rule will select those to be served.

Management ScienceAn Upperbound Algorithm for the Single and Multiple Terminal Delivery Problem

88 Citations1972Frank A. Tillman, Thomas M. N. Cain

An upperbound algorithm is presented for solving the multiterminal delivery problem, which involves determining savings from joining points on routes and making possible assignments as a function of the maximum savings for joining cities on routes.