Determination of routes for express delivery companies

A problem that must be solved by express delivery companies is the design of a distribution network for the collection and delivery of small packages. This is a complex problem for which exact solution methods are not readily available. The present work involves the definition of a simplified version of the problem, which is solved through heuristic methods. The simplified problem is treated as a variation of the capacitated minimum spanning tree problem and for its solution two local search heuristics have been developed. For small networks (with up to 20 cities), some computational experiments were conducted to compare the results obtained from the two heuristics with optimal solutions obtained through a mathematical formulation of the problem. The solutions obtained through the heuristics were very close to the optimal solutions; it must be considered, however, that the sample is small and consists of small problems. The two heuristics are also compared to each other for networks of up to 100 cities.