Optimisation of large-scale overnight delivery networks

This thesis is concerned with scheduling the delivery of a product (mail or similar courier products) across a large scale network serviced by several types of vehicle (aircraft and trucks) over a fixed time horizon (overnight). Mathematically the problem can be described as a vehicle routing-like problem with multiple depots coupled with a multi-commodity network flow problem for product. It is shown that a straightforward mixed integer program formulation can solve only very small problem instances of this NP-hard problem. Hence a heuristic solution framework is developed which is suitable for largescale problems, as inspired by similar heuristics used in related transportation problems (the less-than-truckload motor carrier industry in particular). The technique presented decomposes the problem into a product-flow subproblem and a vehicle routing-like subproblem. It is shown that the application of this heuristic produces high quality solutions in terms of the overall transport network cost, and that embedding within multistart and simulated annealing metaheuristics (with suitable neighbourhoods) obtains slightly better results, and stabilises the search with respect to the parameters, for the more computationally amenable data sets. A variety of implementation and modelling issues are also considered in order that the mathematical model be practical in the context of a national postal corporation. These issues include innovative ways of modelling the costs of transshipping, deciding between transport modes in order to producing realistic mail routes, and modelling Travelling Post Offices.

  • Record URL:
  • Supplemental Notes:
    • PhD thesis presented to the University of Queensland Thesis available for purchase from the university library
  • Authors:
    • Grenfell, A
  • Publication Date: 2007


  • English

Media Info

  • Pagination: 1 vol (various pagings)

Subject/Index Terms

Filing Info

  • Accession Number: 01386825
  • Record Type: Publication
  • Source Agency: ARRB
  • Files: ATRI
  • Created Date: Aug 22 2012 9:50PM