مسئله تخصیص حمل و نقل با تمام واحد های مبتنی بر مقدار تخفیف: الگوریتم هیوریستیک

This paper studies a problem encountered by a buying office for one of the largest retail distributors in the world. An important task for the buying office is to plan the distribution of goods from Asia to various destinations across Europe. The goods are transported along shipping lanes by shipping companies, which offer different discount rates depending on the freight quantity. To increase the reliability of transportation, the shipper imposes a quantity limit on each shipping company on each shipping lane. To guarantee a minimum business volume, each shipping company requests a minimum total freight quantity over all lanes if it is contracted. The task involves allocating projected demand of each shipping lane to shipping companies subject to the above conditions such that the total cost is minimized. Existing work on this and related problems employs commercial linear programming software to solve their models. However, since the problem is NP−hardNP−hard in the strong sense, it is unlikely to be solvable optimally in reasonable time for large cases. Hence, we propose the first heuristic-based algorithm for the problem, which combines a filter-and-fan search scheme with a tabu search mechanism. Experiments on randomly generated test instances show that as the size of the problem increases, our algorithm produces superior solutions in less time compared to a leading mixed-integer programming solver.

This study is motivated by a project awarded by a Hong Kong-based buying office (henceforth referred to as the shipper) for one of the largest international retail corporations in the world with over 2000 outlets in Europe, Africa and Asia. The shipper annually procures diverse products, from textiles and food stuffs to major electrical appliances, from over one thousand suppliers across Asia to satisfy the demands of parent company's sales divisions that are distributed across Europe. Long-distance ocean shipping is the main transportation mode for the shipper for the delivery of the procured products, accounting for around 95% of its total annual turnover on average. Hence, the shipper maintains close relationships with most of the leading international shipping companies (henceforth referred to as the carriers), allowing the shipper to enter into long-term contracts with these carriers at discounted rates. The transportation network under the purview of the shipper comprises more than 1000 shipping lanes connecting 71 loading ports in Asia and 27 discharging ports in Europe. This paper examines the problem of allocating the freight quantity for all lanes to the carriers such that the total transportation cost is minimized. The shipper performs this freight allocation at the strategic level. At the beginning of every fiscal year, the shipper forecasts the total quantity of freight (demand) for the coming year on each lane, taking into account possible market fluctuations. Price quotes are collected from each carrier along with its discount information and minimum quantity commitment (MQC) [1]. The carrier offers discount rates to the shipper according to the total freight quantity it obtains across all lanes, and if it is contracted this total freight quantity must exceed its requested MQC. As a safeguard against the inability of a carrier to fulfill its contractual obligations due to unforeseen circumstances, the shipper also specifies a minimum number of carriers for each lane. We call this problem the freight allocation problem with all-units quantity-based discount (FAPAQD). While some research has been done on problems of this nature, in general they employ exact linear and integer programming solvers to produce optimal solutions on small instances. However, the problem is NP−hardNP−hard in the strong sense, and therefore such approaches are unlikely to be successful for the large and practical scenarios faced by the shipper. Consequently, we developed the first tailored heuristic for the FAPAQD, which makes use of the polynomial-time solvable min-cost network flow problem to generate solutions, and then uses a filter-and-fan search heuristic with tabu search to locate good solutions. In our problem, the discount rates offered by each carrier are expressed as discount intervals. If the discount interval adopted for each carrier is determined, the resultant model can be solved in polynomial-time. Thus, identifying the best discount interval to select for each carrier would allow us to find the optimal solution to this problem. Our approach is based on searching the space of combinations of discount intervals for the carriers. In this paper, we propose a filter-and-fan technique with tabu search (F&F) for this purpose; computational experiments on randomly generated instances of practical size show that our approach outperforms CPLEX 11.0 in terms of both solution quality and computation time. Note that other than the F&F, we have also investigated using a standard simulated annealing algorithm or tabu search algorithm with similar neighborhood structures and a variety of parameter settings, but preliminary experiments indicate that our F&F outperforms both these approaches. The rest of the paper is organized as follows. In Section 2, we provide an overview of existing research that considers the MQC constraint or discounts. We then describe the FAPAQD in detail in Section 3, where we explain the notations used in the remainder of the paper and formulate the problem as a mixed-integer programming (MIP) model. This is followed in Section 4 with a description of the F&F for this problem. Our experimental results are given in Section 5, and we conclude our paper in Section 6 with some closing remarks.

In this paper, we described a heuristic algorithm using a filter-and-fan technique with tabu search to solve the FAPAQD, which models a practical problem encountered by a buying office for a major international retailer. Experiments on data generated based on typical figures supplied by the buying office in question suggest that our algorithm outperforms the leading commercial MIP solver ILOG CPLEX 11.0 in terms of running time and solution quality, especially for large instances that reflect the scale of the practical problem. The heuristic approach was necessary because the FAPAQD is NP−hardNP−hard in the strong sense, and the problem instances faced by our client are too large to be optimally solved by commercial solvers in reasonable time. We presented the solutions generated by our algorithm to the managers and planners in charge of freight space procurement at the buying office. They found our approach interesting, and agreed that the generated solutions were logical and reasonable.