Two-stage stochastic nonlinear winner determination for logistics service procurement auctions under quantity discounts

Xiaohu Qian; Mingqiang Yin; Xin Li; Qingyu Zhang

doi:10.3934/jimo.2022252

Article Contents

2023, Volume 19, Issue 10: 7072-7089. Doi: 10.3934/jimo.2022252

This issue Previous Article Next Article Bond portfolio optimization with long-range dependent credits

Two-stage stochastic nonlinear winner determination for logistics service procurement auctions under quantity discounts

1.
Research Institute of Business Analytics & Supply Chain Management, College of Management, Shenzhen University, Shenzhen 518060, China
2.
College of Information and Control Engineering, Liaoning Petrochemical University, Fushun, Liaoning 113001, China
3.
Department of Mathematics and Information Technology, The Education University of Hong Kong, Hong Kong, China

^*Corresponding author: Mingqiang Yin
^*Corresponding author: Mingqiang Yin

Received: January 2022

Revised: September 2022

Early access: December 2022

Published: October 2023

This work has been sponsored by NSFC Grant #71801157; Foundation of Shenzhen Science and Technology Program Grant #20220810100345001, #JCYJ202103240932080; National Social Science Foundation of China Grant #21AGL014; Guangdong NSF Grant #2021A1515011894; and Guangdong 13th-Five-Year-Plan Philosophical and Social Science Fund Grant #GD20CGL28.

Abstract / Introduction Full Text(HTML) Figure(3) / Table(6) Related Papers Cited by

Abstract

Quantity discount is a frequently adopted scheme that has not been explicitly investigated in logistics service procurement auctions. This paper focuses on a revised winner determination problem under quantity discounts and demand uncertainty for a fourth-party logistics (4PL) provider in a combinatorial reverse auction. To characterize our research problem, a two-stage stochastic nonlinear programming model is constructed. Inspired by the idea of sample average approximation (SAA), the nonlinear model is reformulated as a deterministic mixed integer linear programming model by using a linearization technique with superior expressions. Since the reformulation has a large number of decision variables and constraints, we integrate SAA with a dual decomposition Lagrangian relaxation technique (DDLR) to develop a solution method called SAA-DDLR. Numerical experiments are conducted to illustrate the effectiveness and applicability of our model and method. Sensitivity analysis reveals that both the 4PL and 3PLs can benefit from the quantity discount scheme. Managerial insights are drawn for the 4PL to run a cost-effective logistics system in the presence of quantity discounts.

Keywords:

Mathematics Subject Classification: Primary: 90B06, 90C15; Secondary: 68W25.

Citation:

Full Text(HTML)

Figure 1. The CRA process of a 4PL via a logistics platform

Download: Full-size image PowerPoint slide

Figure 2. The impact of $ CV $ on 3PLs' revenues

Download: Full-size image PowerPoint slide

Figure 3. The impact of $ N_{\min} $ and $ N_{\max} $ on 3PLs' revenues

Download: Full-size image PowerPoint slide

Table 1. The summary of notations

Sets
$ I $	set of lanes
$ J $	set of 3PLs
$ K_j $	set of packages submitted by 3PL $ j $
$ S $	set of uncertain scenarios
Parameters
$ \xi_{i} $	uncertain demand of shipment volume on lane $ i $
$ N_{\min} $	minimum number of winning 3PLs specified by 4PL
$ N_{\max} $	maximum number of winning 3PLs specified by 4PL, $ N_{\max} \geq N_{\min} $
$ LS_{jk} $	minimum shipment volume of 3PL $ j $ on package $ k $
$ US_{jk} $	maximum shipment volume of 3PL $ j $ on package $ k $
$ e_i $	unit outside cost for shipping freights on lane $ i $ by other 3PLs
$ b_{jk} $	bid price of shipping 1 unit of demand quoted by 3PL $ j $ on package $ k $
$ a_{ijk} $	1 if lane $ i $ is included in 3PL $ j $'s package $ k $, and 0 otherwise
$ d_{iw} $	demand of shipment volume on lane $ i $ under scenario $ w \in S $
$ v_{j} $	transaction cost related to 3PL $ j $
Decision variables
$ y_{jk} $	shipment volume assigned to 3PL $ j $ on package $ k $
$ p_{jk} $	1 if 3PL $ j $'s package $ k $ wins the auction, and 0 otherwise
$ \varphi_{i} $	shipment volume on lane $ i $ assigned to other 3PLs out of CRA

