This thesis studies transportation procurement planning problems for the ship per with three different side constraints. In the transportation market, the key players are shippers and carriers. Shippers are manufacturers, distributors and any company that needs to move freight, and the carriers are the transportation companies which move the freight, e.g. shipping and trucking companies. In the transportation procurement process, the shippers are the auctioneers and the carriers are the bidders. Very often the shipper need to optimize their procurement decisions on selecting carriers and allocating freight volumes under various side constraints....[ Read more ]

This thesis studies transportation procurement planning problems for the ship per with three different side constraints. In the transportation market, the key players are shippers and carriers. Shippers are manufacturers, distributors and any company that needs to move freight, and the carriers are the transportation companies which move the freight, e.g. shipping and trucking companies. In the transportation procurement process, the shippers are the auctioneers and the carriers are the bidders. Very often the shipper need to optimize their procurement decisions on selecting carriers and allocating freight volumes under various side constraints.

The Minimum Quantity Commitment is motivated by the United States Federal Maritime Commission's stipulation that requires a shipper to guarantee a minimum quantity of freight volumes to each carrier that has engaged to carry cargos to the United States. With such a constraint for volume guarantees, the procurement planning problem becomes intractable. To solve the problem practically, we provide a mixed-integer programming model defined by a number of strong facets. Based on this model, a branch-and-cut search scheme is applied to solve small-size instances and a linear programming rounding heuristic for large ones. We also devise a greedy approximation method, whose solution quality depends on the scale of the minimum quantity if the shipping cost forms a distance metric. Extensive experiments have been conducted to measure the performance of the formulations and the algorithms and have shown that the linear rounding heuristic behaves best. Moreover, we have also introduced the minimum quantity commitment constraint into the study of facility location problems, and have developed several approximation algorithms that provide constant performance guarantees.

Although the minimum quantity commitment provides volume guarantees to carriers, it is sometimes too restrictive for shippers to adopt, and cannot smooth the volume allocation for carriers. According to industrial practice, carriers, who operate in seasonal markets where differences in demand occur in peak and non-peak periods, often negotiate for some form of demand smoothing with the customer, i.e., the shipper. We therefore study a shipper's transportation procurement model in which the shipper gives assurances, through volume guarantees negotiated with the transportation companies, that shipments made in non-peak periods will be commensurate with shipments in peak periods. The shipper uses the model in an auction process, in which the transportation companies bid for routes giving prices and capacity limits, to procure freight services from the companies which minimize its total transportation costs. The model is formulated as an integer programming problem, which is shown to he strongly NP-hard even for a single-route network. We develop a solution approach which builds on the solution of the subproblem when only one transportation company is available to construct heuristic algorithms, including a linear programming relaxation-based method. Worst-case analysis is given and the effectiveness of the algorithms is tested in numerical experimentation. By examining parameter sensitivity, insight is provided on how the algorithms can be used by the shipper for making procurement decisions. The practical usefulness of the model and the solution approaches is substantiated by its deployment with a multinational shipper for its sea freight procurement.

Since most global shippers are large manufacturers, they have various business units all over the world. When purchasing transportation service from carriers, the central decision maker of the shipper needs to satisfy the preferences of different business units. We therefore study a service provider allocation problem for global shippers to procure transportation service with various preferences constrained by their business units all over the world. The problem has been formulated by a constraint programming model, and its hardness has been discussed extensively. In order to resolve the intractability, we propose a decomposition approach to structure the preference constraints, so that the model can be solved optimally under some conditions. We also illustrate how such conditions can be satisfied in practice. The model and solution approaches have been integrated into a decision support system for a multinational shipper to purchase its express courier service.