Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock

Binghai Zhou; Yuanrui Lei; Shi Zong

doi:10.3934/jimo.2021151

Article Contents

2022, Volume 18, Issue 6: 4129-4149. Doi: 10.3934/jimo.2021151

This issue Previous Article A new smoothing spectral conjugate gradient method for solving tensor complementarity problems Next Article Optimal pricing, ordering, and credit period policies for deteriorating products under order-linked trade credit

Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock

Institute of Industrial Engineering, School of Mechanical Engineering, Tongji University, Shanghai 201804, China

^* Corresponding author: Binghai Zhou
^* Corresponding author: Binghai Zhou

Received: November 30, 2020

Revised: May 31, 2021

Early access: September 2021

Published: September 2022

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

Abstract

Cross-docking is a kind of process that products are unloaded in front of the inbound doors, consolidated based on the downstream demand, and then directly transferred to the outbound doors without a long storage process during the transportation. In this paper, a multi-door cross-dock truck scheduling problem is investigated in which the scheduling and sequencing assignment of trucks need to be considered, with the objectives of minimizing the inner transportation cost in the cross-dock and the total truck waiting cost. The major contribution of this paper is that a novel product-related time window constraint and the temporary storage area are firstly introduced to adapt to different physical conditions of goods considering real-world requirements. Then, a Lagrangian relaxation algorithm is proposed which aims to decompose the relaxed problem into several easy-to-be-solved sub-problems. Besides, a subgradient algorithm is used at each iteration to further deal with these sub-problems. Finally, theory analysis and simulation experiments of different problem scales are carried out during the comparison with a Greedy algorithm to evaluate the performance of the proposed algorithm. Results indicate that the Lagrangian relaxation algorithm is able to achieve more satisfactory near-optimal solutions within an acceptable time.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C11.

Citation:

Full Text(HTML)

Figure 1. The scheduling process at cross-dock

Download: Full-size image PowerPoint slide

Figure 2. Several values of %gap (group2) based on the different value of slackness

Download: Full-size image PowerPoint slide

Figure 3. Values of %gap and %dev in group 2

Download: Full-size image PowerPoint slide

Table 1. Computer results for problems in group 1, b = 0.98, 0.95, and 0.90

			p=0.98						p=0.95						p=0.90
				L			G			L			G			L			G
