An algorithm for the freight allocation problem with all-units quantity-based discount

Xiang Gao; Andrew Lim; Wee-Chong Oon; Hu Qin

doi:10.1007/978-3-642-21827-9_26

An algorithm for the freight allocation problem with all-units quantity-based discount

Xiang Gao
, Andrew Lim
, Wee-Chong Oon
, Hu Qin^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

This study is motivated by a project awarded by one of the largest international retail distributors in the world. An important task for the distributor is to plan the distribution of goods from Asia to various destinations across Europe. The goods are transported by shipping companies along shipping lanes, and these companies offer different discount rates depending on the freight quantity. The task involves purchasing freight capacity from shipping companies for each shipping lane based on projected demand, and subject to minimum quantity requirements, such that the total transportation cost is minimized. Existing work on this and related problems employs commercial linear programming software to solve their models. The problem is NP-hard, and is therefore unlikely to be solvable optimally in reasonable time for large instances. Hence, we propose a heuristic-based algorithm that combines a filter and fan search scheme with a tabu search mechanism for the problem. Experiments on randomly generated test instances show that our algorithm produces superior solutions in less computation time and requires less computer memory compared to ILOG CPLEX 11.0. © 2011 Springer-Verlag.

Original language	English
Title of host publication	Modern Approaches in Applied Intelligence
Subtitle of host publication	24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, USA, June 28 - July 1, 2011, Proceedings, Part II
Editors	Kishan G. Mehrotra, Chilukuri K. Mohan, Jae C. Oh, Pramod K. Varshney, Moonis Ali
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	256-265
Volume	Part II
ISBN (Electronic)	978-3-642-21827-9
ISBN (Print)	9783642218262
DOIs	https://doi.org/10.1007/978-3-642-21827-9_26
Publication status	Published - 2011
Event	24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011 - Syracuse, NY, United States Duration: 28 Jun 2011 → 1 Jul 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	6704
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011
Place	United States
City	Syracuse, NY
Period	28/06/11 → 1/07/11

Research Keywords

filter and fan
freight allocation
quantity discount
tabu search

Access Output

10.1007/978-3-642-21827-9_26

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Gao, X., Lim, A., Oon, W.-C., & Qin, H. (2011). An algorithm for the freight allocation problem with all-units quantity-based discount. In K. G. Mehrotra, C. K. Mohan, J. C. Oh, P. K. Varshney, & M. Ali (Eds.), Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, USA, June 28 - July 1, 2011, Proceedings, Part II (Vol. Part II, pp. 256-265). (Lecture Notes in Computer Science; Vol. 6704). Springer . https://doi.org/10.1007/978-3-642-21827-9_26

Gao, Xiang ; Lim, Andrew ; Oon, Wee-Chong et al. / An algorithm for the freight allocation problem with all-units quantity-based discount. Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, USA, June 28 - July 1, 2011, Proceedings, Part II. editor / Kishan G. Mehrotra ; Chilukuri K. Mohan ; Jae C. Oh ; Pramod K. Varshney ; Moonis Ali. Vol. Part II Berlin, Heidelberg : Springer , 2011. pp. 256-265 (Lecture Notes in Computer Science).

@inproceedings{49acb83922b94744b9ddde886fa91964,

title = "An algorithm for the freight allocation problem with all-units quantity-based discount",

abstract = "This study is motivated by a project awarded by one of the largest international retail distributors in the world. An important task for the distributor is to plan the distribution of goods from Asia to various destinations across Europe. The goods are transported by shipping companies along shipping lanes, and these companies offer different discount rates depending on the freight quantity. The task involves purchasing freight capacity from shipping companies for each shipping lane based on projected demand, and subject to minimum quantity requirements, such that the total transportation cost is minimized. Existing work on this and related problems employs commercial linear programming software to solve their models. The problem is NP-hard, and is therefore unlikely to be solvable optimally in reasonable time for large instances. Hence, we propose a heuristic-based algorithm that combines a filter and fan search scheme with a tabu search mechanism for the problem. Experiments on randomly generated test instances show that our algorithm produces superior solutions in less computation time and requires less computer memory compared to ILOG CPLEX 11.0. {\textcopyright} 2011 Springer-Verlag.",

keywords = "filter and fan, freight allocation, quantity discount, tabu search",

author = "Xiang Gao and Andrew Lim and Wee-Chong Oon and Hu Qin",

year = "2011",

doi = "10.1007/978-3-642-21827-9\_26",

language = "English",

isbn = "9783642218262",

volume = "Part II",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "256--265",

editor = "Mehrotra, \{Kishan G.\} and Mohan, \{Chilukuri K.\} and Oh, \{Jae C.\} and Varshney, \{Pramod K.\} and Moonis Ali",

booktitle = "Modern Approaches in Applied Intelligence",

note = "24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011 ; Conference date: 28-06-2011 Through 01-07-2011",

}