| Show Table

DownLoad: CSV

Table 2. Performance of SAA-DDLR for different problems

$e_i$	Small-scale problems				Medium-scale problems				Large-scale problems
	CPLEX		SAA-DDLR		CPLEX		SAA-DDLR		CPLEX		SAA-DDLR
	CPLEX		SAA-DDLR		CPLEX		SAA-DDLR		CPLEX		Upper bound		Low bound		Gap			Time (s)
	TC	Time (s)	TC	Time (s)	TC	Time (s)	TC	Time (s)	TC	Time (s)	TC (avg.)	std.	TC (avg.)	std.	avg.	std.	Max(%)	Time (s)
100	171700	109	171700	59	635935	29278	635935	2901	NA	NA	40944354	4829	40880426	801	63928	4895	0.18	3616
150	197182	1468	197182	822	681755	33512	681755	3456	NA	NA	41813999	6453	41731699	1040	82300	6536	0.22	6268
200	201707	1482	201707	897	704696	74022	704696	4929	NA	NA	42375911	7646	42266304	1113	109607	7727	0.29	7081
300	202660	1247	202660	941	720490	75249	720703	8289	NA	NA	43227780	10485	42994511	1537	233269	10597	0.58	6613
500	203542	1444	203542	959	725943	93081	727184	8895	NA	NA	44284222	13944	43951873	3030	332349	14270	0.80	5847

| Show Table

DownLoad: CSV

Table 3. Results of SAA-DDLR under different discounts and $ CV $s

CV	$ e_i $	Large$ ^* $		Small$ ^* $		No$ ^* $
CV	$ e_i $	TC	OC	TC	OC	TC	OC
0.10	100	570146	77869	718563	94353	851095	150080
	150	592303	57796	752952	64913	890678	100780
	200	610902	29658	774338	84544	913478	60420
	300	625731	44487	800306	51034	936512	30984
	500	630370	0	807990	652	943188	6784
0.29	100	635935	154880	777393	206830	899721	231050
	150	681755	85072	858079	148910	993020	262330
	200	704696	65641	891102	113430	1050868	148810
	300	720703	11289	927948	42813	1095192	58462
	500	727184	16319	941930	18815	1110862	21681
0.48	100	711495	235370	847148	280600	967307	373700
	150	784838	104850	968396	276860	1107871	404140
	200	821074	87554	1026127	139800	1197159	223080
	300	831696	29084	1076190	29084	1265924	101890
	500	842965	26030	1090704	31941	1292423	22447
^*“Small” indicates that the discount percentage is small. “Large” indicates that the discount percentage is large. “No” indicates that the discount policy is absent.

| Show Table

DownLoad: CSV

Table 4. Comparison analysis with the EVP model

$ CV $	$ e_i $	Large		Small		No
$ CV $	$ e_i $	TC-EVP	GAP	TC-EVP	GAP	TC-EVP	GAP
0.1	100	570146	0	718563	0	853257	2162
	150	592303	0	752952	0	892582	1904
	200	611854	952	774338	0	919980	6502
	300	628865	3134	800306	0	956195	19683
	500	646673	16302	816947	8957	988468	45280
0.29	100	640176	4241	780353	2960	916108	16386
	150	690916	9162	858079	0	1014682	21662
	200	725487	20791	905826	14724	1092516	41649
	300	778852	58150	963726	35778	1220591	125400
	500	849565	122380	1033421	91491	1412704	301841
0.48	100	719822	8327	854017	6869	990430	23124
	150	808026	23188	978127	9730	1146772	38902
	200	861934	40861	1061857	35729	1276379	79220
	300	967840	136145	1162982	86791	1502996	237072
	500	1138397	295432	1332713	242009	1886639	594216

| Show Table

DownLoad: CSV

Table 5. The impact of $ N_{\min} $ and $ N_{\max} $ on the total cost

	$ N_{\min}=0, N_{\max}=10 $					$ N_{\min}=20, N_{\max}=40 $
	100	150	200	300	500	100	150	200	300	500
Large	570834	605166	628896	677022	763169	645659	656289	657062	657062	657062
Small	718563	759572	793251	841977	931730	789182	810858	819950	821883	822363
No	851095	897258	933603	994752	1082627	901511	931529	946081	952939	954209

| Show Table

DownLoad: CSV

