Models and algorithms for packing and transportation problems in logistics


Student thesis: Doctoral Thesis

View graph of relations


  • Qian HU

Related Research Unit(s)


Awarding Institution
Award date15 Jul 2014


Packing and transportation are very important processes in logistics. In the transportation market, manufacturers, distributors and companies that need to move freight are called shippers. Shippers are confronted with optimization problems in transportation planning and operations. In transportation planning, the shippers seek strategic solutions to allocate freight to carriers who provide transportation services. In transportation operations, shippers require executable solutions to pack their goods into cartons before being transferred to a carrier for shipping. Cartons with different weights are usually charged differently according to the cost structure provided by the carrier. Therefore, a good packing solution can reduce the total delivery cost. In this thesis, we study a class of packing and transportation problems faced by shipper in practice. Models and dedicated algorithms are developed to solve these problems. Extensive experiments show that the solutions obtained by our approaches considerably reduce transportation costs and secure better transportation services. Thus, our work can help to strengthen the competitiveness of shippers in their industries. Packing problems can be found in the area of transportation operations. For example, the two-dimensional vector packing problem with piecewise linear cost function (2DVPP-PLC) is a typical and practical packing problem faced by a manufacturer of children's apparel that ships products using courier service from a carrier. The manufacturer must ship a number of items using standard-sized cartons, where the cost of a carton is a piecewise linear function of its weight, which can be any monotonically increasing function. The objective is to pack all given items into a set of cartons such that the total delivery cost is minimized while observing the weight limitation and volume capacity of each carton. This problem is faced by many manufacturers that ship products using courier service. In our study, the 2DVPP-PLC is formulated into an integer programming model. Solving it directly using commercial solvers such as CPLEX is successful only for small instances. To provide exact solutions to the 2DVPP-PLC instances of practical size, we develop a branch-and-price algorithm. It is well known that the column generation procedure is a key component affecting the performance of a branch-and-price algorithm. Unlike the articles in the existing literature that prioritize preserving the convexity of the feasible region of the pricing problem, we opt to sacrifice the convexity for two practical considerations: efficiency of the LP solver and numerical stability of the overall algorithm. Although the convexity is sacrificed, the derived pricing problem exhibits an interesting structure that allows decomposing it into subproblems that form a lattice. We explore dominance relations on the lattice and design an efficient algorithm for the pricing problem. To the best of our knowledge, our branch-and-price algorithm is the first exact solution approach for this problem. Its competence is proven by experiments on numerous test instances generated based on real data provided by the manufacturer. The 2DVPP-PLC can be generalized to the two-dimensional vector packing problem with general costs (2DVPP-GC), where the delivery cost can be retrieved from a cost table. The cost table may not generate any special cost structure since it can specify an arbitrary amount of cost at each possible weight. Such generalized charging scheme meets the needs of more real-word applications since the price of delivery service is usually determined by many complex and correlated factors, i.e., the resultant cost table is usually not consistent with any known function. The 2DVPP-GC is more complex and challenging than the 2DVPPPLC. To solve the problem, we first propose a simple but very fast greedy heuristic to produce initial solutions. Subsequently, an iterative local search algorithm is developed to compute high-quality solutions. These two algorithms are evaluated through comparison experiments on the 2DVPP-GC test instances that are extended from the 2DVPP-PLC test instances. In transportation planning, transportation service procurement is an important business activity. In a transportation service procurement auction, a shipper announces its transportation requests and invites carriers to submit bids containing rates and capacities on their dedicated shipping lanes. The shipper then seeks solutions to determine the winner carriers and allocate the freight volume. Generally, solutions with minimal transportation cost are desirable. In addition, the shipper is most concerned with the transit time on the shipping lanes because it determines the service level and further affects the relationship with clients. Shorter transit time indicates better delivery service. To minimize both total transportation cost and overall transit time, the problem faced by the shipper is the biobjective transportation service procurement problem with transit time. We develop a biobjective integer programming model to solve the problem. This model includes several practical side constraints related to the minimum quantity commitments, the allowed minimum and maximum number of carriers, and the shipper's other preferences. A biobjective branch-and-bound algorithm that is capable of finding all extreme supported nondominated solutions is developed, and accelerating strategies for the algorithm are investigated. We generate a set of test instances based on practical data and conduct computational experiments to evaluate the performance of the algorithm.

    Research areas

  • Business logistics, Packing for shipment