Gao, X, Lim, A, Oon, W-C & Qin, H 2011, An algorithm for the freight allocation problem with all-units quantity-based discount. in KG Mehrotra, CK Mohan, JC Oh, PK Varshney & M Ali (eds), Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, USA, June 28 - July 1, 2011, Proceedings, Part II. vol. Part II, Lecture Notes in Computer Science, vol. 6704, Springer , Berlin, Heidelberg, pp. 256-265, 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, United States, 28/06/11. https://doi.org/10.1007/978-3-642-21827-9_26

An algorithm for the freight allocation problem with all-units quantity-based discount. / Gao, Xiang; Lim, Andrew; Oon, Wee-Chong et al.
Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, USA, June 28 - July 1, 2011, Proceedings, Part II. ed. / Kishan G. Mehrotra; Chilukuri K. Mohan; Jae C. Oh; Pramod K. Varshney; Moonis Ali. Vol. Part II Berlin, Heidelberg: Springer , 2011. p. 256-265 (Lecture Notes in Computer Science; Vol. 6704).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An algorithm for the freight allocation problem with all-units quantity-based discount

AU - Gao, Xiang

AU - Lim, Andrew

AU - Oon, Wee-Chong

AU - Qin, Hu

PY - 2011

Y1 - 2011

N2 - This study is motivated by a project awarded by one of the largest international retail distributors in the world. An important task for the distributor is to plan the distribution of goods from Asia to various destinations across Europe. The goods are transported by shipping companies along shipping lanes, and these companies offer different discount rates depending on the freight quantity. The task involves purchasing freight capacity from shipping companies for each shipping lane based on projected demand, and subject to minimum quantity requirements, such that the total transportation cost is minimized. Existing work on this and related problems employs commercial linear programming software to solve their models. The problem is NP-hard, and is therefore unlikely to be solvable optimally in reasonable time for large instances. Hence, we propose a heuristic-based algorithm that combines a filter and fan search scheme with a tabu search mechanism for the problem. Experiments on randomly generated test instances show that our algorithm produces superior solutions in less computation time and requires less computer memory compared to ILOG CPLEX 11.0. © 2011 Springer-Verlag.

AB - This study is motivated by a project awarded by one of the largest international retail distributors in the world. An important task for the distributor is to plan the distribution of goods from Asia to various destinations across Europe. The goods are transported by shipping companies along shipping lanes, and these companies offer different discount rates depending on the freight quantity. The task involves purchasing freight capacity from shipping companies for each shipping lane based on projected demand, and subject to minimum quantity requirements, such that the total transportation cost is minimized. Existing work on this and related problems employs commercial linear programming software to solve their models. The problem is NP-hard, and is therefore unlikely to be solvable optimally in reasonable time for large instances. Hence, we propose a heuristic-based algorithm that combines a filter and fan search scheme with a tabu search mechanism for the problem. Experiments on randomly generated test instances show that our algorithm produces superior solutions in less computation time and requires less computer memory compared to ILOG CPLEX 11.0. © 2011 Springer-Verlag.

KW - filter and fan

KW - freight allocation

KW - quantity discount

KW - tabu search

UR - https://www.scopus.com/pages/publications/79960504379

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79960504379&origin=recordpage

U2 - 10.1007/978-3-642-21827-9_26

DO - 10.1007/978-3-642-21827-9_26

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783642218262

VL - Part II

T3 - Lecture Notes in Computer Science

SP - 256

EP - 265

BT - Modern Approaches in Applied Intelligence

A2 - Mehrotra, Kishan G.

A2 - Mohan, Chilukuri K.

A2 - Oh, Jae C.

A2 - Varshney, Pramod K.

A2 - Ali, Moonis

PB - Springer

CY - Berlin, Heidelberg

T2 - 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011

Y2 - 28 June 2011 through 1 July 2011

ER -

Gao X, Lim A, Oon WC, Qin H. An algorithm for the freight allocation problem with all-units quantity-based discount. In Mehrotra KG, Mohan CK, Oh JC, Varshney PK, Ali M, editors, Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, USA, June 28 - July 1, 2011, Proceedings, Part II. Vol. Part II. Berlin, Heidelberg: Springer . 2011. p. 256-265. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-21827-9_26

An algorithm for the freight allocation problem with all-units quantity-based discount

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this