Pickup an delivery

THE TRUCK DISPATCHING PROBLEM*
G. B. DANTZIG' AND J. H. RAMSER' The paper is concerned with 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. The shortest routes between any two points in the system are given and a demand for one or several products is specified for a number of stations within thedistribution system. It is desired to find a way to assign stations to trucks in such a manner that station demands are satisfied and total mileage covered by the fleet is a minimnin A procedure based on a linear programming formulation is given for obtaining a near optimal solution. The calculations may he readily performed by hand or by an automatic digital computing machine. No practicalapplications of the method have been made as yet. A number of trial problems have been calculated, however. 1. Introduction

The "Truck Dispatching Problem" formulated in this paper may be considered asa generalization of the "Traveling-Salesman Problem".(1) In its simplest form the Traveling-Salesman Problem is concerned with the determination of the shortest route which passes through each of n givenpoints once. Assuming that each pair of points is joined by a link, the total number of different routes through n points is |n!. Even for small values of n the total number of routes is exceedingly large, e.g. for n = 15, there are 653,837,184,(XX) different routes. One of the authors has collaborated with Fulkerson and Johnson in developing a "cutting plane" approach for testing whether a proposedtour is optimal or finding an improved solution if it is not. (2), (3) The Traveling-Salesman Problem may be generalized by introducing additional conditions. Thus, the salesman may be required to return to the "terminal point" whenever he has contacted m of the n — 1 remaining points, m being a divisor of « — 1. For given n and m the problem is to find loops such that all loops have a specifiedpoint in common and total loop length is a minimum. Since the loops have one point in common, this problem may be called the "Clover Leaf Problem". If m is small, optimal sets of m points may often be determined by inspection of a map which contains the points and the arcs connecting them. One woiild look for "clusters of points" and determine by trial and error the order in which they should betraversed, taking care that no loop crosses itself. However, when clusters are not present in sufficient numbers or when m is large, this procedure becomes inapplicable. In this case near-best solutions may be obtained by the algorithm in this paper.

2. The Truck Dispatching Prohlem
The Traveling Salesman Problem may also be generalized by imposing the condition that specified deliveries g, bemade at every point P< (excepting the terminal point). If the capacity of the carrier
• Received Novemioer 1958 ' The RAND Corporation, Santa Monica, Califomia • The Atlantic Refining Company, Philadelphia, Pennsylvania
80

THE TRUCK DISPATCHING PROBLEM

81

(1)

c^
i

the problem is formally identical with the Traveling-Salesman Problem in its original form since the carrier can serve everydelivery point on one trip which links all the points. In the "Truck Dispatching Problem" the relation between C and the g< is such that the carrier can only make between 1 and t deliveries on each trip. Thus, the Truck Dispatching Problem is characterized by the relation

(2)

c « E?.-.
s'

It is obvious that the number of carriers does not enter the problem when they have the same capacity. Even whencarriers of different capacities are involved, or when a number of different products are to be delivered to every point, the same mathematical model may be used as will be shown below. For simplicity of presentation it will be assumed first that only one product is to be delivered and that all trucks have the same capacity C. The method of solution starts from the basic idea to synthesize the...