Table 6. Results of total cost and the number of selected packages under different discount policies

$ N_{\min} $	$ N_{\max} $	$ e_i $	Problem A			Problem B					Original problem
$ N_{\min} $	$ N_{\max} $	$ e_i $	TC	$ [FS^1, FS^4) $	$ [FS^4, FS^5] $	TC	$ [FS^1, FS^2) $	$ [FS^2, FS^3) $	$ [FS^3, FS^4) $	$ [FS^4, FS^5) $	TC	$ [FS^1, FS^2) $	$ [FS^2, FS^3) $	$ [FS^3, FS^4) $	$ [FS^4, FS^5) $
0	10	100	570834	0	10	570834	0	0	0	10	570834	0	0	0	10
		150	605167	0	10	605167	0	0	0	10	605166	0	0	0	10
		200	628896	0	10	628896	0	0	0	10	628896	0	0	0	10
		300	677022	0	10	677022	0	0	0	10	677022	0	0	0	10
		500	763169	0	10	763169	0	0	0	10	763169	0	0	0	10
20	40	100	650638	9	11	642172	6	4	2	8	645659	6	4	0	10
		150	662443	6	14	653019	2	6	4	8	656289	6	4	1	9
		200	662869	6	14	653203	2	6	4	8	657062	2	8	1	9
		300	663026	6	14	655164	3	3	6	8	657062	2	8	1	9
		500	663187	6	14	655264	3	3	6	8	657062	2	8	1	9
