Publication details

Title Maximum dispersion algorithm for delivery scheduling from multiple sites
Document Type Conference Paper
Year 1999
Authors Mokashi, S.D., Kokossis, A.C.
Source Computers and Chemical Engineering, vol.23, no.SUPPL. 1
Keywords Delivery scheduling; Dispersion; Graph; Maximum dispersion; Optimization
Abstract The problem of optimal scheduling of product deliveries from multiple sites to customers in general is neither amenable to simple transportation models nor to algorithms on vehicle routing. Previous experience on single site problems shows the limitation of a pure mathematical programming approach in solving large scale industrial problems. This work provides a new formulation for multi-site delivery problems in the form of a weighted graph representation of various delivery options and their costs. The notion of dispersion of a graph is introduced to form the basis of the formulation and the optimization objective. The optimization objective is to search for a set of vertices, which form a dispersion, with the maximum aggregate weight. The maximum dispersion is shown to correspond to the optimal delivery schedule. An algorithm to achieve this objective is outlined. The smaIl CPU times over graphs of industrial size problems demonstrate the efficiency of the algorithm. The minor deviations of the solutions from those of the corresponding relaxed LPs provide good guarantees of optimality. © 1999 Elsevier Science Ltd.
More info Publication link