The Truck Dispatching Problem

TLDR

The study addresses optimal routing of gasoline delivery trucks between a bulk terminal and many service stations. The goal is to assign stations to trucks to satisfy demands while minimizing total fleet mileage, using a linear programming approach. The method uses known shortest routes and station demands, applying a linear programming formulation that can be solved manually or with a computer to produce near‑optimal assignments. The method has not yet been applied in practice, though several trial problems were solved.

Abstract

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 the distribution 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 minimum A procedure based on a linear programming formulation is given for obtaining a near optimal solution. The calculations may be readily performed by hand or by an automatic digital computing machine. No practical applications of the method have been made as yet. A number of trial problems have been calculated, however.