I	#t×#d	s	IP	LR	%gap	CPU	UB	%dev	IP	LR	%gap	CPU	UB	%dev	IP	LR	%gap	CPU	UB	%dev
1		15	1.683	1.683	5.32	0.55	1.815	10.43	1.98	1.98	4.97	0.56	2.187	10.43	1.643	1.643	5.27	0.46	1.99	11.99
2		20	1.701	1.701	4.82	0.5	1.89	8.37	2.1	2.1	4.38	0.33	2.278	8.45	1.785	1.785	5.39	0.42	1.754	8.03
3	4×2	30	1.729	1.729	3.44	0.53	2.004	15.27	2.059	2.059	3.55	0.42	2.358	14.54	1.997	1.997	3.59	0.51	1.769	14.69
4		15	2.56	2.56	9.55	0.66	2.45	14.81	2.56	2.56	9.27	0.68	2.816	14.52	2.765	2.765	9.83	0.84	3.013	14.96
5		20	2.26	2.26	8.15	0.8	3.064	13.02	2.659	2.659	7.03	0.8	3.225	12.76	2.872	2.872	6.89	0.8	2.838	13.4
6	5×3	30	2.498	2.498	10.55	0.65	2.648	12.76	2.602	2.602	9.02	0.8	3.152	12.76	2.862	2.862	11	0.96	3.089	12.89
7		15	2.709	2.709	6.58	1.59	3.954	26.35	3.078	3.078	6.33	1.61	4.163	26.62	2.924	2.924	6.46	1.07	3.83	27.95
8		20	3.108	3.108	4.32	1.64	3.533	25	3.205	3.205	4.32	1.06	4.257	24.27	2.66	2.66	4.62	1.33	4.087	23.06
9	6×3	30	2.495	2.495	7.55	1.6	3.735	26.32	3.08	3.08	6.29	1.02	4.016	26.06	2.957	2.957	6.54	1.27	4.257	27.1
10		15	3.31	3.31	4.76	1.92	4.153	13.37	3.755	3.988	4.21	2.35	4.72	13.37	4.068	4.068	4.04	1.88	4.153	12.84
11		20	3.425	3.624	6.35	1.93	4.337	14.81	3.89	3.897	4.96	1.91	4.518	15.11	4.155	4.17	6.05	2.38	3.433	15.87
12	7×3	30	3.257	3.471	3.69	3.13	3.747	21.32	3.572	3.732	3.55	2.66	4.625	21.98	3.375	3.471	3.41	3.19	4.163	22.2
13		15	3.18	3.381	7.79	5.86	4.848	29.61	3.58	3.636	6.04	7.1	5.051	30.53	3.09	3.09	7.61	7.1	3.788	30.84
14		20	3.155	3.301	6.23	4.89	4.847	29.92	3.42	3.628	6.23	7.41	5.049	30.53	3.171	3.301	6.17	4.94	3.786	29
15	7×4	30	3.178	3.204	6.83	5.38	4.262	32.8	3.595	3.641	5.38	8.41	5.014	31.24	3.285	3.386	6.62	8.41	4.061	32.49
16		15	3.65	3.826	5.76	4.4	5.089	24.08	4.058	4.159	5.7	4.27	5.472	24.08	3.588	3.701	5.81	5.34	5.472	25.28
17		20	3.425	3.425	5.58	5.79	5.329	21.76	4.117	4.228	5.03	4.45	5.438	22.91	4.489	4.608	5.53	5.57	4.894	23.14
18	8×3	30	3.785	3.85	6.41	8.54	4.745	22.79	4.095	4.184	5.57	10.05	5.214	23.49	4.258	4.435	7.19	8.37	4.432	24.19
19		15	3.455	3.485	4.57	8.09	5.375	35.21	3.986	4.1	4.76	7.03	5.973	36.3	3.698	3.772	4.57	7.03	5.973	35.94
20		20	3.576	3.678	5.81	6.36	4.802	34.09	4.168	4.18	4.76	7.64	5.856	33.42	3.259	3.344	5.09	9.17	6.09	33.09
21	8×4	30	3.385	3.428	6.14	9.16	5.446	32.42	4.15	4.18	4.76	11.33	5.856	33.42	3.857	3.929	4.52	11.33	5.739	33.09
Instance is short for $i$, $t$ for trucks, $d$ for doors, $s$ for the slackness of temporary storage capacity (%), $L$ for the Lagrangian relaxation algorithm, $G$ for the Greedy algorithm. The value of $IP, LP$ and $UB$ is in $10^5$.

| Show Table

DownLoad: CSV

Table 2. Computer results for problems in group 2 (slackness = 10)

Instances	#trucks×#doors	Lagrangian relaxation algorithm			Greedy algorithm
		LR	%gap	CPU time	UB	%dev
1	9×3	4.759	5.21	18	5.965	18.8
2	9×4	4.856	5.28	19.76	6.382	24.5
3	9×5	4.661	4.38	30.13	6.8	39.5
4	10×3	5.527	5.25	42.36	6.876	14.43
5	10×4	5.595	4.76	15.57	7.014	21.56
6	10×5	5.055	5.75	44.57	7.609	43.35
7	11×5	6.017	7.86	77.65	8.618	31.41
8	11×6	5.997	9.09	80.49	9.149	38.69
9	15×6	8.223	9.09	177.84	12.43	37.39
10	15×7	8.21	7.42	124.02	13.09	47.64
11	20×10	10.89	9.91	265.06	20.73	71.41

