هزینه برنامه ریزی کامیون پایدار در مرکز حوض های متقاطع با ورود کامیون های ناشناخته: رویکرد متاهیوریستیک

We study a cross-dock operator’s truck scheduling problem at inbound doors in case of unknown truck arrival times. Due to uncertainty of truck arrivals, a scheduling strategy is subject to variations in costs of serving the trucks. A cost-stable scheduling strategy is defined as a schedule with low variation levels. In this paper, we analyze the cross-dock operator’s problem of determining a cost-stable scheduling strategy while minimizing the average of total service costs. A bi-objective bi-level optimization problem is formulated and we discuss a genetic algorithm based heuristic to find Pareto efficient schedules. The proposed approach is compared to first-come-first-served policies.

It is well known that cross-docking may achieve substantial savings for a supply chain (see, e.g., Kinnear, 1997, Gümüş and Bookbinder, 2004, Waller et al., 2006, Kreng and Chen, 2008 and Galbreth et al., 2008), hence, it is practiced by many companies. The benefits of cross-docking are due to decreased warehousing costs, utilized transportation capacity as consolidated shipments result in fewer but full truckload deliveries, which decreases transportation costs, and increased service levels. The common processes included within a cross-dock facility are unloading incoming trucks at the inbound doors, sorting, storing and staging, and loading outgoing trucks at the outbound doors.1 A successful cross-docking implementation requires efficiently locating cross-dock facilities within supply chain networks (see, e.g., Syarif et al., 2002, Jayaraman and Ross, 2003, Sung and Song, 2003, Gümüş and Bookbinder, 2004, Campbell, 2005, Chen et al., 2006, Ross and Jayaraman, 2008, Bachlaus et al., 2008, Sung and Yang, 2008 and Kreng and Chen, 2008), designing the layout of the cross-dock facilities (see, e.g., Bartholdi and Gue, 2004, Heragu et al., 2005, Hauser and Chung, 2006, Vis and Roodbergen, 2008 and Yanchang and Min, 2009), and planning cross-dock operations. The studies on cross-dock operations constitute the major part of the literature on cross-docking. In a recent study, Agustina et al. (2010) review the studies on cross-dock operations. It is noted that allocating products to cross-dock facilities (Li et al., 2008 and Li et al., 2009), assignment of docks based on delivery origins and destinations (Tsui and Chang, 1990, Tsui and Chang, 1992, Gue, 1999, Bartholdi and Gue, 2000, Bermudez and Cole, 2001, Oh et al., 2006, Lim et al., 2006, Bozer and Carlo, 2008, Ko et al., 2008, Miao et al., 2009, Marjani et al., 2011 and Shuib et al., 2012), vehicle routing in networks with cross-docks (Lee et al., 2006 and Wen et al., 2009), transfer of loads from inbound doors to outbound doors (Lim et al., 2005 and Miao et al., 2008), and scheduling incoming and outgoing trucks at inbound and outbound doors (cross-dock scheduling), respectively, are the main challenges observed in cross-dock facilities. Most of the studies on cross-dock operations focus on cross-dock scheduling. In a cross-dock scheduling problem, the goal is to determine the assignment of incoming (outgoing) trucks to inbound (outbound) doors and each truck’s order of service. It is worth noting that the cross-dock scheduling problem is different than the dock-door assignment problem, which seeks the optimal assignment of incoming and outgoing trucks to the dock doors of a cross-dock facility (Belle et al., 2012). In particular, the cross-dock scheduling problem takes time dimension into account while time is not considered in the dock door assignment problem (Belle et al., 2012). As noted by Boysen and Fliedner (2010), door environment (dock assignments, number of doors, and inbound-only, outbound-only, and mixed doors) and operational characteristics such as truck arrivals, preemptions, shipment deadlines, and storage restrictions affect truck scheduling at cross-dock facilities. Furthermore, it is noted that the objectives are mainly time related such as minimization of makespan, total service times, and tardiness. In the cross-dock scheduling literature, such objectives are studied assuming that either all trucks are present at the cross-dock facility at the beginning of a planning period or the time each truck arrives at the cross-dock facility is known in advance. McWilliams et al., 2005, Shakeri et al., 2008, Yu and Egbelu, 2008, Maknoon and Baptiste, 2009 and Boysen et al., 2010 assume that truck arrival times are identical and equal to zero, i.e., all trucks are available at the beginning of the planning period. Sadykov, 2009, Vahdani and Zandieh, 2010 and Alpan et al., 2011, on the other hand, assume that truck arrival times are given. However, assuming known truck arrival times with certainty is unrealistic as truck arrivals are subject to uncertainties due to traffic congestion, weather conditions, or engine failures (Boysen and Fliedner, 2010). This assumption, therefore, may result in suboptimal scheduling strategies in practice (Boysen, 2010) and affect cross-docking efficiency as waiting and delivery times heavily depend on the scheduling strategies (Wang and Regan, 2008). In a recent review of cross-docking studies, Belle et al. (2012) note that assuming deterministic travel times and costs is a shortcoming of the truck scheduling studies in the literature. The current paper is intended to overcome this by considering uncertainty of truck arrivals in inbound truck scheduling at a cross-dock facility. One may refer to Boysen and Fliedner, 2010 and Agustina et al., 2010 for a review of cross-dock scheduling problems and a review on mathematical models considered in cross-dock operations, respectively. Belle et al. (2012) provide a detailed literature review on different aspects of cross-docking. In this study, truck arrival times are assumed to be unknown in an attempt to better represent the realistic properties of cross-dock operations by accounting for the uncertainties in truck arrivals. As noted by Stock and Lambert (2001), inbound transportation is subject to higher levels of uncertainty; therefore, the focus of the current study is on incoming truck scheduling at the inbound doors at a cross-dock facility under truck arrival times uncertainty. It is observed that there is a limited number of studies that consider uncertainties in cross-docking operations. Rodriguez-Velasquez et al., 2010 and Arnaout et al., 2010 use simulation to model transportation between a set of warehouses and a set of cross-dock facilities to account for stochastic order sizes generated at the warehouses. Larbi et al. (2011) consider stochastic loads of incoming trucks and they study three cases: full-information, partial-information, and no-information on the incoming trucks’ loads. They focus on a single inbound and a single outbound door case and the emphasis is on assigning the incoming loads to outgoing trucks. In this paper, it is assumed that truck arrival times are unknown to the cross-dock operator, however, s/he knows the incoming trucks’ arrival time windows, i.e., the lower and upper bounds on the truck arrival times. We consider that the cross-dock operator plans his/her scheduling strategies based on the total service costs. Similar to Alpan et al. (2011), we directly focus on operational costs of scheduling. In particular, each incoming truck has a process (handling) cost depending on the inbound door it is assigned to. Boysen et al. (2010) note that this better reflects practical operations at the cross-dock facilities. Furthermore, the cross-dock operator is subject to waiting costs of the incoming trucks. Specifically, truck waiting times are subject to penalties considering the Just-in-Time scheduling (see, e.g., Alvarez-Perez et al., 2009). Arabani et al. (2010) point out that delays in shipments can result in shortage costs at the destinations. One can consider truck waiting as inventory holding, hence, it results in inventory holding costs as well. In addition, truck waiting times are associated with driver labor cost during the wait. Therefore, we consider that the cross-dock operator has costs associated with truck waiting times. Particularly, we consider that each incoming truck has a specific waiting cost per unit time. In the case of truck arrival uncertainties, a simple approach is to use a first-come-first-served (FCFS) policy. However, FCFS policies do not result in a stable schedule, that is, the schedule is not known until the last incoming truck arrives at the cross-dock facility and it changes for different truck arrival time realizations. Therefore, trucks’ waiting and process costs are both subject to variations. A fixed schedule is desirable by a cross-dock operator for planning purposes such as workforce planning, service pricing, and material handling equipment capacity planning. Variations in schedule costs hinders the efficiency of such planning decisions. While a fixed schedule would not have variations in process costs, there will still be variations in total service costs due to the fact that trucks’ waiting costs vary as a result of truck arrival uncertainty. However, these variations are expected to be lower compared to a FCFS policy, under which variations can be observed in trucks’ waiting and process costs. Cook et al. (2005) note that stable scheduling is important for lean cross-dock facilities. A stable schedule is also important for outbound transportation as variations in inbound scheduling transfer to variations in outbound scheduling, which increases costs due to delays, increased storage, or additional staging effort. Therefore, we take into account the variations in total service costs associated with a schedule in solving the cross-dock operator’s scheduling problem. In particular, a bi-objective optimization problem is formulated where the first objective minimizes the average total service costs and the second objective minimizes the cost range. Total costs associated with a schedule heavily depend on the actual truck arrivals and we define the average total service costs as the arithmetic average of the possible maximum and possible minimum total service costs. However, solely minimization of the average total service costs may result in high variations in total service costs, i.e., a cost-unstable schedule. Therefore, we also consider minimizing the cost range of a schedule, which is defined as the difference between the possible maximum and possible minimum total cost of a schedule. It is worth noting that robustness/stability is an important concept studied in scheduling problems, for various applications, in uncertain environments. Robustness of a schedule may be defined as its insensitiveness to the uncertainties and stability, performance range of a given schedule, can be used to measure robustness of a schedule (Billaut et al., 2008). The cost range of a schedule, defined for the problem of interest in this paper, is assumed to represent the stability of a schedule, i.e., it is used to measure the schedule’s robustness. As aforementioned, cost-stable scheduling may be attractive to the cross-dock operator for planning purposes. We refer the reader to the book by Billaut et al. (2008) for detailed discussion on robustness in scheduling problems that arise in different practical applications. We propose a genetic algorithm (GA) based heuristic to find an efficient Pareto frontier set of schedules. It is worth noting that heuristic and meta-heuristic methods are commonly used for efficiently solving combinatorial problems. Moghadam and Seyedhosseini (2010) effectively use particle swarm approach to solve vehicle routing problem with uncertain demand, Chen and Wang (2010) utilize particle swarm approach for an economic dispatch problem, and Sayadi et al. (2010) apply a discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. We compare the proposed bi-objective approach with two FCFS policies through a set of numerical studies. It is observed that the proposed bi-objective approach results in schedules that outperform FCFS policies in terms of cost-stability as well as average total service costs. To the best knowledge of the authors, this study is the first in introducing cost stability for the cross-dock scheduling problem in case of unknown truck arrival times. In this study, we contribute to the literature by analyses of cost stability in scheduling while explicitly regarding truck arrival uncertainty. The organization of the rest of the paper is as follows. Section 2 gives the bi-objective formulation of the cross-dock operator’s scheduling problem. In Section 3, a GA based heuristic method to find a set of Pareto efficient schedules is proposed. Section 4 demonstrates the advantages of the proposed bi-objective approach compared to two FCFS policies. In Section 5, we summarize our results, contributions, and related future research directions.

