Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics

We develop an optimization-based approach for a point-to-point route planning problem that arises in many large scale delivery systems (for example, less-than-truckload freight, rail, mail and package delivery, communications). In these settings, a firm which must ship goods between many origin and destination pairs on a network needs to specify a route for each origin–destination pair so as to minimize transportation costs and/or transit times. Typically, the cost structure is very complicated. The approach discussed in this paper exploits the structure of the problem to decompose it into two smaller subproblems, each amenable to solution by a combination of optimization and heuristic techniques. One subproblem is an “assignment” problem with capacity constraints. The other subproblem is a mixed-integer multicommodity flow problem. We propose solution methods based on Lagrangian relaxation for each subproblem. Computational results with these methods and with a heuristic procedure for the multicommodity flow problem on a problem met in practice are encouraging and suggest that mathematical programming methods can be successfully applied to large-scale problems in delivery systems planning and other problems in logistical system design.