Scheduling Compound Trucks with Various Arrival Times in A Multi-Door Cross-Docking SystemAbtahiZeinabDepartment of Mechanical and Polymer Engineering, Lorestan University, Lorestan, Iran.
In this study, we are exploring the scheduling of the compound truck in the context of cross-docking while the arrival times of the trucks coming and going to the cross-docking center are different. The main goal is to assign the trucks to the doors at the dock and determine the appropriate sequence for them. This study proposes a mixed integer mathematical model to address these issues in multi-door cross-docking centers. Due to the NP-hard structure of the related problem, the proposed model in a small size was solved using CPLEX 12.1. According to the literature, the Simulated Annealing (SA) algorithm provides an effective solution for a short time in parallel machine scheduling problems. Due to the similarity of the parallel machine scheduling problems with the considered problem, SA was proposed to solve the model in large sizes. The primary goal is to maximize shipping efficiency and productivity during a given working period. Various test problems are generated and compared to evaluate the effectiveness of the proposed solution.
Cross-docking is one of the most innovative strategies to improve operational performance in a distribution network. Using the cross-docking system, products are delivered via inbound trucks to distribution centers, sorted at the center, reassembled according to customer demands, and loaded onto outbound trucks for delivery to customers. In this way, there is no need to keep stocks in distribution centers [1]. Scheduling is an important activity within the scope of logistics activities of businesses, and efficient use of resources in cross-docking centers depends on good scheduling. One of the most vital operational management problems in multi-door cross-docking centers is the truck scheduling. This problem involves assigning the trucks to and from the cross-docking center to the doors and determining the truck queue at each door. Cross-docking centers mainly seek efficient unloading and loading of inbound and outbound trucks. When the order volume increases, product delivery cannot be controlled, and the increase in the number of products in the center requires the correct management of the cross-docking center. Maximizing the number of products loaded in a given working time is the main objective of the truck scheduling problem. In addition, in the truck scheduling problem, it is necessary not only to assign the trucks to the doors and determine their order, but also to make the product assignments that will determine which outgoing truck should be loaded with the products unloaded from the incoming trucks. In real-life problems, the arrival times of the trucks coming and going to the cross-docking center are different. Therefore, in this study, the arrival times of inbound and outbound trucks at the cross-docking center are considered separately. This study proposes a mathematical model for the truck scheduling problem in multi-door cross-docking centers by considering different arrival times for compound trucks apart from inbound and outbound trucks. Since the related problem has an NP-hard problem structure, the SA algorithm was exploited, and its performance was compared with the results of the mathematical model in small-sized problems. The remaining parts of the work are arranged as follows. In the third part, the truck scheduling problem in cross-docking is explained, in the fourth part, the solution to the problem is mentioned, and in the fifth part, the results and suggestions are given.
Literature Review
McWilliams [2] address the short-run truck scheduling problem. In their study, a postal service center was considered to minimize the operation time for the transfer of products, and a simulation-based algorithm using Genetic Algorithm (GA) was proposed. A mathematical model was proposed by Arabani et al. [3] to minimize the total operation time to determine the best schedule for all inbound and outbound trucks. Theophilus et al. [4] reviewed studies on the truck scheduling problem in three main groups. The first group was related to truck scheduling in cross-docking centers dealing with one reception and one transport door [3–11], and the second group, to the scheduling of incoming or outgoing trucks in multi-door cross-docking centers [2], [12–16]. In the last group, some studies schedule incoming and outgoing trucks in multi-door cross-docking centers. Yang et al. [17] proposed a dynamic programming method and a Simulated Annealing (SA) algorithm for solving the truck scheduling problem in the cross-docking center. Yu et al. [1] proposed a mixed integer programming model for assigning trucks to doors and determining their order at the doors. In their studies, GA was employed to maximize the number of products loaded in a given run time. Joo and Kim [18] examined the truck scheduling problem by considering three different truck groups (inbound trucks, outbound trucks, and inbound-outbound trucks). This truck cluster, which functions as both an inbound and outbound truck, has been addressed for the first time by researchers. GA and Self-Evolution (SE) algorithms are employed to minimize the maximum completion time in solving the truck scheduling problem. Rijal et al. [19] used two different Tabu Search algorithms in solving large-sized problems by addressing the scheduling of inbound and outbound trucks in a multi-door cross-docking center. Shahmardan and Sajadieh [20] aimed to minimize the total operation time by scheduling inbound and outbound trucks in a multi-door cross-docking center. The Variable Neighborhood Search method and four different SA-based algorithms are proposed to solve the problem. Theophilus et al. [4] proposed the Particle Swarm Optimization (PSO) algorithm for scheduling inbound and outbound trucks in a multi-door cross-docking center to minimize overall operation time. Within the scope of this study, incoming and outgoing trucks are assigned to the receiving and shipping gates in multi-door cross-docking centers, and incoming and outgoing trucks are lined up at the gates. An important factor affecting the assignment and scheduling of trucks to the correct door is the arrival time of the trucks at the cross-docking center. In real life, apart from inbound and outbound trucks, the third relevant set of trucks is trucks of both inbound and outbound nature. Following Joo and Kim [18] considered inbound-outbound trucks, in this research, trucks are responsible for delivering products to cross-docking, and also in distribution centers are called compound trucks, apart from inbound and outbound trucks. Yang et al. [17], Yu et al. [1], and Joo and Kim [18] considered the arrival time of trucks at the cross-docking center to be the same in a multi-door cross-docking center. However, in real-life problems, the arrival times of the trucks coming and going to the cross-docking center are different. Therefore, in this study, the arrival times of inbound and outbound trucks at the cross-docking center are considered separately. A mathematical model is proposed for the truck scheduling problem in multi-door cross-docking centers by considering different arrival times for compound trucks apart from inbound and outbound trucks. Since the related problem has an NP-hard problem structure, the solution time also increases by increasing the size of the problem increases, and the need for meta-heuristic solution approaches arises [21]. For this purpose, the SA algorithm was coded, and its performance was compared with the results of the mathematical model in small-sized problems.
Problem Definition and Model ConstructionDefining the Problem
In this study, all trucks arrive at the cross-docking center at different times, and their arrival times are known. Inbound and outbound trucks are available at the beginning of the planning period. Each door is dedicated to unloading or loading operations only. The time required to unload or load each unit of goods, regardless of its type, is fixed and specified. Incoming and outgoing trucks contain different products, and products reaching the cross-docking center with incoming trucks are unloaded at the acceptance gates. Unloaded products are sorted and combined to be loaded on outgoing trucks, and products are loaded on outgoing trucks at the shipping gates to be sent to their respective destinations. The products that need to be loaded on the outgoing trucks and the products inside the incoming trucks are known. Incoming trucks perform the unloading process at the door to which they are assigned and leave the acceptance door as soon as this process is completed. Outgoing trucks perform the loading process at the assigned door in order and leave the door as soon as the process is finished. Combined trucks are directed to the shipment area to load new products after unloading at the acceptance gate they are assigned. Standard pallets or boxes are used during the loading and unloading operations of the products. Therefore, regardless of the product type, the loading or unloading time is for all products. During the unloading and loading operations, the order of the products in the vehicle was ignored. Some products are temporarily held in the center until the truck to be loaded arrives at the cross-docking center and is ready in line. The unit product transfer time (from the acceptance gate to the shipping gate) is assumed to be the same for all products. The truck change time (the time it takes for one truck to leave the queue and get the other truck in line) is assumed to be the same for all trucks. The truck changeover time is divided into two. The respective times are the time it takes for one truck to get in the queue and the time it takes for the other truck to get out of the queue. Each incoming or outgoing truck can only unload or load one unit of goods at a time. It is not possible to unload or load several units simultaneously. Interruption in unloading and loading operations is not allowed. Temporary storage is permitted and has infinite capacity. Materials are replaceable. In other words, the goods needed by each outgoing truck can be supplied from any of the incoming trucks.
Parameters
Set of arriving trucks.
Outbound truck set.
Set of inbound-outbound trucks.
Set of inbound-outbound trucks.
Product type set.
Set of acceptance gates.
The amount of product type k contained in the incoming truck i.
The amount of product type k needs to be loaded on the outgoing truck j.
ALi Arrival time of the inbound truck i at the cross-docking center.
ADj Arrival time of the outbound truck j at the cross-docking center.
TC Truck change time.
UL Unit product unloading time.
UT Unit product loading time.
The amount of product type k contained in the incoming truck i.
The amount of product type k needs to be loaded on the outgoing truck j.
ALi Arrival time of the inbound truck i at the cross-docking center.
ADj Arrival time of the outbound truck j at the cross-docking center.
TC Truck change time.
UL Unit product unloading time.
TF Transition time from the acceptance area to the shipment area for inbound and outbound trucks.
ET The time it takes for a truck to approach the door.
LT The time it takes for a truck to leave the door.
N The time spent until the products go from the acceptance gate to the shipment gate. W Working time interval.
Indices
When the unloading of the ith incoming truck starts.
When the unloading of the ith incoming truck is finished.
When the loading of the jth outgoing truck is started.
When the loading of the jth outgoing truck is finished.
The amount of the kth product type transferred from the ith inbound truck to the jth outbound truck.
are integer variables. is 1 if the product is transferred from the truck to the truck. is one if the truck arrives after truck at the shipping door. is one if the The incoming truck is assigned to the Receiving door. is one of the The outgoing truck is assigned to the Receiving door. is one of the products that need to be loaded on the outgoing trucks are loaded within the time window.
Mathematical Model
According to Boysen and Fliedner's [22] definition, the truck scheduling problem is expressed with the notation:
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
The Objective Function (2) maximizes the number of products loaded in a given run time. The Constraint (3) determines the trucks loaded until the end of the working period. Constraints (4) and (5) determine the priority relationship for incoming trucks assigned to the same door. The Constraints (6) and (7) determine the priority relationship for outgoing trucks assigned to the same gate. The Constraints (8) and (9) ensure that the inbound and outbound trucks (if these trucks are to be unloaded or loaded in the first place at the acceptance and shipment gates) start the unloading and loading process longer than their arrival time at the cross-docking center. The Constraint (10) connects the time when the inbound truck leaves the acceptance gate with the time when the outgoing truck enters the shipping gate, if product transfer is taking place between both trucks. The Constraint (11) ensures that each incoming truck is assigned to only one acceptance gate. The Constraint (12) ensures that only one truck is placed at the beginning of the queue at each admission gate. In this constraint, a decision variable is used. If the incoming truck is in the first row at the assigned door, it takes the value "1". Constraint (13) specifies that if an inbound truck is assigned to a door, that truck precedes another truck. Constraint (14) indicates that if an inbound truck is assigned to a door, it follows at most one truck. Constraint (15) ensures that each outbound truck is assigned to only one shipping port. The Constraint (16) ensures that only one truck is placed at the beginning of the queue at each shipping door. In this constraint, a decision variable is used. If the outgoing truck is in the first row at the assigned gate, it takes the value "1". The Constraint (17) specifies that if an outbound truck is assigned to a door, that truck precedes another truck. The Constraint (18) specifies that if an outbound truck is assigned to a door, it follows at most one truck. There will be no other trucks after the last outbound truck in the queue. The Constraint (19) ensures that the amount transferred from the product type k to the outgoing truck j from the incoming trucks is equal to the amount of product type k that needs to be loaded on the outgoing truck j. Similarly, the Constraint (20) ensures that the amount transferred from all incoming trucks to outgoing trucks of the product type k of all outgoing trucks is equal to its need for the product type. The Constraint (21) provides the relationship between and ℎ decision variables. The Constraint (22) connects the time of inbound and outbound trucks to the time to complete the unloading at the reception area and the time to start the loading at the shipment area. Constraints (23)-(30) satisfy the conditions of being an integer and being positive.
Solution Method
The truck scheduling problem in multi-door cross-docking centers has an NP-hard problem structure, i.e., the solution time increases with problem size, so meta-heuristic solution approaches are widely used [21]. The truck scheduling problem multi-door cross-docking problem, is similar to the parallel machine scheduling [23]. It has been shown that the SA algorithm provides effective solutions in a short time for the truck scheduling multi-door cross-docking problem [23]. So, SA was chosen in the study and is coded with R2023a Matlab. The mixed-integer mathematical model of the specified truck scheduling problem is solved using CPLEX 12.1, and the solution results are compared with the results of the metaheuristic approach. SA is utilized to solve large-scale problems.
The mechanism of extracting the initial suitable solution
The trucks are prioritized according to the first-to-last prioritization rule. If the arrival time of both trucks is the same, the one with more products will receive the order before the other. The trucks are assigned to the reception gates in order. Similarly, outgoing trucks are sorted from first to last. Inbound-outbound trucks are added to the order after the outbound trucks are sorted. The following steps are applied in the designed mechanism to derive an initial suitable solution:
I. Arriving trucks are sorted according to their arrival time at the cross-docking center (from the earliest arrival to the latest), I={1, 2, …, n}, for all i ∈ I.
II. The number of incoming trucks/the number of reception doors is determined.
III. Admission gates are added to the ranking.
IV. Outgoing trucks are sorted by the arrival time at the cross-docking center (from the earliest arrival to the latest), O = {1, 2 , … , m}, for all j ∈ O.
V. Inbound-outbound trucks are sorted by their arrival time at the cross-docking center and added to the end of the outbound truck list, O = {1, 2 , … , m}, for all j, c ∈ O.
VI. The number of outgoing trucks/shipping gates is determined.
Neighbor solution extraction mechanism
For a neighbor solution generation, two separate numbers are obtained for the incoming and outgoing truck queues. The two cells are swapped in the sort based on the two derived numbers. The cells shown can be the location of two trucks or one door and one truck or two doors (Fig. 1).
Neighbor solution extraction mechanism.
This figure is shown in the PDF version of the article.
According to the current order in Fig. 1, there are three admission gates, five inbound trucks, three shipping ports, and five outbound trucks. Based on the current ranking and assignments, trucks No. 4 and 5 are unloaded at the first entry gate, trucks No. 3 and 2 at the second entry gate, and truck No. 1 at the third entry gate. Likewise, according to the current order, outbound trucks 1, 3, and 5 are loaded at the first loading gate, outbound truck No. 2 is loaded at the second loading gate, and outbound truck No. 4 is loaded at the third. The two shipping doors are designed for inbound trucks 2 and 4 and outbound trucks 3 and 4. New rankings were created by relocating the cells corresponding to the derived numbers. According to the new rank, trucks 4 and 3 are unloaded at the first entrance gate, trucks 5 and 2 at the second entrance gate, and truck 1 at the third entrance gate. Likewise, according to the new order, outbound trucks No. 1, 3 will be loaded at the first cargo door, outbound trucks 5, 2 will be loaded at the second loading gate, and outbound truck No. 4 will be loaded at the 3rd cargo door.
Experimental Results
Test problems were created using data according to different parameters, and the solution results were analyzed. The mathematical model of the test problems is solved using CPLEX 12.1. In Table 1, the results of solving SA are compared with the best solutions of CPLEX. As a result of the tests, the starting temperature for SA was determined to be 100°C, the cooling rate to be 90%, and the stopping criterion to be 250 consecutive steps. Each test problem was solved 10 times with SA. All tests are built into a computer with an Intel Core i7, 12GB RAM, and a 3.0 GHz processor. In Table 1, there are solution results for 7 incoming, 7 outgoing trucks, and fewer. It has been shown that the solution time of the mathematical model increases significantly when the number of 6 incoming and 6 outgoing trucks is exceeded. When the solution results and solution time of SA are examined, it is seen that it gives appropriate solutions in a reasonable time. In the test problems using 7 inbound and 7 outbound trucks, it was observed that the solution time exceeded three hours with the CPLEX. It is not possible to find a solution in a reasonable time with optimization programs for test problems on 6 incoming and 6 outgoing trucks [1], observed values related to solution time support the related study. The objective function value of the mathematical model and the objective function value of the SA algorithm were found to be the same for the related problem type. This shows that the algorithm, which has been proven successful in small-sized problems, can also be used in solving large-sized problems.
The results of SA compared to the best solutions of CPLEX.
This table is shown in the PDF version of the article.
Conclusion
The truck scheduling problem is one of the most fundamental problems that must be addressed to synchronize the incoming and outgoing product flow in cross-docking centers and to send products to the customer on time. In the study, the truck scheduling problem in a multi-door cross-docking center is handled to maximize the number of products loaded in a given working time. In the related issue, it is assumed that trucks arrive at the cross-docking center at different times, as in real-life problems. In addition to the incoming and outgoing trucks included in the truck scheduling problems, the "inbound-outbound" trucks that come to the center to unload the product and go to the shipment area after the unloading process is completed are also included in the problem. The mathematical model of the problem was established, and the best solutions were obtained using CPLEX for the derived test problems. The solution results of the mathematical model were compared with the SA, which was coded to be used in the solution of large-scale trials. In future studies, the problem can be examined concerning different features, constraints, and purposes. In addition, taking into account the distances between the acceptances and shipping doors in the cross-docking center, the transfer can be carried out to minimize the path of the products within the center. Apart from maximizing the number of products loaded in a particular working period, a multi-purpose structure can be created to optimize more than one purpose, considering other purposes.
Acknowledgments
The authors would like to express their sincere appreciation to all individuals who contributed to this research through their valuable comments, suggestions, and support.
Funding
This research received no external funding.
Data Availability
The data used in this study were generated and processed by the authors for numerical analyses and model validation. The datasets supporting the findings of this study are available from the corresponding author upon reasonable request.
ReferencesYu, W., Ha, C., & Park, S. (2021). A hybrid genetic algorithm for integrated truck scheduling and product routing on the cross-docking system with multiple receiving and shipping docks. Mathematical problems in engineering, 2021(1), 2026834. https://doi.org/10.1155/2021/2026834McWilliams, D. L. (2009). Genetic-based scheduling to solve the parcel hub scheduling problem. Computers & industrial engineering, 56(4), 1607–1616. https://doi.org/10.1016/j.cie.2008.10.011Arabani, A. R. B., Ghomi, S. M. T. F., & Zandieh, M. (2011). Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage. Expert systems with applications, 38(3), 1964– 1979. https://doi.org/10.1016/j.eswa.2010.07.130Theophilus, O., Dulebenets, M. A., Pasha, J., Abioye, O. F., & Kavoosi, M. (2019). Truck scheduling at cross-docking terminals: A follow-up state-of-the-art review. Sustainability, 11(19), 5245. https://doi.org/10.3390/su11195245Vahdani, B., Soltani, R., & Zandieh, M. (2010). Scheduling the truck holdover recurrent dock cross-dock problem using robust meta-heuristics. The international journal of advanced manufacturing technology, 46, 769–783. https://doi.org/10.1007/s00170-009-2152-2%0A%0AShi, W., Liu, Z., Shang, J., & Cui, Y. (2013). Multi-criteria robust design of a JIT-based cross-docking distribution center for an auto parts supply chain. European journal of operational research, 229(3), 695–706. https://doi.org/10.1016/j.ejor.2013.03.013Walha, F., Chaabane, S., Bekrar, A., & Loukil, T. (2014). The cross docking under uncertainty: State of the art. 2014 international conference on advanced logistics and transport (ICALT) (pp. 330-335). IEEE. https://doi.org/10.1109/ICAdLT.2014.6866334Shiguemoto, A. L., Cavalcante Netto, U. S., & Bauab, G. H. S. (2014). An efficient hybrid meta-heuristic for a cross-docking system with temporary storage. International journal of production research, 52(4), 1231– 1239. https://doi.org/10.1080/00207543.2013.848485Mohtashami, A., Tavana, M., Santos-Arteaga, F. J., & Fallahian-Najafabadi, A. (2015). A novel multi-objective meta-heuristic model for solving cross-docking scheduling problems. Applied soft computing, 31, 30–47. https://doi.org/10.1016/j.asoc.2015.02.030Mohtashami, A. (2015). Scheduling trucks in cross docking systems with temporary storage and repetitive pattern for shipping trucks. Applied soft computing, 36, 468–486. https://doi.org/10.1016/j.asoc.2015.07.021Behnamian, J., Fatemi Ghomi, S. M. T., Jolai, F., & Heidary, P. (2018). Location-allocation and scheduling of inbound and outbound trucks in multiple cross-dockings considering breakdown trucks. Journal of optimization in industrial engineering, 11(1), 51–65. https://www.academia.edu/download/112933953/article_535407_468af830794a45a451fb16d806c64cb9.pd fMcWilliams, D. L., Stanfield, P. M., & Geiger, C. D. (2008). Minimizing the completion time of the transfer operations in a central parcel consolidation terminal with unequal-batch-size inbound trailers. Computers & industrial engineering, 54(4), 709–720. https://doi.org/10.1016/j.cie.2007.10.006Alpan, G., Larbi, R., & Penz, B. (2011). A bounded dynamic programming approach to schedule operations in a cross docking platform. Computers & industrial engineering, 60(3), 385–396. https://doi.org/10.1016/j.cie.2010.08.012Tootkaleh, S. R., Ghomi, S. M. T. F., & Sajadieh, M. S. (2016). Cross dock scheduling with fixed outbound trucks departure times under substitution condition. Computers & industrial engineering, 92, 50–56. https://doi.org/10.1016/j.cie.2015.12.005Konur, D., & Golias, M. M. (2013). Analysis of different approaches to cross-dock truck scheduling with truck arrival time uncertainty. Computers & industrial engineering, 65(4), 663–672. https://doi.org/10.1016/j.cie.2013.05.009Shahabi-Shahmiri, R., Asian, S., Tavakkoli-Moghaddam, R., Mousavi, S. M., & Rajabzadeh, M. (2021). A routing and scheduling problem for cross-docking networks with perishable products, heterogeneous vehicles and split delivery. Computers & industrial engineering, 157, 107299. https://doi.org/10.1016/j.cie.2021.107299Yang, Y., Zhong, M., Dessouky, Y., & Postolache, O. (2018). An integrated scheduling method for AGV routing in automated container terminals. Computers & industrial engineering, 126, 482–493. https://doi.org/10.1016/j.cie.2018.10.007Joo, C. M., & Kim, B. S. (2013). Scheduling compound trucks in multi-door cross-docking terminals. The international journal of advanced manufacturing technology, 64, 977–988. https://doi.org/10.1007/s00170-012-4035-1%0A%0ARijal, A., Bijvank, M., & de Koster, R. (2019). Integrated scheduling and assignment of trucks at unit-load cross-dock terminals with mixed service mode dock doors. European journal of operational research, 278(3), 752–771. https://doi.org/10.1016/j.ejor.2019.04.028Shahmardan, A., & Sajadieh, M. S. (2020). Truck scheduling in a multi-door cross-docking center with partial unloading--Reinforcement learning-based simulated annealing approaches. Computers & industrial engineering, 139, 106134. https://doi.org/10.1016/j.cie.2019.106134Agustina, D., Lee, C. K. M., & Piplani, R. (2010). A review: Mathematical modles for cross docking planning. International journal of engineering business management, 2, 13. https://doi.org/10.5772/9717Boysen, N., & Fliedner, M. (2010). Cross dock scheduling: Classification, literature review and research agenda. Omega, 38(6), 413–422. https://doi.org/10.1016/j.omega.2009.10.008Bektur, G., & Saraç, T. (2019). A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Computers & operations research, 103, 46–63. https://doi.org/10.1016/j.cor.2018.10.010