This paper studies truck scheduling at inbound doors of a cross-dock facility. We consider uncertainty in truck arrival times to better capture real life operational conditions. In case of uncertain truck arrivals, the costs associated with the inbound scheduling are subject to variations. These variations hinder the efficiency of the cross-docks. Therefore, a cost-stable approach is considered. In the cost-stable approach, while the scheduling service costs are minimized, the range of these costs are also aimed to be reduced to avoid high variations due to uncertain truck arrivals. In particular, a bi-objective bi-level optimization problem is formulated for the stable scheduling problem (SSP). SSP is bi-objective as minimization of average total service costs and minimization of total service cost range are simultaneously considered. SSP is bi-level due to the fact that definitions of average total service costs and total service cost range require determining maximum and minimum total service costs that can be realized for a given schedule with random truck arrival times. As multi-objective multi-level problems are challenging, a Genetic Algorithm based search heuristic (GASH) is proposed to achieve an efficient Pareto frontier. We compare the proposed cost-stable approach with two different First-Come-First-Served (FCFS) policies. Our numerical studies indicate that the former approach is efficient in determining schedules that have low average total service costs with low ranges, that is, variations in the service costs are low. While FCFS policies are able to result in low average total service costs for some of the problem instances, the ranges observed in FCFS policies are high compared to the cost-stable approach. Furthermore, when a weighted approach is used by the cross-dock operator, the cost-stable approach to the scheduling problem outperforms the FCFS policies. Thus, we conclude that the cost-stable approach is an efficient scheduling method that result in cost-stable schedules with low service costs in case of uncertain truck arrivals. To the best knowledge of the authors, this paper is first to consider cost-stability in cross-dock scheduling in case of truck arrival uncertainty and propose a robust solution method independent of probability distributions of truck arrival times. Future research directions would be in analyzing the cost-stable scheduling problem when probability distributions for truck arrival times are known. Studying different solution methods and their performances remain as a future research study. Further future research direction would be in integrating inbound with outbound scheduling in case of truck arrival time uncertainty.