×

The freight allocation problem with lane cost balancing constraint. (English) Zbl 1244.90041

Summary: We consider a problem faced by a buying office for one of the largest retail distributors in the world. The buying office plans the distribution of goods from Asia to various destinations across Europe. The goods are transported along shipping lanes by shipping companies, many of which have collaborated to form strategic alliances; each lane must be serviced by a minimum number of companies belonging to a minimum number of alliances. The task involves purchasing freight capacity from shipping companies for each lane based on projected demand, and subject to minimum quantity requirements for each selected shipping company, such that the total transportation cost is minimized. In addition, the allocation must not assign an overly high proportion of freight to the more expensive shipping companies servicing any particular lane, which we call the lane cost balancing constraint.
This study is the first to consider the lane cost balancing constraint in the context of freight allocation. We formulate the freight allocation problem with this lane cost balancing constraint as a mixed integer programming model, and show that even finding a feasible solution to this problem is computationally intractable. Hence, in order to produce high-quality solutions in practice, we devised a meta-heuristic approach based on tabu search. Experiments show that our approach significantly outperforms the branch-and-cut approach of CPLEX 11.0 when the problem increases to practical size and the lane cost balancing constraint is tight. Our approach was developed into an application that is currently employed by decision-makers at the buying office in question.

MSC:

90B06 Transportation, logistics and supply chain management

Software:

Tabu search; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, R.; Ergun, Ö., Ship scheduling and network design for cargo routing in liner shipping, Transportation Science, 42, 2, 175-196 (2008)
[2] Bassok, Y.; Anupindi, R., Analysis of supply contracts with total minimum commitment, IIE Transactions, 29, 5, 373-381 (1997)
[3] Bassok, Y.; Anupindi, R., Analysis of supply contracts with commitments and flexibility, Naval Research Logistics, 55, 5, 459-477 (2008) · Zbl 1209.90014
[4] Caplice, C.; Sheffi, Y., Optimization-based procurement for transportation services, Journal of Business Logistics, 24, 2, 109-128 (2003)
[5] Caplice, C.; Sheffi, Y., Combinatorial auctions of truckload transportation, (Cramton, P.; Shoham, Y.; Steinberg, R., Combinatorial Auctions (2005), MIT Press: MIT Press Cambridge, MA), 539-572
[6] Chen, F. Y.; Krass, D., Analysis of supply contracts with minimum total order quantity commitments and nonstationary demands, European Journal of Operational Research, 131, 2, 309-323 (2001) · Zbl 0984.90002
[7] De Vries, S.; Vohra, R. V., Combinatorial auctions: a survey, Informs Journal on Computing, 15, 3, 284-309 (2003) · Zbl 1238.91003
[8] Elmaghraby, W.; Keskinocak, P., Combinatorial auctions in procurement, (Billington, C.; Harrison, T.; Lee, H.; Neale, J., The Practice of Supply Chain Management (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 245-258
[9] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA, USA · Zbl 0930.90083
[10] Goossens, D. R.; Maas, A. J.T.; Spieksma, F. C.R.; van de Klundert, J. J., Exact algorithms for procurement problems under a total quantity discount structure, European Journal of Operational Research, 178, 2, 603-626 (2007) · Zbl 1107.90043
[11] Guha, S., Meyerson, A., Munagala, K., 2000. Hierachical placement and network design problems. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 603-612.; Guha, S., Meyerson, A., Munagala, K., 2000. Hierachical placement and network design problems. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 603-612.
[12] Katz, P.; Sadrian, A.; Tendick, P., Telephone companies analyze price quotations with bellcore’s pdss software, Interfaces, 24, 1, 50-63 (1994)
[13] Ledyard, J. O.; Olson, M.; Porter, D.; Swanson, J. A.; Torma, D. P., The first use of a combined-value auction for transportation services, Interfaces, 32, 5, 4-12 (2002)
[14] Lian, Z.; Deshmukh, A., Analysis of supply contracts with quantity flexibility, European Journal of Operational Research, 196, 2, 526-533 (2009) · Zbl 1163.90336
[15] Lim, A.; Rodrigues, B.; Wang, F.; Xu, Z., k-center problems with minimum coverage, Theoretical Computer Science, 332, 1-3, 1-17 (2005) · Zbl 1070.68155
[16] Lim, A.; Rodrigues, B.; Xu, Z., Transportation procurement with seasonally varying shipper demand and volume guarantees, Operations Research, 56, 3, 758-771 (2008) · Zbl 1167.90382
[17] Lim, A.; Wang, F.; Xu, Z., A transportation problem with minimum quantity commitments, Transportation Science, 40, 1, 117-129 (2006)
[18] Lim, A.; Xu, Z., The bottleneck problem with minimum quantity commitments, Naval Research Logistics, 53, 1, 91-100 (2006) · Zbl 1112.90069
[19] Lim, A.; Xu, Z.; Wang, F., The bidding selection and assignment problem with minimum quantity commitment, Journal of the Operational Research Society, 59, 693-702 (2007) · Zbl 1156.90402
[20] Sadrian, A. A.; Yoon, Y. S., A procurement decision support system in business volume discount environments, Operations Research, 42, 1, 14-23 (1994)
[21] Sheffi, Y., Combinatorial auctions in the procurement of transportation services, Interfaces, 34, 4, 245-252 (2004)
[22] Song, D.; Panayides, P., A conceptual application of cooperative game theory to liner shipping strategic alliances, Maritime Policy and Management, 29, 3, 285-301 (2002)
[23] Song, J., Regan, A.C., 2003. An auction based collaborative carrier network. Working paper (UCI-ITS-LI-WP-03-6), Institute of Transportation Studies, University of California Irvine, Irvine, CA.; Song, J., Regan, A.C., 2003. An auction based collaborative carrier network. Working paper (UCI-ITS-LI-WP-03-6), Institute of Transportation Studies, University of California Irvine, Irvine, CA.
[24] Song, J.; Regan, A. C., Combinatorial auctions for transportation service procurement: the carrier perspective, Transportation Research Record: Journal of the Transportation Research Board, 1833, 40-46 (2004)
[25] Song, J.; Regan, A. C., Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts, Transportation Research Part B, 39, 10, 914-933 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.