| Show Table

DownLoad: CSV

Table 3. Computer results for problems in group 2 (slackness = 15)

Instances	#trucks×#doors	Lagrangian relaxation algorithm			Greedy algorithm
		LR	%gap	CPU time	UB	%dev
1	9×3	4.742	5.17	24.5	5.892	19.3
2	9×4	4.813	4.97	22.69	6.382	24.5
3	9×5	4.559	5.65	36.25	6.66	40.72
4	10×3	5.456	5.09	40.71	6.674	16.1
5	10×4	5.195	4.76	31.97	7.142	30.92
6	10×5	5.355	5.3	42.97	7.609	35.32
7	11×5	6.017	6.54	55.32	8.618	33.86
8	11×6	5.6	7.45	91.46	9.149	41.4
9	15×6	8.403	8.26	125.77	12.43	35.68
10	15×7	8.237	6.65	81.64	13.18	49.35
11	20×10	10.64	8.26	164.22	20.69	68.47

| Show Table

DownLoad: CSV

Table 4. Computer results for problems in group 2 (slackness = 20)

Instances	#trucks×#doors	Lagrangian relaxation algorithm			Greedy algorithm
		LR	%gap	CPU time	UB	%dev
1	9×3	5.035	4.53	18.16	6.003	13.12
2	9×4	4.764	5.32	27.23	6.173	29.83
3	9×5	4.758	6.02	26.69	6.899	34.3
4	10×3	5.466	4.92	29.03	6.674	16.1
5	10×4	5.087	5.56	27.07	7.142	32.45
6	10×5	5.075	4.9	40.41	7.609	42.79
7	11×5	6.037	7.41	62.67	8.618	32.18
8	11×6	5.777	7.41	62.09	9.139	46.64
9	15×6	8.012	7.41	133.29	12.4	36.94
10	15×7	8.045	5.82	159.65	13.22	45.71
11	20×10	10.85	7.41	226.27	20.73	66.9

| Show Table

DownLoad: CSV

Table 5. Computer results for problems in group 2 (slackness = 30)

Instances	#trucks×#doors	Lagrangian relaxation algorithm			Greedy algorithm
		LR	%gap	CPU time	UB	%dev
