Vehicle Routing with Cross Docks, Split Deliveries, and Multiple Use of Vehicles by Arun Kumar Ranganathan Jagannathan A thesis submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Master of Science Auburn, Alabama December 12, 2011 Keywords: VRP, Cross dock, Integer programming Copyright 2011 by Arun Kumar Ranganathan Jagannathan Approved by Chase C. Murray, Chair, Assistant Professor of Industrial and Systems Engineering Je rey S. Smith, Professor of Industrial and Systems Engineering Kevin R. Gue, Associate Professor of Industrial and Systems Engineering Abstract Cross docking plays a vital role in supply chain management. Cross docks can reduce the lead time of the product from supplier to retailer. The bene t of the cross dock would be reduced without e cient vehicle routing and scheduling. This research work proposes a mixed integer linear programming formulation to obtain feasible vehicle routes and sched- ules. The vehicle routing problem is characterized by heterogeneous vehicles, split deliveries, discrete time windows, linehaul, and backhaul operations. The problem is modeled to facil- itate the pick up of empty pallets at the retailer during the linehaul operation and delivery of empty pallets to the suppliers during the backhaul operation. The mathematical formula- tion is solved using CPLEX. The research work also proposes an algorithm to obtain initial feasible vehicle routes. ii Acknowledgments I would like to thank Dr Chase C. Murray, for his guidance and for providing me an opportunity to work on my research work. I would like to thank Dr Je rey S. Smith and Dr Kevin R. Gue for their reviews on my thesis work and for serving on my committee. iii Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 VRP and Cross Docking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 VRP and Non Cross Docking Environment . . . . . . . . . . . . . . . . . . . 14 4 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1 Notation { Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Notation { Network Description . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Notation { Decision Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4 Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4.1 Network Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4.2 Supplier Pickup Constraints . . . . . . . . . . . . . . . . . . . . . . . 31 4.4.3 Retailer Delivery Constraints . . . . . . . . . . . . . . . . . . . . . . 32 4.4.4 Backhaul Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4.5 Cross Dock Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.4.6 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5 Numerical Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.1 Input Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 iv 6 Heuristic Approach for Determining Initial Solutions . . . . . . . . . . . . . . . 48 6.1 The Pickup function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 The DeliveryAndPickup function . . . . . . . . . . . . . . . . . . . . . . . . 55 6.3 The VehicleCopy function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.1 Generation of Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2 Initial Solution Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8 Conclusions & Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 v List of Figures 4.1 Sample network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Activity in CDin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Activity in 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.4 Route taken by vehicle 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5 Route taken by vehicle 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.1 Nodes in the network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Routes taken by the vehicles in the network . . . . . . . . . . . . . . . . . . . . 44 vi List of Tables 3.1 A comparison of cross dock models . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.1 Possible de nitions for vj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.1 Location and time interval details . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Apalrs values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.3 Dprodrs values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.4 Cv values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.5 1ij values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.6 2ij values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.7 3ij values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.8 4ij values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.9 Vehicle route sequence: xtvij . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.10 Supplier full pallet pickup sequence . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.11 Cross dock in full pallet delivery and pick up sequence . . . . . . . . . . . . . . 46 5.12 Retailer full pallet delivery sequence . . . . . . . . . . . . . . . . . . . . . . . . 46 5.13 Empty pallet pick up sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.14 Empty pallet delivery sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7.1 Input parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.2 Time interval Tj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.3 Summary of small problem sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.4 Summary of heuristic solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.5 Details of heuristic performance on problems with 5 retailers . . . . . . . . . . . 73 7.6 Details of heuristic performance on problems with 10 retailers . . . . . . . . . . 73 vii Chapter 1 Introduction Today in many industries, logistics is one of the major cost factors. For example, Bayer AG, a chemical company with annual sales equivalent to $25 billion, has a logistics budget of $5 billion; it involves 3,000 di erent distribution points with handling about 740,000 di erent shipments (Johnson and Wood 1990). Trucking accounts for 83% of freight transportation in the US alone (Wilson 2002). A continuous surge in oil prices and increasing competition have forced industries to implement novel cost-reduction strategies. Distribution centers are important components of the logistics distribution network. They facilitate the consolidation of goods from a variety of suppliers to a variety of retail- ers. According to the functions of the distribution center, there is a distinction between an inventory coordination point and an inventory storage point. The former is a cross docking strategy, while the latter is a traditional warehousing strategy (Kreng and Chen 2008). The cross docking strategy has been acknowledged as having great potential to reduce trans- portation costs and delivery times without increasing inventory (Sung and Song 2003). Two critical requirements of cross docking are simultaneous arrival and consolidation. If all vehicles do not arrive at the cross dock simultaneously, some vehicles have to wait. Therefore, the timing for all vehicles in the pickup process must be synchronized to reduce waiting times. According to the destination, all products are classi ed and loaded to each vehicle in the cross dock. Then, all vehicles leave the cross dock to distribute products to their destinations. If simultaneous arrival and consolidation can be easily accomplished in a supply chain?s physical ow, all products can be moved from suppliers to customers without any interruptions. Therefore, we can expect to reduce inventory levels and lead times for 1 delivery (Lee et al. 2006). In the case of Wal-Mart, cross docking is often regarded as a key driver of the retailer?s superior logistics management (Hammer 2004). The bene ts of cross docks do not come without some risks. For example, Apte and Viswanathan (2000) caution that, \cross docking inherently leads to a minimal level of in- ventory at the warehouse, and thereby strips the system of safety stocks traditionally held at the warehouse. Consequently, cross docking raises the probability of stock-out situations." Fortunately, this issue may be addressed by utilizing the concept of vendor managed inven- tory (VMI). With VMI, the supplier (which is often a manufacturer) controls the buyer?s (retailer?s) inventory levels, so as to ensure that predetermined customer service levels are maintained. In such a relationship, the supplier takes the replenishment decision for the buyer, dispatching a quantity of product that may be xed (Waller et al. 2006). Replen- ishment occurs when the stock level at the buyer reaches a speci ed level, based on both the average demand during transportation lead time and a safety stock to cover for demand variations (Kaipia et al. 2002). VMI brings a number of bene ts to all parties participating in the supply chain. First, the impact of demand ampli cation is dampened, as the man- ufacturer now receives a direct view of end consumer demand patterns and can use this in forecasting (Disney et al. 2003). This generates cost bene ts through a reduction in bu er stocks at the buyer and supplier (Sabath 1995). Further, there are improvements in service levels as product availability is increased (Waller et al. 2006). Finally, VMI can, in the long run, increase the pro tability of both the supplier and buyer in supply chain (Dong and Xu 2002). The buyer bene ts from lower inventory costs and can o er a price reduction. This then increases sales volume, which bene ts both parties in terms of increased pro tability (Disney et al. 2003). Motivated by the usefulness of the cross docks, several authors have focused on im- proving the performance within the cross dock itself. Some of the notable studies include the design of the cross dock layout (Bartholdi and Gue 2000; Bartholdi and Gue 2004), bene ts of the cross dock layout when compared to traditional warehouse (Kreng and Chen 2 2008), analysis of retailer inventory levels when cross docks are used (Waller et al. 2006) and scheduling of trucks at cross dock doors (Boysen and Fliedner 2010). However, less work has been done on the problem of routing and scheduling in a cross dock distribution network. The distribution network has several key components. These include suppliers, con- sumers (retailers), cross docks, and the vehicles that transport goods between nodes in the network. It is important to select the proper mix of vehicles, and to schedule them ap- propriately. The vehicles may be routed in a truckload operation or a less-than-truckload operation. Less-than-truckload operations are observed if the loaded capacity of the vehicle for a particular route will be less than the capacity of the vehicle. Transportation costs may increase if less-than-truckload operations are frequently scheduled. If the customers are willing to receive goods in multiple shipments, a practice known as \split delivery", the occurrence of less-than-truckload operations may be reduced. The operations of the truck may have only linehaul operations or it may have both linehaul and backhaul operations. In linehaul operations, the goods are either picked up or delivered. In backhaul operations, after goods are delivered to customers, trucks are routed for pick up from the suppliers. The combination of the linehaul and the backhaul operation is considered e cient, as it may reduce the occurrence of vehicles travelling empty (dead heading). This research e ort makes several contributions. A mathematical model is developed for the vehicle routing problem (VRP) for cross docks. Some work has been reported on the VRP for cross docks, with extensions like time windows, split deliveries, heterogeneous eet of vehicles, and multiple cross docks. All the reported work has one of the above mentioned extensions, or a combination of only a couple of extensions to the VRP for cross docks. In this thesis, the proposed VRP model is built with all the above mentioned extensions, in addition to three new extensions. First, to improve the vehicle utilization, a feature to allow pick up during a linehaul operation is added. Second, backhaul operations are added. Finally, a feature to allow delivery during a backhaul operation is added. In addition to developing a mathematical model, a heuristic approach is proposed for determining feasible vehicle routes. 3 The solution from the heuristic approach can be used within a broader solution approach, like tabu search, to obtain better solutions. Moreover, a procedure is explained to develop test problems for this model. The remainder of this thesis is organized as follows. A formal description of the dis- tribution problem involving cross docks, backhaul operations, and multiple use of vehicles is presented in Chapter 2. Chapter 3 contains a review of relevant literature. In Chapter 4, parameters and decision variables used in the development of the mixed integer linear programming formulation for the model are explained. Moreover, network constraints, cross dock constraints, supplier pick up constraints and retailer delivery constraints of the model are also explained. In Chapter 5, a numerical example is provided to further explain the details of the mathematical model. A heuristic approach for obtaining initial feasible vehicle routes is explained in Chapter 6. Numerical analysis of the mathematical model for di erent parameter values is included in Chapter 7. Finally, concluding remarks and suggestions for future research are given in Chapter 8. 4 Chapter 2 Problem Description The problem of interest involves a distribution network consisting of retailers, suppliers, cross docks, and vehicles of potentially-di ering capacities. Goods must be delivered from suppliers to retailers through one or more cross docks. Within each cross dock, goods arriving on multiple inbound trucks are sorted and consolidated onto multiple outbound trucks. To facilitate e cient ow of goods through the cross dock, orders are assumed to be loaded onto pallets of uniform size. Each retailer has a known demand of goods from each supplier. The allowable times in which deliveries may be made to each retailer are de ned by one or more time windows, such that deliveries may not be scheduled outside of these windows. Split deliveries, in which multiple vehicles may deliver goods at separate times, are allowed in this system in an e ort to maximize vehicle utilization. The delivery of goods to retailers is described by a linehaul operation. As goods are delivered to retailers, an inventory of empty pallets may accumulate. These empty pallets must be returned to the appropriate suppliers as part of a backhaul operation. As with retailers, vehicles may pick up goods from suppliers only within pre-de ned time windows. These time windows also de ne the allowable times in which vehicles may return empty pallets, which were delivered as full pallets to retailers as part of the linehaul operation, to a given supplier. Split deliveries of empty pallets are permissible, and may be necessary due to vehicle capacity limitations, time window constraints, or vehicle coordination issues at the cross dock. The actual quantity of each retailer?s demand is assumed to be determined by the application of vendor managed inventory (VMI). As such, the demand of each retailer is 5 known, and there is no need to maintain inventory levels in the distribution centers (in this case, the cross docks). By assumption, there is no space to store inventory in the cross dock. In order to operate an inventory-free cross dock, the transfer operation within cross docks requires the applicable vehicles to arrive at the cross dock simultaneously. Goods are assumed to travel directly from inbound to outbound trucks. There may be multiple cross docks in pre-de ned ( xed) locations. Each cross dock con- sists of a set of terminals for inbound trucks (containing pallets from suppliers) and another set of terminals for outbound trucks (to be loaded with pallets for delivery to retailers). It is important to note that the problem of interest here is not concerned with the scheduling of vehicles to particular terminals in the cross dock. Therefore, it is not practical to consider terminal-speci c transfer times between incoming and outgoing shipments. A heterogeneous eet of vehicles (trucks) is available, such that each vehicle may have a unique capacity. Vehicles may be assigned to multiple routes over the course of the planning horizon. Each truck is assumed to begin empty at its current location at the beginning of the planning horizon. Trucks may travel from their initial locations to either a supplier (where the pickup process for goods commences) or to the outbound terminal of a cross dock (where trucks wait to be loaded with goods picked up by other trucks visiting suppliers). Less-than-truckload (LTL) operations are allowed. Because all goods bound for retailers must pass through a cross dock, vehicles may not travel directly from suppliers to retailers. However, vehicles may deliver empty pallets directly from retailers to suppliers as part of a backhaul operation. The objective of the problem is to determine the minimum-cost vehicle schedules, where the total cost may be calculated in multiple ways. For example, there may be a cost associ- ated with the number of vehicles utilized. To facilitate more equitable numbers of routes for each vehicle, a cost may be included for each route taken by each vehicle. Additionally, a preference may be given for delivering to retailers as early as possible within their allowable time windows. Although VMI is used to establish demand values, it is possible that not all 6 demand can be satis ed. This may be due to vehicle capacity limitations, cross dock avail- ability issues, or time window limitations. As such, another cost may be associated with the quantity of unmet demand, both for goods needed by retailers and for empty pallets requested by suppliers. 7 Chapter 3 Literature Review The problem of interest here may be considered as a vehicle routing problem (VRP) with multiple side constraints. Such constraints include, but are not limited to, split deliveries, time windows, and heterogeneous vehicles in a cross docking environment. Many studies have been done separately on the VRP with varying constraints, and on cross docking. However, very little research exists on the integration of the VRP with cross docking. This literature review is divided into two parts. First, literature describing the VRP with cross docks is considered. Next, relevant vehicle routing problems in non-cross dock environments are reviewed. 3.1 VRP and Cross Docking This section contains a review of articles involving vehicle routing, sequencing, and scheduling of trucks in a cross docking environment. A summary of the literature appears in Table 3.1, which also contrasts aspects of the existing literature with the model proposed in this thesis. In Table 3.1, the \Backhaul Operation" column indicates whether vehicles are permitted to visit suppliers after making delivery to retailers. The \Pick up at Linehaul" column indicates whether vehicles may pick up empty pallets during the time of delivery of full pallets to retailers. 8 Multiple Split Time Hetero. Backhaul Pick up at Author Cross Dock Delivery Windows Vehicle Operation Linehaul Sung and Song (2003) Yes No No Yes No No Gumus and Bookbinder (2004) Yes Yes No No No No Chen et al. (2006) Yes No Yes No No No Lee et al. (2006) No No No No No No Wen et al. (2008) No No Yes No No No Liao et al. (2010) No No No No No No Miao et al. (2010) Yes No Yes No No No Musa et al. (2010) Yes No No No No No Soltani and Sadjadi (2010) No No No No No No Ma et al. (2011) Yes Yes Yes No No No This Thesis Yes Yes Yes Yes Yes Yes Table 3.1: A comparison of cross dock models Sung and Song (2003) develop an integrated service network design problem based on a path based formulation. The authors have chosen a path based formulation approach instead of an arc- ow based formulation approach on the possibility of getting an e cient and e ective formulation. The authors give a prede ned cut o time at the origin nodes within which all packages should be loaded and a prede ned critical entry time at the destination nodes after which all the packages should be delivered. The consolidation of the packages should take place between those times. The problem is modeled considering multiple cross docks and multiple origin and destination nodes. The problem is solved using a tabu search heuristic, and a separation heuristic was developed for identifying violated valid inequalities. Gumus and Bookbinder (2004) studied cross docking and its implications in the location distribution system. A model was developed to determine the best locations to operate the cross docks. The model was built taking into consideration transportation costs, facility costs, inventory costs at the manufacturers and retailers, and in-transit inventory costs. The research work also addresses the issue of the location for product consolidation. 9 Lim et al. (2005) developed transshipment models with time window constraints and addressed the issue of the just-in-time objective to the cross docks. The time windows considered in this work include both xed and exible time windows. In a xed time window, shipping and delivery at suppliers and customers are allowed only at a particular time. In a exible time window, shipping and delivery are allowed at any time within the time window. The authors also used mixed time windows, a mixture of xed and exible time windows. The aim of this research is to minimize inventory delay and to nd optimal schedule for trucks in the transshipment centers. Chen et al. (2006) proposed a cross docking problem to minimize the total cost in the distribution plan within the speci ed time windows. In this model, capacity constraints were considered at the cross docks and an inventory holding cost was assigned for the amount of inventory held at the cross dock. The initial solution to this problem was obtained by a greedy method. The authors used simulated annealing, tabu search, and a hybrid heuristic method to solve the problem. Lee et al. (2006) developed a mathematical model and proposed a heuristic algorithm based on tabu search with an objective of minimizing the transportation cost and xed cost of vehicles, and to determine the number of vehicles, optimal vehicle routing, and scheduling with cross docks. The assumptions of the model include homogeneous vehicles with no split deliveries, with all vehicles starting and returning to a cross dock. Time window constraints were developed only at the cross dock to facilitate simultaneous arrival of vehicles and the consolidation process, and to reduce the waiting time of vehicles. No time windows were considered for the suppliers and retailers. Separate vehicles were used for the pickup and delivery operation. The proposed algorithm rst nds the initial solution, which gives the possible nodes to which each vehicle may travel from the existing position by selecting the route which has a ratio of transportation cost to minimum transportation cost less than a tolerance value of 1.5. Then the remaining nodes are allotted randomly. The solution was improved by exchanging the nodes with corresponding vehicle routes. This algorithm was 10 tested for up to 50 nodes. Results were compared with results obtained from the enumeration process. E ects of tolerance value on results were analyzed. Wen et al. (2008) developed a mixed integer programming formulation to solve the VRP with cross docking and time window constraints on the nodes with the objective of reducing the total travel time. The authors solved the problems using a tabu search heuristic em- bedded within an adaptive memory procedure (AMP). Instead of simultaneous arrival and departure of vehicles at the cross dock, as proposed by Lee et al. (2006), the authors deter- mined the dependency among the vehicles based on consolidation decisions. A homogeneous set of vehicles was considered. In the consolidation process a set of vehicles pick up materials from the suppliers and deliver to the cross dock. This same set of vehicles deliver materials from the cross dock to retailers. Time windows were considered only at the nodes with no split deliveries. The authors considered a time horizon for whole transportation operation. In the AMP, the set of vehicle tours made by vehicles was stored in adaptive memory and the initial solution was formed by combining the vehicle tours. In the neighborhood search phase, the authors proposed two approaches: small neighborhood search and large neigh- borhood search. In small neighborhood search, the algorithm tries to nd the best solution by moving the nodes from a small subset of nodes to a small subset of vehicles. If the best solution is not found, the algorithm alternates to nd the best solution from the large neighborhood (i.e., from the whole solution space). Aspiration criterion was used to avoid repeated assignment of nodes to the same vehicles. The algorithm was tested for up to 200 nodes. To reduce the computational time, the authors used the aggressive skip technique, where, when a feasible route is identi ed for a vehicle, this skip applies. This method led to a considerable reduction in computational time when compared to the conservative skip technique. Liao et al. (2010) extended the work of Lee et al. (2006) and proposed a heuristic algorithm based on tabu search, with the aim of reducing the computational time and the number of vehicles used. The objective of the problem was to reduce the transportation and 11 operational cost. The initial solution was developed in two steps. In the rst step, the pick up process was considered. The algorithm calculated the minimum number of vehicles required and assigned the nodes to the vehicles. The same procedure was followed in step two for the delivery process. In the neighborhood search phase, total cost was minimized by continuously arranging the nodes from one vehicle to another. In order to reduce the operational cost, only full truck load capacities were considered. The tabu search algorithm removed empty vehicles from the system, while it was disallowed in Lee et al. (2006). Moreover, this paper showed di erences in the assignment of nodes to vehicles. The authors showed improved performance of their algorithm by considering the same parameters of Lee et al. (2006) and by comparing the computational time. However, the model has its own limitations. One of the limitations is that each supplier or retailer can be picked up only once and the quantity picked up must not exceed the capacity of the vehicle. If the demand of the product at a retailer from the supplier is greater than the capacity of the truck, this model cannot be used. Miao et al. (2010) developed a VRP problem with soft and hard time windows. The hard time window is the allowable time a node can be serviced and the soft time window is the preferred time window for the node within the hard time window. The authors developed a transshipment model with cross docks to develop a transportation schedule with the aim of minimizing the transportation cost, inventory handling, and penalty costs. A penalty cost is added to the cost factor if cargo is not delivered to the customer within the soft time window. The model consists of multiple cross docks with multiple suppliers and customers. The authors employ a three stage assignment process to develop initial solutions, where stage one is the supplier cross dock route assignment, stage two is customer cross dock route assignment, and stage three is a deterministic repair strategy to adjust schedules to obtain feasible solutions. The problem was solved using two heuristic approaches, adaptive tabu search and adaptive genetic algorithm. 12 Musa et al. (2010) developed an integer programming formulation for solving a VRP in a cross docking environment. The objective of the article was to reduce the transportation cost by routing the vehicles directly from suppliers to retailers or through the cross dock. The authors proposed a new ant colony optimization algorithm (ACO) to solve the model. The authors used more than one cross docking facility in this problem. The authors have considered a homogeneous eet with unlimited supply of trucks. The less than truck load is assumed for direct supply to the retailers from suppliers with no time window constraints and split deliveries. The problem did not mention the coordination of the trucks in the cross docks or the movement of goods between the cross docks. By using the ACO technique, the authors were able to determine the number of trucks required to travel directly from suppliers to retailers and the trucks that visit the cross dock(s) and to determine the transportation cost. Like most optimization algorithms, the authors embedded a local search algorithm in the ACO algorithm which searches for neighboring solutions to get the improved transportation cost. The parameters for the ACO algorithm were found by using design of experiments (DOE), a statistical method. D-optimal design was used to reduce the computational time, by reducing the number of runs at the same time to get better results. The factors in this experiment were analyzed using regression and ANOVA techniques. The computations were performed for up to 75 origin and destination points and for up to 50 cross docks. The proposed algorithm was able to outperform the branch and bound algorithm in the case of large problem instances. Soltani and Sadjadi (2010) developed a model to optimize the scheduling of trucks in cross docking systems (i.e., to nd the matching pairs of inbound and outbound trucks and sequence them). The authors used a metaheuristic approach, hybrid simulated annealing, and hybrid simulated variable neighborhood search to nd the truck pairs. The model was built taking into consideration one cross dock, multiple suppliers, multiple retailers, and multiple products. The idea behind the paper is to minimize the ow time of products in the cross dock by sequencing and scheduling the transportation facilities. For larger problems 13 the authors expected an exponential growth of variables and constraints, so the mixed integer formulation is not used. Moreover, for the mathematical models the computational time was expected to be more. The authors expected the computational complexity to increase with the increase of inbound and outbound trucks and product types when heuristics were used. Therefore, the authors used a metaheuristic approach to solve the problem. The robustness of the proposed algorithm was tested using the Taguchi scheme. The Taguchi parameter design method and ANOVA were used to nd the parameters that had signi cant impact on the algorithm. The algorithm was tested for up to 20 inbound trucks, 20 outbound trucks and 12 product types. Ma et al. (2011) developed a model to study the issue of shipment consolidation and transportation in a cross docking environment. The model was developed taking into con- sideration the transportation costs, truck setup costs, the number of trucks used, and their trade-o s. The model was formulated as an integer programming model and solved using a two-stage heuristic algorithm. In the rst stage, the truck load plan was developed to determine a less-than-truckload plan. In the second stage, the supply and demand at the nodes that are not satis ed are quanti ed. 3.2 VRP and Non Cross Docking Environment This section contains a review of articles of VRP in a non cross docking environment. The review contains studies on the vehicle routing problem with constraints such as time windows, split deliveries, and use of a heterogeneous eet. Yano et al. (1987) developed vehicle routing software with an objective of minimizing the total cost of routes and to make sure that all the transportation requirements are ful lled. The authors proposed a set covering approach based on Lagrangian relaxation in a branch and bound framework. The constraints were framed to minimize the total number of trucks. The authors considered the pickup and delivery process by the same vehicles, while the linehaul operation is completed before the backhaul operation starts. In this problem, the 14 total number of deliveries and pick ups were restricted to four, with no split deliveries or time window constraints. Moreover, the authors have considered the origin and destination of the trucks as the warehouse. The authors used two heuristics to nd good initial feasible solutions. The rst heuristic was used to nd the routes that did not completely satisfy the transportation requirements and to nd an initial feasible solution. The second heuristic was used to minimize the cost di erence between the initial feasible solution and the optimal solution. A branch and bound procedure was used in the optimization process. The algorithm used an e cient lower bounding technique and the nodes in the branch were characterized by unordered Cartesian products. Subgradient optimization was used to determine appropriate Lagrangian multipliers at the nodes. The database created by the authors consists of 50 stores and 200 suppliers. The algorithm was able to work e ectively with problems containing 20 to 40 transport requirements only. One transportation requirement was considered as the movement of one truck from warehouse to retailers to suppliers and back to warehouse. Toth and Vigo (1997) proposed the asymmetric version of the VRP with backhauls, where the distance between each pair of locations is not same in both directions. Symmetric versions were also considered. The objective function was to minimize the transportation cost. The authors proposed an integer linear programming model with vertices consisting of depot, linehaul, and backhaul nodes. The arc set was disjointed into three subsets (i.e., arcs from depot to linehaul vertices, backhaul vertices to depot, and linehaul vertices to backhaul vertices). Arcs connecting backhaul to linehaul vertices were not allowed. The authors used three di erent relaxation techniques. The purpose of the rst relax- ation technique is to lead to the solution of the transportation problem by dropping the capacity cut constraints. The second relaxation was based on the projection of the feasible solution space by determining the shortest spanning tree or arborescence and optimal solu- tion to the minimal cost ow problems. Third, a Lagrangian lower bound was derived by including the relaxed degree constraints in the objective function. The lower rst branch 15 and bound algorithm was used to nd the optimal solution for the vehicle routing problem. Variable reduction and feasibility checks were used to improve the performance of the branch and bound algorithm. The authors were able to provide computational results for up to 100 customers. Mingozzi et al. (1999) proposed a new integer programming formulation for solving the VRP with backhauls. The authors proposed a procedure to calculate the lower bound to the optimal solution by combining di erent heuristic methods. This procedure was used to solve the dual of the LP relaxation. The authors considered a homogeneous eet with no constraints on time windows or split deliveries. All backhaul customers were visited before the linehaul customers. Depot, linehaul, and backhaul customers were considered as vertices on a directed graph with non-negative costs on the arcs. The authors found the lower bound for this problem by solving the dual problem of the LP relaxation using heuristic procedures. The authors used the dual solution to obtain a feasible route and then an optimal solution by reducing the number of routes. A procedure was proposed to reduce the number of variables for solving using the branch and bound method. The authors used CPLEX, an LP solver, to solve the problem for up to 100 customers. Priv e et al. (2005) considered a VRP with the distribution center for a soft drink industry with heterogeneous eet, time windows, capacity, and volume constraints. The objective of the problem was to minimize the routing costs minus the revenue derived from the collection of empty recyclable containers. The vehicle movement is between the distribution center (DC) and the retailers with origin and destination of the vehicles at the DC. The authors did not consider the pick up process from the bottling center (suppliers) to the DC. The pick up process in this problem is the pickup of empty cans from the retailers to the DC. No split deliveries were allowed and the time horizon is one day. The problem formulation is based on graph theory, where the DC and the retailers were considered as vertices and arcs the routes. The authors solved the problem using three heuristics, one is neighborhood search and the other two are improvement procedures which use a combination of 3-opt and 16 2-interchange moves and route mergers. The nearest neighborhood search was used to nd the set of feasible routes and nds the route and vehicle with smallest cost per customer visited. The rst petal heuristic considers the problem as a set partitioning problem and second petal heuristics considers till the route expansion phase in rst petal heuristics and nds an optimal selection from the possible routes based on nearest neighborhood search. The improved solution was obtained by applying 3-opt and 2-interchange techniques. Vehicle routing problem with backhauls (VRPB) is a variant of VRP where the same vehicle performs both the linehaul and backhaul operations in a single route. Normally the backhaul operation is performed once the linehaul operation is completed. Linehaul operation is the delivery process and backhaul is the pickup process. The backhaul operation proposed in this article is relevant to the delivery of empty pallets and pickup of full pallets in the proposed thesis work. Gulczynski et al. (2011) proposed a new variant of vehicle routing problems called the \multiple depot split delivery vehicle routing problem." A mixed integer programming based model is developed, where a set of customers is served from multiple depots, and all customers accept split deliveries. The objective is to reduce the travel distance. A comparison study is performed to determine the reduction in distance travelled, by allowing split deliveries among vehicles based at the same depot and vehicles based at di erent depots. A heuristic is proposed to solve the problem. First, each customer is assigned to the nearest depot based on distance. Second, a heuristic is developed with constraints such that customers will receive goods only from their assigned depot. Third, a heuristic is developed that allows customers to receive goods from multiple depots. The authors, through their numerical analysis, identi ed that the bene ts obtained by allowing split deliveries to customers served by vehicles from multiple depots are higher. Zhong and Aghezzaf (2011) proposed a new variant of the vehicle routing problem called the \single vehicle cyclic inventory routing problem." The problem is formulated as a mixed integer programming model with linear constraints and a non-linear objective 17 function. In this model, repeated distribution of a product from a single depot to a selected subset of retailers having stable demands takes place. The objective of this model is to determine the subset of retailers and quantity to be delivered to each retailer, and to minimize the total distribution and inventory cost. The authors proposed an optimization approach combining DC programming and branch-and-bound with a steep descent hybrid algorithm. The proposed algorithm worked e ciently for small problem sizes. 18 Chapter 4 Mathematical Formulation In this chapter, a mixed integer linear programming (MILP) formulation of the problem is proposed. First, the required notation, including parameters and decision variables, are de ned. Next, the complete MILP formulation is presented. 4.1 Notation { Parameters In this formulation, R represents the set of all retailers and S represents the set of all suppliers. Each retailer r 2 R has a demand for products (goods) provided by supplier s2S. This demand is given by Dprodrs , and is expressed in units of pallets. Under a VMI system, where it is assumed that each supplier has a su cient availability of goods, it is unnecessary to de ne a parameter for each supplier?s available inventory levels. In other words, it is assumed that each retailer?s stated demand may be satis ed by the suppliers. However, the same assumption is not made for pallets. The reason for this di erence is that accurate counts of empty pallet inventory may not be available, possibly due to the absence of a tracking mechanism, damage or theft of pallets, or the re-use of pallets by the retailer for other purposes. Thus, each retailer is responsible for reporting its availability of empty pallets. As a result, it is possible that a supplier?s demand for empty pallets exceeds the available supply. Each supplier s 2 S has a demand for empty pallets, Dpals . This demand may be satis ed by transporting available empty pallets from each retailer r2R. The corresponding parameter is represented by Apalrs . The scaling parameter captures the fraction of a fully- loaded pallet that is consumed by an empty pallet. For example, = 1=10 if 10 empty pallets occupy the space of 1 loaded pallet. 19 To facilitate the appropriate assignment of vehicles to cross docks, each cross dock is represented by two nodes in the network. The inbound node may be visited only by loaded vehicles, while the outbound node may be visited only by empty vehicles. The sets of all inbound and outbound nodes are given by CDin and CDout, respectively. Thus, the set of all cross dock nodes, represented by CD, is such that CD =fCDin [ CDoutg. The proposed formulation utilizes a discretized time approach, such that the planning horizon is partitioned into discrete time intervals of equal duration. The width of each time interval may be a function of the length of the planning horizon. For example, 15-minute intervals may be appropriate for planning over an 8-hour horizon, while multi-day horizons may be more appropriately modeled with longer intervals. Let T represent the set of discrete time intervals comprising the planning horizon, where the interval t0 = minfTg represents the start of the planning horizon. All vehicles are assumed to be at their initial locations and ready for service at time t0. Although not considered in this formulation, it is possible to customize the model to account for a situation where each vehicle is ready for service at a unique time by changing this parameter to t0;v, where v represents a particular vehicle. Each supplier, retailer, and cross dock has an allowable time window in which service may begin. The time window for node j is represented by the set Tj. Because Tj is a discrete set, it is possible to include multiple disjoint time windows. This is a primary motivation for employing a discrete time formulation for this problem, as demonstrated in the constraints below. Because the proposed model allows vehicles to travel multiple routes (or tours), a mech- anism for tracking the number of routes assigned to each vehicle is required. This is ac- complished by designating a unique identi cation (ID) number to each vehicle, such that this ID indicates the physical vehicle itself, as well as the route number. The identi cation scheme is managed as follows. First, let set V0 represent each physical vehicle in the het- erogeneous eet, such that the cardinality of V0 indicates the total number of vehicles in the eet. Throughout this manuscript, elements of set V0 may be referenced as \original" 20 vehicles. For each vehicle v2V0, a corresponding set, denoted as V00v contains unique vehicle ID numbers for each additional route that may be taken by vehicle v. Vehicle IDs in set V00v may be referenced as vehicle \copies." Thus, vehicle v?s rst route will be attributed to vehicle ID v, and v?s second route will be attributed to the vehicle ID contained in the rst element of V00v . The cardinality of V00v represents the number of additional routes that may be taken by vehicle v2V0. Finally, the set V is de ned to be the set of all unique vehicle IDs, such that V = fV0[V00vg for all v 2V0. Vehicle v 2V has a capacity of Cv loaded pallets. For an example of these vehicle sets, suppose a eet contains two vehicles, such that V0 =f1;2g. Further, suppose vehicle 1 may take three additional tours, and vehicle 2 may take two additional tours. Thus, V001 =f3;4;5g and V002 =f6;7g. The time required for vehicle v to travel from node i to node j is given by vij, and is expressed in units of discrete time intervals. Any service duration required at node i (such as loading or unloading times) should be included in the value of vij. 4.2 Notation { Network Description To facilitate a complete description of the underlying network, additional notation char- acterizing the network nodes is bene cial. First, let 0v represent the initial location (at time t0) of each vehicle v2V0. Recall that V0 is the set of all \original" vehicles. Because the \copies" of each vehicle have yet to be assigned, their initial locations are unknown a priori. This node may represent any location in space, and is not associated with any other node in the network. Each vehicle is required to terminate each route to which it is assigned at a node in the set 1. When vehicle v2V reaches a node in 1, the vehicle receives a new identi cation number (from the set V00v ), and the vehicle is ready to start a new route. For example, vehicle v 2V0 starts at its initial location, 0v. It may visit several nodes in its rst tour before terminating that tour at some node in the set 1. The vehicle will then be assigned to the 21 rst element of the set V00v , as its second tour will be attributed to the rst \copy" of the vehicle. This rst copy will begin its route at the node in 1 where the \original" vehicle terminated, and it will terminate this route at any node in 1. Upon returning to a node in 1, the vehicle will be assigned to the next unique number in V00v . This process repeats until all vehicle copies in V00v have been assigned. By assumption (construction), each element j2 1 should correspond to a cross dock location. Thus, three nodes are associated with each cross dock { a particular node j2CDin, a particular node j2CDout, and a particular node j2 1. Each vehicle route is de ned to be a sequence of arcs in the network. For example, if a vehicle traverses arc (i;j) it departs from node i and travels directly to node j. Due to the speci c nature of this problem, not all nodes in the network are directly connected. Therefore, two additional sets of nodes are de ned to simplify the characterization of valid network arcs. The rst such set, +v , represents all nodes in the network to which vehicle v may travel. To a ord maximum exibility in the model, we de ne +v f 1[CD[R[Sg for all v2V. Note that 0v =2 +v because vehicles may not travel to (i.e., return to) their initial location. The second set, vj, represents all nodes in the network from which vehicle v may travel to node j2 +v . The nodes contained in vj depend upon the classi cation of vehicle v (e.g., whether it is an \original" or \copy" vehicle) as well as the type of node j (e.g., whether it is a retailer or supplier node). Table 4.1 contains the de nitions of vj for all possible v and j. Vehicle Classi cation Destination Node v2V0 v2V00 j2 1 vj f 0v [ R [ S [ CDing vj fj [ R [ S [ CDing j2R vj f 0v [ R [ CDoutg vj f 1 [ R [ CDoutg j2S vj f 0v [ R [ Sg vj f 1 [ R [ Sg j2CDin vj fSg vj fSg j2CDout vj = 0v vj f 1g Table 4.1: Possible de nitions for vj 22 1 r1 (s1,s3,s4) 2 r2 (s2,s3) 3 r3 (s1) 4 r4 (s3) 5 s1 6 s2 7 s3 8 s4 9 CD 1 10 11 11 12 01 13 02 14 03 15 04 Figure 4.1: Sample network Figure 4.1 shows a sample network, which includes four retailers (R = f1;2;3;4g), four suppliers (S = f5;6;7;8g), and one cross dock, decomposed into CDin = f9g and CDout =f10g. The 1 node, which is the node a liated with the cross dock where vehicles are assigned new ID numbers, is represented by node 1 =f11g. The sample network has four original vehicles whose initial locations are de ned by 0v nodes, for all v 2V. The node numbers of the initial location are represented as 01 = 12, 02 = 13, 03 = 14, 04 = 15. Node 1 (retailer r1) is to receive full pallets from suppliers s1, s2, and s3. In Figure 4.1, this is denoted as (s1;s2;s3) above node 1. Similarly, node 2 (r2) receives full pallets from s2 and s3, node 3 (r3) from s1, and node 4 from s3. The routes taken by vehicles 1 and 2 are explained as follows. In Figure 4.1, vehicle 1 starts from its initial location (i.e., 01 node), picks up full pallets from suppliers s1, and 23 6 s2 9CDin 10 CDout 14 03 15 04 Figure 4.2: Activity in CDin 9CDin 10CDout 11 1 Figure 4.3: Activity in 1 s2, and reaches CDin. Vehicle 2 starts from its initial location (i.e., 02 node), picks up full pallets from suppliers s4, s3, and s2 and reaches the CDin node. Node 6 (s2) is served by both vehicles 1 and 2 as part of a split pick up process. Simultaneous arrival of vehicles at the cross dock is shown in Figure 4.2. Vehicles 1 and 2 travel from node 6 (s2) to node 9 (CDin). Meanwhile, vehicles 3 and 4 travel from their initial locations (i.e., 03 and 04, respectively) to node 10 (CDout). At the cross dock, goods from incoming vehicles 1 and 2 are unloaded, consolidated, and loaded to the outbound vehicles 3 and 4. Since no inventory storage is allowed at the cross dock, consolidated goods are directly moved to the outbound trucks. For this event to happen, all vehicles should reach the cross dock at the same time interval, tmaxj , where j2CD. In Figure 4.3, vehicles 1 and 2 leave node 9 (CDin) after unloading the full pallets, and travel to node 11 ( 1) to get assigned new vehicle numbers. The vehicles that leave the 1 node are the copies of vehicles that enters the 1 node. The vehicles coming out from the 1 node will start the new cycle in similar manner to the assignments of vehicle 3 and 4. The route taken by vehicle 3 is shown in Figure 4.4. Vehicle 3 starts from node 14 ( 03), visits retailers r1, r2, and r3 to deliver full pallets picked up from CDout. In Figure 4.4, (s1, s2, s3) mentioned above the node 1 (r1) explains that vehicle 3 delivers full pallets picked 24 1 r1 (s1,s3,s4) 2 r2 (s2,s3) 3 r3 (s1) 10 CD 114 03 Figure 4.4: Route taken by vehicle 3 3 r3 (s1) 4 r4 (s3) 10 CD 1 15 04 Figure 4.5: Route taken by vehicle 4 up from nodes s1, s2 and s3 to r1, as a result of consolidation process. The route taken by vehicle 4 is shown in Figure 4.5. Vehicle 4 starts from node 15 ( 04), visits retailers r4 and r3, to deliver full pallets picked up from CDout. From Figures 4.4 and 4.5, it is observed that demand at node 3 (r3), is ful lled by both vehicles 3 and 4. This is an example of a split delivery operation. During the time of delivery of full pallets to retailers, empty pallets are picked up from the retailers. Then vehicles 3 and 4 follow the similar pattern of route of vehicles 1 and 2, to visit the supplier nodes to pick up full pallets and deliver empty pallets. 4.3 Notation { Decision Variables Several types of decision variables are required to determine the route taken by each vehicle, the quantity of loaded pallets delivered from suppliers to retailers, the quantity of pallets transferred at the cross docks, and the quantity of empty pallets delivered from retailers to suppliers. Additionally, there are decision variables that capture the quantity 25 of unmet demand requested by retailers and the number of empty pallets that cannot be delivered to suppliers. The decision variables are listed below. xtvij Binary decision variable, such that xtvij = 1 if vehicle v2V travels from node i to node j and begins service at node j at time interval t2T. Otherwise, xtvij = 0. atvsr Quantity of loaded pallets picked up from supplier s2S by vehicle v2V at time t2Ts that are bound for retailer r2R. btvsrj Quantity of loaded pallets that are delivered by vehicle v2V to cross dock j2CDin at time t2Tj from supplier s2S bound for retailer r2R. ctvsrj Quantity of loaded pallets that are picked up by vehicle v2V at cross dock j2CDout at time t2Tj from supplier s2S bound for retailer r2R. qtvsr Quantity of loaded pallets delivered by vehicle v 2V from supplier s2S to retailer r2R. etvsr Quantity of empty pallets picked up by vehicle v2V at retailer r2R at time t2Tr bound for supplier s2S. ftvs Quantity of empty pallets delivered by vehicle v2V to supplier s2S at time t2Ts. Zprodrs Quantity of unmet demand by retailer r2R for products not delivered from supplier s2S. Zprodrs is expressed in units of pallets. Zpals Number of empty pallets requested by supplier s2S that cannot be delivered. 4.4 Mathematical Model The MILP formulation of this problem may be divided into ve classes of constraints. These include network constraints describing valid routes for each vehicle, supplier con- straints addressing the quantity of goods picked up from each supplier, retailer constraints 26 ensuring appropriate deliver of goods to retailers, backhaul constraints relating empty pallets picked up from retailers to those delivered to suppliers, and cross dock constraints governing the coordination of vehicles at the cross dock locations. In a slight departure from convention, the objective function will be described after an explanation of the necessary constraints. 4.4.1 Network Constraints The following network constraints ensure that each vehicle is assigned to valid routes, starting from the vehicle?s initial location and ending with the last \copy" of each vehicle terminating at a node in 1. These constraints are analogous to those found in traditional vehicle routing problems, and are adapted from the formulation of Murray and Karwan (2010), who studied the problem of unmanned aircraft routing. The rst two network constraints are concerned only with the initial route taken by each vehicle. In other words, only the \original" instance of each vehicle is considered, not \copies." X j2f +nCDing X t2Tj xtv; 0v;j = 1 8v2V0 (4.1) X j2f +: 0v2 vjg X t2Tj t 0, is enroute to supplier s2 (which has an earlier time window), supplier s1 will not be visited. Finally, in a cycle, or wave, only half of the vehicle eet is utilized. For example, if 10 vehicles are available, only 5 vehicles are used in a cycle for pick up and delivery operations while the other 5 vehicles will wait in their 1 nodes. As per the cross dock constraint in 48 the mathematical model, the transfer of pallets at a cross dock must take place from the inbound truck to outbound truck. To facilitate this feature, in this heuristic some vehicles are forced to wait at the cross dock. However in future research, the vehicles waiting at the cross dock can be utilized to make shorter routes, in addition to satisfying the cross dock constraints. This wave phenomenon occurs because all vehicles are assumed to be initially empty. The heuristic begins by initializing several variables. First, the set of all \original" vehicles, V0, is partitioned into two subsets, such that set PV represents the set of all vehicles that are available to be assigned to pickup full pallets from suppliers and set DV is the set of vehicles that are available to pickup goods from a cross dock and deliver these to retailers. These sets are initialized as follows: PV = 1;2;:::; jV0j 2 ; DV = V0nPV: Every cycle will end at the 1 node and a new vehicle ID number is generated for each vehicle at this node. Set DV1 contains the copies of vehicles that are created at the end of function Pickup, and DV2 contains the copies of vehicle created at the end of function DeliveryAndPickup. Next, the initial location and the starting time for each vehicle must be initialized: myPrevNodev = 0v 8v2V0; tv = t0 8v2V0: Third, let D0prodr;s represent the unsatis ed demand of goods by retailer r from supplier s. This value will be updated as the heuristic progresses, and is initialized to equal the corresponding 49 value of Dprodr;s : D0prodr;s = Dprodr;s 8r2R;s2S: Fourth, let A0palr;s represent the unsatis ed demand of empty pallets by supplier s from retailer r. This value will be updated as the heuristic progresses, and is initialized to equal the corresponding value of Apalr;s: A0palr;s = Apalr;s 8r2R;s2S: Finally, to facilitate the coordinated arrival of vehicles at each cross dock, let tmaxj represent the latest time that an active vehicle is assigned to visit cross dock j 2CDin. This value will be updated by the heuristic, and is initialized to equal the starting time interval of the planning horizon: tmaxj = t0 8j2CDin: The remainder of this chapter provides detailed descriptions of the three functions em- ployed by the proposed heuristic. 6.1 The Pickup function Step 1. In this step, each vehicle in set PV will be assigned to pick up full pallets from suppliers. Goods will be loaded onto each of these vehicles until either the vehicle contains no excess capacity, or there are no more goods to pick up. When vehicle v is assigned to visit a particular eligible supplier j2S0, after having previously visited node i2 v;j, the heuristic sets the value of xtv;i;j, where t represents the earliest feasi- ble time that the vehicle can visit node j. Here, the set S0 represents all suppliers that may be visited within their time windows and which hold goods for retailers whose 50 time windows have yet to close. The process of assigning the vehicle to suppliers re- peats until the vehicle has no further suppliers to visit, at which point the vehicle is routed to the nearest cross dock. Once all vehicles have been routed to a cross dock, the vehicles are routed to the appropriate node in set 1, where the vehicle ends its route and is assigned a new vehicle number. for all v2PV do i = myPrevNodev; // Set the initial location for this vehicle. LQv = 0; // Loaded quantity of vehicle v is zero. while LQv >< >>:s2S : tv + v;i;s maxfTsg; X r2R tv maxfTrg D0prodr;s > 0 9 >>= >>;; // Choose the eligible supplier that can be visited earliest. // Break ties by selecting the eligible supplier with the smallest ID: j min s2S0 : minfTsg= min k2S0 fminfTkgg ; // Load goods bound for retailer r from supplier j: for all r2R do if (tv maxfTrg) then LQv LQv+minfD0prodr;j ;cv LQvg; // Update loaded quantity on vehicle v. Qpickv;r;j Qpickv;r;j + minfD0prodr;j ;cv LQvg; // Update quantity picked up. D0prodr;j D0prodr;j Qpickv;r;j; // Update remaining availability. end if end for tv maxftv + v;i;j;minfTjgg; // Find earliest feasible time to visit supplier j. Set xtvv;i;j = 1; // Assign v to visit supplier j at a feasible time. 51 i j; // Update the current location. end while // Find nearest cross dock j2CDin such that v;i;j = min k2CDin f v;i;kg. myCDv j; // Store the node number of the chosen CD for Step 2. myPrevNodev i; // Store the previous node for Step 2. tmaxj maxftmaxj ;tv + v;i;jg; // Update the latest time a vehicle is assigned to this CD. end for Step 2. At this point, we have determined the earliest possible time that each \pickup" vehicle may be routed to a cross dock. Now, we must coordinate the arrival times of these vehicles at each cross dock. After visiting the cross dock, the vehicles are routed to a 1 node to get assigned a new vehicle ID number. Each of the vehicles in set PV, after getting assigned a new number, is added to set DV1. The set DV1 contains the copies of vehicle, and is updated every cycle (when new vehicle copies are generated). Qinj;r;s = 0 8j2CDin;r2R;s2S; // Initialize the quantity of goods arriving at the cross dock. for all v2PV do i myPrevNodev; // Last supplier visited. j myCDv; // Selected cross dock. tv tmaxj ; // Coordinated time for visiting this cross dock. Set xtvv;i;j = 1; // Assign v to visit cross dock at appropriate time. // Route v to the appropriate 1 node, ending its tour: tv tv + v;j; 1j; // Updated time. Set xtvv;j; 1 j = 1; // Assign v to nal node. v0 next copy of vehicle v; tv0 = tv; // Initialize the starting time of vehicle v0. 52 myPrevNodev0 = 1j; // Initialize starting node of v0. // Add the vehicle copy to the set DV1. Set DV1 v0; //Update DV1, to be used in Function Vehicle Copy end for Step 3. In a cross dock, no storage of pallets are allowed, by assumption. Therefore, all pallets brought by the inbound trucks must be transferred to outbound trucks. To satisfy this condition, the total quantity of pallets brought by the inbound trucks should not exceed the total capacity of the outbound trucks at a cross dock. The vehicles are paired, such that if the rst vehicle in set PV reaches CDin1 , then the rst vehicle in set DV should reach CDout1 . To satisfy this condition, rst the quantity of full pallets brought by the inbound trucks to each CDin is calculated, and then the quantity of pallets that can be loaded to the outbound trucks is calculated. The excess pallets (i.e., the di erence between the loaded quantity of vehicles and the capacity of their paired vehicle at a particular cross dock) that cannot be loaded to outbound trucks are added back to D0prodr;j . For example, if 25 pallets are brought by vehicle 1 and 28 by vehicle 2 to CDin1 , and if the maximum capacity of both outbound truck is 26 pallets each, then the di erence in capacity of 1 pallet (i.e., 26+26-28-25) is again added back to the respective D0prodr;j value. // Initialize the quantity of pallets in CD QCDoutj = 0 8j2CDout; // Initialize the quantity of goods in the cross dock out. // Calculate the full pallets brought to CDin and quantity that can be loaded at CDout for all v2PV do for all v02DV do if (v and v? are the nth vehicle in the sequence) then j myCDv; // Selected cross dock. QCDinj = QCDinj + LQv; // Update quantity in CDin 53 QCDoutj = QCDoutj + Cv0; // Update available capacity at CDout end if end for end for // Transfer the excess capacity to D0prodr;s . for all v2PV do for all j2CDin do while ((QCDinj >QCDoutj )) do // Choose the eligible supplier to update the D0prodb;a value // Break ties by selecting the eligible supplier with the largest ID: a max s2S : minfTsg= max k2S fminfTkgg ; // Choose the eligible retailer to update the D0prodb;a value // Break ties by selecting the eligible retailer with the largest ID: b max r2R : minfTrg= max n2R fminfTngg ; if ((QCDinj QCDoutj ) Qpickv;b;a) then // If full pallets picked up at a supplier for a retailer is less than the quantity to be transferred, then D0prodb;a D0prodb;a + Qpickv;b;a; // Update the D0prodb;a value QCDinj QCDinj - Qpickv;b;a ; // Update the full pallet capacity at CDin Qpickv;b;a =0; // Update the full pallet quantity picked up. else // If full pallets picked up at a supplier for a retailer is greater than the quantity to be transferred, then D0prodb;a D0prodb;a + (QCDinj - QCDoutj ); // Update the D0prodb;a value QCDinj QCDinj - (QCDinj - QCDoutj ) ; // Update the full pallet capacity at CDin 54 Qpickv;b;a Qpickv;b;a - (QCDinj - QCDoutj ) ; // Update the full pallet quantity picked up. end if end while end for end for //Update the quantity of goods arriving at CD Qinj;r;s = 0 8j2CDin;r2R;s2S; // Initialize the quantity of goods arriving at the cross dock. for all v2PV do j myCDv; // Selected cross dock. for all r2R do for all s2S do Qinj;r;s Qinj;r;s +Qpickv;r;s; // Update quantity of goods arriving at cross dock. end for end for end for 6.2 The DeliveryAndPickup function Step 1. In this step, goods are rst transferred from the unloading to loading bay of the cross dock. Then, each vehicle in set DV will be assigned to pick up full pallets from the cross dock. For example, if there are two cross docks and, from the previous function, if two vehicles reach CDin1 and three vehicles reach CDin2 , then in this function two vehicles should be routed to CDout1 and three vehicles to CDout2 . The vehicles should reach the corresponding cross dock at time tmaxj , j2CD. Goods are then loaded onto each of these vehicles until either the vehicle contains no excess capacity, or there are no more goods to pick up. The set R0 represents all retailers that should be visited to 55 deliver the full pallets. At the cross dock, goods are rst loaded for the retailer with the earliest time window. After goods are loaded, the heuristic rst sets the value of xtv;i;j for vehicles with LQv > 0, where t represents the coordinated time for visiting the cross dock, and i is the previous node for the vehicle, and j2CDout. Next, for all vehicles such that LQv = 0, the heuristic sets the value of xtv;i;j in Step 4. Here i and j refer to the 1 node. Only vehicles which are loaded with full pallets must start the route. A variable, Counterv, is introduced to di erentiate the loaded and unloaded vehicles. Counterv is initialized as 1 if the vehicle is loaded, and as 0 if the vehicle is not loaded. // Transfer the goods from CDin to CDout for all k2CDin do for all l2CDout do if (k and l are the CDin and CDout values of same cross dock) then for all r2R do for all s2S do Qoutl;r;s Qink;r;s ; // Transfer goods from CDin to CDout. end for end for // Find the appropriate CD for vehicles. for all v02PV do for all v2DV do i myPrevNodev; // Set the initial location for this vehicle. LQv = 0; // Loaded quantity of vehicle v is zero. if (v and v? are the nth vehicle in the sequence) then if (k == myCDinv0) then myCDoutv l; // Initialize the Cross dock. j myCDoutv ; // Initialize the Cross dock. 56 tmaxj tmaxk ; // Assign the max time value at CDout tv tmaxj ; // Coordinated time for visiting this cross dock // Load goods bound for retailer r from CD: // De ne the set of eligible retailers R0 = ( r2R : X s2S X l2CDout Qoutl;r;s > 0 ) ; for all r2R0 do for all s2S do while LQv 0) then Set xtvv;i;j = 1; // Assign v to visit cross dock at appropriate time. myPrevNodev j; // Set the previous node for Step 2. Counterv = 1; // Initialize the Counterv value. end if if (LQv == 0) then Counterv = 0; // Initialize the Counterv value. end if end if end if end for end for 57 end if end for end for Step 2. In this step, each vehicle in set DV will be assigned to deliver full pallets and pick up empty pallets at retailers. Goods will be loaded onto each of these vehicles until either the vehicle contains no excess capacity, or there are no more empty pallets to pick up. When vehicle v is assigned to visit a particular eligible retailer j2R0, after having previously visited node i2 v;j, the heuristic sets the value of xtv;i;j, where t represents the earliest feasible time that the vehicle can visit node j. Here, the set R0 represents all retailers for whom the full pallets are picked up. The process of assigning the vehicle to retailers repeats until all the full pallets picked up by the vehicles are delivered. Empty pallets are only picked up from the retailers who also receive full pallets. After all the full pallets are delivered, the vehicles are routed to the appropriate nodes in the set +v . for all v2DV do if (Counterv > 0) then // Choose the eligible retailer that can be visited earliest from set R?. // Break ties by selecting the eligible retailer with the smallest ID: j min r2R0 : minfTrg= min k2R0 fminfTkgg ; t0v=maxf(tv + vij), minfTjgg; if (t0v maxfTjg) then // Deliver full pallets to retailers. for all s2S do if (Qpickv;j;s > 0) then LQv LQv Qpickv;j;s; // Update loaded quantity in vehicle Qpickv;j;s 0; // Reset the full pallet quantity to zero // If current time is less than the maximum time interval at S 58 if (t0v maxfTsg) then // Pick up empty pallets at retailers. if (A0palj;s > 0) then while LQv 0) then // De ne the sets of eligible suppliers S00 = ( s2S : X r2R X v2DV Qemptyv;r;s > 0 ) ; S000 = ( s2S : X r2R X v2DV Qemptyv;r;s = 0 ) ; // Deliver empty pallets to suppliers in set S00 and pick up full pallets. // Choose the eligible supplier that can be visited earliest from set S". // Break ties by selecting the eligible retailer with the smallest ID: j min s2S00 : minfTsg= min k2S00 fminfTkgg ; t0v=maxf(tv + vij), minfTjgg; if (t0v maxfTjg) then for all r2R do if (Qemptyv;r;j > 0) then LQv LQv Qemptyv;r;j ; // Update loaded quantity in vehicle 60 Qemptyv;r;j 0; // Reset the empty pallet quantity to zero // Load goods bound for retailer r from supplier j: while (LQv 0) then LQv = LQv Qemptyv;r;s ; // update the loaded quantity Qemptyv;r;s = 0; // Assign empty pallet quantity to zero end if end for end for // Pick up full pallets from suppliers in set S000. // Choose the eligible supplier that can be visited earliest from set S000. // Break ties by selecting the eligible retailer with the smallest ID: j min s2S00 : minfTsg= min k2S000 fminfTkgg ; t0v =maxf(tv + vij), minfTjgg; if (t0v maxfTjg) then for all r2R do if (t0v maxfTrg) then while LQv 0;j2S000) then i myPrevNodev; // Set the previous node for Step 3. tv maxf(tv + vij), minfTjgg; // Coordinated time for visiting this supplier Set xtvv;i;j = 1; // Assign v to visit supplier at appropriate time. myPrevNodev j; // Set the previous node for Step 4. end if end for end if end if end for Step 4. In this step, each vehicle in set DV is routed to either a 1 node or the nearest CDin. If LQv = 0, the vehicle is routed to 1. If LQv > 0, the vehicle is routed to CDin. In cases where the vehicle is routed to CDin, after delivering goods at CDin, the vehicles are routed to the appropriate node in set 1. Each vehicle ends its route at the 1 node, where it is assigned a new vehicle number. for all v2DV do if (LQv = 0) then i myPrevNodev; // Store the previous node for Step 4. // Find nearest node, j2 1, such that v;i;j = min k2 1 f v;i;kg. tv ftv + v;i;jg; // Update the latest time a vehicle is assigned to this 1 node. Set xtvv;i;j = 1; // Assign v to visit cross dock at appropriate time. v0 Next copy of vehicle v; 63 tv0 = tv; // Initialize the starting time of vehicle v0. myPrevNodev0 = 1j; // Initialize starting node of v0. end if if (LQv > 0) then // Find nearest cross dock j2CDin such that v;i;j = min k2CDin f v;i;kg. myCDv j; // Store the node number of the chosen CD for Step 4. myPrevNodev i; // Store the previous node for Step 4. tmaxj maxftmaxj ;tv + v;i;jg; // Update latest time a vehicle is assigned to this CD. // At this point, we have determined the earliest possible time that each \pickup" vehicle may be routed to a cross dock. Now, we must coordinate the arrival times of these vehicles at each cross dock. Qinj;r;s = 0 8j2CDin;r2R;s2S; // Initialize the quantity of goods arriving at the cross dock. i myPrevNodev; // Last supplier visited. j myCDv; // Selected cross dock. tv tmaxj ; // Coordinated time for visiting this cross dock. Set xtvv;i;j = 1; // Assign v to visit cross dock at appropriate time. // In a cross dock, no storage of pallets are allowed, so all the pallets brought by the inbound trucks should be transferred to outbound trucks. Thus, the total quantity of pallets brought by the inbound trucks should not exceed the total capacity of the outbound trucks at a cross dock. To satisfy this condition, the heuristic adds the di erence in quantity to D0prodr;j . QCDinj = 0 8j2CDin; // Initialize the quantity of goods in the cross dock in. QCDoutj = 0 8j2CDout; // Initialize the quantity of goods in the cross dock out. for all v2DV do 64 for all v02DV2 do if (v and v?, are the nth vehicle in the sequence) then QCDinj = QCDinj + LQv; // Update quantity in CDin QCDoutj = QCDoutj + Cv0; // Update available capacity at CDout end if end for end for for all v2DV do for all j2CDin do while ((QCDinj >QCDoutj )) do // Choose the eligible supplier to be visited // Break ties by selecting the eligible supplier with the largest ID: a max s2S : minfTsg= max k2S fminfTkgg ; // Choose the eligible retailer to be visited // Break ties by selecting the eligible retailer with the largest ID: b max r2R : minfTrg= max n2R fminfTngg ; if ((QCDinj QCDoutj ) Qpickv;b;a) then // If full pallets picked up at a supplier for a retailer is less than the quantity to be transferred, then D0prodb;a D0prodb;a + Qpickv;b;a; // Update the D0prodb;a value QCDinj QCDinj - Qpickv;b;a ; // Update full pallet capacity at CDin Qpickv;b;a =0; // Update full pallet quantity picked up. else D0prodb;a D0prodb;a + (QCDinj - QCDoutj ); // Update the D0prodb;a value QCDinj QCDinj - (QCDinj - QCDoutj ) ; // Update the full pallet capacity at CDin 65 Qpickv;b;a Qpickv;b;a - (QCDinj - QCDoutj ) ; // Update the full pallet quantity picked up. end if end while end for end for // Update quantity of goods arriving at cross dock Qinj;r;s = 0 8j2CDin;r2R;s2S; // Initialize quantity of goods arriving at the CD. for all r2R do for all s2S do Qinj;r;s Qinj;r;s +Qpickv;r;s; // Update quantity of goods arriving at cross dock. end for end for // Route v to the appropriate 1 node, ending its tour: tv tv + v;j; 1j; // Updated time. Set xtvv;j; 1 j = 1; // Assign v to nal node. v0 next copy of vehicle v; tv0 = tv; // Initialize the starting time of vehicle v0. myPrevNodev0 = 1j; // Initialize starting node of v0. end if // Add the vehicle copy to the set DV2. set DV2 v0; // Update set DV2, to be used in VehicleCopy function end for 66 6.3 The VehicleCopy function Step 1. In this step, rst the contents of set DV are updated with the values in set DV1. Next, the contents of setDV1 are replaced by setDV2. The function DeliveryAndPickup is repeated with the updated DV. This process continues until all vehicle copies are used. Let numCopy be the number of vehicle copies and numCycle be the number of cycles that function DeliveryAndPickup should be repeated. numCycle = numCopy * 2; for all numCycle do // Transfer the contents of set DV1 to set DV DV DV1 // Transfer the contents of set DV2 to set DV1 DV1 DV2 Execute function DeliveryAndPickup; end for The idea behind the development of this heuristic is the expectation that, if the xtvij values for each vehicle are added as constraints to the existing model, then CPLEX would determine the pick up and delivery quantities for vehicles at the retailer and supplier nodes in the network. The initial solution heuristic can be improved by using metaheuristic approaches, such as tabu search, to select among candidate routes for each vehicle. 67 Chapter 7 Numerical Analysis This chapter contains a numerical analysis on generated test problems for the math- ematical model. First, analysis is performed for test problems solved via CPLEX. Next, analysis is conducted on test problems solved using CPLEX with the incorporation of the heuristic proposed in the previous chapter. In addition, a procedure to develop test problems is discussed. Numerical analysis helps to identify the time taken to solve the problem, to compare the solutions generated using the heuristic against CPLEX, and to suggest possible improvements to be incorporated in future research. 7.1 Generation of Test Problems The examples provided in the literature do not provide su cient numerical values for all of the input parameters required for this thesis work. Therefore, the input parameters are programmed to generate randomly using the software Octave, version 3.2.4. Table 7.1 shows how input parameter values are created. 68 Parameter Value jRj Hard coded jSj Hard coded jCDj Hard coded jV0j Hard coded jV00vj, where v2V0 Hard coded Hard coded Cv U(24,30) Speed of V U(50,70) [miles/hr] Dprodrs U(l,u) Apalrs U(0,40) x coordinate for nodes U(0,500)[miles] y coordinate for nodes U(0,500)[miles] vij Programmed to calculate Table 7.1: Input parameters The parameter values for the number of retailers, suppliers, cross docks, vehicles, number of vehicle copies, and are hard-coded in the program in order to test the model under di erent scenarios. The capacity and speed of each vehicle is randomly generated and follow a uniform distribution. The demand of full pallets, Dprodrs , follows a uniform distribution, U(l,u), where the lower limit (l) is assumed to be 0 and the upper limit (u) is calculated using the following expression. In the expression, UDemand represents the total demand value at the upper limit: UDemand = (# of vehicle copies) * X v2V0 Cv; Upper limit = UDemand/(# of retailers * # of suppliers): 69 The demand of empty pallets Apalrs , is randomly generated for each supplier/retailer combination and follows a uniform distribution. The location of the nodes in the network are represented as (x;y) coordinates. Depending on the number of nodes in the network, separate (x;y) coordinates are generated randomly for each node and follow a uniform distribution. With the help of the coordinates, the distance between two nodes in the network is calculated. The speed of each vehicle is randomly generated and the average speed of all vehicles is assumed to have a lower limit of 50 [miles/hr] and an upper limit of 70 [miles/hr], and follows a uniform distribution. With the two data (i.e., the distance between two nodes and average speed of the vehicle), vij values, which represent the travel time by vehicle v from node i to destination node j, are calculated. Table 7.2 shows how the lower limit and the upper limit for the time intervals are randomly generated. One time interval is assumed to be 15 minutes. (i.e., for one hour, four time intervals are considered). The upper limit for the suppliers are considered higher than the retailers to facilitate the back haul operation. Parameter Time Interval Time Interval Lower Limit Upper Limit Retailer U(5,7) U(16,18) Supplier U(4,6) U(21,23) Cross Dock 1 24 1 1 24 Table 7.2: Time interval Tj All the parameter values are randomly generated only for the calculation purposes. Any user can vary the lower and upper limits and the hard coded values to suit a particular scenario. 70 7.2 Initial Solution Scheme Using the aforementioned problem generator, 30 \small" test problems were created for problem sizes shown in Table 7.3, where j j represents the cardinality of the given set. Ten problems were generated for each row of this table. Average # of Average # of jRj jSj jVj Copies jCDj Decision Variables Constraints 5 3 3 1 1 77,486 22,190 10 6 5 1 1 281,044 67,494 20 10 10 1 2 3,130,490 * Table 7.3: Summary of small problem sizes CPLEX was unable to nd a feasible solution to any of the 30 problem instances within 30 minutes. The reason might be due to the large number of decision variables and con- straints. In Table 7.3, columns 6 and 7 give the average number of decision variables and constraints developed for the test problems. It can be inferred that, as the size of the test problem increases, the number of decision variables and constraints also increases drastically. On average, approximately 3 million decision variables were required for problems with 20 retailers. CPLEX, in the process of solving the problem with 20 retailers, encountered computer memory issues. One reason for this computer memory issue might be due to large number of decision variables. Because of this memory issue, CPLEX was not able to generate the constraints required to nd a solution to 20-retailer problems. Next, the problems were tested with the heuristic explained in Chapter 6. Although the proposed heuristic cannot solve the computer memory issues for larger problems, it was expected to give a solution to smaller problems. 71 Average # of Average # of Average jRj jSj jVj Copies jCDj Decision Variables Constraints Run Time [sec] 5 3 4 1 1 77,486 22,190 5.923 10 6 4 1 1 281,044 67,494 37.395 20 10 10 1 2 3,130,490 * * Table 7.4: Summary of heuristic solution Table 7.4 shows the summary of results for the problems solved with the help of the pro- posed heuristic. Using the heuristic, CPLEX was able to nd the solution for test problems with 5 and 10 retailers. Column 8 in Table 7.4 shows the average time taken to solve the problem. An average time of approximately 6 seconds to solve problems with 5 retailers is found to be reasonable. However, for problems with 10 retailers, the average run time of 37 seconds is very high. Because the solution developed by the heuristic is only an initial solu- tion, in future research, this solution should be used in a metaheuristic approach to develop better solutions. For every iteration in a metaheuristic approach, CPLEX should be used to check whether the solution developed is a better solution. For example, if a metaheuristic approach performs 100 iterations, then the solution time will be 3700 seconds, which will be approximately 1 hour. For larger problems, the solution time may increase signi cantly. The results for all the individual problems of 5 and 10 retailers are shown in Tables 7.5 and 7.6. For some problems it can be noted that the size of the objective function value is high. For these problems we may infer that some of the nodes are not visited within the given time windows. To reduce the number of undelivered full pallets and empty pallets to their destination nodes, one solution is to increase the number of original vehicles in the system. Column 6 refers to the average number of time intervals considered in each node. Column 7 gives the details of average time window size in percentage. It can be inferred that, for 5-retailer problems, on average, each node is open for delivery or pick up 67% of the available time. For 10-retailer problems, this gure is 61%. The average number of time intervals is calculated by taking into consideration retailer, supplier, CDin, CDout, and 1 72 nodes. The CD and 1 nodes are open for almost the entire time period. So, when average time window size is calculated only taking into consideration supplier and retailer node, the average time window size is only 53%. Test Objective Solution # of decision # of Avg. # of Avg. Time Problem # Function Value Time [sec] Variables Constraints Time Int. Window Size [%] 1 6165 6.681834 77474 22198 63.6363 66.28 2 174 4.680644 76834 22070 70.5454 73.48 3 210 5.122504 76322 22006 62.5454 65.15 4 3323 5.83187 78434 22324 64.3636 67.05 5 10136 5.964095 77474 22197 63.6363 66.28 6 112 7.498031 78818 22389 64.7272 67.42 7 10957 6.281562 77026 22133 63.2727 65.90 8 10517 5.045159 75874 21941 62.1818 64.77 9 176 5.550253 77026 22133 63.2727 65.90 10 2122 6.573162 79586 22516 65.4545 68.18 Table 7.5: Details of heuristic performance on problems with 5 retailers Test Objective Solution # of decision # of Avg. # of Avg. Time Problem # Function Value Time [sec] Variables Constraints Time Int. Window Size [%] 1 8803 72.470761 279562 67363 58.9474 61.40 2 14713 31.846418 277098 67167 58.3157 60.74 3 15047 27.31317 280042 67424 59.1578 61.22 4 15831 32.395646 282634 67617 59.7894 62.28 5 13824 34.230393 283370 67683 60.0000 62.50 6 17061 32.975578 280906 67484 59.3684 61.84 7 17847 34.551907 284714 67806 60.4210 62.93 8 11117 31.887243 281034 67488 59.3684 61.84 9 17070 44.365912 280042 67419 59.1578 61.62 10 15009 31.912833 281034 67490 59.3684 61.84 Table 7.6: Details of heuristic performance on problems with 10 retailers 73 Two main problems that were experienced in this modeling approach are computer memory issues and long runtimes to solve the problem. Some of the recommendations to address these issues are as follows. First, in order to solve the problem related to computer memory issues, the mathematical problem must be modeled with fewer decision variables. If the number of decision variables is reduced, the memory space consumed may also be reduced. Second, the problem should have narrow time windows. For the test problems, the average time window size considered is approximately 63%. If the time windows are narrowed, then the number of decision variables in the model will get reduced. Third, the current model has a time slice for every 15 minutes. If the time slice is increased (i.e, a time slice for every 30 minutes or 1 hour), then the number of decision variables may also be reduced. Fewer decision variables may in turn reduce the time taken to solve the problem. From this numerical analysis, it can be concluded that a more e cient mathematical model must be developed with fewer decision variables. This may help to overcome the computer memory problems, and may reduce the time taken to solve the problem. 74 Chapter 8 Conclusions & Future Research 8.1 Conclusions The research work tries to integrate the vehicle routing problem in a cross docking en- vironment, to provide better utilization of the vehicle eet. This research introduces new formulations to solve vehicle routing problem with pick up during the linehaul operation and delivery during the backhaul operation. The entire problem is based on a cross docking environment with allowable split deliveries and time window constraints using a heteroge- neous eet. The research work carried out to date by various authors addresses the VRP model with cross docks with only a subset of the di erent characteristics mentioned above. In this research work the mathematical model is developed using all of the above mentioned characteristics. The goal of this research work is to build a mathematical model with the above mentioned criteria and to produce a feasible solution. The problem is modeled as a mixed integer linear programming (MILP) model. The model was validated using CPLEX. During the validation stage it was found that CPLEX was not able to solve the problem within the test time of 30 minutes. However, it was found that if the schedules were modeled as constraints to the model, CPELX was able to nd a feasible solution to the problem (although not optimal) and it was able to determine the quantity of full and empty pallets that must be transferred from one node to another. This motivated the need to develop a heuristic solution approach. The goal of the heuristic was to determine feasible routes and schedules for every vehicle in the system. The output of the heuristic is a collection of xtvij values, where i is the starting node and j is the destination node of vehicle v, and t is the time the vehicle reaches node j. These xtvij values are treated as constraints of the model, in addition to the already existing node and network constraints. 75 A sample problem was generated as an example to demonstrate the di erent features in the model. A procedure to develop the test problems is described in this thesis, as well. The existing literature does not provide test problems with numerical values for all of the parameter values described in this model, thus forcing the development of a procedure to generate test problems with maximum exibility. Numerical analysis was conducted on three sets of test problems with retailer node sizes of 5, 10 and 20. Each set contained 10 test problems, totalling 30 test problems. All of the test problems were rst solved using CPLEX with a maximum run time of 30 minutes. CPLEX was not able to nd a feasible solution. Next, all of the problems were solved using CPLEX with the help of the heuristic and CPLEX was able to nd solutions for problem sizes of 5 and 10 retailers. During this stage computer memory issues were encountered when large problems were solved. Recommendations for overcoming the computer memory issues were also discussed. At the end of the numerical analysis, it was concluded that the present mathematical model and the developed heuristic work well for the small problem sizes, but there is a need for a better model with fewer decision variables and time intervals to solve larger problems. 8.2 Future Research The research work can be extended by incorporating metaheuristic approaches to solve the problem, and by developing a mathematical model with fewer decision variables. Instead of empty pallets that are considered in this model, a more realistic reverse logistic operation of transporting returned or damaged products back to the supplier for service or replacement can be considered. Currently, constant transfer time is assumed for transferring pallets at the cross dock, regardless of the quantity of pallets transferred or the location of the inbound and outbound trucks. In future research, more realistic transfer time of pallets can be introduced to the model depending on the number of pallets to be transferred and travel time of pallets from 76 the inbound to outbound doors of the cross dock. Moreover, the model can be improved by including a separate optimization procedure to assign trucks to the cross dock to reduce the travel time of pallets inside the cross dock. Currently, by assumption, there is no space to store inventory in the cross dock and pal- lets must be transferred directly from the inbound trucks to the outbound trucks. To satisfy this condition, a group of trucks are scheduled for simultaneous arrival and departure. This constraint can be improved by allowing storage of inventory at the cross dock. This requires constraints that limit the quantity of goods in inventory and also limit the length of time that these goods remain in the cross dock. This also requires modifying the current model to allow transfer of goods without requiring all trucks to be at the cross dock simultaneously. As a result, vehicle utilization may be improved. 77 Bibliography U.M. Apte and S. Viswanathan. E ective cross docking for improving distribution e ciencies. International Journal of Logistics Research and Applications, 3(3):291{302, 2000. ISSN 1367- 5567. Nils Boysen and Malte Fliedner. Cross dock scheduling: Classi cation, literature review and re- search agenda. Omega, 38(6):413 { 422, 2010. ISSN 0305-0483. P. Chen, Y. Guo, A. Lim, and B. Rodrigues. Multiple crossdocks with inventory and time windows. Computers & operations research, 33(1):43{63, 2006. S.M. Disney, A.T. Potter, and B.M. Gardner. The impact of vendor managed inventory on transport operations. Transportation Research Part E: Logistics and Transportation Review, 39(5):363{ 380, 2003. ISSN 1366-5545. Y. Dong and K. Xu. A supply chain model of vendor managed inventory. Transportation Research Part E: Logistics and Transportation Review, 38(2):75{95, 2002. D. Gulczynski, B. Golden, and E. Wasil. The multi-depot split delivery vehicle routing prob- lem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, 2011. M. Gumus and J.H. Bookbinder. Cross-docking and its implications in location-distribution sys- tems. Journal of Business Logistics, 25(2):199{228, 2004. M. Hammer. Deep change. Harv Bus Rev, 82:84{93, 2004. J.C. Johnson and D.F. Wood. Contemporary logistics. The Macmillan series in marketing. Macmil- lan, 1990. ISBN 9780023608414. R. Kaipia, J. Holmstrom, and K. Tanskanen. Vmi: What are you losing if you let your customer place orders? Production Planning & Control, 13(1):17{25, 2002. 78 V.B. Kreng and F.T. Chen. The bene ts of a cross-docking delivery strategy: a supply chain collaboration approach. Production Planning & Control, 19(3):229{241, 2008. ISSN 0953- 7287. Y.H. Lee, J.W. Jung, and K.M. Lee. Vehicle routing scheduling for cross-docking in the supply chain. Computers & Industrial Engineering, 51(2):247{256, 2006. ISSN 0360-8352. C.J. Liao, Y. Lin, and S.C. Shih. Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications, 37(10):6868{6873, 2010. ISSN 0957-4174. A. Lim, Z. Miao, B. Rodrigues, and Z. Xu. Transshipment through crossdocks with inventory and time windows. Naval Research Logistics (NRL), 52(8):724{733, 2005. H. Ma, Z. Miao, A. Lim, and B. Rodrigues. Crossdocking distribution networks with setup cost and time window constraint. Omega, 39(1):64{72, 2011. Z. Miao, F. Yang, K. Fu, and D. Xu. Transshipment service through crossdocks with both soft and hard time windows. Annals of Operations Research, pages 1{27, 2010. A. Mingozzi, S. Giorgi, and R. Baldacci. An exact method for the vehicle routing problem with backhauls. Transportation Science, 33:315{329, 1999. ISSN 0041-1655. C.C. Murray and M.H. Karwan. An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations. Naval Research Logistics (NRL), 2010. R. Musa, J.P. Arnaout, and H. Jung. Ant colony optimization algorithm to solve for the trans- portation problem of cross-docking network. Computers & Industrial Engineering, 59(1): 85{92, 2010. ISSN 0360-8352. J. Priv e, J. Renaud, F. Boctor, and G. Laporte. Solving a vehicle-routing problem arising in soft- drink distribution. Journal of the Operational Research Society, 57(9):1045{1052, 2005. ISSN 0160-5682. R. Sabath. Volatile demand calls for quick response: the integrated supply chain. Logistics Infor- mation Management, 8(2):49{52, 1995. R. Soltani and S.J. Sadjadi. Scheduling trucks in cross-docking systems: A robust meta-heuristics approach. Transportation Research Part E: Logistics and Transportation Review, 46(5):650{ 666, 2010. ISSN 1366-5545. 79 CS Sung and SH Song. Integrated service network design for a cross-docking supply chain network. Journal of the Operational Research Society, 54(12):1283{1295, 2003. P. Toth and D. Vigo. An exact algorithm for the vehicle routing problem with backhauls. Trans- portation Science, 31:372{3852, 1997. ISSN 0041-1655. M.A. Waller, C.R. Cassady, and J. Ozment. Impact of cross-docking on inventory in a decentralized retail supply chain. Transportation Research Part E: Logistics and Transportation Review, 42 (5):359{382, 2006. ISSN 1366-5545. M. Wen, J. Larsen, J. Clausen, J.F. Cordeau, and G. Laporte. Vehicle routing with cross-docking. Journal of the Operational Research Society, 60(12):1708{1718, 2008. ISSN 0160-5682. R.A. Wilson. Transportation in America. Eno Transportation Foundation, 19 edition, 2002. C.A. Yano, T.J. Chan, L.K. Richter, T. Cutler, K.G. Murty, and D. McGettigan. Vehicle routing at quality stores. Interfaces, pages 52{63, 1987. ISSN 0092-2102. Y. Zhong and E.H. Aghezzaf. Combining dc-programming and steepest-descent to solve the single- vehicle inventory routing problem. Computers & Industrial Engineering, 2011. 80