The Distribution Problem with Carrier Service: A Dual Based Penalty Approach

The distribution problem with carrier service is an important optimization problem that often arises in vehicle routing. The problem arises in the distribution of commodities from a central facility to a set of geographically distributed locations. Each location has a certain demand, the distribution vehicle has a load capacity, and the entire operation should be completed within a certain time. An outside carrier is available for direct service of locations from the central facility. The problem is to determine a feasible tour for the company vehicle and the locations to be served by the outside carrier such that the total cost of the operations is minimized. We model this problem and develop a solution technique using valid inequalities. A key feature of the solution approach is that it can easily be extended to solve similar problems with any type and number of side constraints as encountered in the current model. The algorithm has been extensively tested and computational results for problems having up to 200 locations are presented. The results show that the proposed approach is efficient and viable for solving problems of medium to large size. We also present a real-world application, and show how the model is implemented within the framework of an order scheduling and vehicle routing system. We present performance results with real-world data and demonstrate the operational efficiency achieved by using the proposed approach.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.