0	40	100	570146	0	11	570146	0	0	0	11	570146	0	0	0	11
		150	592303	0	11	591957	0	0	1	10	592303	0	0	0	11
		200	610902	0	14	608633	0	0	3	11	610902	0	0	0	14
		300	625731	0	14	623512	0	0	3	11	625731	0	0	0	14
		500	632659	2	14	628251	0	3	3	11	630370	0	3	0	14

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Ağrali, B. Tan and F. Karaesmen, Modeling and analysis of an auction-based logistics market, European J. Oper. Res., 191 (2008), 272-294. doi: 10.1016/j.ejor.2007.08.018.
[2]	J. Asker and E. Cantillon, Procurement when price and quality matter, Rand. J. Econ, 41 (2010), 1-34.
[3]	M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, New York-Chichester-Brisbane, 1979.
[4]	C. C. Carøe and R. Schultz, Dual decomposition in stochastic integer programming, Oper. Res. Lett., 24 (1999), 37-45. doi: 10.1016/S0167-6377(98)00050-9.
[5]	A. Engin and R. Vetschera, Optimistic overconfidence in electronic reverse auctions, Electronic Commerce Research and Applications, 35 (2019), 100842.
[6]	S. D. Handoko, H. C. Lau and S. Cheng, Achieving economic and environmental sustainabilities in urban consolidation center with bicriteria auction, IEEE Transactions on Automation Science and Engineering, 13 (2016), 1471-1479.
[7]	Q. Hu, Z. Zhang and A. Lim, Transportation service procurement problem with transit time, Transportation Research Part B: Methodological, 86 (2016), 19-36.
[8]	M. Huang, X. Qian, S.-C. Fang and X. Wang, Winner determination for risk aversion buyers in multi-attribute reverse auction, Omega, 59 (2016), 184-200.
[9]	M. Huang, J. Tu, X. Chao and D. Jin, Quality risk in logistics outsourcing: A fourth party logistics perspective, European J. Oper. Res., 276 (2019), 855-879. doi: 10.1016/j.ejor.2019.01.049.
[10]	P. Karaenke, M. Bichler and S. Minner, Coordination is hard: Electronic auction mechanisms for increased efficiency in transportation logistics, Management Science, 65 (2019), 5884-5900.
[11]	A. J. Kleywegt, A. Shapiro and T. Homemdemello, The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12 (2001), 479-502. doi: 10.1137/S1052623499363220.
[12]	J. O. Ledyard, M. Olson, D. Porter, J. A. Swanson and D. P. Torma, The first use of a combined-value auction for transportation services, Interfaces, 32 (2002), 4-12.
[13]	R. Liang, J. Wang, M. Huang and Z. Jiang, Truthful auctions for e-market logistics services procurement with quantity discounts, Transportation Research Part B: Methodological, 133 (2020), 165-180.
[14]	Z. Ma, R. H. Kwon and C. Lee, A stochastic programming winner determination model for truckload procurement under shipment uncertainty, Transportation Research Part E: Logistics and Transportation Review, 46 (2010), 49-60.
[15]	Q. Meng, T. Wang and S. Wang, Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand, European J. Oper. Res., 223 (2012), 96-105. doi: 10.1016/j.ejor.2012.06.025.
[16]	V. I. Norkin, Y. Ermoliev and A. Ruszczyński, On optimal allocation of indivisibles under uncertainty, Operations Research, 46 (1998), 381-395.
[17]	X. Qian, F. T. Chan, M. Yin, Q. Zhang, M. Huang and X. Fu, A two-stage stochastic winner determination model integrating a hybrid mitigation strategy for transportation service procurement auctions, Computers & Industrial Engineering, 149 (2020), 106703.
[18]	X. Qian, S.-C. Fang, M. Yin, M. Huang and X. Li, Selecting green third party logistics providers for a loss-averse fourth party logistics provider in a multiattribute reverse auction, Inform. Sci., 548 (2021), 357-377. doi: 10.1016/j.ins.2020.09.011.
[19]	X. Qian, M. Huang, W.-K. Ching, L. H. Lee and X. Wang, Mechanism design in project procurement auctions with cost uncertainty and failure risk, J. Ind. Manag. Optim., 15 (2019), 131-157. doi: 10.3934/jimo.2018036.
[20]	X. Qian, M. Yin, F. T. Chan, J. Zhang and M. Huang, Sustainable-responsive winner determination for transportation service procurement auctions under accidental disruptions, J. Cleaner Production, 320 (2021), 128833.
[21]	M. Rekik and S. Mellouli, Reputation-based winner determination problem for combinatorial transportation procurement auctions, J. the Operational Research Society, 63 (2012), 1400-1409.
[22]	N. Remli, A. Amrouss, I. E. Hallaoui and M. Rekik, A robust optimization approach for the winner determination problem with uncertainty on shipment volumes and carriers' capacity, Transportation Research Part B: Methodological, 123 (2019), 127-148.
[23]	N. Remli and M. Rekik, A robust winner determination problem for combinatorial transportation auctions under uncertain shipment volumes, Transportation Research Part C: Emerging Technologies, 35 (2013), 204-217.
[24]	V. Robu, H. Noot, H. La Poutre and W. Van Schijndel, A multi-agent platform for auction-based allocation of loads in transportation logistics, Expert Systems With Applications, 38 (2011), 3483-3491.
[25]	P. Schutz, A. Tomasgard and S. Ahmed, Supply chain design under uncertainty using sample average approximation and dual decomposition, European J. Operational Research, 199 (2009), 409-419.
[26]	Y. Sheffi, Combinatorial auctions in the procurement of transportation services, Interfaces, 34 (2004), 245-252.
[27]	C. Triki, S. Mirmohammadsadeghi and S. Piya, Heuristic methods for the periodic Shipper Lane Selection Problem in transportation auctions, Computers & Industrial Engineering, 106 (2017), 182-191.
[28]	D. Wang, X. Liu and L. Liu, Bid evaluation behavior in online procurement auctions involving technical and business experts, Electronic Commerce Research and Applications, 12 (2013), 328-336.
[29]	F. Yang and Y. Huang, Linearization technique with superior expressions for centralized planning problem with discount policy, Phys. A, 542 (2020), 122746. doi: 10.1016/j.physa.2019.122746.
[30]	F. Yang, Y. Huang and J. Li, Alternative solution algorithm for winner determination problem with quantity discount of transportation service procurement, Phys. A, 535 (2019), 122286. doi: 10.1016/j.physa.2019.122286.
[31]	M. Yin, X. Qian, M. Huang and Q. Zhang, Winner determination for logistics service procurement auctions under disruption risks and quantity discounts, Engineering Applications of Artificial Intelligence, 105 (2021), 104424.
[32]	B. Zhang, H. Ding, H. Li, W. Wang and T. Yao, A sampling-based stochastic winner determination model for truckload service procurement, Netw. Spat. Econ., 14 (2014), 159-181. doi: 10.1007/s11067-013-9214-6.
[33]	B. Zhang, T. Yao, T. L. Friesz and Y. Sun, A tractable two-stage robust winner determination model for truckload service procurement via combinatorial auctions, Transportation Research Part B: Methodological, 78 (2015), 16-31.