An analysis of a garbage collection operation

Abstract

In this paper we consider a vehicle routeing problem in which trucks are assigned streets from which to collect house refuse. We discuss the construction of simple networks which aid in the solution of the garbage collection problem. After the construction of the networks, we consider two solution procedures.

The vehicle routeing problem is formulated as an integer linear programming problem, ILP. The ILP formulation is appropriate here because the decision for a particular truck to collect or not to collect house refuse along a particular street is captured by use of binary variables which can take the values zero or one. In this case we use the computer package VINO1 (visual interactive nonlinear optimization) to solve the ILP. The VINO package uses Lotus 1‐2‐3 or Symphony as an interface (i.e. input and output medium).

We use graph theory results to solve the vehicle routeing problem. In particular we use the result that a graph is Eulerian (i.e. each arc of the graph can be traversed exactly once) if and only if each node (vertex) has an even degree (the degree of a node is the number of arcs incident with it) to determine the minimum total distance that all the trucks must travel in order to collect all the house refuse. This value and the Eulerian result is then used in constructing the routes for each truck.

Notes

* Current address: School of Applied Science, Monash University College, Gippsland, Churchill, Victoria, Australia 3842. 1 VINO is a LINDO Inc. trademark.

Additional information

Notes on contributors

Richard Egudo*

* Current address: School of Applied Science, Monash University College, Gippsland, Churchill, Victoria, Australia 3842. 1 VINO is a LINDO Inc. trademark.