1	9×3	4.76	4.8	17.01	5.965	19.3
2	9×4	4.647	5.08	22.76	6.108	30.38
3	9×5	4.684	3.9	22.59	6.8	39.5
4	10×3	5.943	4.9	35.42	6.344	6.74
5	10×4	5.375	4.76	42.1	7.082	26.54
6	10×5	5.315	4.76	47.71	7.609	36.34
7	11×5	6.057	4.76	50.29	8.618	35.51
8	11×6	5.817	6.54	77.44	9.149	46.99
9	15×6	8.221	6.54	114.18	12.37	40.67
10	15×7	8.527	4.29	148.43	13.3	47.33
11	20×10	10.79	5.66	302.54	23.68	70.76

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Amini and R. Tavakkoli-Moghaddam, A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks, Computers & Industrial Engineering, 96 (2016), 180-191. doi: 10.1016/j.cie.2016.03.023.
[2]	H. Arbabi, M. M. Nasiri and A. Bozorgi-Amiri, A hub-and-spoke architecture for a parcel delivery system using the cross-docking distribution strategy, Eng. Optim., 53 (2021), 1593-1612. doi: 10.1080/0305215X.2020.1808973.
[3]	M. T. Assadi and M. Bagheri, Differential evolution and Population-based simulated annealing for truck scheduling problem in multiple door cross-docking systems, Computers & Industrial Engineering, 96 (2016), 149-161. doi: 10.1016/j.cie.2016.03.021.
[4]	P. Bodnar, R. de Koster and K. Azadeh, Scheduling trucks in a cross-dock with mixed service mode dock doors, Transportation Science, 51 (2017), 112-131. doi: 10.1287/trsc.2015.0612.
[5]	N. Boysen and M. Fliedner, Cross dock scheduling: Classification, literature review and research agenda, Omega, 38 (2010), 413-422. doi: 10.1016/j.omega.2009.10.008.
[6]	A. Chiarello, M. Gaudioso and M. Sammarra, Truck synchronization at single door cross-docking terminals, OR Spectrum, 40 (2018), 395-447. doi: 10.1007/s00291-018-0510-x.
[7]	H. Chen, C. Chu and J. M. Proth, An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method, IEEE Transactions on Robotics and Atomation, 14 (1998), 786-795. doi: 10.1109/70.720354.
[8]	J. Chen, K. Wang and Y. Huang, An integrated inbound logistics mode with intelligent scheduling of milk-run collection, drop and pull delivery and LNG vehicles, Journal of Intelligent Manufacturing, (2020), 1–9. doi: 10.1007/s10845-020-01637-3.
[9]	L. Chen, Y. Liu and A. Langevin, A multi-compartment vehicle routing problem in cold-chain distribution, Comput. Oper. Res., 111 (2019), 58-66. doi: 10.1016/j.cor.2019.06.001.
[10]	U. Clausen, D. Diekmann, M. Pöting and C. Schumacher, Operating parcel transshipment terminals: A combined simulation and optimization approach, Journal of Simulation, 11 (2017), 2-10. doi: 10.1057/s41273-016-0032-y.
[11]	H. Corsten, F. Becker and H. Salewski, Integrating truck and workforce scheduling in a cross-dock: Analysis of different workforce coordination policies, Journal of Business Economics, 90 (2020), 207-237.
[12]	C. Dong, Q. Li, B. Shen and X. Tong, Sustainability in supply chains with behavioral concerns, Sustainability, 11 (2019), 4051. doi: 10.3390/su11154051.
[13]	G. B. Fonseca, T. H. Nogueira and M. G. Ravetti, A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem, European J. Oper. Res., 275 (2019), 139-154. doi: 10.1016/j.ejor.2018.11.033.
[14]	T. Garai and H. Garg, Multi-objective linear fractional inventory model with possibility and necessity constraints under generalised intuitionistic fuzzy set environment, CAAI Transactions on Intelligence Technology, 4 (2019), 175-181.
[15]	M. Gaudioso, M. F. Monaco and M. Sammarra, A Lagrangian heuristics for the truck scheduling problem in multi-door, multi-product Cross-Docking with constant processing time, Omega, 101 (2021), 102255. doi: 10.1016/j.omega.2020.102255.
[16]	A. Golshahi-Roudbaneh, M. Hajiaghaei-Keshteli and M. M. Paydar, Developing a lower bound and strong heuristics for a truck scheduling problem in a cross-docking center, Knowledge-Based Systems, 129 (2017), 17-38. doi: 10.1016/j.knosys.2017.05.006.
[17]	O. Guemri, P. Nduwayo, R. Todosijević, S. Hanafi and F. Glover, Probabilistic tabu search for the cross-docking assignment problem, European J. Oper. Res., 277 (2019), 875–885., doi: 10.1016/j.ejor.2019.03.030.
[18]	A. Gunawan, A. T. Widjaja, P. Vansteenwegen and V. F. Yu, A matheuristic algorithm for solving the vehicle routing problem with cross-docking, International Conference on Learning and Intelligent Optimization Springer, (2020), 9–15. doi: 10.1007/978-3-030-53552-0_2.
[19]	A. Gutierrez, L. Dieulle, N. Labadie and N. Velasco, A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands, Comput. Oper. Res., 99 (2018), 135-147. doi: 10.1016/j.cor.2018.06.012.
[20]	A. L. Ladier and G. Alpan, Robust cross-dock scheduling with time windows, Computers & Industrial Engineering, 99 (2016), 16-28. doi: 10.1016/j.cie.2016.07.003.
[21]	A. L. Ladier and G. Alpan, Crossdock truck scheduling with time windows: Earliness, tardiness and storage policies, J. Intell. Manufacturing, 29 (2018), 569-583.
[22]	S. M. Mousavi and B. Vahdani, Cross-docking location selection in distribution systems: A new intuitionistic fuzzy hierarchical decision model, International J. Computational Intelligence Systems, 9 (2016), 91-109. doi: 10.1080/18756891.2016.1144156.
[23]	W. Nassief, I. Contreras and R. As'ad, A mixed-integer programming formulation and Lagrangean relaxation for the cross-dock door assignment problem, International Journal of Production Research, 54 (2016), 494-508. doi: 10.1080/00207543.2014.1003664.
[24]	W. Nassief, I. Contreras and B. Jaumard, A comparison of formulations and relaxations for cross-dock door assignment problems, Comput. Oper. Res., 94 (2018), 76–88., doi: 10.1016/j.cor.2018.01.022.
[25]	S. Niroomand, H. Garg and A. Mahmoodirad, An intuitionistic fuzzy two stage supply chain network design problem with multi-mode demand and multi-mode transportation, ISA transactions, 107 (2020), 117-133. doi: 10.1016/j.isatra.2020.07.033.
[26]	C. Serrano, X. Delorme and A. Dolgui, Scheduling of truck arrivals, truck departures and shop-floor operation in a cross-dock platform, based on trucks loading plans, International Journal of Production Economics, 194 (2017), 102-112. doi: 10.1016/j.ijpe.2017.09.008.
[27]	I. Seyedi, M. Hamedi and R. Tavakkoli-Moghaddam, Truck Scheduling in a Cross-Docking Terminal by Using Novel Robust Heuristics, International Journal of Engineering, 32 (2019), 296-305.
[28]	M. Shakeri, M. Y. H. Low, S. J. Turner and E. W. Lee, An efficient incremental evaluation function for optimizing truck scheduling in a resource-constrained crossdock using metaheuristics,, Expert Systems with Applications, 45 (2016), 172-184. doi: 10.1016/j.eswa.2015.09.041.
[29]	J. G. Urzúa-Morales, J. P. Sepulveda-Rojas, M. Alfaro, G. Fuertes, R. Ternero and M. Vargas, Logistic modeling of the last mile: Case study santiago, chile,, Sustainability, 12 (2020), 648. doi: 10.3390/su12020648.
[30]	B. Vahdani and S. Shahramfard, A truck scheduling problem at a cross-docking facility with mixed service mode dock doors, Engineering Computations, 12 (2019), 648.
[31]	R. H. Waliv, U. Mishra, H. Garg and H. P. Umap, A nonlinear programming approach to solve the stochastic multi-objective inventory model using the uncertain information, Arabian Journal for Science and Engineering, 45 (2020), 6963-6973. doi: 10.1007/s13369-020-04618-z.
[32]	Z. Yong-wu, A Quantity discount model for two-echelon supply chain coordination under stochastic demand, Systems Engineering-Theory & Practice, 7 (2006), 25-32.
[33]	B. H. Zhou and W. L. Liu, A modified column generation heuristic for hybrid flow shop multiple orders per job scheduling problem, International Journal of Manufacturing Technology and Management, 33 (2019), 88-113. doi: 10.1504/IJMTM.2019.100166.
[34]	B. H. Zhou, M. Yin and Z. Q. Lu, An improved Lagrangian relaxation heuristic for the scheduling problem of operating theatres, Computers & Industrial Engineering, 101 (2016), 490-503. doi: 10.1016/j.cie.2016.09.003.
[35]	W. Zhou and Y. H. JIN, Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem, Control Decis., 11 (2004), 1213-1217.
[36]	L. Zhu, X. Ren, C. Lee and Y. Zhang, Coordination contracts in a dual-channel supply chain with a risk-averse retailer, Sustainability, 9 (2017), 2148. doi: 10.3390/su9112148.