ii 
 
 
 
 
 
 
ABSTRACT 
 
 
 
 
Title of Document: THE INVENTORY ROUTING PROBLEM 
WITH THIRD PARTY LOGISTICS  
  
 Hadi Sadrsadat, 2012 
  
Directed By: Professor Ali Haghani 
Department of Civil and Environmental 
Engineering 
 
 
There are two key planning issues in supply chain: inventory management and 
transportation. In this research, the inventory control and transportation of syrup 
concentrate and final products for one bottling company working for a beverage 
company is studied. Operation of most of beverage companies is based on a 
franchised distribution system. In this operation, syrup concentrate is produced by a 
beverage company and sold to bottlers. Bottlers, in turn, mix the syrup concentrate 
with different ingredients to produce various products and distribute them to retailers.   
Unsatisfied orders have several harmful effects on the bottling company. The bottling 
company may not satisfy all demands due to its small fleet size, which is not able to 
cover all deliveries in the right timeframe. One method for preventing missed orders 
is sending orders to some retailers in advance to hold for future use. This allows the 
fleet to be free to service the rest of the retailers. This policy is possible if those 
retailers have available capacity to keep products. Another way to deal with this 
 
iii 
 
problem is by renting vehicles, which increases the fleet size. The last option for 
delivering to a retailer when the owned fleet is not able to do so is outsourcing 
shipping and/or warehousing.  The bottling company contracts with a Third Party 
Logistics Provider (TPLP), who is responsible for delivery of final products to some 
of the bottler?s retailers. Also, TPLPs can store commodities in their warehouses and 
deliver products to retailers at the right time if there is no available capacity in the 
bottler?s warehouses.  
This problem belongs to Inventory Routing Problem (IRP) with some new 
features such as options for rental vehicle and TPLPs. IRP is a well-studied problem 
in Operation Research but most of the studies take a single period into account. In 
contrast, the proposed model in this study includes several time steps in which a 
decision in one time step can affect future time steps. The proposed model is a multi-
 tier, multi-plant, multi-warehouse, and multi-product model which considers non-
 homogeneous fleet. No model in the literature considers all of these characteristics 
simultaneously.  
In this research heuristic methods are developed to solve large problems for 
which optimization packages cannot find even a feasible solution. Two heuristic 
methods are proposed for this problem, which are based on fix-and-run algorithm. 
Three improvement phases are also developed to enhance the final solution of 
heuristics. The proposed heuristic methods in this research can find an appropriate 
feasible solution with only a small gap from an upper bound and in reasonable 
running time. 
 
 
 
iv 
 
 
 
 
 
 
 
 
 
 
 
THE INVENTORY ROUTING PROBLEM WITH THIRD PARTY LOGISTICS    
 
 
 
By 
 
 
Hadi Sadrsadat 
 
 
 
 
 
Dissertation proposal submitted to the Faculty of the Graduate School of the  
University of Maryland, College Park, in partial fulfillment 
of the requirements for the degree of 
Doctor of Philosophy 
2012 
 
 
 
 
 
 
 
 
 
 
Advisory Committee: 
Professor Ali Haghani, Chair 
Professor Paul M. Schonfeld 
Professor Philip T. Evers 
Professor Martin Dresner 
Professor Cinzia Cirillo 
 
 
 
v 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
?Copyright by 
Hadi Sadrsadat 
2012 
 
 
ii 
 
 
 
 
Acknowledgements 
 
I would like to express my sincere gratitude to my advisor, Prof. Ali Haghani 
who offered invaluable assistance, guidance, and support throughout my Ph.D. 
studies in the University of Maryland. His valuable advice was remarkably helpful to 
the success of this research. Also a special appreciation is acknowledged to Prof. 
Philip Evers for his helpful instructions and suggestions through this research. Thanks 
are extended to the other committee members Prof. Paul Schonfeld, Prof. Martin 
Dresner, and Prof. Cinzia Cirillo for their guidance and support during the completion 
of this dissertation. 
I offer my regards to my friends, especially Dr. Masoud Hamedi and Kaveh 
Farokhi Sadabadi for the help and support they provided me. Also, with deep sense of 
gratitude, I would like to express my thanks to my parents, my brother and his lovely 
wife. Their love, patience, and support have helped me significantly to finish this 
study. Finally, and most importantly, I would like to express my thanks to my lovely 
wife and my best friend, Elham, for her valuable help and support. We started our 
journey 8 years ago and every second of this journey she stood by me patiently. This 
dissertation would never have been completed without the support and 
encouragement of my beloved family. 
I also would like to express my thanks to FICO Corporation for providing 
Xpress 7.1 for this research. This software added remarkable value to this study. 
  
iii 
 
Table of Contents 
 
 
Acknowledgements ....................................................................................................... ii 
Table of Contents ......................................................................................................... iii 
List of Tables ............................................................................................................... vi 
List of Figures .............................................................................................................. ix 
Chapter 1: Introduction ................................................................................................. 1 
1.1. Supply Chain ...................................................................................................... 1 
1.2. A Beverage Company?s Supply Chain .............................................................. 3 
1.3. Problem Description .......................................................................................... 5 
1.4. Motivation for and Objective of the Research ................................................... 8 
1.5. Contributions of the Research .......................................................................... 10 
1.6. Organization of the Dissertation ...................................................................... 11 
Chapter 2: Literature Review ...................................................................................... 13 
2.1. Supply Chain .................................................................................................... 13 
2.2. Inventory Routing Problem (IRP) .................................................................... 16 
2.2.1. IRP Classifications .................................................................................... 18 
2.2.2. IRP Literature............................................................................................ 20 
2.2.3. Conclusions ............................................................................................... 30 
2.3. Third Party Logistics Provider ......................................................................... 31 
2.3.1. Introduction ............................................................................................... 31 
2.3.2. TPLP Literature ........................................................................................ 32 
2.3.3. Conclusions ............................................................................................... 37 
Chapter 3: Problem Description and Formulation ...................................................... 38 
3.1. Problem Description ........................................................................................ 38 
3.2. Modeling Approach ......................................................................................... 42 
3.3. Assumptions ..................................................................................................... 43 
3.4. Mathematical Formulation ............................................................................... 45 
3.4.1. Sets ............................................................................................................ 45 
3.4.2. Parameters ................................................................................................. 46 
3.4.3. Decision Variables .................................................................................... 50 
3.4.4. Objective Function .................................................................................... 52 
3.4.5. Constraints ................................................................................................ 53 
3.5. Summary .......................................................................................................... 64 
Chapter 4: Numerical Study........................................................................................ 69 
4.1. Design of Sample Problems ............................................................................. 69 
4.1.1. Planning Horizon and Time Step .............................................................. 69 
4.1.2. Facility Locations...................................................................................... 70 
4.1.3. Network..................................................................................................... 71 
4.1.4. Supply and Demand .................................................................................. 71 
4.1.5. Vehicles..................................................................................................... 74 
4.1.6. Third Party Logistics Providers ................................................................ 75 
4.2. Numerical Results ............................................................................................ 75 
4.2.1. Scenario 1.................................................................................................. 76 
4.2.2. Scenario 2.................................................................................................. 80 
iv 
 
4.2.3. Scenario 3.................................................................................................. 83 
4.2.4. Scenario 4.................................................................................................. 85 
4.2.5. Scenario 5.................................................................................................. 88 
4.2.6. Scenario 6.................................................................................................. 90 
4.3. Summary .......................................................................................................... 91 
Chapter 5: The First Heuristic Approach .................................................................... 95 
5.1. Branch-and-Bound Algorithm ......................................................................... 95 
5.2. Fix-and-run Algorithm ..................................................................................... 98 
5.3. Applying a Fix-and-Run Algorithm to the Proposed Model ........................... 99 
5.4. Fix-and-Run Algorithm Steps (Heuristic 1) .................................................. 100 
5.4.1. Step 1: Removing Unnecessary TPL Contracts ...................................... 100 
5.4.2. Step 2: Fixing Selected TPL Contracts of the First Step ........................ 102 
5.4.3. Step 3: Fixing Retailers visited by TPLP ................................................ 103 
5.4.4. Step 4: Fixing Tours of Owned Vehicles in the Upper Level................. 104 
5.4.5. Step 5: Fixing Tours of Owned Vehicles in the Lower Level ................ 107 
5.4.6. Step 6: Using other vehicles according to shortage and inventory level 107 
5.4.7. Step 7: Checking the Cost Binary Variables of Rental Vehicles ............ 109 
5.4.8. Step 8: Executing the Same Procedures for the Next Time Step ............ 109 
5.5. Improvement of a Solution ............................................................................ 117 
5.5.1. Phase 1: Reconsidering TPL Warehousing ............................................. 117 
5.5.2. Phase 2: Avoiding Redundant TPL Contracts ........................................ 120 
5.5.3. Phase 3: Saving in Tour Cost .................................................................. 122 
5.6. Numerical Results .......................................................................................... 125 
5.6.1. Category 1 ............................................................................................... 125 
5.6.2. Category 2 ............................................................................................... 128 
5.6.3. Category 3 ............................................................................................... 130 
5.6.4. Category 4 ............................................................................................... 133 
5.6.5. Evaluation of Improvement Phases? Impact on Final Solutions ............. 135 
5.6.6. Category 5 ............................................................................................... 137 
5.6.7. Category 6 ............................................................................................... 139 
5.6.8. Category 7 ............................................................................................... 141 
5.7. Summary ........................................................................................................ 143 
Chapter 6:  The Second Heuristic Approach ............................................................ 147 
6.1. Changes Applied to the First Approach ......................................................... 148 
6.1.1. Fixing the Whole Path for Every Vehicle in Steps 4 and 5 .................... 148 
6.1.2. Sending more vehicles in Step 6 ............................................................. 150 
6.2. Numerical Results .......................................................................................... 160 
6.2.1. Category 1 ............................................................................................... 160 
6.2.2. Category 2 ............................................................................................... 162 
6.2.3. Category 3 ............................................................................................... 163 
6.2.4. Category 4 ............................................................................................... 164 
6.2.5. Category 5 ............................................................................................... 165 
6.2.6. Category 6 ............................................................................................... 166 
6.2.7. Category 7 ............................................................................................... 167 
6.3. Summary ........................................................................................................ 169 
Chapter 7:  Level Decomposition ............................................................................. 172 
v 
 
7.1. Mathematical Formulation for Level Decomposition.................................... 172 
7.1.1. The Upper-Level Model ......................................................................... 173 
7.1.2. The Lower Level Model ......................................................................... 177 
7.2. Numerical Results .......................................................................................... 181 
7.3. Summary ........................................................................................................ 183 
Chapter 8: Sensitivity Analysis ................................................................................. 185 
8.1. The Base Scenario.......................................................................................... 185 
8.2. Vehicle Capacity ............................................................................................ 187 
8.3. Inventory Cost ................................................................................................ 189 
8.4. Production Cost .............................................................................................. 192 
8.5. Contract and Warehousing Cost of TPLP ...................................................... 193 
8.6. Fuel Price ....................................................................................................... 196 
8.7. Product Price .................................................................................................. 199 
8.8. The Value of Information .............................................................................. 200 
8.9. The Effect of a Longer Planning Horizon on the Objective Function ........... 201 
8.10. Summary ...................................................................................................... 207 
Chapter 9: Summary, Conclusions, and Recommendations for Future Research .... 211 
9.1. Summary ........................................................................................................ 211 
9.2. Conclusions .................................................................................................... 214 
9.3. Recommendations for Future Research ......................................................... 216 
References ................................................................................................................. 219 
 
 
 
 
 
 
 
 
 
 
 
vi 
 
List of Tables 
 
 
 
Table 2-1. Distribution of articles by journal in the period 1989-2006 ????? 34 
Table 3-1. The entire mathematical formulation of the problem of this study ??. 65 
Table 4-1. Network travel time (minute) ????????????????.. 71 
Table 4-2. Parameters of normal distributions for different supply and demand input 
data ?????????????????...?????????????. 72 
Table 4-3. Values of different supply and demand input data ????????.. 73 
Table 4-4. Orders of different retailers in three time steps ??????????73 
Table 4-5. Different vehicle types? characteristics for the base case ??????74 
Table 4-6. TPL candidate contracts? characteristics ????????????. 75 
Table 4-7. General output information for the optimal solution of Scenario 1 ?? 76 
Table 4-8. Load factor of different vehicles used in Scenario 1 ???????..  80 
Table 4-9. Input data for Scenario 2 ?????????????????..... 81 
Table 4-10. General output information for the optimal solution of Scenario 2 ?.. 81 
Table 4-11. Load factor of different vehicles used in Scenario 2 ???????. 82 
Table 4-12. Input data for Scenario 3 ?????????????????... 83 
Table 4-13. General output information for the best solution of Scenario 3 ??? 84 
Table 4-14. Load factor of different vehicles used in Scenario 3 ??????.? 85 
Table 4-15. Input data for Scenario 4 ?????????????????... 86 
Table 4-16. General output information for the best solution of Scenario 4 ??? 87 
Table 4-17. Load factor of different vehicles used in Scenario 4 ??????.? 87 
Table 4-18. Input data for Scenario 5 ?????????????????... 88 
Table 4-19. General output information for the best solution of Scenario 5 ??? 89 
Table 4-20. Load factor of different vehicles used in Scenario 5 ???????. 90 
Table 4-21. Input data for Scenario 6 ?????????????????... 91 
Table 5-1. Main characteristics of Category 1 ?????????????? 126 
Table 5-2. Comparison between results of Xpress and Heuristic 1 on Category 1 
scenarios ?????????????????...??????????... 126 
Table 5-3. Criteria for comparison of Xpress and fix-and-run based on Category 1 
scenarios ?????????????????...??????????... 128 
Table 5-4. Main characteristics of Category 2 ?????????????? 129 
Table 5-5. Comparison of results of Xpress and Heuristic 1 on Category 2 scenarios 
????????????????????????????????.. 129 
Table 5-6. Criteria for comparison of Xpress and fix-and-run based on Category 2 
scenarios ?????????????????...??????????... 130 
Table 5-7. Main characteristics of Category 3 ?????????????? 131 
Table 5-8. Comparison of results of Xpress and Heuristic 1 on Category 3 scenarios 
????????????????????????????????.. 131  
Table 5-9. Criteria for comparison of Xpress and fix-and-run based on Category 3 
scenarios ?????????????????...??????????... 132 
Table 5-10. Main characteristics of Category 4 ?????????????.. 133 
vii 
 
Table 5-11. Comparison of results of Xpress and Heuristic 1 on Category 4 scenarios 
????????????????????????????????.. 133 
Table 5-12. Criteria for comparison of Xpress and Fix & Run based on Category 4 
scenarios ?????????????????...??????????... 134 
Table 5-13. Impact of different improvement phases on the objective function (%) 
????????????????????????????????.. 136 
Table 5-14. Main characteristics of Category 5 ?????????????.. 137 
Table 5-15. Comparison of results of Xpress and Heuristic 1 on Category 5 scenarios 
????????????????????????????????.. 137 
Table 5-16. Criteria for comparison of Xpress and fix-and-run based on Category 5 
scenarios ?????????????...??????????????... 138 
Table 5-17. Main characteristics of Category 6 ?????????????.. 139 
Table 5-18. Comparison of results of Xpress and Heuristic 1 on Category 6 scenarios 
????????????????????????????????.. 140 
Table 5-19. Criteria for comparison of Xpress and fix-and-run based on Category 6 
scenarios ?????????????...??????????????... 140 
Table 5-20. Main characteristics of Category 7 ?????????????.. 141 
Table 5-21. Comparison of results of Xpress and Heuristic 1 on Category 7 scenarios 
????????????????????????????????.. 142 
Table 5-22. Criteria for comparison of Xpress and fix-and-run based on Category 7 
scenarios ????????????????????????????.. 142 
Table 6-1. Comparison of results of Xpress and Heuristic 2 on Category 1 scenarios 
????????????????????????????????.. 160 
Table 6-2. Criteria for comparison of Xpress and Heuristic 2 based on Category 1 
scenarios ?????????????????...??????????... 161 
Table 6-3. Comparison of the results of Xpress and Heuristic 2 on Category 2 
scenarios ??????????????...?????????????... 162 
Table 6-4. Criteria for comparison of Xpress and Heuristic 2 based on Category 2 
scenarios ?????????????????...??????????... 162 
Table 6-5. Comparison of the results of Xpress and Heuristic 2 on Category 3 
scenarios ?????????????????...??????????... 163 
Table 6-6. Criteria for comparison of Xpress and Heuristic 2 based on Category 3 
scenarios ?????????????????...??????????... 163 
Table 6-7. Comparison of the results of Xpress and Heuristic 2 on Category 4 
scenarios ?????????????????...??????????... 164 
Table 6-8. Criteria for comparison of Xpress and Heuristic 2 based on Category 4 
scenarios ?????????????????...??????????... 164 
Table 6-9. Comparison of the results of Xpress and Heuristic 2 on Category 5 
scenarios ?????????????????...??????????... 166 
Table 6-10. Criteria for comparison of Xpress and Heuristic 2 based on Category 5 
scenarios ?????????????????...??????????... 166 
Table 6-11. Comparison of the results of Xpress and Heuristic 2 on Category 6 
scenarios ?????????????????...??????????... 167 
Table 6-12. Criteria for comparison of Xpress and Heuristic 2 based on Category 6 
scenarios ?????????????????...??????????... 167 
viii 
 
Table 6-13. Comparison of the results of Heuristic 1 and Heuristic 2 on Category 7 
scenarios ?????????????????...??????????... 168 
Table 6-14. Criteria for comparison of Heuristics 1 and 2 based on Category 7 
scenarios ?????????????????...??????????? 168 
Table 7-1. Solutions using the level-decomposition approach on some scenarios .. 182 
Table 7-2. Comparison of the performances of different heuristic methods ??... 182 
Table 8-1. Main characteristics of the base scenario ???????????... 186 
Table 8-2. General output information for the best solution of base scenario ??. 186 
Table 8-3. Criteria from the best solution found by Xpress for different scenarios of 
vehicle capacity ?????????????????...????????. 188 
Table 8-4. Criteria from the best solution found by Xpress for different scenarios for 
inventory cost ?????????????????...????????? 190 
Table 8-5. Criteria from the best solution found by Xpress for different scenarios of 
TPLP cost ?????????????????...??????????.. 194 
Table 8-6. Criteria from the best solution found by Xpress for different scenarios of 
fuel price ?????????????????...??????????... 197 
Table 8-7. Comparison of considering the entire planning horizon and breaking it up 
????????????????????????????????.. 204 
Table 8-8. Comparison of the method breaking down the planning horizon and 
heuristics ?????????????????...??????????.. 206 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ix 
 
List of Figures 
 
Figure 2-1 The supply chain process ??????????????????. 14 
Figure 3-1 Stepwise cost function considered for TPLP ???????????62 
Figure 4-1 Delivery tours in both levels in the first time step in the first scenario ... 70 
Figure 4-2 Delivery tours in both levels in the first time step in the first scenario ... 77 
Figure 4-3 Delivery tours in both levels in the second time step in the first scenario 77 
Figure 4-4 Delivery tours in both levels in the third time step in the first scenario .. 78 
Figure 4-5 Number of constraints in different scenarios ??????????..  92 
Figure 4-6 Number of decision variables in different scenarios ???????? 92 
Figure 4-7 Running time and gap of the best solution with the best bound in different 
scenarios ???????????????????????????.?? 93 
Figure 5-1 A sample of Xpress output for the relaxed model ???????..? 102 
Figure 5-2 A sample of Xpress output after the first step of heuristic 1 ???..? 103 
Figure 5-3 A sample of Xpress output after the third step of heuristic 1 ???.? 104 
Figure 5-4 Fixing one link per owned vehicle in the upper level ??????.... 105 
Figure 5-5 A sample solution of Xpress after fixing one link per owned vehicle in the 
upper level ???????????????????..???????.?. 106 
Figure 5-6 The flow chart of heuristic 1 in the first time step ???????.? 114 
Figure 5-7 A sample solution of Xpress showing redundant links in the path of one 
vehicle ???????????????????..?????????.... 123 
Figure 5-8 The output of applying phase 3 to the situation shown in Figure 5-7 .... 124 
Figure 5-9. Average gap of the heuristic 1 solution with Xpress outputs in different 
categories ???????????????????..???????....... 145 
Figure 5-10. Average running time for heuristic 1 and Xpress in different categories 
???????????????????..????????????.? 146 
Figure 6-1 A sample of Xpress output after relaxing routing variables in heuristic 2 
???????????????????..????????????.? 149 
Figure 6-2 The output of Xpress after step 4 of heuristic 2 ????????.? 150 
Figure 6-3 The flow chart of heuristic 2 in the first time step ????????. 157 
Figure 6-4 Average gaps of heuristics 1 and 2 solutions with Xpress outputs in 
different categories ???????????..????????????.? 170 
Figure 6-5 Average running time for heuristics 1 and 2 in different categories ..? 171 
Figure 7-1. Assignment of retailers? orders to the demands of bottlers ????... 174 
Figure 8.1 Sensitivity of objective function and number of rental vehicles used in both 
levels to vehicle capacity change ???????????????????. 189 
Figure 8.2 Sensitivity of objective function to inventory-cost change ????? 191 
Figure 8.3 Sensitivity of objective function to change in production cost ??..? 192 
Figure 8.4 Sensitivity of objective function to TPLP shipping and warehousing cost 
change ???????????????????..?????????.... 195 
Figure 8.5 Sensitivity of objective function and quantity of products delivered by 
TPLP to change in fuel price ???????????????????...? 198 
Figure 8.6 Sensitivity of objective function to change in product price ???..? 199 
x 
 
Figure 8.7 Comparison of variation in the objective function and running time in 
different approaches used to solve the problem ?????????????... 207 
 1 
 
Chapter 1: Introduction 
 
 
1.1. Supply Chain  
The supply chain is a set of all activities that integrate suppliers, manufacturers, 
warehouses and stores to produce commodities in the right quantities and send them 
to the right locations at the right time to minimize total cost, while satisfying service-
 level requirements (Simchi-Levi, Kaminsky , & Simchi-Levi, 2003). This chain 
includes different management activities, such as purchasing, production, inventory 
control, and distribution. The main goals of supply-chain management are to organize 
the flow of raw materials and products in the network to all actors in the chain and 
minimize total costs, which include production, inventory and distribution.   
There are two key planning issues in supply-chain management: inventory 
management and transportation. Inventory management includes activities such as 
production, ordering, holding, and shortage of products. Transportation includes 
shipping raw materials and final products between sources, factories, warehouses, and 
retailers.  
Theoretically, there are some benefits in the integration of inventory control 
and transportation, and especially when product demand is high and the costs 
associated with inventory and transportation are considerable. The Inventory Routing 
Problem (IRP), which is the combination of inventory control and transportation, is 
the extension of the Vehicle Routing Problem (VRP), in which decisions about 
routing and inventory control are made simultaneously. However, there are some 
 2 
 
major differences between these two problem categories. In the basic VRP, the target 
is finding the best routes to deliver (or pick up) predetermined amounts of products 
within specific time intervals while minimizing the objective function, which is 
usually the total cost. In this case, delivery quantities are known in advance. 
However, in IRP, besides generating delivery routes for different vehicles, a producer 
must decide how much of each product to deliver to each customer. The producer has 
to consider many criteria, such as production rates at plants and inventory levels in 
warehouses. Another important difference between VRP and IRP is the planning 
horizon. Generally, IRP has a longer planning horizon than VRP, which is usually a 
single day problem (i.e., customers should be served by the end of the day). In 
contrast, with IRP a producer must decide about each day?s delivery, which, in turn, 
influences what may happen in the future.  
The process of assigning a set of customers to receive inventory from a 
specific location (the inventory allocation decision) is based on routing cost 
information and marginal profit for each customer in the set. On the other hand, the 
delivery cost for each customer depends on the location servicing it and the vehicle?s 
route to that customer. This means that information about the assignment of 
customers to each location is required. This interrelationship between inventory 
management and transportation is the main reason researchers cite for integrating 
these two major supply-chain activities (Chien, Balakrishnan, & Wong, 1989). This 
study focuses on inventory control, routing, and their interaction.  
A few commercial optimization-based packages integrate inventory 
management and transportation (Andersson, Hoff, Christiansen, Hasle, & 
 3 
 
Lokketangen, 2010). However, it is not clear that the inventory and transportation 
models in these systems are truly integrated or executed sequentially (Andersson, 
Hoff, Christiansen, Hasle, & Lokketangen, 2010). Most industries solve these two 
models separately as follows. First, they solve the inventory-management problem 
and determine the delivery quantity and the time for each delivery. These outputs then 
become input for the transportation model to route vehicles to customers within the 
scheduled time windows.  
In some industries, there is one player for both inventory management and 
transportation. In other words, these industries tend to jointly manage inventory 
management, transportation, and, sometimes, production (Andersson, Hoff, 
Christiansen, Hasle, & Lokketangen, 2010). On the other hand, some transportation 
companies are interested in managing their customers? inventories to improve service 
quality and to use their fleet better. Therefore, production companies can control their 
production more precisely by outsourcing inventory management and transportation. 
Thus, outsourcing inventory management and transportation may benefit both sides, 
depending on different factors such as each company?s expertise and how they 
contract with each other. Most beverage companies such as Coca-Cola or Pepsi are 
examples of a company that outsources product transportation, which will be 
described in the next section.  
 
1.2. A Beverage Company?s Supply Chain  
The managements of most beverage companies in North America have decided to 
decentralize their various operations to meet changing customer demands. As a result, 
 4 
 
their operation is based on a franchised distribution system. In this operation syrup 
concentrate is produced by a beverage company and sold to bottlers. Bottlers, in turn, 
mix the syrup concentrate with different ingredients to produce various products and 
distribute them to retailers, vending machines, and restaurants (Wan, Evers, & 
Dresner, 2012).  
As a result, the beverage company?s supply chain includes three main tiers. In 
the first tier, factories produce syrup concentrate. Because their output is not ready to 
use, supplementary operations are needed to produce the final products (Wan, Evers, 
& Dresner, 2012). 
The second tier is assigned to bottling companies, which receive syrup 
concentrate as raw material and mix it with other ingredients to produce the final 
products for different brands. Bottlers then fill bottles and cans with products and 
distribute them to consumption locations, which are in the third tier. Bottlers can store 
products for future demand.  If there is no available transportation, products can be 
stored in the bottler?s warehouse for delivery when transportation is again available 
(Wan, Evers, & Dresner, 2012). 
The third tier, consumption locations, includes retailers, vending machines, 
and restaurants. Demand is defined at these locations and should be met at the right 
time. Some of these consumption locations, such as large retailers, have their own 
warehouses and can store products for future demand. However, small customers 
such as restaurants and vending machines, can only stock their current demand and 
future demand must be satisfied by the next delivery (Wan, Evers, & Dresner, 2012). 
 5 
 
The vehicle fleet connects these three tiers. One vehicle can be routed to 
locations in different tiers. This depends on many factors, such as travel time between 
different points, vehicle capacity, and demand of consumption location. Different 
types of vehicles can comprise a fleet; for example, vehicles that transport syrup 
concentrate from plants (the first tier) to bottling companies (the second tier) must be 
specially equipped and differ from the vehicles that deliver the final products from 
bottling companies to retailers (the third tier). In addition, the fleet that carries final 
products from the second to the third tier is not homogeneous. For instance, large 
retailers (e.g., Costco, Wal-Mart, and Target) usually have large areas for unloading 
and maneuvering that makes delivery easy for large trucks, while small retailers like 
7-Eleven and vending machines usually do not and must be serviced by smaller 
vehicles. Therefore, managing vehicles to meet the demands of different types of 
customers within their respective time windows and minimizing total cost is essential. 
 
1.3. Problem Description 
In this research, the inventory control and transportation of syrup concentrate and 
final products for one bottling company working for a beverage company is studied. 
As mentioned in the previous section, the bottling company receives syrup 
concentrate and mixes it with other ingredients to produce final products.  
Final products are stored in warehouses until they are sent to their destination 
in the right time frame. Let?s assume that there are some factories that belong to a 
beverage company and produce syrup concentrate. These are called ?plants?. Let?s 
also assume that there are some locations operated by a bottling company that mix 
 6 
 
syrup with other ingredients and store final products. These are called ?bottlers? for 
the purposes of this study. Finally, assume that there are several consumption 
locations that are served by bottlers. These are called ?retailers?. The main player in 
this problem is a bottling company that manages its bottlers and delivers final 
products to retailers. This company has its own nonhomogeneous fleet for 
transportation of syrup concentrate from plants to bottlers and final products from 
bottlers to retailers. The fleet is divided into two major groups. The first group 
delivers syrup concentrate to bottlers and travels only between plants and bottlers. 
The second group is responsible for delivery of final products to retailers, and 
therefore its vehicles work only between bottlers and retailers. Each of these two 
groups contains non-homogenous vehicles that are different in terms of speed, 
capacity, and equipment. For instance, some vehicles cannot service small retailers 
due to their size.  
The bottling company knows retailers? immediate future demands for a 
timeframe of several days. If the demand is not satisfied, a penalty is applied to the 
bottling company?s total cost based on quantity of demand that has not been met and 
shortage cost, which is not the same for all retailers. Retailers have the capability to 
store final products for future demand at a specific holding cost. Storage capacity and 
holding costs vary among retailers. Thus, if the company is not able to satisfy a 
retailer?s order because of shortage in fleet size or warehouse capacity, it has the 
opportunity to send products earlier to avoid the shortage penalty. In this case, the 
company has to pay the holding cost, which may be less than the penalty cost. 
 7 
 
The same product may have different prices for different retailers. Price can 
be consistent for retailers in the same region, but it will not be the same for all 
retailers overall. Therefore, for each time step, the company must determine which 
retailer?s demand should be satisfied when, for some reason, servicing all retailers is 
impossible.  
One of the main reasons that the bottling company cannot meet the demands 
of some retailers is that its fleet size is too small to cover all deliveries in the right 
timeframe. Considering travel time between each pair of facility locations, service 
time (uploading in plants and bottlers and unloading in bottlers and retailers), and the 
limitations of daily business hours, some demands may be not satisfied. In this case, 
the bottling company has three alternatives: 
1. Do nothing. The bottling company does not serve some retailers and pays the 
penalty. 
2. Use rental vehicles. The company rents a vehicle or vehicles to deliver 
products to retailers whose demands cannot be satisfied by the current fleet. 
Rental vehicles cost the company more than owned vehicles; this includes 
fixed costs and operational costs. The bottling company has to operate rental 
vehicles, so routing and the delivery schedule for each rental vehicle is 
controlled by the bottling company. 
3. Use Third Party Logistics Provider (TPLP). With this alternative which will 
be explained more in the next chapter, the company contracts with a logistics 
service provider which is called Third Party Logistics Provider (TPLP) to 
outsource the shipping of some products to some retailers.  
 8 
 
The main difference between alternatives two and three is that the bottling company 
is responsible for routing rental vehicles, whereas with TPLP, vehicle routing is 
outside the authority of the bottling company. The bottling company asks TPLP to 
deliver products to retailers at a particular time. Although the bottling company is not 
in charge of routing for TPLP vehicles, all of the costs associated with these vehicles 
are included in the contract price and the bottling company pays them. The company, 
therefore, must decide which option is the best according to the costs and benefits 
associated with each.  
Also, the bottling company may not have enough space in its warehouses to 
store its final products. In this case, in addition to storing products in retailers? 
warehouses, it can also store them in TPLP warehouses. In other words, the model 
considers warehousing outsourcing as an option that may benefit the bottling 
company. 
Thus, the company must get raw material from plants, produce final products 
in bottlers, and ship them to retailers. It must also optimize its profit, taking into 
consideration inventory control in warehouses?both its own and retailers??and, 
when necessary, store products in TPLP warehouses. Finally, it must deliver final 
products to retailers using different vehicles including its owned, rental, and TPLP.  
 
1.4. Motivation for and Objective of the Research 
The supply chain plays a key role in a company?s profits and costs. At the same time, 
competition between companies in the same industry is steadily increasing. 
Sometimes the difference in quality between two rival companies? product is high and 
 9 
 
a customer will wait for the better commodity to be available if it is out of stock. 
Most of the time, however, shoppers do not wait for a specific brand?s product and 
instead take a similar one. Thus, it is so important that a company not run out of 
stock.  
On the other hand, price is one of the primary factors affecting a buyer?s 
choice of one commodity over another. Obviously, a company whose products are 
more expensive than another?s?but of the same quality?will lose market share. 
Many different factors influence a commodity?s price, such as the costs of raw 
materials, labor, equipment, inventory, and transportation. To achieve high market 
share, in addition to product quality and marketing, all the above costs should be 
optimized. This research focuses on two factors, inventory and transportation. It 
considers their benefits and costs and proposes a model to optimize both operations 
simultaneously. 
In the real world, industries optimize inventory and transportation activities 
separately. They first solve inventory problems then use the results to address 
transportation problems. The final solution is not optimal, however, because the 
interaction between inventory control and transportation is ignored.  
Fleet shortage is prevalent in many companies. This can cause some retailers 
to be out of stock and, if it happens again, may lead to loss of market share. There are 
two alternatives for avoiding this consequence: renting vehicles and contracting with 
other shipping companies as TPLPs. Either option increases total cost, but may 
benefit the company if the penalty for running out of stock is taken into account. This 
depends on many factors, such as the quantity and price of unshipped product, travel 
 10 
 
time and distance between bottlers and retailers, penalty cost, and, of course, the costs 
associated with alternatives. Creating a model that takes all of these aspects into 
account is the main objective of this study.  
 
1.5. Contributions of the Research 
In this study, the inventory and routing of a bottling company working jointly with a 
beverage company is mathematically formulated. This problem is associated with 
IRP, with some new features such as options for rental vehicle and TPLPs. The IRP 
has been well studied in Operations Research but most of the studies have taken only 
a single period into account. In contrast, the model proposed in this study includes 
several time steps in which a decision in one time step can affect future time steps. 
The model is also multi-tier, multi-plant, multi-warehouse, and multi-product, with a 
nonhomogeneous fleet, which increases its complexity significantly. No model in the 
literature considers all of these characteristics simultaneously; for instance, rental 
vehicles and TPLP have not been included in the literature of IRP. In addition, in 
most of the current models trucks have not been tracked to simplify the problem. In 
other words, they figure out how many products should be delivered to different 
retailers. Even if they consider a vehicle?s capacity, they do not take into account the 
cost of returning vehicles to the depot or providing a path for each vehicle. However, 
tracking vehicles helps managers of a supply chain to improve the quality of shipping 
and delivery. In this study, every vehicle is followed, which renders the model more 
adaptive to the real world than models that do not track vehicles. 
 11 
 
One of the main goals of this research is to build an optimization model at the 
operational level. Inventory control and product transportation belong to the tactical 
and operational level, so the model must be able to capture realistic operational 
activities. Shortage in the fleet, retailer storage capacity, and fleet tracking are real-
 world factors that many industries face in their daily operations.  By being more 
comprehensive, therefore, the proposed model is also more complicated than current 
models. 
This research develops heuristic methods to solve large problems which 
cannot be solved by optimization packages. The optimization packages are not able to 
find even a feasible solution for large problems. Since this problem is not real-time, 
the running time of the heuristic is not the main concern; however, it should be fast 
enough to deliver a solution in reasonable amount of computation time. As a result, 
development of efficient heuristic methods to solve problem of this study is the other 
main contribution of this research. 
 
1.6. Organization of the Dissertation 
In the next chapter, previous works on IRP and TPLP is reviewed. The problem is 
described in more detail in Chapter 3 and the mathematical formulation of the model 
is presented. Chapter 4 presents a set of numerical studies to illustrate different 
capabilities of the model. In Chapter 5, the first heuristic algorithm to solve large 
problems of this study, which is based on Fix and Run algorithm is proposed. The 
numerical results to evaluate capabilities of the first heuristic method are presented in 
Chapter 5. Chapter 6 explains the second heuristic method to solve large problems, 
 12 
 
which is also based on Fix and Run algorithm, and compares performances of two 
proposed heuristic algorithms. In Chapter 7, another heuristic method to solve this 
model, based on decomposition, is proposed and its results are discussed in details. 
Chapter 8 is dedicated to sensitivity analysis of some parameters of the model. 
Finally, a summary of this dissertation and some suggestions for future research are 
presented in Chapter 9. 
 
 
 
  
 13 
 
Chapter 2: Literature Review 
 
 
In this chapter, the supply chain (SC) is described and its literature is reviewed. The 
inventory-routing problem (IRP) is discussed in detail, and the gap between previous 
work and the proposed model is presented, after which the third-party logistics 
provider (TPLP) concept and its literature are reviewed. Finally, differences between 
other studies using the TPLP concept and this study are discussed.  
 
2.1. Supply Chain 
The SC begins with the extraction of raw materials and passes through producers, 
warehouses, and retailers to reach the final user. However, researchers from different 
fields have varying definitions for SC, and there is no unique definition in the 
literature (Tan, 2001). For instance, La Londe and Masters (1994) define SC as a set 
of firms passing materials forward, which is very general. Scott and Westbrook 
(1991) have defined SC in more detail, as a chain that connects different components 
of the production and supply process, from raw materials to the final product in a 
user?s hands. This process includes several organizational boundaries. New and 
Payne (1995) also define SC this way.  
The SC can be viewed from another perspective. The retailer?s goal is to have 
products available for customers. From this standpoint, transportation and integrated 
logistics are also important SC activities. Logistics is the management of the flow of 
goods and services between suppliers and final users to satisfy customer demand. 
 14 
 
This involves the integration of information, transportation, inventory, 
and warehousing. The end result, ideally, is that final products are shipped from 
manufacturers to retailers efficiently and take into account inventory replacement and 
the reduction of transportation costs. 
Therefore, SC is an integrated process in which many actors? raw-materials 
producer, manufacturers, wholesalers, retailers, and transportation companies?must 
cooperate to produce the final commodity and distribute it among users (Eksioglu, 
2002). Figure 2-1 shows Beamon?s (1998) definition of the SC process. 
 
 
 
 
 
 
 
 
Figure 2-1 The supply chain process (Beamon, 1998) 
 
The SC can be divided into two processes:  
1- Production planning and inventory control  
2- Distribution and logistics 
The production planning and inventory control process includes the 
production and inventory of raw materials and final products. Extraction, inventory, 
Suppliers 
Manufacturers Storage 
Facilities 
Transportation Retailers 
Distribution 
Centers 
Production Planning 
and Inventory Control 
Distribution and Logistics 
 15 
 
and storage of raw materials; production schedule; manufacturing-process design; and 
storage of the final product in warehouses are the main activities in this process. 
The distribution and logistics process includes shipping the final product from 
warehouses to retailers and other consumption locations. In some industries, the final 
product is first transported to distribution centers to be distributed among retailers. In 
this case, inventory control in distribution centers? warehouses is also included in the 
process. 
Each of the activities within the SC, such as inventory control or product 
delivery, has been extensively studied. However, most researchers tend to model the 
whole process and see the interaction between different activities. For instance, fleet 
size influences warehouse capacity. Similarly, warehouse capacity affects fleet size. 
Optimizing every element of the SC process individually, therefore, does not 
necessarily guarantee an optimal solution for the whole process, as the effects of 
different components on each other have not been considered.  
Generally, researchers try to resolve the following issues: 
1. Production capacity and related technology at each plant. 
2. Number and locations of plants and warehouses. 
3. Capacity of warehouses. 
4. Delivery quantities for different retailers. 
5. Inventory policies and controls in warehouses. 
6. Routing for vehicles in the fleet to distribute products among retailers. 
These can be divided into three main groups: facility location, inventory 
management, and routing. These groups belong to different levels of decision-
 16 
 
making, however, and some cannot be integrated due to incompatibility of planning 
horizon. At the strategic level, long-term decisions such as where to locate a facility, 
production technology, and plant capacity are made. These overarching SC decisions 
affect efficiency at lower levels (Schmidt & Wilhelm, 2000). 
At the tactical level, midterm decisions such as material-flow management, 
which includes production levels at plants and inventory levels, are made (Schmidt & 
Wilhelm, 2000). Finally, at the operational level?which is the lowest level?, short-
 term decisions such as day-to-day production schedules and distribution management, 
including delivery routes, are made (Schmidt & Wilhelm, 2000).  
This means, for instance, that selecting a facility location, which is a strategic-
 level decision, is not compatible with inventory and routing, which are operational 
activities. Since this study concentrates on activities at the operational level of the SC, 
facility location was excluded from the research design, which focuses only on 
inventory management and routing.  
In the next section, a famous group of optimization problems that combine 
inventory and routing is introduced in more detail. 
 
2.2. Inventory Routing Problem (IRP) 
The Inventory Routing Problem (IRP), which is famous in operation research, is an 
extension of the Vehicle Routing Problem (VRP). The IRP, however, is concerned 
not only with delivery routes, but also determines delivery quantity for each customer 
as well as delivery time (Moin & Salhi, 2007). In the simplest form of IRP, there is a 
warehouse and some retailers. The retailers? demands are known, and a fleet of 
 17 
 
specific vehicles is available to transport a commodity from warehouse to retailers in 
response to their demand and the inventory level at the warehouse. The goal is to 
determine the delivery route for each vehicle in the fleet and the delivery time and 
product quantity for each retailer while minimizing total cost and, at the same time, 
attempt to ensure that no retailer runs out of commodity. The total cost includes 
components such as travel time, transportation cost, and inventory cost. 
Although inventory management and VRP seem to be independent from each 
other, there are benefits in integrating them, such as flexibility in service, better fleet 
usage, and reduction in total cost.  
Both VRP and the inventory problem have been studied extensively, and 
many methods have been developed to solve them. In many cases, IRP is separated 
into inventory and VRP problems. In other words, the inventory problem is solved 
first in order to determine delivery quantity, and the output is used as data for the 
VRP. However, they are not in fact integrated and are solved independently. This 
means that the interaction between inventory and routing is lost in this approach. 
Most of the studies applying this approach to solve IRP adopt a two-stage solution 
method that follows one of two approaches: (Moin & Salhi, 2007)   
1. They solve the routing problem first and then the inventory problem. 
2. They solve the inventory control problem first (sometimes with 
approximate transportation cost), then aggregate customers with the same 
delivery time into one cluster and construct delivery routes for each 
cluster. 
 18 
 
In both methods, modifying the data for one problem forces another problem 
to be resolved, and the algorithm iterates between obtaining a new set of routes and a 
new set of replenishments until a criterion for stopping has been met (Moin & Salhi, 
2007). 
There are currently few, if any, commercial-based systems in use that 
integrate inventory management and routing (Andersson, Hoff, Christiansen, Hasle, 
& Lokketangen, 2010). This method is used in road-based and maritime 
transportation more than in air and rail transportation. Even so, most companies in 
maritime transportation separate inventory management and ship routing and solve 
them consecutively.  
Many different assumptions arise when inventory and routing are integrated. 
Unlike many other routing problems, for which the premises are well-known, almost 
every paper in this field presents new assumptions, generating yet another version of 
the problem (Andersson, Hoff, Christiansen, Hasle, & Lokketangen, 2010).  
 
2.2.1. IRP Classifications 
The IRP is used at the tactical and operational level, but can be categorized into three 
different groups according to the planning horizon. In some IRP studies the planning 
horizon is very short, which results in making at most one visit per retailer in the 
timeframe of the problem. These studies are grouped as the ?instant? planning 
horizon. The instant planning horizon does not necessarily include only one step. If a 
planning horizon consists of more than one step, a retailer is visited in one of the 
periods and all retailers do not need to be visited in the same time step. 
 19 
 
In the second group of IRP problems, a retailer can be visited more than once; 
however, the planning horizon is finite. In this group, which is called ?finite,? a 
decision for one horizon is taken independently?yet it affects what happens in the 
next horizon. For instance, the inventory level at the beginning of each horizon 
depends on all decisions taken in previous horizons. Thus, interactions between the 
time before a horizon and after a horizon are ignored, although rolling-horizon 
method can be applied when decision-making for a timeframe longer than the 
planning horizon is needed.  
The last group is the ?infinite? planning horizon, which is used at the strategic 
level of decision making.  
Inventory-management policies impact inventory levels at warehouses. In 
most industries, there is a minimum inventory level for a commodity, which can be 
either zero or greater than zero. But the inventory level may become negative due to 
lack of the commodity in plants or deficiency in transportation of the product. This 
failure to satisfy demand is called ?stock out,? and requires emergency delivery to 
meet retailers? demands.  
The fleets used in SC can be divided into two groups: homogeneous and 
heterogeneous. In a homogeneous fleet, all vehicles have the same characteristics?
 such as speed, capacity, fixed cost, and operational cost?whereas in a heterogeneous 
fleet vehicles are different in some (or all) of these attributes. Having a heterogeneous 
fleet in IRP makes it more complicated, because using different vehicles leads to 
different total costs due to variation in vehicles? characteristics.  
 20 
 
In terms of solution technique, generally there are two approaches, theoretical 
and practical. Most of the papers in in the theoretical approach decompose the 
problem into two underlying problems, the inventory problem and the traveling-
 salesman problem (Moin & Salhi, 2007). In contrast, the practical approaches use 
heuristic or meta-heuristic methods to obtain near-optimal solutions (Moin & Salhi, 
2007).  
The IRP is a complicated problem. The optimal solution can be found only by 
considering few time steps. As a result, almost all methods available in the literature 
are heuristic and do not prove optimality. In next section, the IRP literature is 
reviewed. 
 
2.2.2. IRP Literature 
Bard and Nananukul (2010) model IRP with a single plant and a set of customers 
whose demands change over time. The problem belongs to a finite planning horizon, 
and the fleet is homogeneous. Customers have their own warehouses and are able to 
hold commodities for their future demand, although daily product distribution usually 
meets their requirements. A new methodology that combines exact and heuristic 
procedures within a branch and price algorithm was developed in this study. A 
column generation heuristic was embedded in the solution methodology to improve 
algorithm efficiency. The numerical results show that a problem with up to 50 
customers and 8 time periods can be solved by this method in less than one hour.  
Bard and Nananukul (2010) model differs from the proposed study in several 
significant ways. First of all, their model has only one level, which includes the plant 
 21 
 
and its customers, with no distribution centers in between. Moreover, the model 
includes only a single plant and a homogeneous fleet. It also assumes that fleet size 
will always be large enough to distribute product among customers. In other words, a 
shortage in fleet size will never happen. Since trucks are always available, demand is 
always satisfied (i.e., production quantity is a decision variable and adapts to 
customer demand). Therefore, customers do not risk unsatisfied demand, which 
makes the problem easier than the model proposed in this study. 
Jang, Jang, Chang, and Park (2002) propose a new method for designing a 
supply network with a global bill of material (BOM). They believe that to operate the 
supply network optimally, the following problems should be optimized 
simultaneously: (a) design for a network that includes all entities, from raw-material 
supplier to customer; (b) production assignment; (c) production planning; and (d) 
capacity planning for different producers. Their supply-network management system 
includes supply-network design optimization, planning for production and 
distribution operations, model management, and data-management modules. They use 
a Lagrangian relaxation and genetic algorithm for supply-network design and 
production/distribution modules.  
Although these researchers (Jang, Jang, Chang, & Park, 2002) claim that all 
decisions should be optimized jointly, their model?s framework shows that decisions 
are made sequentially and interactions between some decision variables are ignored. 
For instance, in the outbound model, the plant locations are determined according to 
the locations of warehouses and retailers. Then, in the inbound model, plant locations 
are used to find suppliers? locations. Thus, the effect of transportation cost between 
 22 
 
suppliers and plants is ignored in the outbound model for optimizing plant location. In 
this approach, transportation cost is roughly calculated for each cluster of customers. 
This means that the locations of different facilities are determined based on 
minimizing approximate total cost, which includes transportation cost. Customer 
demand is not considered in this model, and the demands of a cluster of users are 
aggregated into required capacity for warehouses. Since routing was not included in 
the study, the fleet is not part of the formulation; neither is fleet size or vehicle 
capacity. Generally, this model belongs to the strategic level of IRP, and many 
operational details are not included. 
Campbell and Savelsbergh (2004) developed a two-phase approach to solve 
IRP. They decomposed IRP into the inventory problem and VRP. In the inventory 
problem, the delivery schedule is optimized.  In the VRP, delivery routes are 
determined. An integer model has been developed for the inventory problem, 
however, and some heuristics have been used in the second part. Numerical 
experiments have shown improvement in finding near-optimal solutions, and prove 
that the method is efficient for large-scale problems.  
There are some major differences between Campbell and Savelsbergh?s 
(2004) model and the model proposed in this study. For instance, Campbell and 
Savelsbergh?s model optimizes IRP at the strategic level.  Many details are not 
included in the formulation, such as vehicle capacity, unsatisfied demand, and 
shortage in fleet size. Also, there is no routing in their study, and a subset of 
customers is assigned to one vehicle. Thus, the ordering of customers along a path 
associated with each cluster is not determined. 
 23 
 
Chandra (1993) developed an integrated model to determine replenishment 
quantity at warehouses and delivery routes to customers? locations. There are some 
similarities between his model and the model in this study. For example, both are 
multi-product and have a finite planning horizon of discrete time periods. Also, 
customer demand is deterministic. However, the model proposed in this study is more 
complex than Chandra?s.  For instance, the fleet is heterogeneous in this study, 
whereas in Chandra?s model the fleet is homogeneous. Moreover, vehicles are not 
tracked in his model, and fleet size is infinite. In other words, assigning of 
commodities to customers is determined.  There is no limitation on product 
distribution in terms of vehicle availability, which means that unsatisfied demand is 
not considered. In addition, Chandra?s model has only one level and a single 
warehouse, while the model proposed in this study has two levels and is multi-plant 
and multi-bottler. Also, since Chandra?s model assumes that vehicles are always 
available, rental vehicles and TPLPs?which are taken into account in the proposed 
study so as to avoid penalties?are not included in the model.  
A heuristic method that integrates warehouse replenishment and distribution 
of commodities has been developed, and its results have been compared to the results 
of problems solved separately and sequentially. Improvement in total cost has been 
shown for small-case problems. 
Lee, Bozer, and White III (2003) have studied IRP in a finite planning horizon 
with multi-supplier and capacitated vehicles. The problem was decomposed into two 
sub-problems: inventory control and vehicle routing. A linear model was used to find 
inventory level at warehouses for a set of given routes, then a heuristic method was 
 24 
 
applied to improve the routes. The study found that the optimal solution is dominated 
by transportation cost. In the optimal solution, inventory cost is always less than the 
transportation cost.  
This model (Lee, Bozer, & White III, 2003) is dynamic and multi-product, 
and all demand is deterministic. All characteristics of fleet vehicles, however, are 
identical. Also, fleet shortage is not allowed in this model, because fleet size is not 
limited. It is assumed that at least one vehicle is always available for each supplier. In 
addition, this problem is  to one, which means that different suppliers ship parts to a 
single plant. This model and its heuristic methods were applied to a small-case study 
with six suppliers and seven time steps. Numerical results showed that the gap 
between the optimal solution given by CPLEX and the proposed method was around 
1.15 percent.  
Kim and Kim (2000) considered a multi-period inventory/distribution 
planning problem with deterministic demand, one warehouse, multiple retailers, and a 
heterogeneous fleet. The objective function was to minimize total cost, which 
includes transportation cost and retailers? inventory-holding cost. A Lagrangian 
heuristic algorithm was developed to find a good feasible solution in a reasonable 
amount of computation time, and CPLEX was embedded in this methodology to 
solve some linear models.  
This model (Kim & Kim, 2000) has only one warehouse and one product, and 
vehicles do not deliver to more than one retailer. Each vehicle makes a round trip 
between the warehouse and one retailer. This assumption makes the model 
exceptionally easy. Although the fleet is heterogeneous, there are many vehicles 
 25 
 
available to distribute a product between retailers, so fleet shortage and unsatisfied 
demands do not occur in this model. Therefore, rental vehicles and TPLP are not 
included in the model.  
Kim and Kim?s (2000) results show that an approach developed for medium- 
and large-scale problems can obtain a good?but not optimal?solution with a gap of 
less than 2 percent in a reasonable amount of computational time. The authors claim 
that CPLEX 4.0 is not capable of achieving an optimal solution in less than two hours 
for any of the cases they have considered. In addition, they tested their model on a 
small problem (two vehicles, six retailers, and five time periods), and the gap was less 
than 1 percent. For these small problems, CPLEX 4.0 is able to find optimal solution 
in about two hours CPU time. 
Yu, Chen, and Chu (2008) studied IRP with split delivery and fleet size 
constraints. They used a Lagrangian relaxation method to solve the problem, and the 
relaxed formulation was decomposed into inventory control and routing problems. 
These problems were solved by linear programming and a minimum cost flow 
algorithm, respectively. Despite the fact that some similarities exist between their 
study and the proposed study, such as customers? ability to store products or 
deterministic demand, there are some major differences between the two models. 
First, Yu et al.?s fleet is homogeneous. Also, vehicles are not tracked, and only the 
number of vehicles leaving the depot is counted to be less than fleet size. Second, 
there is a central depot, all facilities are on one level, and even though the fleet is 
limited, in their model is not clear as to what happens if the fleet size is too small to 
satisfy demands. In other words, although they have considered the fleet size, it is 
 26 
 
also stipulated to be large enough to satisfy all demands. Numerical experiments 
show that for a scenario with 100 locations and five time steps, this hybrid approach 
can get a feasible solution with a gap between 5 and 8 percent in a reasonable amount 
of computation time. However, no optimal solution is addressed in this research, even 
for small cases, by using optimization packages. 
Savelsberg and Song (2008) have studied the IRP with continuous moves. 
Their model covers a large geographic area in which delivery routes take several 
days. An integer programming algorithm was developed to solve small to medium-
 sized instances approximately. Then a local search procedure improved solutions by a 
randomized greedy heuristic. This model is single-product but multi-plant, and 
inventory is allowed at customer locations. The advantages of this model over 
Savelsberg and Song?s include consideration of unsatisfied demand, rental vehicles, 
and use of TPLPs. The medium-sized problem, for which a feasible solution was 
found, has 10 time steps, 2 plants, 100 customers, and 3 vehicles. No optimal solution 
was presented in this study. All the results have gaps between 1 and 9 percent for 
medium-sized problems. 
Gaur and Fisher (2004) worked on a periodic IRP for Albert Heijn B.V., 
which is a leading supermarket chain in the Netherlands. It included a periodic IRP, 
which means that customers? demands are repeated every  periods. A heterogeneous 
fleet and only one distribution center were considered in the formulation.  
In their model (Gaur & Fisher, 2004), fleet size is infinite and all demands are 
satisfied. On the other hand, inventory level is ignored in this model, and, as a result, 
it does not have the capability of considering product storage by customers for future 
 27 
 
demand. In addition, the formulation defines two types of shipment, direct and 
shared; the latter refers to a cluster of customers, and its transportation cost is 
calculated by solving the traveling salesman problem for the cluster. However, the 
authors state that having at most two costumers in each cluster makes the model 
equivalent to a generalized minimum-weight-matching problem, which its algorithm 
is well known in the VRP literature. Thus, most clusters have at most two stores. 
Computational results show the heuristic algorithm developed in the study has 
improved Albert Heijn?s quality of service. However, the gap between the model?s 
best solution and the optimal solution was not addressed in the paper. 
Dhaenens-Flipo and Finke (2001) modeled the production-distribution 
problem as a network flow problem. Their problem is multi-facility, multi-product, 
and multi-period. The model has a single plant, several warehouses, and several 
distribution centers. The focus of the model is to determine the best arrangement of 
production lines, which optimizes shipment from plant to warehouse and from 
warehouse to retailers. However, routing is not the concern here, and round trips 
between each pair of locations, instead of tours, are stipulated. Also, vehicles are not 
included in the model; the authors assume that vehicles will always be available to 
transport products from one location to another one. Therefore, options for use of 
rental vehicles and TPLPs are not considered. The model was tested in several cases, 
using CPLEX and since routing was not included in the research design, an optimal 
solution was found for some cases in a reasonable amount of computation time.  
Rusdiansyah and Tsao (2005) considered IRP as it is experienced in vending-
 machine SCs working under a vendor-managed inventory (VMI) scheme. Their 
 28 
 
model includes periodic IRP with time windows, and they have attempted to 
simultaneously optimize replenishment frequency for each retailer and build vehicle 
tours. 
This model (Rusdiansyah & Tsao, 2005) considers only one product, vehicles 
are identical, and fleet size is not a constraint. Thus, delivery shortage is not possible. 
The problem includes a single plant with several retailers, which all are in one level. 
Since the model does not consider split delivery and there is no shortage in delivery, 
each retailer?s demand is less than a vehicle?s capacity. This assumption makes the 
model easy to solve. In addition, delivery quantity is not a decision variable in this 
model. When inventory level drops to zero, it is replenished to equal each retailer?s 
demand. Therefore, inventory level also is not a decision variable here, and it is 
calculated according to total demand and frequency of replenishment. Steady 
consumption rate is another assumption in this model. No optimal solution is found, 
and a heuristic method is used in all solutions for several different cases. A 
comparison of solutions using the heuristic method and the best-known solutions 
shows that on average, there is a gap of 4.2 percent between them.  
Bertazzi, Paletta, and Speranza (2002) studied a model in which a set of 
products is shipped from a single plant to several retailers by a vehicle with specific 
capacity and cost. In any replenishment, the retailer?s inventory level should reach its 
maximum level. Thus, delivery quantity is not a decision variable. Also, like many 
other studies reviewed here, the number of vehicles is not a decision variable.  The 
authors assume that there are numerous vehicles that can transport products to their 
destinations, and vehicle capacity is large enough to distribute products to all 
 29 
 
retailers. Delivery shortage, therefore, is not considered. The authors developed a 
heuristic method to find a near-optimal solution. There is no clear mathematical 
formulation in the paper. Their main goal was to investigate the impact of different 
policies on total cost?for instance, how changing the holding costs of supplier and 
retailers affects operations, number of visits, and total cost?which is why an optimal 
solution was not found.   
Lei, Liu, Ruszczynski, and Park (2006) have addressed the integrated 
production, inventory, and distribution routing problem (PIDRP). Their model 
includes several plants and distribution centers, the fleet is heterogeneous, and 
distribution centers can store products for future demand. A heuristic method is 
developed to solve the problem. In the first phase, routing is limited to direct 
shipment and tours are not generated. The second phase attempts to shift direct 
shipments to tours heuristically. The authors claim that by using this approach, the 
inventory problem and VRP are not optimized separately and production, inventory, 
and transportation are coordinated simultaneously.  
This model (Lei, Liu, Ruszczynski, & Park, 2006) has only one level, and 
products are shipped from the top tier, which includes plants, to the lower tier, which 
includes distribution centers. Unsatisfied demand is not possible in this model?in 
other words; fleet size is large enough to meet all demands. Thus, rental vehicles and 
TPLPs are not considered. The heuristic method is applied to different cases, of 
which most are medium-sized problems, and solutions are compared with CPLEX 
solutions obtained in two hours of CPU time. The authors note that CPLEX did not 
find an optimal solution in two hours for most of the scenario cases. 
 30 
 
2.2.3. Conclusions 
Many studies have looked at IRP from different standpoints and various assumptions 
have been considered, which makes each paper a new version of IRP (Andersson, 
Hoff, Christiansen, Hasle, & Lokketangen, 2010). Most studies consider plant(s) in 
the upper tier and distribution centers/customers in the lower tier. In the proposed 
study, however, there are three tiers (plants, bottlers, and retailers) and there are 
multiple facilities in each tier, which makes the problem more complicated.  
Another critical difference between the proposed study and previous research 
is fleet size. Many previous studies have assumed that fleet size will be large enough 
to handle all shipments. Delivery shortage, therefore, does not happen and at each 
facility location at least one vehicle is available to distribute products to customers or 
warehouses. In the proposed study, in contrast, fleet size and capacity are included. If 
the fleet is not able to satisfy all demands, there are two options available for SC 
management to meet demand and avoid stock out.  
In all of the IRP publications reviewed, the objective has been minimizing 
cost; however, in the proposed study, the objective is to maximize profit. Therefore, 
some retailers may experience stock out with some products if it is more beneficial to 
service other retailers, which, in turn, depends on fleet size, rental-vehicle and TPLP 
costs, and different retailers? product price. Obviously, if the goal of one company is 
retaining customers by always having products available to retailers, it will have to 
rent vehicles, contract with TPLPSs, or apply inventory policies when its fleet size is 
small. Defining different management policies is possible by choosing appropriate 
factors in an objective function which will be explained more in Chapter 3.  
 31 
 
The IRP belongs to the NP-Hard class of linear models, for which running 
time goes up exponentially as the problem size grows. As the literature has shown, 
the medium-sized IRP has not yet been optimally solved, and various heuristic 
methods have been developed to find a feasible solution. This study proposes to 
develop an appropriate heuristic method for solving this problem. Finding a good 
feasible solution in a reasonable amount of computation time is another goal. 
Since the TPLP is one of the main aspects of the proposed study, it will be 
explained in the next section. Publications in this area will be reviewed as well. 
 
2.3. Third Party Logistics Provider 
2.3.1. Introduction 
Third-party logistics (TPL) also known as logistics outsourcing (e.g., Kenemeyer, 
Corsi, & Murphy, 2003) has recently received a lot of attention from industry 
(Marasco, 2008). Despite the fact that many companies in different industries use 
TPLPs for the management of all or parts of their logistics operations (Lieb & Bentz, 
2004), one challenge has been the lack of a consistent definition of the TPL concept 
(Marasco, 2008). In some cases, TPL is the same as outsourcing of transportation 
and/or warehousing, while in other cases it includes more complicated outsourcing 
and encompasses the entire logistics process (Laarhoven, Berglund, & Peters, 2000). 
According to Lieb (1992), TPL involves ?the use of external companies to perform 
logistics functions that have traditionally been performed within an organization. The 
functions performed by the third party can encompass the entire logistics process or 
selected activities within that process.?  
 32 
 
Maloni and Carter (2006) cite three primary reasons for outsourcing logistics: 
1. Reduction in cost due to expertise and economies of scale (Zineldin & 
Bredenlow, 2003; Wilding & Juriado, 2004). 
2. Service-quality improvement (Greaver II, 1999; Lynch, 2004). 
3. Buyers are able to concentrate on TPL providers? qualifications (Razzaque 
& Sheng, 1998; Boyson, Corst, Dresner, & Rabinovich, 1999). 
The above, combined with other benefits, have made the outsourcing of logistics 
more attractive in the last two decades. For instance, the annual growth rate of TPL 
from 1995 to 2005 was between 5 and 10 percent (Ashenbaum, Martz, & Rabinovich, 
2005). 
 
2.3.2. TPLP Literature 
Early studies of TPL focused on logistics-services users, while recent research has 
concentrated on third-party logistics providers. However, most of the publications in 
this area have investigated the strategic behavior of TPLPs (Marasco, 2008). For 
example, Yeung, Selen, Sum, and Huo (2006) investigated the effect of different 
strategic choices such as pure cost, pure differentiation, or a combination of the two 
on the financial performance of TPLPs in Hong Kong, and Carbone and Stone (2005) 
studied 20 leading European TPLPs? strategic behavior.  
Some recent studies have focused on the use of information technology (IT) in 
this area. Lai, Ngai, and Cheng (2005) investigated IT usage in the TPLP industry in 
Hong Kong, and Evangelista and Sweeney (2006) researched its use in Italy. Both 
studies concluded that TPLPs have recognized the contributions of IT to their 
 33 
 
improved performance, but small companies face many problems in using IT, due to 
lack of staff expertise and insufficient financial support.  
Table 2-1, which shows the distribution of articles in different journals during 
the period 1989-2006 (Marasco, 2008), demonstrates that serious research on TPL 
started in the mid- to late 1990s. Lewis and Talalayevsky (2000) believe that 
implementation of IT influences TPL developments by allowing buyers and sellers of 
logistics services to communicate directly, thereby reducing coordination costs. As a 
result, IT supports outsourcing of logistics activities to TPLPs (Marasco, 2008). Most 
of the papers in this area have been published in the International Journal of Physical 
Distribution & Logistics Management, and the Journal of Business Logistics. Some 
of the most famous journals in transportation and operations research, such as 
Transportation Science, European Journal of Operational Research, and 
Transportation Research, encompass a small portion of all papers published during 
the past two decades.  
Less than 7 percent of the papers shown in the Table 2-1 are concerned with 
the TPLP process, which includes partner selection, negotiation, contract design, 
operations planning, coordination, and monitoring. In fact, most of the papers have 
concentrated on behavioral characteristics of TPL relationships, such as trust, 
commitment, dependence, conflict, and equity (Marasco, 2008). For example, Moore 
and Cunningham III (1999) have found that trust and commitment are the main 
behavioral attributes that distinguish logistics alliances, and Lim (2000) developed 
the game theoretic model of how a contract should be designed to encourage TPLPs 
to reveal their true characteristics. 
 
 34 
 
Table 2-1. Distribution of articles by journal in the period 1989-2006 (Marasco, 2008) 
Journal 1989-1994 1995-2000 2001-2006 Total 
International Journal of Physical 
Distribution & Logistics 
Management 
4 13 23 40 
Journal of Business Logistics 4 12 3 19 
The International Journal of 
Logistics Management 
1 7 4 12 
Transportation Journal - 3 9 12 
International Journal of Logistics: 
Research and Applications 
- 1 9 10 
Journal of Enterprise Information 
Management 
- 3 3 6 
Supply Chain Management: An 
International Journal 
- - 6 6 
International Journal of Logistics 
Systems and Management 
- - 5 5 
International Journal of Operations 
& Production Management 
1 - 3 4 
Transportation Research - 1 3 4 
Transport Logistics - 4 0 4 
Asia Pacific Journal of Marketing 
and Logistics 
- 1 2 3 
Journal of Supply Chain 
Management 
- 2 1 3 
European Journal of Operational 
research 
- 1 1 2 
Industrial Marketing Management - 1 1 2 
International Journal of Production 
Economics 
- - 2 2 
Omega - - 2 2 
European Journal of Purchasing & 
Supply Management 
- - 1 1 
Harvard Business Review 1 - - 1 
Journal of Business & Industrial 
Marketing 
- - 1 1 
Production and Operations 
Management 
- 1 - 1 
Transport Reviews - 1 - 1 
Transportation Quarterly - 1 - 1 
Transportation Science - - 1 1 
Other - 3 6 9 
Total 11 55 86 152 
 
 35 
 
 Meanwhile, Chen, Hum, and Sun (2001) considered three different third-party 
warehousing contracts with space commitments and adjustment options. Most of the 
papers in this area, therefore, are not in the scope of this study. They have focused on 
how to select TPLP?s, contract with them, continue the contract, and use IT in 
operation. For instance, more than 90 percent of all publications have investigated 
various characteristics of TPL parties and their impact on the TPL arrangement; this 
is another reason most of the publications are not in operation research journals.  
Zapfel and Wasner (2002) have mentioned that increased competition 
between transportation companies has encouraged small- and medium-sized TPLPs to 
cooperate with each other and form a hub-and-spoke system. In this system, each 
TPLP covers a region and several of them build a common network, providing 
service under the same name. Applying this system to parcel distribution was also 
investigated. In this model, therefore, all TPLPs are considered to be a single 
company and a mathematical formulation is provided to minimize cost. Constraints 
ensure that flow conservation is valid; however constraints on generating tours are 
ignored. Although the title of the paper refers to TPLP, its contributions are the same 
as other papers reviewed in the previous section. The problem has been defined for 
several TPLPs working together, which means that a mathematical formulation can 
be used for other companies, regardless of whether they are TPLPs or not. 
Tyan, Wang, and Du (2003) evaluated freight consolidation policies in global 
third-party logistics. Freight consolidation is an approach that maximizes the 
utilization of expensive modes such as air transport by grouping smaller shipments 
into one large shipment to reduce the shipping cost and increase utilization of vehicle 
 36 
 
capacity (Tyan, Wang, & Du, 2003). For example, truck consolidation happens when 
the shipment quantities are less-than-truckload (LTL). Although three different forms 
of consolidation exist?inventory consolidation, vehicle consolidation, and terminal 
consolidation (Hall, 1987)? Tyan, Wang, and Du, (2003) focused on only vehicle 
consolidation. The formulation proposed in their research minimizes the total cost of 
shipping some products from one location to another one. Inventory capacity and 
touring are not considered and the model attempts to achieve better utilization of 
different modes while total cost is minimized. Three freight-consolidation policies are 
investigated and their performances are compared. 
Ko and Evans (2007) presented a mixed integer nonlinear model for the 
design of a dynamic integrated distribution network for TPLPs that considered 
forward and reverse flows simultaneously. This study dealt with warehousing and 
transportation operations. The model takes facility locations into account; however, 
tours are not generated. Also, vehicles are not included in the model, and all 
commodities are shipped via direct routes between plants and warehouses or 
warehouses and customers. The formulation in this study, like that of Zapfel and 
Wasner (2002), is TPLP manager problem. All facilities in this study (Ko & Evans, 
2007) belong to different TPLPs; however, it can be assumed that they are owned by 
a single company and this company attempts to optimize the total cost of its facilities 
operations.  
 
 37 
 
2.3.3. Conclusions 
There has been little research on TPLPs, which is a new topic to which researchers 
have turned only recently. Most of the papers found in the literature have investigated 
the benefits of outsourcing and other issues such as different forms of contracting 
with TPLPs and consolidation of separate TPLPs, and few have included 
mathematical formulation.  
In some of the papers that have presented a mathematical formulation, the 
TPLP manager?s problem is defined and formulated. However in this research TPLP 
is presented as an option for a company to meet customer demand. The benefit of 
TPLP is not optimized; however, it is data to be entered into the model that helps a 
company be able to satisfy its demand. The approach of the proposed study, therefore, 
is completely different from other studies reviewed in the literature. Specifically, no 
study that integrates IRP and TPL exists in the current literature, to the best of the 
author?s knowledge.  
 
  
 38 
 
Chapter 3: Problem Description and Formulation 
 
 
In this chapter, the problem is described completely and its properties are explained. 
All assumptions considered in this research are reviewed and all parameters and 
decision variables used in the model are explained. The mathematical formulation, 
objective function, and constraints are explained in the last section of the chapter.  
 
3.1. Problem Description 
Assume that there is a bottling company working jointly with a beverage company. 
The beverage company produces syrup concentrate in its plants. Syrup concentrate is 
the raw material and is not ready for drinking. Other processes must be applied to 
produce final products. These processes are done in facilities not belonging to the 
beverage company. The bottling company is responsible for these operations. Bottlers 
are locations at which the final processes are applied to syrup concentrate. The 
number and geographical distribution of bottlers vary among different bottling 
companies. Each bottler has its own production capacity and cost for different 
products. 
Bottling companies sell their products through retailers. These can be big 
clients such as Costco, Target, Wal-Mart, and Giant, or smaller ones such as 7-
 Eleven, and/or restaurants in the region. Each of these locations has its own daily 
demand for different commodities. They order different products according to their 
demand and the bottling company must satisfy these orders at the right time. 
 39 
 
Obviously, unsatisfied demand is a negative point for the bottling company and 
influences future orders.  Therefore, the problem has two levels:  
1- The upper level, which includes the beverage company plants and the 
bottling company?s bottlers. 
2- The lower level, which includes the bottling company?s bottlers and its 
retailers.  
The bottling company has its own fleet to transport syrup concentrate from 
plants to bottlers and final products from bottlers to retailers. The vehicles in the fleet 
are categorized into two groups according to their functionality. The first group 
contains vehicles equipped with the proper equipment to transport syrup concentrate 
from plants to bottlers. The second group includes vehicles that transport final 
products from bottlers to retailers. These vehicles do not have equipment for syrup 
transportation and are more useful for delivery of final products. Therefore, vehicles 
in one group cannot be used in the other group.  
Vehicles within each group are heterogeneous. Vehicle capacity is the 
attribute that varies among all vehicles in each group. Other attributes of the vehicles, 
such as speed or transportation cost, can also be dissimilar.  
Final products have different prices at different retailers. Therefore, meeting 
the demand of one retailer may benefit the bottling company more than meeting the 
demands of other retailers, depending on the price at each retailer and transportation 
cost from the bottlers to the retailers. Due to shortage in fleet size, vehicles have to 
make tours to visit retailers sequentially. Each vehicle can serve a limited number of 
retailers due to its capacity. Hence, the whole operation of the bottling company can 
 40 
 
be described as follows. Syrup concentrate is produced at beverage company plants. 
The first group of vehicles transports syrup concentrate from plants to bottlers 
through several tours. Each tour connects one plant to bottlers in the upper level. The 
syrup concentrate is processed and final products are produced, after which the 
second group of vehicles distributes the final products among retailers through tours 
that start at bottlers and deliver to retailers. 
Retailers have their own storage facilities, with particular capacity for each 
product, and can store commodities for future demand. The bottling company thus 
has the opportunity to store products in a retailer?s warehouse by paying that retailer. 
If the bottling company does this, it may not need to visit that specific retailer again 
in the following days. Many factors, such as location of retailer, quantity of retailer?s 
order in the following days, transportation cost, cost of storage at retailer, fleet size, 
and vehicle capacity affect this decision. For example, if a retailer is far from other 
retailers, it may be more beneficial to send it several orders in one delivery and pay a 
holding cost than to send one vehicle every day to meet daily orders. Holding costs 
vary among retailers.  
There is a penalty for unsatisfied orders, which also varies among retailers. 
The main reason for not serving one retailer is that the number of vehicles in the 
second group is not sufficient for delivery to all retailers. Unsatisfied orders have 
several harmful effects on the bottling company, especially if they happen often. The 
biggest disadvantage is that customers may switch to another brand and threaten the 
bottling company?s share in the market. Unsatisfied demand of a time step is 
transferred to the next time step. In other words, if the demand of a particular retailer 
 41 
 
is not satisfied in one time step, the unsatisfied demand is added to the demand of that 
retailer in the next time step. 
As mentioned, sometimes the fleet is not large enough to meet all retailers? 
orders. One method for preventing missed orders is sending orders to some retailers 
in advance to hold for future use. This allows the fleet to be free to service the rest of 
the retailers. This policy is possible if those retailers have available capacity to keep 
products, but may increase the bottling company?s cost due to storage cost at retailers. 
Another way to deal with this problem is by renting vehicles, which increases 
the fleet size. Rental vehicles have their own characteristics, such as speed and 
capacity which can differ from the bottling company?s owned vehicles. Rental 
vehicles? cost, which includes fixed costs and operational costs, is definitely higher 
than owned vehicles? cost. A rental vehicle also needs routing and a path must be 
provided for it. Rental vehicles can be used at both levels. Unsatisfied orders can 
occur when bottlers do not have enough final products to distribute among all 
retailers or because the fleet size in the lower level is small. In this case, the bottling 
company can increase the fleet size in lower level by renting vehicles.  
The last option for delivering to a retailer when the owned fleet is not able to 
do so is outsourcing shipping and/or warehousing. The bottling company contracts 
with TPLPs, who are then responsible for delivery of final products to some of the 
bottler?s retailers. Also, TPLPs can store commodities in their warehouses and deliver 
products to retailers at the right time if there is no available capacity in the bottler?s 
warehouses. Outsourcing of transportation can be contracted for more than one 
retailer and for several days. In fact, a TPLP can be in charge of shipping to some 
 42 
 
retailers on one day and to other retailers on another. Therefore, a contract includes 
providing services to particular retailers for a specific day with determined cost. A 
difference between rental and TPLP options is that the bottling company is 
responsible for providing paths for rental vehicles, whereas a TPLP is responsible for 
its fleet. The bottling company determines product pick-up time from a bottler and 
delivery time to a retailer for the TPLP. Rental vehicles are used on both levels, while 
TPLP vehicles are used only in the lower level, for delivery to retailers. 
Therefore, the bottling company maximizes its profit by considering all the 
above mentioned conditions. Different policies can be defined by choosing the right 
amount for different parameters in the objective function, which will be described in 
the following sections. The method selected determines how to distribute final 
products among retailers and how to deal with any shortage in the fleet or 
warehouses? capacity. Sending orders in advance, renting additional vehicles, 
contracting with TPLPs, and leaving some orders unsatisfied are options that must be 
considered in the decision-making process. 
 
3.2. Modeling Approach 
A mathematical formulation is suggested to model the problem described in section 
3.1. The modeling approach has the following main characteristics:  
1- The model belongs to IRP class which integrates inventory and routing to 
find the optimal solution. 
2- The mathematical formulation models the problem at the operational level. 
3- The model is multi-plant, multi-bottler, and multi-commodity. 
 43 
 
4- The problem is modeled over a pre-determined planning horizon which is 
separated into several time steps. 
5- The objective function is maximizing the profit of the bottling company 
considering all different costs and penalties. 
6- The model has two levels and the flow of syrup concentrate and 
commodities goes down from the upper level to the lower level. 
7- The production of each commodity type at each bottler is limited to its 
production capacity. 
8- There is a heterogeneous fleet transporting syrup concentrate from plants 
to bottlers and products from bottlers to retailers. 
9- Bottlers and retailers are able to store products for future orders or 
demands, respectively.  
10- The model takes rental vehicles and contract with TPLPs into account as 
well as not satisfying orders when the bottling company faces shortage in 
fleet or warehouses? capacity. 
 
3.3. Assumptions 
The mathematical model proposed in this research has the following assumptions: 
1- Since the problem is defined at the operational level, it is deterministic. 
All information about the bottlers, retailers, vehicles and the distribution 
network is known in advance.  
2- The locations of all facilities are known and no decision is taken about 
them. 
 44 
 
3- The time step is assumed to be one day. 
4- Syrup concentrate is always available in the plants and they can store 
syrup concentrate as much as the model requires. 
5- Vehicles that transport syrup concentrate from plants to bottlers cannot 
work in the lower level. 
6- Vehicles that distribute final products among retailers cannot work in the 
upper level. 
7- At both levels, every vehicle can do only one tour in each time step.  
8- At the beginning of the first time step all vehicles working at the upper 
level are available in the plants and all vehicles transporting products at 
the lower level are available at the bottlers. The model figures out where 
each vehicle must be. 
9- At both levels, each vehicle should return to its origin plant or bottlers at 
the end of each time step. 
10- Inventory level at each retailer is calculated at the end of each time step. 
11- Bottlers and retailers cannot hold syrup concentrate and final products 
more than their capacity allows. 
12- If a retailer?s order is not met in one time step, it is transferred to the next 
time step. In other words, it is assumed that consumers of that order do not 
satisfy their demands from other sources.  A penalty is associated with not 
satisfying orders. 
13- There are two types of rental vehicles, with each type assigned to one 
level. 
 45 
 
14- The bottling company is allowed to outsource transportation of products in 
the lower level, but it cannot contract with a TPLP for transportation of 
syrup concentrate from plants to bottlers. 
15- Every shipping TPLP contract includes providing service to one or more 
retailers in one time step. 
16- Every warehousing TPLP contract determines the quantity of products that 
should be stored in TPLP warehouses as well as duration of storage. 
17- The bottling company can consider more than one contract in daily 
operation. 
18- Each retailer can receive its order with at most one TPLP in each time 
step. 
19- If a retailer is assigned to a TPLP, all of its orders including all commodity 
types will be transported by TPLP.  
 
3.4. Mathematical Formulation 
In this section, all sets and parameters of the formulation are introduced. Decision 
variables of the mathematical model are then defined and finally, the objective 
function as well as the constraints are presented and explained in detail. 
 
3.4.1. Sets 
P: Set of all plants 
W: Set of all bottlers 
 46 
 
R: Set of all retailers 
LN: Set of all network links 
GVU: Set of all vehicles working in the upper level 
GVW: Set of all vehicles working in the lower level 
VU: Set of all rental vehicles ready to work in the upper level 
VW: Set of all rental vehicles ready to work in the lower level 
Su: Set of speed factors of vehicles working in the upper level 
Sw: Set of speed factors of vehicles working in the lower level 
S: Set of products 
S1: Set of different types of syrup concentrate 
T: Set of time steps 
TP: Set of all candidate third party contracts 
L: Set of number of cost function steps of candidate third party contracts 
USL: The maximum number of links outgoing from a node in the upper level 
UEL: The maximum number of links incoming to a node in the upper level 
LSL: The maximum number of links outgoing from a node in the lower level 
LEL: The maximum number of links incoming to a node in the lower level 
 
3.4.2. Parameters 
Supply and Demand: 
istd
 : Quantity of order of retailer  from commodity type  at time step , 
TtSsRi ,,
  
 47 
 
sitPc
 : Price of one unit of commodity type  at retailer  at time step , 
TtRiSs ,,
  
sith
 : Holding cost of one unit of commodity type  at retailer  at time step , 
TtRiSs ,,
  
sitSh
 : Shortage penalty of one unit of commodity type  at retailer  at time step , 
TtRiSs ,,
  
stTc
 : Transportation cost of one unit of commodity type  per mile at time step , 
TtSs ,
  
sitHC
 : Storage capacity of commodity type  at facility location  at time step , 
TtWRiSs ,, ?
  
 
Network: 
ijc
 : Travel time between locations  and , 
PWRji ??,
  
ijlen
 : Length of link between locations  and , 
PWRji ??,
  
)(lNS
 : Starting node of link
 l
 , 
LNl
  
)(lNE
 : Ending node of link
 l
 , 
LNl
  
),( kiLnu
 : The 
thk
 outgoing link from node  in the upper level, 
USLtokWPi 1,?
  
),( kiLeu
 : The 
thk  incoming link to node  in the upper level, UELtokWPi 1,?  
),( kiLnw
 : The 
thk
 outgoing link from node  in the lower level, 
LSLtokWRi 1,?
  
 48 
 
),( kiLew
 : The 
thk  incoming link to node  in the lower level, LELtokWRi 1,?  
TLU
 : Loading time of trucks in the upper level 
TLW
 : Loading time of trucks in the lower level 
TULU
 : Unloading time of trucks in the upper level 
TULW
 : Unloading time of trucks in the lower level 
uTT
 : The maximum business hours of trucks in the upper level  
wTT
 : The maximum business hours of trucks in the lower level 
 
Owned and Rental Vehicles: 
kCku
 : Loading capacity of vehicle  working in the upper level, 
GVUk
  
kCkw
 : Loading capacity of vehicle  working in the lower level, 
GVWk
  
ktFCVu
 : Fixed cost of rental vehicle  at time step , which is working in the upper 
level, 
TtVUk ,
  
ktFCVw
 : Fixed cost of rental vehicle  at time step , which is working in the lower 
level, 
TtVUk ,
  
ktEPCVu
 : Operational cost of rental vehicle  at time step , which is working in the 
upper level, 
TtVUk ,
  
ktEPCVw
 : Operational cost of rental vehicle  at time step , which is working in the 
lower level, 
TtVWk ,
  
SFuk: Speed factor of vehicle  working in the upper level, GVUk  
SFwk: Speed factor of vehicle  working in the lower level, GVWk  
 49 
 
Products: 
sa
 : Product  converting factor. This factor converts different products to the unique 
volume unit, 
Ss
  
s
 : This factor converts syrup concentrate volume unit to volume unit of product type 
, 
Ss
  
sitSHC
 : Storage capacity of syrup concentrate type  in bottler  at time step , 
TtWiSs ,,1
  
sitCAP
 : Production capacity of commodity type  in bottler  at time step , 
TtWiSs ,,
  
isPdCost
 : Production cost of one unit of commodity type  in bottler , 
WiSs ,
  
 
Third Party Logistics: 
sqiCT
 : Cost of transportation of commodity type  by  level of contract , 
LiTPqSs ,,
  
ijNB
 : Binary parameter indicating whether retailer  exists in contract , 
TPjRi ,
  
iNU
 : Number of retailers in contract , 
TPi
  
sqiTLB
 : The maximum quantity of commodity type  can be shipped by TPLP with a 
cost equal to step  of cost function of contract , 
LiTPqSs ,,
  
sWR
 : Holding cost of one unit of product type 
s
  per time step in TPLP warehouse 
TLB 
 
 50 
 
3.4.3. Decision Variables 
Commodity Flow 
ij
 lsktQu
 : Quantity of commodity type  on link  shipped by vehicle  from plant  to 
bottler  at time step , 
TtGVUkSsLNlWjPi ,,,,, ?
   
ij
 lsktQw
 : Quantity of commodity type  on link  shipped by vehicle  from bottler  to 
retailer  at time step , 
TtGVWkSsLNlRjWi ,,,,, ?
   
sitI
 : Inventory level of commodity type  at facility location  at time step , 
TtWRiSs ,, ?
  
iste
 : Shortage amount of commodity type  at retailer  at time step , 
TtSsRi ,,
  
istDE
 : Quantity of commodity type  sold to customers in retailer  at time step , 
TtSsRi ,,
  
istDM
 : The modified demand of commodity type  in retailer  at time step , 
TtSsRi ,,  
istPd
 : Quantity of commodity type  produced in bottler  at time step , 
TtSsWi ,,
  
istSc
 : Quantity of syrup concentrate type  stored in bottler  at time step , 
TtSsWi ,, 1
  
 
 
 
 51 
 
Vehicle Flow 
ijktXU
 : Binary variable equal to one if vehicle  visits location  directly after 
location  in the upper level and it leaves location  at time step , otherwise it is zero,
 TtGVUkWPjWPi ,,, ??
   
ijktXW
 : Binary variable equal to one if vehicle  visits location  directly after 
location  in the lower level and it leaves location  at time step , otherwise it is zero,
 TtGVWkWRjWRi ,,, ??
   
ktVZu
 : Binary variable equal to one if a rental vehicle  is used in the upper level at 
time step , 
TtVUk ,
  
ktVZw
 : Binary variable equal to one if a rental vehicle  is used in the lower level at 
time step , 
TtVWk ,
  
ktUu
 : Binary variable equal to one if the bottling company rents vehicle  at time step 
 for the upper level, 
TtVUk ,
  
ktUw
 : Binary variable equal to one if the bottling company rents vehicle  at time step 
 for the lower level, 
TtVWk ,
  
 
Third Party Logistics 
ij
 smtqTW
 : Quantity of commodity type  shipped by third party?s contract  picked up 
from bottler  at time step  and delivered to retailer  at time step , 
TPqTtmSsRjWi ,,,,,
   
 52 
 
qistw
 : Binary variable equal to one if  level of a contract  is selected for 
transportation of commodity type  in time step , 
TtTPi ,
  
iqtTN
 : Binary variable equal to one if an order of retailer  is served by third party?s 
contract  at time step , 
TtTPqRi ,,
  
ij
 sqtZ
 : The cumulative quantity of commodity type  over time steps which is shipped 
from a bottler  to a retailer  at time step  by third party?s contract  and needs to be 
stored in TPLP?s storage, 
TtTPqSsRjWi ,,,,  
 
3.4.4. Objective Function 
)13(
 Wi Ss Tt
 isist
 Wi Rj TPq Ss Tt
 s
 ij
 sqt
 TPq Li Ss Tt
 qistsqi
 VWk Tt
 ktkt
 VUk Tt
 ktkt
 VWk Tt
 ktkt
 VUk Tt
 ktkt
 Ri Ss Tt
 sitsit
 Ri Ss Tt
 sitist
 Wi Rj LNl Ss GVWk Tt
 ij
 ij
 lskt
 Pi Wj LNl Ss GVUk Tt
 ij
 ij
 lskt
 RWi RWj GVWk Tt
 ijktijk
 ijkt
 PWi PWj GVUk Tt
 ijk
 Ri Ss Tt
 istsit
 PdCostPd
 WRZwCTVZwEPCVw
 VZuEPCVuUwFCVwUuFCVuhI
 ShelenQw
 lenQuXWCSFu
 XUCSFuDEPcM x
 ? ? ?
 ? ?
  
Equation (3-1) represents the objective function of the model which is the 
profit of the company. The first term is the revenue of the company obtained from 
selling final products. The second and the third terms calculate the fixed cost of 
transportation which is independent of volume of shipping. Travel time has been 
considered as a representative of this cost.  is the value of time factor. The fourth 
and fifth terms represent shipping costs and  is the shipping cost of one unit of final 
product per mile. It is assumed that transportation cost is the same for different final 
 53 
 
products due to similarity in size and weight of different products. The sixth term is 
the shortage penalty and the seventh term calculates the inventory cost at retailers. 
The next two terms illustrate fixed rental cost of rental vehicles for the upper and 
lower levels, respectively. Likewise, the 10th and 11th terms present the operational 
cost of rental vehicles in the upper and lower levels. The 12th term is TPLP shipping 
cost and the 13th is TPLP warehousing cost. The last one calculates the production 
cost in different bottlers. 
 
3.4.5. Constraints 
Tour Generation Constraints 
WPj
 ijkt TtGVUkWPiXU
 ?
 ? ,,1
        (3-2) 
Rj
 ijkt TtGVWkWiXW ,,1
               (3-3) 
WRj TPq
 iqtijkt TtGVWkRiTNXW
 ?
 ,,1
               (3-4) 
Constraints (3-2), (3-3), and (3-4) ensure that at each time step, each owned or 
rental vehicle can go to only one facility location after leaving plants, bottlers, or 
retailers. Constraint (3-2) is applied to plants and bottlers in the upper level, 
constraint (3-3) is applied to bottlers in the lower level, and constraint (3-4) is applied 
to retailers in the lower level. Moreover, based on constraint (3-4), if a retailer is 
assigned to a TPLP, all of its orders are shipped by the TPLP fleet; therefore, it is not 
visited by any owned or rental vehicles. This constraint is referred to assumption 19 
in section 3.4.  
 54 
 
WPi WPm
 jmktijkt TtGVUkWjXUXU
 ? ?
 ,,0
                   (3-5) 
WRi WRm
 jmktijkt TtGVWkRjXWXW
 ? ?
 ,,0
                    (3-6) 
Equations (3-5) and (3-6) force vehicles to leave the same facility location that 
they have entered. Equation (3-5) is valid for the upper level and equation (3-6) is 
applied to the lower level. 
GVUkPiXUXU
 Wj Tt
 jikt
 Wj Tt
 ijkt ,0
                     (3-7) 
GVWkWiXWXW
 Rj Tt
 jikt
 Rj Tt
 ijkt ,0
                    (3-8) 
Equations (3-7) and (3-8) force each vehicle to return to its plant or bottler, 
respectively at the end of every time step. 
TtGVUkXU
 Pi PWj
 ijkt ,1
 ?
                      (3-9) 
TtGVWkXW
 Wi RWj
 ijkt ,1
 ?
                    (3-10) 
Constraint (3-9) does not allow a vehicle to leave two separate plants at the 
same time step. Similarly, equation (3-10) does not allow a vehicle to leave two 
different bottlers in the same time step. 
WiXU
 GVUk Tt
 iikt 0
                   (3-11) 
RiXW
 GVWk Tt
 iikt 0
                   (3-12) 
Constraints (3-11) and (3-12) do not allow a vehicle going from one facility 
location to the same facility location directly in the upper and lower levels, 
respectively. 
 55 
 
TtGVUk
 TTSFuCXUTLUUXUTLU
 PWi PWj
 ukijiikt
 PWi PWj
 iikt
 ,
 )1(
 ? ?? ?
    (3-13) 
TtGVWk
 TTSFwCXWTLUWXWTLW
 RWi RWj
 wkijiikt
 RWi RWj
 iikt
 ,
 )1(
 ? ?? ?
 (3-14) 
Equations (3-13) and (3-14) calculate business hours of each vehicle in the 
upper and lower levels respectively, which includes loading time, unloading time, and 
travel time. According to these constraints, the business hours must not be greater 
than predetermined values for each level. 
0
 PWi Tt
 iJKtXU
 ?
                   (3-15) 
0
 RWi Tt
 iJKtXW
 ?
                   (3-16) 
Constraints (3-15) and (3-16) do not allow a specific vehicle to visit a 
particular facility location. According to problem description, some vehicles are not 
able to deliver syrup concentrate/products to some bottlers/retailers due to their size. 
These constraints define these limits in the mathematical formulation. 
       
 
Commodity Flow Constraints 
TtSsWi
 TWQwPdII
 Rj TPq Tm
 ij
 stmq
 kiLnwl GVWk Rm
 im
 lsktisttsisit
 ,,
 ),(
 )1(
                
(3-17) 
 
TtSsRi
 DETWQwII ist
 Wj TPq Tm
 ji
 smtq
 kiLewl GVWk Wm
 mi
 lskttsisit
 ,,
 ),(
 )1(              (3-18) 
Equations (3-17) and (3-18) calculate inventory level at the end of each time 
step for different final products at every bottler in the upper level and every retailer in 
 56 
 
the lower level, respectively. According to equation (3-17), the inventory of 
commodity type s at the end of time step  in a bottler  is equal to the inventory level 
at the end of time step , plus the production quantity of commodity type s at 
the bottler   at time step  minus all final products shipped from the bottler  to the 
retailers at time step  by owned vehicles, rental vehicles, and TPLP vehicles.  
Based on equation (3-18), the inventory level for commodity  at the end of 
time step  at a retailer  location is equal to the inventory level of the same product at 
the end of time step  plus all quantities of commodity  that arrive at the 
retailer  location in time step  by owned, rental, and TPLP vehicles minus quantity 
of product  sold to the customers at the retailer  location at time step . 
TtkiLnulGVUkPWiCkuQua k
 Ss Pm Wn
 mn
 lskts ),,(,,
 1
 ?
      (3-19) 
TtkiLnwlGVWkRWiCkwQua k
 Ss Wm Rn
 mn
 lskts ),,(,,?
     (3-20) 
Constraints (3-19) and (3-20) illustrate the loading capacity of vehicles in 
each link in the upper and lower levels, respectively. Syrup concentrate in the upper 
level and final products in the lower level are converted to the unique volume unit by 
the factor 
sa
 . 
TtSsGVUkWi
 QuQuQu
 kiLeul Pm
 mi
 lskt
 kiLeul Pm Wn
 mn
 lskt
 kiLnul Pm Wn
 mn
 lskt
 ,,,
 ),(),(),(
                                
(3-21) 
TtSsGVWkRi
 QwQwQw
 kiLewl Wm
 mi
 lskt
 kiLewl Wm Rn
 mn
 lskt
 kiLnwl Wm Rn
 mn
 lskt
 ,,,
 ),(),(),(
                               
(3-22) 
Equations (3-21) and (3-22) are flow conservation constraints in the upper and 
lower levels, respectively. For instance, at the lower level, the quantity of a 
 57 
 
commodity that leaves a retailer  is equal to the quantity of that commodity that 
arrives at a retailer  minus the quantity of a commodity stored by retailer . 
TtPmiQu
 mi
 kiLnul Wn GVUk Ss
 mn
 lskt ,,0
 ),(
                             (3-23) 
TtWmiQw
 mi
 kiLnwl Rn GVWk Ss
 mn
 lskt ,,0
 ),(
                            (3-24) 
According to constraint (3-23), a flow of syrup concentrate going from a plant 
 to a bottler  cannot pass through a plant . Similarly, based on constraint (3-24), a 
flow of a final product going from a bottler  to a retailer  cannot passes through a 
bottler . 
TtSsGVUkPminWniQuQu
 kiLeul
 mn
 lskt
 kiLnul
 mn
 lskt ,,,),(,
 ),(),(
  
                             (3-25) 
TtSsGVWkWminRniQwQw
 kiLewl
 mn
 lskt
 kiLnwl
 mn
 lskt ,,,),(,
 ),(),(
  
                             (3-26) 
Equations (3-25) and (3-26) force the flow to pass the location that is not its 
destination.  
TtRWiQu
 kiLnwl Pm Wn GVUk Ss
 mn
 lskt ,0
 ),(
 ?
                     (3-27) 
TtPWiQw
 kiLnul Wm Rn GVWk Ss
 mn
 lskt ,0
 ),(
 ?
                     (3-28) 
Since decision variables of flow (
 Qu
 and
 Qw
 ) are defined over links, flow of 
syrup concentrate must be zero for all lower level links and flow of final products 
must be zero for all upper level links. According to constraints (3-27) and (3-28) all 
non-relevant flow decision variables become zero. 
 58 
 
TtSsWi
 Pd
 ScQu
 Ss s
 ist
 ist
 kiLeul Pm GVUk
 mi
 lskt ,,0 1
 ),( 2 2       
(3-29) 
Constraint (3-29) makes a relation among quantity of syrup concentrate 
delivered to one bottler, quantity of commodity from different types produced, and 
quantity of syrup concentrate stored in that particular bottler. 
2s
 is the parameter 
indicates how many units of syrup concentrate 
1s
  are needed to produce one unit of 
commodity type 
2s
 . 
TtSsWiCAPPd sitist ,,
                 
(3-30) 
TtSsWiSHCSc sitist ,, 1
                
(3-31) 
Equation (3-30) limits the production quantity of commodity type 
s
  in a 
bottler at each time step to its production capacity. Constraint (3-31) also forces the 
model to store syrup concentrate 
s
  in each bottler less than its syrup storage capacity. 
 
Shortage and Holding Amount Constraints 
TtSsRWiHCI sitsit ,,?
           (3-32) 
TtSsRiDMDE istist ,,
                 (3-33)  
TtSsRiDMDEe ististist ,,
                 (3-34) 
TtSsRiDMde ististtis ,,)1(
                 (3-35) 
SsRWiI si ,00 ?
                    (3-36) 
SsRieis ,00
                            (3-37) 
Equation (3-32) emphasizes that the inventory level of commodity type  in 
facility location  at time step  should not exceed storage capacity. Safety stock is the 
 59 
 
amount of inventory invested to response to fluctuations in demand to avoid running 
out of stock. Safety stock, therefore, can be considered as the minimum inventory 
level in bottlers and retailers. However, safety stock is assumed to be zero in this 
study; otherwise it can be easily added to the mathematical formulation.  
Equation (3-33) shows that the delivery amount of final product to customers 
at each retailer cannot be more than its modified demand and equations (3-34) and (3-
 35) calculate the modified demand of commodity type  in retailer  at time step  
based on its original demand and shortage amount of that commodity type in the same 
retailer at the same time step. According to constraint (3-34), shortage in a retailer?s 
order happens when the delivery amount to customers is less than the modified 
demand of that retailer. Moreover, equation (3-35) indicates that the modified 
demand of commodity type  in retailer  at time step  is equal to the original 
demand of the same commodity type in the same retailer at time step  plus shortage 
amount of commodity type  in retailer  at time step . ? is the parameter of the 
model showing the portion of unsatisfied demand transferred to the next time step. In 
this study, the value of ? has been considered to one, which means all unsatisfied 
demand is transferred to the next time step. Equations (3-36) and (3-37) set the 
inventory level and shortage amount of all commodity types at all facility locations at 
the beginning of planning horizon to zero. 
   
Constraints of Relation between Different Decision Variables 
TtGVUkPWjiXUMQu ijkt
 jlNE
 kiLnul Pm Wn Ss
 mn
 lskt ,,,
 )(
 ),(
 ?
          
(3-38)
  
 60 
 
TtGVWkRWjiXWMQw ijkt
 jlNE
 kiLnwl Wm Rn Ss
 mn
 lskt ,,,
 )(
 ),(
 ?
           
(3-39) 
Constraints (3-38)
  
and (3-39) relate flow and path decision variables in the 
upper and lower levels, respectively. In these two equations,  is a very large 
number. According to these constraints, flow of commodity can go from one facility 
location to another one, if a vehicle is available in the link that connects those two 
locations.  
TtVUkVZuMXU kt
 PWi PWj
 jikt ,
 ? ?
         (3-40)
 TtVWkVZwMXW kt
 RWi RWj
 jikt ,
 ? ?
         (3-41) 
Constraints (3-40) and (3-41) find the number of time steps at which each 
rental vehicle is used, to calculate the operational cost of a rental vehicle.  is a very 
large number and 
VZu
  and 
VZw
  are binary decision variables representing whether a 
rental vehicle is used in time step . Since 
VZu
  and 
VZw
  decrease objective function 
value, the model makes them equal to one when decision variables 
XU
  or 
XW
  are 
equal to one. 
TtVUkUuVZuVZuIf tkkttk ,11 )1()1(                           
(3-42) 
TtVWkUwVZwVZwIf tkkttk ,11 )1()1(                          
(3-43) 
VUkUuMVZu kk 11                                     
(3-44)  
VUkUwMVZw kk 11                                     
(3-45) 
Equations (3-42) to (3-45) find the first time step at which a rental vehicle is 
used in the upper and lower levels, respectively. There are two different expenses 
associated with rental vehicles: fixed cost, and operational cost. Fixed cost is paid 
 61 
 
once when the bottling company rents a vehicle and it is independent of rental 
duration. On the other hand, operational cost is a linear function of vehicle usage. So, 
figuring out which time step is the first one in which a rental vehicle is used is 
essential. Constraints (3-44) and (3-45) determine at which time steps a rental vehicle 
is used. According to equations (3-42) and (3-43), if a rental vehicle in two 
consecutive time steps is only used in the second one, the vehicle starts to work in the 
second time step. Since these equations cannot determine whether a rental vehicle 
starts to work on the first time step, equations (3-44) and (3-45) have been added to 
the model.  
 
Third Party Logistics Provider Constraints 
TtTPqRjTNMTW jqt
 Wi Ss Tm
 ij
 smtq ,,                            
(3-46) 
TtTPqRiTNTWNB iqt
 Wj Ss Tm
 ji
 smtqiq ,,                            
(3-47)
   
 
According to equations (3-46) and (3-47), flow of commodity is sent to a 
retailer by a TPLP if that retailer is supposed to get service from a TPLP. 
iqtTN
 is the 
binary decision variable equal to one when a retailer  receives its order by TPLP in 
time step . 
iqNB
  is the parameter which is equal to one if contract  serves retailer . 
 is a very large number and 
ij
 stmqTW
 represents the flow of commodity sent to a 
retailer by TPLP and it leaves a bottler  at time step  and arrives at retailer  at time 
step . In other words, a package of products can be sent in time step  but received 
at its destination at time step . It means TPLP stores the package for  time 
steps. It may happen when the capacity of bottler-owned warehouses and retailer-
 62 
 
owned storage are not enough to keep all products. Despite the fact that TPLP storage 
increases the cost, which is considered in the objective function, it may increase 
profit, depending on TPLP warehousing cost and penalty for shortage in delivery. 
This means that the model is able to consider TPLP warehousing as well as TPLP 
transportation. According to equation (3-47) a retailer cannot be served by a TPLP if 
the retailer does not exist in its contract and based on equation (3-46) flow can be sent 
to a retailer by that particular TPLP if that retailer exists in its contract. 
TtSsLiTPqwMTLBTW qistsqi
 Wm Rn Tp
 mn
 stpq ,,,        
(3-48)
  
Constraint (3-48) determines the value for  decision variable needed in 
objective function. Cost function of TPLP is considered as a step function in this 
study. In other words, the cost of TPLP depends on the quantity of commodities 
shipped by TPLP but it does not change linearly. Figure 3-1 shows the typical step 
function considered for cost of TPLP.  
 
Figure 3-1 Stepwise cost function considered for TPLP 
 63 
 
For example a cost of TPLP contract shown in Figure 3-1 has three levels. 
The first level has cost of 
1CT
  for all shipping less than 
1TLB
 unit. If the volume of 
shipping is more than 
1TLB
 and less than
 2TLB
 , the cost of TPLP will be 
2CT
 . Upper 
and lower bounds of shipping for each level of contract cost function (or 
iTLB
 ) are 
parameters of the model. Therefore, equation (3-48) chooses the correct value for 
iw
  
binary variable used in objective function. According to constraint (3-48), if a step  
of a contract is selected, all steps lower than  are selected, however the total cost 
must be equal to 
thi
 step cost. Therefore, 
iCT
  is defined as the incremental cost of the 
thi
 step in compare to its last step cost.  
tmTmtTW
 TPq Wi Rj Ss
 ij
 stmq ,0
                           
(3-49) 
According to equation (3-49), 
TW
  is zero for all deliveries earlier than 
departure time.  
TmSsTPqRjWiTWmnZ
 Tn
 ij
 smnq
 ij
 sqm ,,,,)(
         
(3-50) 
Finally, equation (3-50) is the last constraint which calculates the cumulative 
quantity of product type 
s
 stored in TPLP?s warehouses. Obviously, if a product is 
shipped and received in the same time step, 
Z
  becomes zero which means that 
nothing is stored by TPLP. 
Z  is included in objective function and increases the cost.  
 
Non-negativity and Integrality Constraints 
0,,
 ,,,,,,
 istist
 ij
 sqm
 ij
 stmq
 istististsit
 mn
 lskt
 mn
 lskt
 PdandScZTW
 DMDEeIQwQu                                Real-valued decision variable 
 64 
 
1,0
 ,,,,,,
 qistit
 ktktktktijktijkt
 wandTN
 UwUuVZwVZuXWXU                          Binary integer variables 
 
3.5. Summary 
This Chapter introduced the mathematical formulation that is developed for the 
Inventory-Routing problem of a bottling company. Different details such as 
nonhomogeneous fleet, rental vehicles, and TPLP have been considered in the 
mathematical formulation. Table 3-1 presents the entire mathematical formulation 
proposed for the problem of this study. Limited numerical experiments are conducted 
to show different capabilities of the model and the results are reported in Chapter 4. 
This mathematical formulation which is limited to problems with three tiers and two 
levels can be applied to some other industries. For instance, auto industry has the 
same structure. Parts are shipped from the different suppliers in the first tier to car 
manufacturers in the second tier. Then, cars are sent to dealers in the third tier to sell 
to final customers. However, this structure has a limit that does not allow applying 
this model to some industries. According to the assumptions, the vehicles in the upper 
level cannot work in the lower level and vice versa. This model, therefore, cannot be 
applied to industries for which this assumption is not valid.  
  
 65 
 
 
Table 3-1. The entire mathematical formulation of the problem of this study 
Wi Ss Tt
 isist
 Wi Rj TPq Ss Tt
 s
 ij
 sqt
 TPq Li Ss Tt
 qistsqi
 VWk Tt
 ktkt
 VUk Tt
 ktkt
 VWk Tt
 ktkt
 VUk Tt
 ktkt
 Ri Ss Tt
 sitsit
 Ri Ss Tt
 sitist
 Wi Rj LNl Ss GVWk Tt
 ij
 ij
 lskt
 Pi Wj LNl Ss GVUk Tt
 ij
 ij
 lskt
 RWi RWj GVWk Tt
 ijktijk
 ijkt
 PWi PWj GVUk Tt
 ijk
 Ri Ss Tt
 istsit
 PdCostPd
 WRZwCTVZwEPCVw
 VZuEPCVuUwFCVwUuFCVuI
 ShelenQw
 lenQuXWCSFu
 XUCSFuDEPcMax
 ? ? ?
 ? ?
  
WPj
 ijkt TtGVUkWPiXU
 ?
 ? ,,1
     
Rj
 ijkt TtGVWkWiXW ,,1
             
WRj TPq
 iqtijkt TtGVWkRiTNXW
 ?
 ,,1
              
WPi WPm
 jmktijkt TtGVUkWjXUXU
 ? ?
 ,,0
              
WRi WRm
 jmktijkt TtGVWkRjXWXW
 ? ?
 ,,0
       
GVUkPiXUXU
 Wj Tt
 jikt
 Wj Tt
 ijkt ,0
           
GVWkWiXWXW
 Rj Tt
 jikt
 Rj Tt
 ijkt ,0
          
TtGVUkXU
 Pi PWj
 ijkt ,1
 ?
                   
TtGVWkXW
 Wi RWj
 ijkt ,1
 ?
             
WiXU
 GVUk Tt
 iikt 0
              
 
 
 
 66 
 
 
Table 3-1 (Cont?d). The entire mathematical formulation of the problem of this study
  
RiXW
 GVWk Tt
 iikt 0
          
TtGVUk
 TTSFuCXUTLUUXUTLU
 PWi PWj
 ukijiikt
 PWi PWj
 iikt
 ,
 )1(
 ? ?? ?
     
TtGVWk
 TTSFwCXWTLUWXWTLW
 RWi RWj
 wkijiikt
 RWi RWj
 iikt
 ,
 )1(
 ? ?? ?
  
0
 PWi Tt
 iJKtXU
 ?
        
0
 RWi Tt
 iJKtXW
 ?
           
TtSsWi
 TWQwPdII
 Rj TPq Tm
 ij
 stmq
 kiLnwl GVWk Rm
 im
 lsktisttsisit
 ,,
 ),(
 )1(
                
 
TtkiLnulGVUkPWiCkuQua k
 Ss Pm Wn
 mn
 lskts ),,(,,
 1
 ?
     
TtkiLnwlGVWkRWiCkwQua k
 Ss Wm Rn
 mn
 lskts ),,(,,?
   
TtSsGVUkWi
 QuQuQu
 kiLeul Pm
 mi
 lskt
 kiLeul Pm Wn
 mn
 lskt
 kiLnul Pm Wn
 mn
 lskt
 ,,,
 ),(),(),(
                                
 
TtSsGVWkRi
 QwQwQw
 kiLewl Wm
 mi
 lskt
 kiLewl Wm Rn
 mn
 lskt
 kiLnwl Wm Rn
 mn
 lskt
 ,,,
 ),(),(),(
                               
 
TtPmiQu
 mi
 kiLnul Wn GVUk Ss
 mn
 lskt ,,0
 ),(
                          
TtWmiQw
 mi
 kiLnwl Rn GVWk Ss
 mn
 lskt ,,0
 ),(
                        
 
 
 67 
 
 
Table 3-1 (Cont?d). The entire mathematical formulation of the problem of this study
  
TtSsGVUkPminWniQuQu
 kiLeul
 mn
 lskt
 kiLnul
 mn
 lskt ,,,),(,
 ),(),(
  
TtSsGVWkWminRniQwQw
 kiLewl
 mn
 lskt
 kiLnwl
 mn
 lskt ,,,),(,
 ),(),(
    
TtRWiQu
 kiLnwl Pm Wn GVUk Ss
 mn
 lskt ,0
 ),(
 ?
              
TtPWiQw
 kiLnul Wm Rn GVWk Ss
 mn
 lskt ,0
 ),(
 ?
            
TtSsWi
 Pd
 ScQu
 Ss s
 ist
 ist
 kiLeul Pm GVUk
 mi
 lskt ,,0 1
 ),( 2 2      
 
TtSsWiCAPPd sitist ,,
                
 
TtSsWiSHCSc sitist ,, 1
               
 
TtSsRWiHCI sitsit ,,?
       
TtSsRiDMDE istist ,,
                 
TtSsRiDMDEe ististist ,,
           
TtSsRiDMde ististtis ,,)1(
           
SsRWiI si ,00 ?
               
SsRieis ,00
                      
TtGVUkPWjiXUMQu ijkt
 jlNE
 kiLnul Pm Wn Ss
 mn
 lskt ,,,
 )(
 ),(
 ?
         
  
TtVUkVZuMXU kt
 PWi PWj
 jikt ,
 ? ?
   
TtVWkVZwMXW kt
 RWi RWj
 jikt ,
 ? ?
    
 
Table 3-1 (Cont?d). The entire mathematical formulation of the problem of this study
  
 68 
 
 
TtVUkUuVZuVZuIf tkkttk ,11 )1()1(                      
TtVWkUwVZwVZwIf tkkttk ,11 )1()1(                     
 
VUkUuMVZu kk 11                                
VUkUwMVZw kk 11                               
 
TtTPqRjTNMTW jqt
 Wi Ss Tm
 ij
 smtq ,,                      
TtTPqRiTNTWNB iqt
 Wj Ss Tm
 ji
 smtqiq ,,                    
 
TtSsLiTPqwMTLBTW qistsqi
 Wm Rn Tp
 mn
 stpq ,,,    
tmTmtTW
 TPq Wi Rj Ss
 ij
 stmq ,0
                
 
TmSsTPqRjWiTWmnZ
 Tn
 ij
 smnq
 ij
 sqm ,,,,)(
      
0,,
 ,,,,,,
 istist
 ij
 sqm
 ij
 stmq
 istististsit
 mn
 lskt
 mn
 lskt
 PdandScZTW
 DMDEeIQwQu                       Real-valued decision variable 
1,0
 ,,,,,,
 qistit
 ktktktktijktijkt
 wandTN
 UwUuVZwVZuXWXU                 Binary integer variables 
 69 
 
Chapter 4: Numerical Study 
 
 
In this chapter, different sample problems are solved to evaluate the mathematical 
formulation proposed in this research. These experiments have been designed for 
small to large size problems so that they include different features of real-world 
problems. The main focus of this chapter is on small and medium size problems 
because interpreting the results is much easier for them. As it will be shown, large 
problems cannot be solved by commercial software. In this chapter, input data for the 
models is described first and then numerical results provided by Xpress 7.1 are 
presented in details. 
 
4.1. Design of Sample Problems 
The parameters provided in next sections are related to Scenario 1. Many of them will 
be changed in other scenarios to illustrate the effect of different parameters on the 
final solution as well as model capabilities.   
 
4.1.1. Planning Horizon and Time Step 
In this study, time-step length is assumed to be one day and the planning horizon 
varies over different sample problems, from 3 days for small problems to 5 days for 
large problem. Time steps shorter than one day are not appropriate for this problem, 
because in the real world, no retailer is met more than once every day. Although 
 70 
 
shorter time steps help to capture more details in the model such as exact delivery 
time, it increases the number of parameters and decision variables so significantly 
that even small problems cannot be solved optimally.  
 
4.1.2. Facility Locations 
As mentioned in previous chapters, there are three tiers in this model: plants, bottlers, 
and retailers. Two plants, three bottlers, and six retailers have been considered, in the 
first scenario. In other scenarios more facility locations will be added to the model. 
To determine the location of facilities, 11 locations of Giant and Wal-Mart 
stores in Maryland were chosen arbitrarily and divided among three tiers. These 
known locations are helpful in determining network parameters, which are described 
in the next section. Figure 4-1 shows locations of selected plants, bottlers, and 
retailers. 
 
Figure 4-1 Delivery tours in both levels in the first time step in the first scenario 
 71 
 
4.1.3. Network 
The network of the problem contains 11 nodes representing plants, bottlers, and 
retailers, and also the links that connect each pair of locations. Therefore, the network 
has 121 links. The travel time for each link was obtained using Google Map. Travel 
times are triangular, which means that travel time for each pair of nodes is shorter 
than travel time for any other paths connecting those two nodes through other nodes. 
Table 4-1 represents the travel time matrix in minutes for this network. Nodes one to 
six represent retailers, nodes seven to nine represent bottlers, and nodes 10 and 11 
represent plants. Since the time step is one day, all of these travel times should be 
divided by 1,440 to be used in the formulation.  
Table 4-1. Network travel time (minutes) 
Node 1 2 3 4 5 6 7 8 9 10 11 
1 0 10.8 7.2 13.5 11.7 11.7 15.3 7.2 13.5 15.3 18.9 
2 11.7 0 10.8 8.1 7.2 12.6 14.4 15.3 19.8 19.8 13.5 
3 5.4 9.9 0 12.6 9.9 14.4 18.9 6.3 16.2 21.6 17.1 
4 15.3 9 17.1 0 8.1 13.5 15.3 20.7 20.7 20.7 13.5 
5 10.8 6.3 9.9 8.1 0 13.5 15.3 15.3 20.7 20.7 7.2 
6 9.9 12.6 12.6 10.8 13.5 0 9 16.2 11.7 9.9 19.8 
7 15.3 14.4 18 11.7 14.4 9.9 0 19.8 17.1 17.1 20.7 
8 8.1 15.3 6.3 18 16.2 16.2 19.8 0 11.7 19.8 21.6 
9 13.5 20.7 17.1 18 20.7 11.7 16.2 12.6 0 11.7 27 
10 17.1 21.6 21.6 18.9 21.6 10.8 17.1 19.8 13.5 0 27 
11 18 13.5 16.2 14.4 7.2 19.8 20.7 22.5 26.1 26.1 0 
   
4.1.4. Supply and Demand 
At this stage, there are two commodity types considered and results for problems with 
more commodity types will be shown in future applications. A pack of 24 bottles of 
two different types of soft drink is considered as a unit of final product in the first 
scenario.  
 72 
 
As mentioned in previous chapters, price, order amount, holding cost, 
shortage penalty, and holding capacity vary over different retailers. Therefore, for 
every product and for each of these parameters a normal distribution with specific 
mean and standard deviation has been considered to generate corresponding values 
for each retailer. Table 4-2 presents the assumed parameters of normal distribution for 
different supply and demand input data. 
Table 4-2. Parameters of normal distributions for different supply and demand input data 
Input Data Commodity Type Mean 
Standard 
Deviation 
Price 
1 24$ per unit 0.4$ per unit 
2 22$ per unit 0.3$ per unit 
Order Amount 
1 100 unit 15 unit 
2 105 unit 17 unit 
Holding Cost 
1 0.5$ per unit 0.03$ per unit 
2 0.5$ per unit 0.03$ per unit 
Penalty Cost 
1 3$ per unit 0.30$ per unit 
2 3$ per unit 0.30$ per unit 
Holding Capacity 
at Bottlers 
1 800 unit 30 unit 
2 800 unit 30 unit 
Holding Capacity 
at Retailers 
1 100 unit 10 unit 
2 100 unit 10 unit 
 
Tables 4-3 and 4-4 illustrate the values for different input data generated 
according to the normal distribution parameters shown in Table 4-2.  
  
 73 
 
Table 4-3. Values of different supply and demand input data 
Data 
Commodity 
Type 
Price 
Holding 
Cost 
Penalty Cost 
Holding 
Capacity 
Retailer 1 
1 24.34 0.52 2.75 113 
2 22.16 0.52 2.75 113 
Retailer 2 
1 24.00 0.49 3.00 103 
2 21.92 0.49 3.00 103 
Retailer 3 
1 23.90 0.46 3.25 100 
2 22.25 0.46 3.25 100 
Retailer 4 
1 23.90 0.53 3.08 103 
2 22.08 0.53 3.08 103 
Retailer 5 
1 23.79 0.49 3.08 97 
2 22.16 0.49 3.08 97 
Retailer 6 
1 24.00 0.46 2.62 113 
2 22.38 0.46 2.62 113 
Bottler 1 
1 0 0 0 792 
2 0 0 0 792 
Bottler 2 
1 0 0 0 825 
2 0 0 0 825 
Bottler 3 
1 0 0 0 808 
2 0 0 0 808 
 
 
Table 4-4. Orders of different retailers in three time steps 
Time Steps 
Commodity 
Type 
Time Step 
1 
Time Step 
2 
Time Step 
3 
Retailer 1 
1 108 96 119 
2 108 96 119 
Retailer 2 
1 81 104 119 
2 100 108 108 
Retailer 3 
1 92 81 119 
2 108 92 113 
Retailer 4 
1 119 96 109 
2 109 127 101 
Retailer 5 
1 96 127 127 
2 114 119 91 
Retailer 6 
1 127 127 114 
2 101 109 127 
 
 74 
 
4.1.5. Vehicles 
As mentioned earlier, two groups of owned vehicles have been considered in the 
model. The first group works in the upper level and the second group distributes 
products in the lower level. Each group contains two different vehicle types in terms 
of capacity and speed. Similarly, two different groups of rental vehicles exist, one for 
each level, with two different vehicle types for each level. Besides capacity and 
speed, fixed cost and operational cost are also different for rental vehicle types. Table 
4-5 presents the parameters of different vehicle types used in the model, which have 
been found from online data. The last column in Table 4-5 affects speed of vehicles in 
the fleet. Higher speed factor leads to lower speed for a truck. 
Table 4-5. Different vehicle types? characteristics for the base case 
Owned/ 
Rental 
Level 
Vehicle 
Type 
Capacity 
(Unit) 
Marginal 
Fixed Cost 
($/day) 
Marginal 
Operational 
Cost ($/day) 
Speed 
Factor 
Owned 
Vehicles 
Upper 
Level 
Type 1 590 0 0 1 
Type 2 635 0 0 2 
Lower 
Level 
Type 1 440 0 0 1 
Type 2 440 0 0 2 
Rental 
Vehicle 
Upper 
Level 
Type 1 620 49 16 1 
Type 2 610 54 17 3 
Lower 
Level 
Type 1 440 99 16 1 
Type 2 450 103 18 3 
 
All data in Table 4-5 are valid for Scenario 1. Some will be changed for other 
cases, which will be explained later. 
In addition, the value of time and transportation costs that are used in the 
objective function are assumed as $45/day and $0.05/unit-mile, respectively.    
 
 75 
 
4.1.6. Third Party Logistics Providers 
Although the model allows for several candidate contracts that the manager of the 
bottling company can choose from, Scenario 1 has only two candidate contracts. Cost 
function of each contract has two steps. Characteristics of each candidate contract are 
shown in Table 4-6. These numbers were considered based on quotes from some 
TPLP websites. 
Table 4-6. TPL candidate contracts? characteristics 
Contract 
Covered 
Retailers 
Cost of the 
1st Step 
($/day) 
Cost of the 
2nd Step 
($/day) 
Upper bound 
of volume for 
the 1st step 
(unit) 
Upper bound 
of volume for 
the 2nd step 
(unit) 
Contract 
1 
5 155 513 760 1500 
Contract 
2 
4 and 6 163 519 755 1500 
 
4.2. Numerical Results 
In this section, results obtained from solving different scenarios with Xpress 7.1 are 
presented and described in detail. The set of all scenarios includes the first scenario, 
whose parameters and input data were described in the previous section, and several 
other cases. In other scenarios, some parameters have been altered and the effects of 
these changes on the final solution are shown. Therefore, the results associated with 
the first scenario are presented first, followed by sections that present final solutions 
for the rest of the scenarios. 
 
 76 
 
4.2.1. Scenario 1 
As mentioned earlier, this scenario has three time steps (or three days), and all 
required information?such as supply and demand data, owned- and rental-vehicle 
data, network characteristics, and TPLP candidate contracts?has been introduced in 
previous sections. Table 4-7 presents general information for the final solution of 
Scenario 1.  
Table 4-7. General output information for the optimal solution of Scenario 1 
Criterion Value 
Number of Constraints 6320 
Number of Decision Variables 62423 
LP Relation Objective Function 48860.7 
Best Bound for Objective Function 47877.4 
Best Solution Objective Function 47827.7 
Gap with the Best Bound (%) 0.009 
Running Time (Seconds) 318.3 
 
According to Table 4-7, the solver has found the optimal solution for Scenario 
1 in reasonable running time. The gap in Table 4-7 represents the difference between 
objective function values of the best bound that is not feasible and the best feasible 
solution. Figures 4-2, 4-3, and 4-4 illustrate the tours of different vehicles and 
delivery quantity to each retailer in the first, second, and third time steps, 
respectively. 
 
 77 
 
 
Figure 4-2 Delivery tours in both levels in the first time step in the first scenario 
 
 
Figure 4-3 Delivery tours in both levels in the second time step in the first scenario 
 
 78 
 
 
Figure 4-4 Delivery tours in both levels in the third time step in the first scenario 
 
Different tours have been represented by different line types and colors to 
make them clear. Tours shown with ticker lines represent rental-vehicle paths. In the 
first and second time steps, a rental vehicle has been used in the upper level to 
transport more syrup concentrate to bottlers. According to the output of Xpress, in the 
optimal solution all orders have been satisfied without any penalty, and retailers 2 and 
3 have stored commodity type 1 in the second time step for future demand. By this 
plan, the bottling company does not need to rent another vehicle for the third time 
step, because the owned trucks have used their capacity completely in the third time 
step and they are not able to deliver whole demands of retailers 2 and 3. In fact, the 
model has three options to deal with this deficiency in the fleet: storing a part of 
retailer 2 and 3?s demands in the second time step, adding a rental vehicle to the fleet 
of the lower level, and outsourcing the delivery of the demands of retailers 2 and 3. 
The model has found the first option more beneficial. In addition, according to 
Bottlers 
 79 
 
Figures 4-3 and 4-4, in the upper level, vehicles transported bottler 8?s orders for the 
second and third time steps together in the second time step. Since bottler 8 has 
enough capacity to store the products needed for delivery in the third time step with 
zero cost, this design model, therefore, sends more syrup concentrate to bottler 8 and 
saves the cost of upper-level tours in the third time step. Vehicles? capacities prohibit 
the model from sending all orders for the three time steps together in the first time 
step.  
Owned vehicles and TPLP vehicles are enough for all deliveries in the lower 
level. The second TPLP, which fulfills the orders of retailers 4 and 6, has been 
selected for shipping final products to the designated retailers. Besides this TPLP, 
owned vehicles are able to deliver orders of the rest of the retailers; this is why the 
model does not elect to rent any other vehicles in the lower level. Retailers 4 and 6 
are visited by TPLP vehicles in different time steps. Their first time step orders are 
satisfied by the second TPLP from bottler 9. The TPLP also picks up the orders for 
the second and third time steps from bottlers 8 and 9 and keeps them in its warehouse, 
which is shown in Figure 4-2. In the second time step, the TPLP delivers partial 
orders to retailers 4 and 6, and the balance comes from commodities stored in the 
TPLP warehouse. Again, some products are stored in the TPLP warehouse in the 
second time step for delivery to retailers 4 and 6 by TPLP in the third time step. Table 
4-8 presents the load factor of different vehicles used in both levels in Scenario 1. 
  
 80 
 
Table 4-8. Load factor of different vehicles used in Scenario 1 
Owned/ 
Rental 
Level 
Capacity 
(Unit) 
Time Step 1 
Load Factor 
Time Step 2 
Load Factor 
Time Step 3 
Load Factor 
Owned 
Vehicles 
Upper 
Level 
590 1.00 0.79 0.75 
635 1.00 1.00 0.00 
Lower 
Level 
440 0.90 0.98 1.00 
440 0.93 0.98 1.00 
Rental 
Vehicle 
Upper 
Level 
620 0.85 1.00 0.00 
 
 
4.2.2. Scenario 2 
This scenario has more retailers and a larger fleet size than Scenario 1. Scenario 2 
includes 10 retailers, three owned and three rental vehicles in the upper level, and 
three owned and three rental trucks in the lower level. The rest of the characteristics, 
such as number of plants, number of bottlers, number of commodities, and number of 
candidate TPL contracts, are the same as in Scenario 1. Also, the same normal 
distributions have been used to generate input data for this scenario. Table 4-9 
summarizes input data for Scenario 2.  
Scenario 2 was solved by Xpress 7.1. Since there are more facility locations in 
this scenario?as well as more vehicles in both levels?showing all tours for each 
time step, with their commodity flow like that was shown in Scenario 1, makes each 
figure very disordered. Therefore, important outputs of this scenario are reported in 
Table 4-10. 
  
 81 
 
Table 4-9. Input data for Scenario 2 
Criterion Value 
Total Demand of Commodity Type 1 (unit) 3344 
Total Demand of Commodity Type 2 (unit) 3262 
Production Capacity of Commodity Type 1 (unit/day) 6080 
Production Capacity of Commodity Type 2 (unit/day) 6080 
Total Owned Fleet Capacity in the Upper Level (unit/day) 1920 
Total Owned Fleet Capacity in the Lower Level (unit/day) 1300 
Total Rental Fleet Capacity in the Upper Level (unit/day) 1840 
Total Rental Fleet Capacity in the Lower Level (unit/day) 1270 
Retailers That Can be Served by Contract 1 3, 4, and 10 
Retailers That Can be Served by Contract 2 1, 2, 9, and 10 
 
Table 4-10. General output information for the optimal solution of Scenario 2 
Criterion Value 
Number of Constraints 19846 
Number of Decision Variables 270319 
LP Relation Objective Function ($) 81541.3 
Best Bound for Objective Function ($) 80417.8 
Best Solution Objective Function ($) 80239.4 
Gap with the Best Bound (%) 0.22 
Running Time (CPU seconds) 19755.3 
Unsatisfied Demand for Commodity Type 1 (unit) 0 
Unsatisfied Demand for Commodity Type 2 (unit) 0 
Commodity Type 1 Stored in Retailers? Storage (unit) 5 
Commodity Type 2 Stored in Retailers? Storage (unit) 0 
Number of Rental Vehicles Used in the Upper Level 1 
Number of Rental Vehicles Used in the Lower Level 1 
Number of TPLP Contracts Selected 2 
Commodity Type 1 Delivered by TPLP (unit) 1698 
Commodity Type 2 Delivered by TPLP (unit) 1594 
Commodity Type 1 Stored in TPLP?s Warehouse (unit) 413 
Commodity Type 2 Stored in TPLP?s Warehouse (unit) 536 
 
Scenario 2 has more constraints and decision variables than Scenario 1. Table 
4-10 shows that adding 4 retailers and 4 vehicles results in a large increase in the 
number of constraints and decision variables. It also confirms that the model is very 
sensitive to the number of facility locations and fleet size. 
The solver has not found the optimal solution for this scenario in a reasonable 
amount of computation time; however, the gap between the best feasible solution and 
 82 
 
the best bound is very small. According to the best feasible solution, all retailers 
receive their orders at the right time, and one retailer holds some products for future 
demand. Moreover, in addition to the owned fleet, one rental vehicle in each level has 
been used, although the model has decided to deliver some products by TPLP. 
According to the best solution, both TPLP contracts have been selected and they 
deliver almost 50% of all demands. Also, 12% of commodity type 1 demand and 16% 
of commodity type 2 demand have been stored in a TPLP warehouse. As a result, the 
model found shipping and warehousing outsourcing more beneficial than renting 
another vehicle or storing products in retailers? warehouses. Table 4-11 presents the 
load factor of different vehicles used in both levels. According to Table 4-11, some 
owned vehicles were not used for delivery because based on some assumptions, they 
were not able to visit some retailers or their travel time cost was very high in 
comparison to rental vehicles due to speed factors in Scenario 2.  
Table 4-11. Load factor of different vehicles used in Scenario 2 
Owned/ 
Rental 
Level 
Capacity 
(Unit) 
Time Step 1 
Load Factor 
Time Step 2 
Load Factor 
Time Step 3 
Load Factor 
Owned 
Vehicles 
Upper 
Level 
620 0.96 1.00 1.00 
650 1.00 1.00 0.78 
650 1.00 1.00 0.00 
Lower 
Level 
400 0.68 0.52 0.44 
450 1.00 0.00 0.57 
450 1.00 0.51 0.56 
Rental 
Vehicle 
Upper 
Level 
590 1.00 0.99 0.83 
Lower 
Level 
420 0.50 0.93 1.00 
 
   
 83 
 
4.2.3. Scenario 3 
This scenario is the same as Scenario 2, except that the number of retailers has 
increased to 15. It still has six trucks in the upper level and six trucks in the lower 
level for deliveries. All input data were generated based on normal distributions 
described in Section 4.1. Table 4-12 presents information about Scenario 3 input data. 
Table 4-12. Input data for Scenario 3 
Criterion Value 
Total Demand of Commodity Type 1 (unit) 4873 
Total Demand of Commodity Type 2 (unit) 5435 
Production Capacity of Commodity Type 1 (unit/day) 5550 
Production Capacity of Commodity Type 2 (unit/day) 5550 
Total Owned Fleet Capacity in the Upper Level (unit/day) 1640 
Total Owned Fleet Capacity in the Lower Level (unit/day) 1250 
Total Rental Fleet Capacity in the Upper Level (unit/day 1560 
Total Rental Fleet Capacity in the Lower Level (unit/day) 1180 
Retailers That Can be Served by Contract 1 1, 3, 5, & 9 
Retailers That  Can be Served by Contract 2 3, 7, 9, 11, & 15 
 
Some outputs of the best solution found by Xpress 7.1 are reported in Table 4-
 13. According to Table 4-13, increasing the number of retailers leads to a large 
increase in the number of constraints and decision variables. For instance, Scenario 3 
has almost 700,000 decision variables, which put this problem in the category of 
medium size problems. Moreover, the total demand for both commodity types for all 
retailers is greater than fleet capacity in the lower level. Although the model has the 
opportunity to satisfy more demand with the TPLP option, it depends on TPLP 
contract cost and shortage penalty.  
  
 84 
 
Table 4-13. General output information for the best solution of Scenario 3 
Criterion Value 
Number of Constraints 39721 
Number of Decision Variables 696819 
LP Relation Objective Function ($) 115097 
Best Bound for Objective Function ($) 113557 
Best Solution Objective Function ($) 113127 
Gap with the Best Bound (%) 0.38 
Running Time (CPU seconds) 50870.9 
Unsatisfied Demand for Commodity Type 1 (unit) 462 
Unsatisfied Demand for Commodity Type 2 (unit) 928 
Commodity Type 1 Stored in Retailers? Storage (unit) 0 
Commodity Type 2 Stored in Retailers? Storage (unit) 0 
Number of Rental Vehicles Used in the Upper Level 3 
Number of Rental Vehicles Used in the Lower Level 3 
Number of TPLP Contracts Selected 2 
Commodity Type 1 Delivered by TPLP (unit) 2099 
Commodity Type 2 Delivered by TPLP (unit) 2068 
Commodity Type 1 Stored in TPLP?s Warehouse (unit) 0 
Commodity Type 2 Stored in TPLP?s Warehouse (unit) 0 
 
The solver could not find the optimal solution; however, the gap between the 
best bound and the best solution is less than 0.5%. On the other hand, the running 
time was very high, which confirms that the problem is very sensitive to the number 
of facility locations and fleet size. The running time was more than double that of 
Scenario 2, but it was still in reasonable range. 
According to Table 4-13, there are unsatisfied demands for both commodity 
types in the best solution. All rental vehicles have been used in the solution, and a 
large portion of deliveries are made by TPLP trucks. In other words, all owned and 
rental trucks in the lower level use their full capacity to deliver products to different 
retailers and the balance is delivered by TPLP. Therefore, the main reason for 
unsatisfied demand is insufficient capacity in the upper level to bring enough syrup 
concentrate to bottlers to produce more final products. Looking at the best solution 
confirms that all owned and rental trucks in the upper level have delivered syrup 
 85 
 
concentrate to bottlers as much as their capacity allows, and the model does not have 
any other options for sending more syrup concentrate. The unsatisfied demand 
reported in Table 4-13 is cumulative. As mentioned in the Chapter 3, unsatisfied 
demand is transferred to the next time step. Table 4-14 presents the load factor of 
different vehicles used in both levels in Scenario 3. 
Table 4-14. Load factor of different vehicles used in Scenario 3 
Owned/ 
Rental 
Level 
Capacity 
(Unit) 
Time Step 1 
Load Factor 
Time Step 2 
Load Factor 
Time Step 3 
Load Factor 
Owned 
Vehicles 
Upper 
Level 
550 1.00 1.00 1.00 
540 1.00 1.00 1.00 
550 1.00 1.00 1.00 
Lower 
Level 
450 1.00 0.82 0.76 
400 0.79 0.96 0.74 
400 0.89 0.50 0.99 
Rental 
Vehicle 
Upper 
Level 
450 1.00 1.00 1.00 
600 1.00 1.00 1.00 
510 1.00 1.00 1.00 
Lower 
Level 
350 1.00 1.00 1.00 
450 0.91 0.56 0.47 
380 0.51 0.56 0.00 
 
 
4.2.4. Scenario 4 
In this scenario, the number of facility locations is the same as in Scenario 3; 
however, one commodity type has been added to the model. Moreover, the bottling 
company has one more owned truck in each level. As in Scenario 3, the bottling 
company has an option of three rental vehicles at each level in case its owned fleet is 
not large enough for deliveries. Table 4-15 presents Scenario 4 input data. 
  
 86 
 
Table 4-15. Input data for Scenario 4 
Criterion Value 
Total Demand of Commodity Type 1 (unit) 4593 
Total Demand of Commodity Type 2 (unit) 4673 
Total Demand of Commodity Type 3 (unit) 4647 
Production Capacity of Commodity Type 1 (unit/day) 6080 
Production Capacity of Commodity Type 2 (unit/day) 6080 
Production Capacity of Commodity Type 3 (unit/day) 6080 
Total Owned Fleet Capacity in the Upper Level (unit/day) 2400 
Total Owned Fleet Capacity in the Lower Level (unit/day) 1800 
Total Rental Fleet Capacity in the Upper Level (unit/day) 1500 
Total Rental Fleet Capacity in the Lower Level (unit/day) 1050 
Retailers That Can be Served by Contract 1 4,6,7,8,10,12,14 
Retailers That  Can be Served by Contract 2 3,4,5,12,14 
 
 Demand of commodity type 3 follows the normal distribution, with a 
mean of 102 units and standard deviation equal to 14 units. Also, its price across 
different retailers has a normal distribution, with a mean and standard deviation equal 
to 25 and 0.6 units. TPLP contracts cover more retailers in this scenario. Some 
outputs of the best solution found by Xpress 7.1 for this scenario are reported in Table 
4-16. According to Table 4-16, this scenario has more than 1,100,000 decision 
variables. As a result, the model is also very sensitive to the number of commodity 
types. For this size problem, Xpress 7.1 was not able to find an optimal solution after 
38000 CPU seconds. In total, more than 4300 units of products of different types have 
not been satisfied due to the lack of vehicle in the upper level. Similar to Scenario 3, 
all vehicles that are available in the upper level work with their full capacity, and the 
model does not have enough syrup concentrate to produce enough final products for 
all demand. In this case, the model has to leave unsatisfied the orders of some 
retailers, for which the loss is minimal. The interesting point in the solution is that the 
model has not used one of the rental vehicles in the lower level. Instead, it has found 
that outsourcing shipping is more beneficial. Since many retailers are covered by 
 87 
 
TPLP contracts, this decision seems reasonable. Table 4-17 presents the load factor of 
different vehicles used in both levels in Scenario 4. 
Table 4-16. General output information for the best solution of Scenario 4 
Criterion Value 
Number of Constraints 61141 
Number of Decision Variables 1189923 
LP Relation Objective Function ($) 144025 
Best Bound for Objective Function ($) 142583 
Best Solution Objective Function ($) 142503 
Gap with the Best Bound (%) 0.06 
Running Time (CPU seconds) 38038.1 
Unsatisfied Demand for Commodity Type 1 (unit) 481 
Unsatisfied Demand for Commodity Type 2 (unit) 3425 
Unsatisfied Demand for Commodity Type 3 (unit) 476 
Commodity Type 1 Stored in Retailers? Storage (unit) 0 
Commodity Type 2 Stored in Retailers? Storage (unit) 0 
Commodity Type 3 Stored in Retailers? Storage (unit) 0 
Number of Rental Vehicles Used in the Upper Level 3 
Number of Rental Vehicles Used in the Lower Level 2 
Number of TPLP Contracts Selected 2 
Commodity Type 1 Delivered by TPLP (unit) 2299 
Commodity Type 2 Delivered by TPLP (unit) 1311 
Commodity Type 3 Delivered by TPLP (unit) 2293 
Commodity Type 1 Stored in TPLP?s Warehouse (unit) 0 
Commodity Type 2 Stored in TPLP?s Warehouse (unit) 0 
Commodity Type 3 Stored in TPLP?s Warehouse (unit) 0 
 
Table 4-17. Load factor of different vehicles used in Scenario 4 
Owned/ 
Rental 
Level 
Capacity 
(Unit) 
Time Step 1 
Load Factor 
Time Step 2 
Load Factor 
Time Step 3 
Load Factor 
Owned 
Vehicles 
Upper 
Level 
600 1.00 1.00 1.00 
600 1.00 1.00 1.00 
600 1.00 1.00 1.00 
600 1.00 1.00 1.00 
Lower 
Level 
450 0.62 0.68 0.59 
450 0.70 1.00 0.93 
450 0.48 0.61 0.63 
450 1.00 0.62 0.91 
Rental 
Vehicle 
Upper 
Level 
500 1.00 1.00 1.00 
500 1.00 1.00 1.00 
500 1.00 1.00 1.00 
Lower 
Level 
350 0.86 0.82 0.95 
350 0.85 0.79 1.00 
 
 88 
 
4.2.5. Scenario 5 
This scenario has several changes from previous scenarios. It covers three plants, four 
bottlers, and 20 retailers, which means a total of 27 facility locations. Moreover, four 
owned and four rental trucks can be used in the operation in each level. Finally, three 
TPLP contracts exist for delivery to some retailers. Table 4-18 shows Scenario 5 
input data. According to Table 4-18, production capacity is higher than total demands 
but fleet size in the upper level is not large enough to transport all required syrup 
concentrate to bottlers. Unsatisfied demand, therefore, is expected to be seen in the 
solution. Some outputs of the best solution found by Xpress 7.1 for this scenario are 
reported in Table 4-19. 
Table 4-18. Input data for Scenario 5 
Criterion Value 
Total Demand of Commodity Type 1 (unit) 6197 
Total Demand of Commodity Type 2 (unit) 6065 
Total Demand of Commodity Type 3 (unit) 6161 
Production Capacity of Commodity Type 1 (unit/day) 8080 
Production Capacity of Commodity Type 2 (unit/day) 8080 
Production Capacity of Commodity Type 3 (unit/day) 8080 
Total Owned Fleet Capacity in the Upper Level (unit/day) 2460 
Total Owned Fleet Capacity in the Lower Level (unit/day) 1875 
Total Rental Fleet Capacity in the Upper Level (unit/day) 2460 
Total Rental Fleet Capacity in the Lower Level (unit/day) 1845 
Retailers That Can be Served by Contract 1 1,2,3,4,7,9,10,14,15,19 
Retailers That  Can be Served by Contract 2 1,3,11,14,19,20 
Retailers That  Can be Served by Contract 3 6,8,911,12,13,14,18 
 
  
According to Table 4-19, Scenario 5 includes more than 150,000 constraints 
and 4,400,000 decision variables. Therefore, this scenario is a large problem. Xpress 
was not able to find the optimal solution for this scenario; however, the gap between 
the best solution and the best bound after 18 hours running was less than 0.5%, which 
is acceptable. As expected, there is unsatisfied demand in the best solution, mostly for 
 89 
 
the second commodity type. The reason that the model preferred to produce 
commodity types 1 and 3 more than type 2 is that commodity type 2 has the lowest 
price among all products. Since the shortage penalty is the same for different product 
types, satisfying demand for products 1 and 3 is more profitable for the bottling 
company.  
 
Table 4-19. General output information for the best solution of Scenario 5 
Criterion Value 
Number of Constraints 152049 
Number of Decision Variables 4,421,770 
LP Relation Objective Function ($) 183667 
Best Bound for Objective Function ($) 182504 
Best Solution Objective Function ($) 181661 
Gap with the Best Bound (%) 0.46 
Running Time (CPU seconds) 65167.9 
Unsatisfied Demand for Commodity Type 1 (unit) 519 
Unsatisfied Demand for Commodity Type 2 (unit) 6331 
Unsatisfied Demand for Commodity Type 3 (unit) 470 
Commodity Type 1 Stored in Retailers? Storage (unit) 0 
Commodity Type 2 Stored in Retailers? Storage (unit) 0 
Commodity Type 3 Stored in Retailers? Storage (unit) 0 
Number of Rental Vehicles Used in the Upper Level 4 
Number of Rental Vehicles Used in the Lower Level 0 
Number of TPLP Contracts Selected 3 
Commodity Type 1 Delivered by TPLP (unit) 5019 
Commodity Type 2 Delivered by TPLP (unit) 2259 
Commodity Type 3 Delivered by TPLP (unit) 4991 
Commodity Type 1 Stored in TPLP?s Warehouse (unit) 0 
Commodity Type 2 Stored in TPLP?s Warehouse (unit) 0 
Commodity Type 3 Stored in TPLP?s Warehouse (unit) 0 
 
Another interesting point in this scenario is that the model has not used any 
rental vehicles in the lower level. Owned trucks and the TPLP fleet operate all 
deliveries. The reason is that TPLP contracts have cost functions with two steps, and 
the second step has a very high upper bound. For instance, the first TPLP ships more 
than 700 units and less than 3000 units with a flat rate. As a result, the model sends 
 90 
 
full owned trucks, and the rest of the deliveries fall within the lower and upper 
bounds of the second step of the TPLP cost function. The model, therefore, does not 
need to rent any vehicles and prefers to use the maximum capacity of TPLP vehicles 
for deliveries. If the upper bound of the second step of the contract was significantly 
less than 3000 units, the model might use some rental vehicles in the lower level 
instead of outsourcing deliveries. Table 4-20 presents the load factor of different 
vehicles used in both levels in Scenario 5. 
Table 4-20. Load factor of different vehicles used in Scenario 5 
Owned/ 
Rental 
Level 
Capacity 
(Unit) 
Time Step 1 
Load Factor 
Time Step 2 
Load Factor 
Time Step 3 
Load Factor 
Owned 
Vehicles 
Upper 
Level 
620 1.00 1.00 1.00 
650 1.00 1.00 1.00 
590 1.00 1.00 1.00 
600 1.00 1.00 1.00 
Lower 
Level 
475 0.44 0.45 0.43 
450 0.71 0.44 0.50 
475 0.99 0.00 0.91 
475 0.00 0.00 0.45 
Rental 
Vehicle 
Upper 
Level 
610 1.00 1.00 1.00 
590 1.00 1.00 1.00 
650 1.00 1.00 1.00 
610 1.00 1.00 1.00 
 
 
4.2.6. Scenario 6 
This scenario has a longer planning horizon compared to Scenario 5. In this 
scenario planning for five days is a goal and other characteristics of the model, such 
as number of facility locations, number of commodity types, fleet size, and number of 
TPLP contracts, are the same as Scenario 5. Table 4-21 displays input data for 
Scenario 6. Xpress 7.1 was not able to find a feasible solution for this scenario after 
 91 
 
15 hours, which means that Scenario 6 is larger than Xpress?s capabilities. According 
to Table 4-21, Scenario 6 includes more than 8,800,000 decision variables and 
300,000 constraints, which show that this scenario is a large problem.  
Table 4-21. Input data for Scenario 6 
Criterion Value 
Total Demand of Commodity Type 1 (unit) 10397 
Total Demand of Commodity Type 2 (unit) 10245 
Total Demand of Commodity Type 3 (unit) 10236 
Production Capacity of Commodity Type 1 (unit/day) 8080 
Production Capacity of Commodity Type 2 (unit/day) 8080 
Production Capacity of Commodity Type 3 (unit/day) 8080 
Total Owned Fleet Capacity in the Upper Level (unit/day) 2485 
Total Owned Fleet Capacity in the Lower Level (unit/day) 1840 
Total Rental Fleet Capacity in the Upper Level (unit/day) 2400 
Total Rental Fleet Capacity in the Lower Level (unit/day 1840 
Retailers That Can be Served by Contract 1 4,7,8,15 
Retailers That Can be Served by Contract 2 5,6,13 
Retailers That Can be Served by Contract 3 4,7,10,11,12 
Number of Constraints 300451 
Number of Decision Variables 8,892,749 
 
 
4.3. Summary 
Six sample problems in this chapter were designed to test the proposed model and 
evaluate its capabilities. Problems varied from small to large. Figures 4-5 and 4-6 
illustrate the difference in size of these sample problems in terms of number of 
constraints and decision variables. 
 
 92 
 
 
Figure 4-5 Number of constraints in different scenarios 
 
 
Figure 4-6 Number of decision variables in different scenarios 
 
 93 
 
According to Figures 4-5 and 4-6, the model is very sensitive to some input 
data, such as number of facility locations, fleet size, and number of commodity types. 
An increase in any of these parameters increases the problem size significantly. The 
running time, therefore, also increases significantly. Figure 4-7 presents running time 
and the gap between the best solution and the best bound found by Xpress for each 
scenario. 
 
Figure 4-7 Running time and gap of the best solution with the best bound in different scenarios 
 
Figure 4-7 shows that Xpress could solve only the first scenario, which is a 
small problem; for the rest of scenarios, the optimal solution was not found in a 
reasonable amount of computation time. However, the gap between the best solution 
and the best bound was less than 0.5%, meaning that the solution was very close to 
the optimal one. Finally, Scenario 6, which is the largest scenario, could not be solved 
 94 
 
by Xpress; the software was not able to provide even a feasible solution for this 
scenario.  
The results demonstrate that the model is able to take the different details of 
an operation into account, but medium and large size problems are not solved 
optimally in a reasonable amount of computational time. As mentioned earlier, IRP 
belongs to the NP-hard class of problems, for which running time increases 
exponentially when size increases. Even if the optimal solution is not a target, finding 
a feasible solution with a small gap from the best bound takes a long time for medium 
size problems with known solver packages. In addition, these known solvers are not 
able to deliver a feasible solution for large size or real-world problems. Therefore, 
developing a heuristic method that solves these problems optimally?or finds a good 
feasible solution with an appropriate gap in a short time?is essential. 
 
 
  
 95 
 
Chapter 5: The First Heuristic Approach  
 
 
In this chapter, the first heuristic algorithm proposed in this study to solve large-sized 
problems is described. As mentioned in Chapter 4, the mixed-integer model proposed 
in Chapter 3 was not solved by Xpress 7.1 for large-scale problems. The heuristic 
method, therefore, is needed to find a good feasible solution in a reasonable running 
time. Section 5.1 explains the Branch-and-bound algorithm used by Xpress to solve 
integer models. Section 5.2 describes the Fix-and-run algorithm in general, followed 
by Section 5.3, which describes the main challenges in applying the algorithm in this 
study. In Section 5.4, different steps of the proposed Fix-and-run algorithm are 
described in detail.  
Section 5.5 introduces three improving phases applied to the final solution of 
the algorithm. In Section 5.6, more numerical analyses are performed to evaluate the 
robustness of this heuristic algorithm. Finally, Section 5.7 summarizes the efficiency 
of the first heuristic algorithm. 
 
5.1. Branch-and-Bound Algorithm 
The mathematical formulation proposed in Chapter 3 is a mixed-integer program, 
which means that continuous and integer decision variables exist in the model. All 
decision variables used in the model can be categorized into four groups: 
 96 
 
1- The vehicle flow decision variables group, which includes owned and 
rental routing binary variables (XU and XW), fixed, and operational cost 
binary decision variables of rental trucks (VZu, VZw, Uu, and Uw). 
2- The commodity flow decision variables group, containing flow of 
different commodity types in links (Qu, Qw, and TW), inventory level at 
different facility locations (I), shortage of each commodity type at retailer 
(e), stored products in TPLP warehouse (Z), modified demand (DM), and 
delivery amount to each retailer (DE). These decision variables are 
inherently integer; however, due to the integrity of retailers? orders, they 
become integer in final output even if they are defined as continuous 
decision variables. 
3- The production decision variables group, which includes stored syrup 
concentrate (Sc) and production quantity (Pd). This group has the same 
character as the second group and can be defined as continuous decision 
variables; however, in the output they will be integer. 
4- The third party contract decision variables group, which consists of the 
contract binary variable (w) and retailer visiting binary decision variable 
(TN). 
Groups one and four make the model very complicated. The rest of the 
decision variables affect the size of the model without an increase in complexity of 
the model. The main focus of the heuristic algorithm, therefore, must be on binary 
decision variables. Xpress applies a modified branch-and-bound algorithm to solve 
these problems. In this method, all integer decision variables are relaxed and the 
 97 
 
model is solved optimally with relaxed variables. In each iteration, a decision about 
one integer decision variable with decimal value in the optimal solution is made. 
According to this decision, the search domain is divided into two areas. In one of 
these two domains, the closest smaller integer number is assigned to that particular 
decision variable and, in the other, the closest larger number. The relaxed model, with 
a new value for the decision variable, is solved again and the same procedure applied 
to other integer decision variables if they have decimal values. The solution of 
relaxed models provides upper or lower bounds for the problem, depending on 
objective function. If a feasible solution is found by the algorithm that has integer 
values for all integer decision variables, the gap is calculated between its objective 
function and the best bound found by the model. The algorithm ends if decisions for 
all variables are made or a gap between an integer solution and a bound is ignorable.  
The branch-and-bound algorithm, which is the most commonly used IP 
solution algorithm, is implemented in many commercial solvers. The main 
disadvantage of this method is its running time. In other words, its use can be 
expensive depending on the size of the problem and complexity of integer decision 
variables. The algorithm produces several intermediate and not optimal solutions; 
however, they are used to make the bound tighter. Most of the time, the branch-and-
 bound algorithm comes up with near optimal solutions quickly but it takes a long time 
to verify its optimality. 
  
 98 
 
5.2. Fix-and-run Algorithm 
The fix-and-run algorithm suggested by (Haghani & Oh, 1996) is a heuristic 
algorithm having a good performance for the vehicle routing problem (VRP). This 
method focuses mainly on relaxing integer decision variables; however, it makes 
decisions about them faster than the branch-and-bound. The main steps of the fix-
 and-run algorithm can be described as follows: 
1- All integer decision variables are relaxed and the model is solved 
optimally. 
2- The values of some integer variables are fixed in an orderly manner. The 
rest of the integer variables are relaxed and the model is solved again. 
3- Step 2 continues iteratively until all integer variables are fixed. 
The fix-and-run algorithm is similar to the branch-and-bound algorithm in 
terms of relaxing integer decision variables and making a decision based on the 
optimal solution found for the relaxed model. However, this algorithm is much faster 
than branch-and-bound because it fixes some integer variables at each iteration, 
while branch-and-bound separates the feasibility domain for one decision variable at 
each iteration. Moreover, fix-and-run ends after a limited number of iteration; 
however, the branch-and-bound needs to continue until either all branches terminate 
or a predetermined gap is found. 
As a result, fix-and-run is an appropriate heuristic for models with a large 
number of integer decision variables, especially models that include VRP as one of 
the main parts of the problem. The study problem meets both criteria; however, it 
 99 
 
has its own challenges in using fix-and-run as a heuristic method, which will be 
explained in the following sections. 
 
5.3. Applying a Fix-and-Run Algorithm to the Proposed Model  
The fix-and-run algorithm described in the previous section will be applied to the 
study problem as follows: 
1- Divide the problem into several segments. Each segment includes one 
time step of the whole model. 
2- Relax all integer decisions and solve the relaxed model optimally. 
3- Fix some of the integer variables of the first time step and rerun the whole 
model while the rest of the integer variables of the first time step and the 
integer variables of other time steps are relaxed. 
4- If all integer variables of the first time step have integer values, do the 
same process for the second time step; otherwise, fix some other integer 
variables and continue until all integer variables have integer values. 
5- Do the same procedure for the next time step until all integer variables in 
all time steps are fixed. 
The described algorithm presents some challenges when it is applied to the 
model. First, it needs Xpress as a solver of relaxed models. The algorithm, therefore, 
needs to communicate with Xpress to get the solution and give the new values for 
some variables. The code, which controls this communication and adds some new 
constraints continuously, must consider different details to be efficient; otherwise, a 
significant amount of running time is wasted for communication. Second, the model 
 100 
 
has different groups of integer variables, such as vehicle routing, rental-vehicle cost, 
TPLP contract, and TPLP warehousing. Fixing some of these decision variables 
affects the others. As a result, the order of decision variables fixed in each time step 
is another challenge, which may impact the final solution. The different steps of the 
first fix-and-run algorithm proposed for this research are described in detail in 
Section 5.4. 
 
5.4. Fix-and-Run Algorithm Steps (Heuristic 1) 
As mentioned in the previous section, the order of fixing integer variables impacts the 
final solution. Therefore, it is important to determine which decision variable should 
be fixed first and which variable will be the next. In this section, the first fix-and-run 
algorithm developed for this problem will be explained step by step. 
 
5.4.1. Step 1: Removing Unnecessary TPL Contracts 
In the first step, all unnecessary TPL contracts are excluded from the solution. As 
described in previous sections, all integer variables are relaxed at the beginning and 
the relaxed model is solved optimally. The first decision variable for which a decision 
is made is the TPL contract binary variable. According to the mathematical 
formulation described in Chapter 3, the TPL contract binary variable (w) must satisfy 
the following constraint: 
        
(5-1) 
TtSsLiTPqwMTLBTW qistsqi
 Wm Rn Tp
 mn
 stpq ,,,
 101 
 
According to equation 5-1, the left-hand side can be at least one to force w to 
take a non-zero value; otherwise, w is set to zero due to its impact on increasing total 
cost. Therefore, if w is forced to take a non-zero value, it must be greater than 1/M. In 
a relaxed model, the solver is free to choose a very small value for TW. In this case, it 
can be a very small number that does not increase the total cost significantly. In the 
first step of the algorithm, therefore, all w decision variables with a value smaller than 
1/M are fixed to zero. This procedure is applied to all time steps. In other words, all 
unnecessary TPL contract variables for every time step are excluded from the final 
solution. This assignment is fed to the model by adding some constraints to the 
model. Each constraint is defined for one w binary variable and assigns zero to that 
variable. These constraints will remain until the end of algorithm, and the algorithm is 
not able to change any of these decisions. Figure 5-1 shows a sample output of 
solving a relaxed model by Xpress with M equal to 1000. According to this figure, 
retailers 1, 2, and 4 are visited by TPLP; however, after applying the first step of 
heuristic 1, the TPL contract binary variables (w) associated with retailers 1 and 4 are 
set to zero because their values are less than 0.001, while no decision is made about 
the other contract variable. 
 
 102 
 
 
 
Figure 5-1 A sample of Xpress output for the relaxed model 
 
 
5.4.2. Step 2: Fixing Selected TPL Contracts of the First Step 
After fixing some w variables to zero in Step 1, the relaxed model with new 
constraints is solved using Xpress. In this step, a decision about TPL contract binary 
variable (w) for the first time step is made. The w variables of the first time step that 
exist in the optimal solution found by Xpress are considered. The w that has the 
maximum non-integer value is selected and is fixed to one. Therefore, one constraint 
is added to the relaxed model which assigns one to that particular w variable. The new 
relaxed model is solved again by Xpress optimally and the new optimal solution is 
analyzed for another non-integer w variable. If all w variables of the first time step are 
integers, Step 2 is finished; otherwise, another w variable is selected randomly and 
fixed to one and the related constraint is added to the relaxed model. This process 
continues until all w variables of the first time step have the value of either zero or 
 103 
 
one. For instance, the delivery plan shown in Figure 5-2 can be the output of Xpress 
after the first step of heuristic 1 has been applied. The TPL contract binary variable 
for retailers 1 and 4 is equal to zero, and for retailer 2 has decimal value greater than a 
threshold. The algorithm, therefore, assigns retailer 2 to a TPLP and adds another 
constraint to the relaxed model, which sets the associated binary variable to one. 
 
 
Figure 5-2 A sample of Xpress output after the first step of heuristic 1 
 
 
5.4.3. Step 3: Fixing Retailers visited by TPLP 
The heuristic algorithm has fixed TPLP contract binary variables in Step 1 and 2 for 
the first time step. As mentioned in Section 5.1, the retailer visiting binary decision 
variable (TN) is another integer variable whose values can be determined in this step. 
Since all w variables are fixed to either zero or one, the retailers visited by TPLP are 
 104 
 
known. Moreover, it is clear which selected TPL contract serves each retailer. As a 
result, all information needed to fix TN is known after Step 2, and the algorithm fixes 
these binary variables in Step 3.  
 
5.4.4. Step 4: Fixing Tours of Owned Vehicles in the Upper Level 
In the first stage of Step 4, all rental vehicles of the upper level are excluded from the 
fleet and the model is solved by Xpress with this reduced fleet size in the upper level. 
Using rental vehicles for deliveries increases the total cost, which the model may 
cancel out by assigning very small numbers to their routing binary variable. This 
strategy, however, forces the model to use its owned fleet for all deliveries first. The 
delivery plan shown in Figure 5-3 can be an output after excluding rental trucks from 
the upper fleet. Since the focus of this step is on the upper level, details of the lower 
level have not been included in the figure.  
 
Figure 5-3 A sample of Xpress output after the third step of heuristic 1 
 105 
 
According to Figure 5-3, the model has used two owned vehicles for 
transportation of syrup concentrate in the upper level. Each vehicle visits two bottlers 
through two separate tours. Moreover, the routing binary variable shown in the figure 
has a decimal value over all used links in the upper level. Therefore, the current 
solution is not feasible for the original model from two standpoints: First, the binary 
variable has non-integer value, and second, each truck does more than one trip per 
time step, which is inconsistent with the 7th assumption in Section 3.3. 
 In the next stage of Step 3, for every vehicle available in the solution of the 
upper level, one link among all the links used by different tours of that particular 
vehicle is chosen randomly and fixed to one. For instance, in the solution shown in 
Figure 5-3, which has used two vehicles in four tours, the routing binary variable of 
two links are fixed to one, as shown in Figure 5-4. 
 
 
Figure 5-4 Fixing one link per owned vehicle in the upper level 
 
 106 
 
As a result, some constraints are added to the model. The number of added 
constraint is equal to the number of used owned vehicles in the upper level. In each 
constraint, one link is fixed to one for one particular truck. The new relaxed model is 
solved again with Xpress and the solution is analyzed to see whether it has any other 
non-integer value for a routing binary variable in the upper level. In the new solution, 
more owned vehicles than in the previous solution may be used?or the same 
vehicles used?but the fixed links are definitely in the solution, and the number of 
tours may be decreased. For example, the decision made in Figure 5-4 means that the 
vehicle visiting bottlers 8 and 9 cannot have two tours anymore, because constraint 3-
 1 forces the summation of the routing variables of a vehicle leaving a plant to be less 
than or equal to one, and this vehicle has already a link with a value of 1 for its 
routing variable. Figure 5-5 presents a potential solution found by Xpress.  
 
Figure 5-5 A sample solution of Xpress after fixing one link per owned vehicle in the upper level 
 
 107 
 
According to Figure 5-5, one vehicle has a complete tour with an integer value 
for the routing binary variable; however, this step of the algorithm needs to be 
repeated until the model finds a complete and feasible tour for the other vehicle. If, 
during this stage, another unused owned vehicle is added to the fleet, the algorithm 
fixes links for that vehicle as well. The final output of Step 3 includes feasible tours 
of owned vehicles in the upper level.  
 
5.4.5. Step 5: Fixing Tours of Owned Vehicles in the Lower Level 
This step is identical to Step 4, but is applied to owned vehicles in the lower level. 
Rental vehicles, therefore, are excluded from the fleet first. The algorithm then fixes 
one link for every owned vehicle used in each iteration, and Xpress solves the new 
model with added constraints. The final output of this step is a feasible solution, with 
tours in the upper and lower levels operated by owned vehicles. 
 
5.4.6. Step 6: Using other vehicles according to shortage and inventory level 
In Step 6, another vehicle is added to the fleet if the model needs it. There are two 
parameters needed to make a decision as to whether adding another vehicle improves 
the profit or not. Shortage is the first parameter, which is defined as a summation of 
shortages of all products over all retailers in the first time step. The second parameter 
is inventory level, which is equal to summation of inventory levels of all commodity 
types over all bottlers in the first time step. According to shortage amounts and 
inventory levels, different scenarios happen as follows: 
 108 
 
1- Shortage > 0, Inventory level > 0, and Shortage < Inventory level 
In this case, enough products have been produced by bottlers; however, the 
fleet of the lower level is not large enough to satisfy some orders. As a result, one 
vehicle must be added to the fleet of the lower level. 
2- Shortage > 0 and Inventory level = 0 
  In this scenario, bottlers do not have enough syrup concentrate to produce 
more commodity. Consequently, some retailers? orders are not satisfied completely. 
In this case, a vehicle must be added to the fleet of the upper level. 
3- Shortage > 0, Inventory level > 0, and Shortage > Inventory level 
In this case, not only the fleet size of the lower level is small for deliveries, 
but more syrup concentrate is needed to produce more final product at bottlers. 
Therefore, if a vehicle can be added to the fleet of the upper level, more syrup 
concentrate can be brought to bottlers; otherwise, adding another vehicle to the fleet 
of the lower level fills some unsatisfied demands. 
4- If a vehicle is added to the upper level and the quantity of shortage is still 
positive and has not changed after adding that vehicle, the fleet in the lower level 
needs another vehicle to deliver products. This scenario happens after any of previous 
cases occur and the associated decisions have been made.  
In any of these scenarios, the algorithm gives a priority to owned vehicles. In 
other words, if the algorithm needs to add a vehicle and if an unused owned vehicle is 
available, that vehicle is added. Otherwise, the algorithm adds the rental vehicle with 
the minimum fixed and operational costs. This policy is applied for both levels. 
 109 
 
After a vehicle is added to the fleet, the relaxed model is executed again with 
the new fleet size. The solution may have infeasible tour(s) for the new vehicle. Then, 
Step 4 or 5 is executed repeatedly, depending on the level to which the vehicle is 
added, until the tour of that added vehicle becomes feasible. Step 6 is performed on 
the solution again and adds another vehicle to one of the levels if any of cases 
mentioned above become true. Again, Step 4 or 5 is executed. The loop is terminated 
when either all orders are satisfied or the algorithm uses all owned and rental trucks. 
 
5.4.7. Step 7: Checking the Cost Binary Variables of Rental Vehicles 
In Step 7, if a rental vehicle is used in the upper or lower level, the algorithm fixes its 
fixed and operational costs? binary variables. These variables are relaxed in the 
Xpress model, and since they increase the cost?which then decreases the company?s 
profit?the model assigns a small number to them if it cannot take them as zero. 
Therefore, the algorithm fixes any costs? binary variables of rental vehicles to one if 
they are not zero in the solution found by Xpress. 
 
5.4.8. Step 8: Executing the Same Procedures for the Next Time Step 
After Step 7, the algorithm has found the feasible solution for the first time step. The 
algorithm considers the effects of future time steps on the current one and makes a 
decision based on those effects. The algorithm then runs the same procedures for the 
second time step while all variables of the first time step have been fixed. As a result, 
the running time of each step is decreased. The algorithm still takes the impact of 
 110 
 
future time steps on the second one into account. After all steps are finished for the 
second time step, the solution is complete for the first two time steps and the 
algorithm continues running the procedures for the third time step. The algorithm 
keeps running until it finds the solution for the last time step. The entire algorithm of 
heuristic 1 can be described as follows:  
Step 1: Set Counter = 0 and t=1. Relax all integer decision variables and solve 
the model optimally. 
Step 2: Find all w decision variables in all time steps, which are less than 1/M. 
Step 3: Add a constraint for each w decision variable found in previous step to 
fix that variable to zero.  
Step 4: Do the rest of algorithm for time step t. 
Step 5: Find all w decision variable(s) greater than 1/M and less than one. 
Step 6: If only one w is found, add a constraint to the model and fix that w to 
one. Run the new relaxed model and go to Step 5. 
Step 7: If more than one w is found, find the w which has the maximum value. 
Add a constraint to the model to fix this w to one. Run the new relaxed model and go 
to Step 5. 
 Step 8: For each pair of a retailer and a TPL contract, check the associated TN 
decision variable (TNi) to see if it is integer or not. If it is not integer go to Step 9, 
otherwise go to Step 12. 
 Step 9: If the set of Fix_TN includes another TN decision variable for the same 
retailer but with different TPL contract, add TNi to Exclude_TN; otherwise add TNi to 
Fix_TN. 
 111 
 
 Step 10: Add one constraint for each TN variable in Fix_TN and fix it to one. 
 Step 11: Add one constraint for every TN decision variable in Exclude_TN and 
fix it to zero. 
 Step 12: Go to Step 8 and do the same process for another pair of a retailer 
and a TPL contract. 
Step 13: If Added_Rental_Upper set is empty and Counter = 0, exclude all 
rental vehicles from the fleet of the upper level; otherwise, if Added_Rental_Upper 
set is not empty, add every vehicle k in Added_Rental_Upper set to the fleet of the 
upper level. 
Step 14: Solve the new relaxed model optimally. 
Step 15: Find all non-integer XU in the optimal solution of the relaxed model. 
Step 16: Find vehicles used in the optimal solution of the relaxed model. 
Step 17: For every vehicle used, find one link used by that vehicle and has a 
non-integer XU. Add a constraint to the model to fix XU of the selected link to one. 
Step 18: Solve the new relaxed model optimally. 
Step 19: If there is any non-integer XU in the optimal solution, go to Step 15. 
Step 20: If Added_Rental_Lower set is empty and Counter = 0, exclude all 
rental vehicles from the fleet of the lower level; otherwise, if Added_Rental_Lower 
set is not empty, add every vehicle k in Added_Rental_Lower set to the fleet of the 
lower level. 
Step 21: Solve the new relaxed model optimally. 
Step 22: Find all non-integer XW in the optimal solution of the relaxed model. 
Step 23: Find vehicles used in the optimal solution of the relaxed model. 
 112 
 
Step 24: For every vehicle used, find one link used by that vehicle and has a 
non-integer XW. Add a constraint to the model to fix XW of the selected link to one. 
Step 25: Solve the new relaxed model optimally. 
Step 26: If there is any non-integer XW in the optimal solution, go to Step 22. 
Step 27: Add one unit to Counter 
Step 28: Calculate the shortage(Counter) in retailers and inventory 
level(Counter) at bottlers for every commodity type. 
Step 29: If Counter is not equal to 1 and shortage(Counter)= 
shortage(Counter-1) and shortage(Counter)>0 go to Step 30; otherwise go to Step 
31. 
Step 30: If there is unused rental vehicles in the fleet of the lower level, find 
the rental vehicle with the minimum fixed and operational costs and add it to the 
Added_Rental_Lower set. Then, go to Step 20. 
Step 31: If shortage(Counter)> 0 and inventory level(Counter)> 0 and 
inventory level(Counter)> shortage(Counter) go to Step 32; otherwise go to Step 33. 
Step 32: If there is unused rental vehicles in the fleet of the lower level, find 
the rental vehicle with the minimum fixed and operational costs and add it to the 
Added_Rental_Lower set. Then, go to Step 20. 
Step 33: If (shortage(Counter)> 0 and inventory level(Counter)= 0) or 
(inventory level(Counter)>0 and  shortage(Counter)>0 and  shortage(Counter)> 
inventory level(Counter)) go to Step 34; otherwise go to Step 36. 
 113 
 
Step 34: If there is unused rental vehicles in the fleet of the upper level, find 
the rental vehicle with the minimum fixed and operational costs and add it to the 
Added_Rental_Upper set. Then, go to Step 13. Otherwise, go to Step 35. 
Step 35: If there is unused rental vehicles in the fleet of the lower level, find 
the rental vehicle with the minimum fixed and operational costs and add it to the 
Added_Rental_Lower set. Then, go to Step 20. 
Step 36: For every used rental vehicles in the upper level, add constraints to 
fix its variables of fixed and operational costs to one. 
Step 37: For every used rental vehicles in the lower level, add constraints to 
fix its variables of fixed and operational costs to one. Run the new relaxed model. 
Step 38: If a vehicle has not been used by the model in the upper level, add it 
to Exclude_Upper set. Add a constraint to the model for each vehicle in 
Exclude_Upper set to fix its XU over all links of the upper level to zero. 
Step 39: If a vehicle has not been used by the model in the lower level, add it 
to Exclude_Lower set. Add a constraint to the model for each vehicle in 
Exclude_Lower set to fix its XW over all links of the lower level to zero. 
Step 40: Solve the new relaxed model optimally. 
Step 41: If the algorithm is in the last time step, it terminates; otherwise, set 
t=t+1 and go to the Step 4. 
Figure 5-6 shows the flow chart of the proposed heuristic for the first time 
step.   
 114 
 
Is there any 
0.001<w<1? 
Yes 
Is there any 
0<XU<1? 
No 
A E 
  
Start 
Solve the relaxed model 
Fix all w<0.001 to 0 for all time steps 
Solve the relaxed model 
IIs t 
Find the 
maximum 
w and fix 
it to 1 
Fix all TN>0 to 1 
Fix all XU for rental vehicles to 0 
Solve the relaxed model 
Put all non-integer XU in set ku 
For each vehicle in a set ku, fix one XU to 1 
Solve the relaxed model 
IIs t 
Yes 
No 
Figure 5-6 The flow chart of heuristic 1 in the first time step 
 115 
 
Is there any 
0<XW<1? 
Yes 
c<>1 and shortage(c) > 0 and 
shortage(c) = shortage(c-1)? 
IIs t 
A 
B 
No 
No 
Is there any 
unused rental 
vehicle in the 
lower level? 
Yes 
Yes 
No 
C D 
E 
 
 
  
Fix all XW for rental vehicles to 0 
Solve the relaxed model 
Put all non-integer XW in set kw 
For each vehicle in a set kw, fix one XW to 1 
Solve the relaxed model 
IIs t 
Calculate shortage at retailers 
and inventory level at bottlers 
c := c + 1 
IIs t 
Add a rental vehicle 
to the lower level 
with the minimum 
cost 
Add a rental vehicle 
to the lower level 
with the minimum 
cost 
Figure 5-6 The flow chart of heuristic 1 in the first time step (Cont?d) 
 116 
 
B 
shortage(c)>0 & Inventory(c)>0 
& Shortage(c)<inventory(c)? 
Is there any 
unused rental 
vehicle in the 
lower level? 
C 
Yes 
Yes 
[Shortage(c)>0 & inventory(c)=0)] 
or [(shortage(c)>0 & inventory(c)>0 
& shortage(c)>inventory(c)]? 
No 
No 
Is there any 
unused rental 
vehicle in the 
upper level? 
Yes 
No 
D 
Yes 
No 
Is there any 
unused rental 
vehicle in the 
lower level? 
Yes 
No 
 
 
 
  
IIs t 
IIs t 
IIs t 
IIs t 
Add a rental vehicle 
to the upper level 
with the minimum 
cost 
Fix variables related to costs of rental vehicles 
Fix variables of unused vehicles to 0 
Do the same processes on the next time step 
until the last time step is reached 
Keep the solution as the best solution of the 
algorithm (BS) 
Figure 5-6 The flow chart of heuristic 1 in the first time step (Cont?d) 
IIs t 
 117 
 
5.5. Improvement of a Solution 
In developing the first heuristic described in Section 5.4, the target was considering 
all aspects so as to build a comprehensive heuristic method. The final solution found 
by heuristic 1, however, can potentially be improved. In this section, three different 
procedures are introduced that can improve the objective function of the final 
solution. These procedures reconsider TPL warehousing, avoiding redundant TPL 
contracts, and saving in tour cost. The performance of these improvement phases 
depends on the quality of the input data and final solution, which will be explained in 
detail later. 
 
5.5.1. Phase 1: Reconsidering TPL Warehousing 
In the first phase of improvement, TPL warehousing is analyzed to see whether it can 
lower the total cost. As mentioned in Chapter 3, the model has a capability of storing 
products in TPLP warehouses to save TPL shipping cost. If the original model with 
binary variables is solved, the difference between the cost of two separate deliveries 
by TPLP and the cost in the case of one delivery and storage in a TPLP warehouse is 
recognized correctly. In the proposed heuristic, the algorithm is free to pick any small 
numbers for binary variables. The mentioned difference, therefore, is canceled out, 
whereas the real objective function will decrease.  
According to Step 3 of the algorithm described in Section 5.4.3, the algorithm 
fixes one TPL shipping contract at each iteration. The contract is selected randomly 
and its binary variable must have a positive value. As mentioned, the model may 
choose a very small number, which results in two separate deliveries instead of 
 118 
 
storage in a TPLP warehouse. Therefore, in the first phase of improvement, the 
potential benefit of storing products in TPLP warehouses is analyzed.  
If a TPL shipping contract is selected for two successive time steps, the binary 
variable associated with the second time step is fixed to zero. The new relaxed model 
is solved by Xpress optimally. Since it is assumed that all retailers visited by the 
deleted contract must be served with the same TPLP, the model has to store products 
in a TPLP warehouse.  
The added constraint, which set the second contract binary variable to zero, is 
not consistent with the previous solution. Therefore, the current solution, which is the 
best one so far, is stored. In other words, all TPL contract binary variables except for 
the deleted contract are kept in the solution. Constraints associated with other 
contracts remain in the model. Other variables such as routing and commodity flow 
variables are relaxed, and the new solution is found by Xpress. In this solution, in 
addition to TPL binary variables, other variables may have non-integer values. 
Therefore, all steps after Step 2 are executed on the solution to find a feasible 
solution. Tours can be changed, in comparison to the previous feasible solution. Also, 
more or fewer rental vehicles can be used in the final solution. Eventually, the 
objective function of the final solution is compared to that of the best solution found 
before starting the improvement phases. If the new objective function shows 
improvement, the current solution is stored as the best solution; otherwise, the 
algorithm keeps the best solution, which means the fix-and-run algorithm ignores the 
final output of phase 1. Then the procedure is executed again for more savings. The 
 119 
 
first phase of improvement is finished when it checks all successive selected TPL 
contracts. The algorithm of the first improvement phase can be described as follows: 
Step 1: Set t = the last time step 
Step 2: Generate Temp_Set and Temp_Var for different sets and decision 
variables of the current solution. Store elements of each set in its associated Temp_Set 
and value of each variable in its associated Temp_Var. This phase uses Temp sets and 
variables in the operation. 
Step 3: If the same w variable has been selected in time steps t and t-1, go to 
Step 4; otherwise go to Step 9. 
Step 4: If w exists in Tabu_Set, go to Step 8; otherwise go to Step 5. 
Step 5: Add a temporary constraint to the model to fix w to zero in time step t 
and solve the new relaxed model optimally. 
Step 6: Do Steps 13 to 37 of heuristic 1 with temporary sets and variables. 
Step 7: Compare the obtained objective function with the objective function of 
the solution before starting the first improvement phase. If it has improved, keep the 
change and update all sets and variables. In fact, store Temp_Sets in permanent sets 
and Tem_Vars in permanent variables. Then, go to Step 2; otherwise, add w to the 
Tabu_Set and go to Step 2. 
Step 8: Check another w variable in time step t. If there is another w in time 
step t go to Step 3.  
Step 9: Set t=t-1. If t=1 this phase is terminated; otherwise, go to Step 3. 
 
 120 
 
5.5.2. Phase 2: Avoiding Redundant TPL Contracts 
The main goal of this phase of improvement is the same as the first phase: saving on 
the cost of TPLP contracts. However, phase 2 is different from phase 1 in some 
details. In phase 1, the algorithm considers only contracts that have been selected for 
two successive time steps, on the second time step. For instance, if a contract is 
selected in time steps one and two, the algorithm relaxes the binary variable of time 
step two to determine whether it benefits the model. By this policy, the contract on 
time step 1 will definitely be in the final solution. Moreover, if a contract is selected 
only in one time step, it will not be checked by the first phase. As a result, all TPL 
contracts selected in the solution are not considered by phase 1.  
Phase 2 of improvement analyzes all TPL contracts one by one to see whether 
there is any benefit in removing a contract from the solution. Another main difference 
between phase 1 and 2 is that in phase 2, if a contract is deleted from the solution, 
retailers served by that contract can be visited by owned or rental trucks. In other 
words, the algorithm can change the shipping plan significantly, meaning that some 
retailers which had been visited by TPLP trucks in the best solution can be served by 
owned or rental trucks. In fact, tours of owned and rental trucks may change 
substantially. Therefore, the operation of phase 2 can be summarized as follows: It 
keeps the current solution as the best solution. It then relaxes all routing and flow 
variables, as well as one of the selected TPL contracts. The rest of the selected TPL 
contracts remain in the model. Xpress solves the new relaxed model and generates 
new tours, which may visit retailers of the deleted TPL contract. All steps of the fix-
 and-run algorithm that fix routing variables and rental-vehicle cost variables are 
 121 
 
executed to reach a feasible solution. If the objective function of the new solution is 
greater than that of the best solution, the best solution is replaced with the new one 
and all changes are accepted; otherwise, the deleted TPL contract is known as the 
crucial contract and will remain in the solution. Another TPL contract is then 
analyzed and the same procedure executed. Phase 2 is finished after analyzing all 
selected TPL contracts. The algorithm of the second improvement phase can be 
described as follows: 
Step 1: Generate Temp_Set and Temp_Var for different sets and decision 
variables of current solution. Store elements of each set in its associated Temp_Set 
and value of each variable in its associated Temp_Var. Similar to Phase 1, this phase 
uses Temp sets and variables in the operation. 
Step 2: Empty Temp_Fix_TN and Temp_Exclude_TN. In fact, the model is 
free to make decision for every TN variable. 
Step 3: Pick one of the w variables has been selected in time steps t. If w exists 
in Tabu_Set, go to Step 7; otherwise go to Step 4. 
Step 4: Add a temporary constraint to the model to fix w to zero in time step t 
and solve the new relaxed model optimally. 
Step 5: Do Steps 8 to 37 of heuristic 1 with temporary sets and variables for 
all time steps. 
Step 6: Compare the obtained objective function with the objective function of 
the solution before starting the second improvement phase. If it has improved, keep 
the change and update all sets and variables. In fact, store Temp_Sets in permanent 
 122 
 
sets and Tem_Vars in permanent variables; otherwise, add w to the Tabu_Set and go 
to Step 1. 
Step 7: Check another w variable. If there is no more w, the second phase of 
improvement is terminated; otherwise, go to Step 2. 
 
5.5.3. Phase 3: Saving in Tour Cost 
Heuristic 1 fixes one link for every vehicle in each iteration. The selected link for a 
vehicle carries products to the facility location at the end of the link in that particular 
iteration. In next iterations, the algorithm may find delivery to that facility location by 
another vehicle more beneficial. In other words, other links that end at the same 
facility location may be selected by the algorithm for other delivery vehicles. 
Therefore, in the final solution of heuristic 1, more than one vehicle visits one 
location, but only one of them serves it. This situation happens in the final situation, 
because heuristic 1 selects links one by one and, as it gets close to the end, using all 
selected links for delivery is not optimal. As a result, vehicles move along some links 
without serving bottlers or retailers located at the end of the link. Figure 5-7 shows a 
sample of final output in which a vehicle visits retailers 1, 2, 3, and 4; however, it 
delivers to only retailers 1 and 4.  
 
 123 
 
 
Figure 5-7 A sample solution of Xpress showing redundant links in the path of one vehicle 
 
Since travel times of links are triangular, the model saves the tour cost if the 
vehicle goes from retailer 1 to retailer 4 directly. In this case, the truck skips 
redundant retailers in its path and visits only retailers for which it has products. This 
situation can happen in the upper level, where a truck can pass some bottlers with no 
delivery. Figure 5-8 shows the output of running phase 3 on the solution shown in 
Figure 5-7. 
 124 
 
 
Figure 5-8 The output of applying phase 3 to the situation shown in Figure 5-7 
 
The algorithm of the third improvement phase can be described as follows: 
Step 1: Set t = 1. 
Step 2: Set routing variable XU to one for all selected links in time step t in 
the current solution. 
Step 2: Put all links passed by a vehicle k in separate set Route_k. 
Step 3: Sort links of each set Route_k based on the path of the vehicle k. 
Step 4: If delivery of vehicle k to location j is zero, the link which ends at 
location j is deleted from the set Route_k. Also, the link which starts from location j is 
deleted from the set Route_k. 
Step 5: Connect the origin node of the first deleted link to the destination node 
of the second deleted link. 
Step 7: Repeat Step 1 to 5 for XW in time step t. 
 125 
 
Step 8: Set t = t+1. If t is less than or equal to planning horizon length, repeat 
Steps 1 to 8 for the new time step; otherwise, go to Step 9. 
Step 9: Compare the obtained objective function with the objective function of 
the solution before starting the third improvement phase. If it does not change, the 
third improvement phase is terminated; otherwise, go to Step 1. 
 
5.6. Numerical Results 
In this section, results obtained by solving different scenarios with heuristic 1 are 
presented and described in detail. First, several categories were designed, each having 
particular characteristics. Then several scenarios were generated in each category 
according to the characteristics of that category. Therefore, scenarios that are in one 
category have the same number of facility locations, fleet size, number of commodity 
types, number of candidate TPL contracts, and other major model characteristics; 
however, input data for scenarios in the same category are different.  
 
5.6.1. Category 1 
The first category is the smallest of all the categories. Table 5-1 illustrates the 
main characteristics of category 1.  The smallest category of scenarios has 6,320 
constraints and 62,423 decision variables. 10 scenarios were generated in this 
category, which have different input data?but the main characteristics are the same 
and equal to the amounts shown in Table 5-1. All input data for the 10 scenarios were 
generated randomly according to the assumed normal distribution introduced in 
 126 
 
Chapter 4. Each scenario was solved by both Xpress 7.1 and heuristic 1. The results 
of different solvers on scenarios are reported in Table 5-2. 
 
Table 5-1. Main characteristics of Category 1 
Criterion Value 
Number of Plants 2 
Number of Bottlers 3 
Number of Retailers 6 
Number of Commodity Types 2 
Number of Available TPL Contracts 2 
Number of Owned Trucks in the Upper Level 2 
Number of Rental Trucks in the Upper Level 2 
Number of Owned Trucks in the Lower Level 2 
Number of Rental Trucks in the Lower Level 2 
Number of Time Steps 3 
Number of Constraints 6,320 
Number of Decision Variables 62,423 
 
 
Table 5-2. Comparison between results of Xpress and Heuristic 1 on Category 1 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 49330 48875 0.92 0.92 771 43 
2 49105 48259 1.72 1.82 9473 43 
3 49330 48791 1.09 1.09 152 37 
4 49356 49035 0.65 0.65 204 40 
5 45088 44971 0.25 0.25 23 47 
6 47877 47167 1.48 1.48 318 46 
7 45726 45068 1.43 1.46 79040 53 
8 45088 44486 1.34 1.34 98 45 
9 44841 44484 0.79 0.79 30 45 
10 46299 45951 0.75 0.91 1530 50 
 
Xpress was not able to find the optimal solution for some scenarios. For these 
scenarios, the best solution found by Xpress is reported in Table 5-2, which may not 
be the optimal. The gap between the objective function of the solution found by 
 127 
 
heuristic 1 and the best solution found by Xpress is reported in the fourth column, and 
the gap between the objective function of the heuristic 1 solution and the best bound 
found by Xpress can be found in the fifth column of Table 5-2. The best bound is the 
closest infeasible solution to the best solution. Obviously, for scenarios for which 
Xpress finds the optimal solution, the best bound and the best solution are equal to 
each other. In these cases, the gaps reported in the 4th and 5th columns in Table 5-2 are 
equal. The last two columns of Table 5-2 represent running times of Xpress and 
heuristic 1, respectively. 
According to Table 5-2, Xpress could not find the optimal solution for 
scenarios 2, 7, and 10. In all scenarios, Xpress found better solutions than heuristic 1; 
however, the gap between heuristic 1?s objective function and the best solutions 
found by Xpress is less than 2%. On the other hand, heuristic 1 found the solution in 
less than one minute, while the running time of Xpress was significantly longer.  
Table 5-3 summarizes the information presented in Table 5-2. According to 
Table 5-3, the average gap between the heuristic 1 solution?s objective function and 
the Xpress solution?s objective function is around 1%, which is very small. In 
addition, Table 5-3 indicates the advantage of using the proposed heuristic, which is 
its short running time. Xpress needed to run 9100 seconds on average to find the 
optimal or near-optimal solution. Also, if Scenario 7 is not considered, Xpress still 
needed to run 1400 seconds on average; however, heuristic 1, after less than 45 
seconds, found a solution that was very close to the Xpress solution.     
  
 128 
 
Table 5-3. Criteria for comparison of Xpress and fix-and-run based on Category 1 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
1.07 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
0.21 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
1.04 
Variance of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress 
0.20 
Average of Xpress Running Time (CPU seconds) 9164 
Average of Xpress Running Time without considering Scenario 7 
(CPU seconds) 
1400 
Average of the Heuristic 1 Running Time (CPU seconds) 45 
 
Table 5-3 indicates that the proposed algorithm is efficient on small   
problems. The performance of this algorithm on larger problems is analyzed in the 
following sections. 
 
5.6.2. Category 2 
This category contains more retailers and larger fleet size than Category 1. As 
a result, the scenarios generated in this category are larger than scenarios for Category 
1. Table 5-4 presents the main characteristics of Category 2. This category of 
scenarios has 19846 constraints and 270319 decision variables, which is three times 
larger than for the scenarios in Category 1. Similar to Category 1, 10 scenarios with 
differences in input data were generated in this category. Again, each scenario was 
solved by both Xpress 7.1 and heuristic 1, and the results are reported in Table 5-5. 
 
 
 
 
 
 129 
 
Table 5-4. Main characteristics of Category 2 
Criterion Value 
Number of Plants 2 
Number of Bottlers 3 
Number of Retailers 10 
Number of Commodity Types 2 
Number of Available TPL Contracts 2 
Number of Owned Trucks in the Upper Level 3 
Number of Rental Trucks in the Upper Level 3 
Number of Owned Trucks in the Lower Level 3 
Number of Rental Trucks in the Lower Level 3 
Number of Time Steps 3 
Number of Constraints 19,846 
Number of Decision Variables 270,319 
 
 
Table 5-5. Comparison of results of Xpress and Heuristic 1 on Category 2 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 80170 78940 1.53 1.53 42615 438 
2 79901 78405 1.87 1.90 21570 860 
3 80122 78527 1.99 2.39 4482 599 
4 80129 79125 1.25 1.53 9283 469 
5 80239 79763 0.59 0.81 19755 389 
6 81656 81042 0.75 0.90 9897 404 
7 82998 82470 0.63 0.74 25387 382 
8 82681 82101 0.70 0.70 36195 424 
9 81235 79062 2.67 3.38 17306 433 
10 80455 78234 2.76 3.47 61521 387 
 
In this category, more scenarios than Category 1 were not solved by Xpress 
optimally. According to Table 5-5, Xpress was not able to find the optimal solution in 
8 scenarios out of 10. Since the problems in Category 2 are larger than Category 1, 
the running times for Xpress and heuristic 1 increase compared to the previous 
category. Running time of heuristic 1 was, at most, less than 15 minutes, which is 
 130 
 
short; however, in some cases, after 5 hours Xpress had still not found the optimal 
solution. Table 5-6 summarizes information presented in Table 5-5, which more 
clearly compares the performance of Xpress and the fix-and-run algorithm on 
Category 2.  
Table 5-6. Criteria for comparison of Xpress and fix-and-run based on Category 2 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
1.71 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
1.09 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
1.47 
Variance of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress 
0.68 
Average of Xpress Running Time (CPU seconds) 24801 
Average of the Heuristic 1 Running Time (CPU seconds) 478 
 
According to Table 5-6, the average gap between heuristic 1?s objective 
function and the objective function of the best solution found by Xpress was 1.47%. 
The gap with the best bound found by Xpress was 1.71%. On the other hand, the 
average running time for heuristic 1 and Xpress was 478 and 24801 seconds, 
respectively. As a result, heuristic 1 found solutions that were close to Xpress results 
in a short time. In other words, the gap and running time are in a reasonable range, 
which shows the strength of the proposed heuristic.  
  
5.6.3. Category 3 
This category includes 15 retailers, but the rest of its main characteristics are 
the same as those of Category 2. Table 5-7 shows the main characteristics of 
Category 3. This category of scenarios has 39721 constraints and 696819 decision 
 131 
 
variables, meaning that problems in this category are medium size. Similar to 
Category 1 and 2, 10 scenarios with different input data were generated in this 
category to be solved with Xpress 7.1 and heuristic 1. The results are reported in 
Table 5-8. 
Table 5-7. Main characteristics of Category 3 
Criterion Value 
Number of Plants 2 
Number of Bottlers 3 
Number of Retailers 15 
Number of Commodity Types 2 
Number of Available TPL Contracts 2 
Number of Owned Trucks in the Upper Level 3 
Number of Rental Trucks in the Upper Level 3 
Number of Owned Trucks in the Lower Level 3 
Number of Rental Trucks in the Lower Level 3 
Number of Time Steps 3 
Number of Constraints 39,721 
Number of Decision Variables 696,819 
 
 
Table 5-8. Comparison of results of Xpress and Heuristic 1 on Category 3 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 118019 115040 2.52 3.01 38656 5027 
2 89067 84750 4.84 5.86 12029 15255 
3 115753 109276 5.59 6.05 53738 11330 
4 118047 115864 1.85 2.30 29160 6456 
5 122439 120294 1.75 2.01 18072 5569 
6 113127 110855 2.00 2.37 50871 5054 
7 109817 108639 1.07 1.67 25023 2751 
8 111336 107411 3.52 3.89 29228 6386 
9 121530 119689 1.51 2.00 13021 5711 
10 109682 107916 1.60 1.60 15123 5849 
 
 132 
 
In this category, only the last scenario was solved optimally by Xpress. This 
demonstrates that the complexity of the problem is sensitive to the number of facility 
locations in the lower level. Increasing the number of retailers from 10 to 15 not only 
increases the size of the problem significantly, but also makes the problem very 
complicated. As a result, the running times for Xpress and heuristic 1 increase 
remarkably in comparison to Categories 1 and 2. Table 5-9 summarizes the 
information reported in Table 5-8.  
Table 5-9. Criteria for comparison of Xpress and fix-and-run based on Category 3 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
3.08 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
2.76 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
2.62 
Variance of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress 
2.33 
Average of Xpress Running Time (CPU seconds) 28492 
Average of the Heuristic 1 Running Time (CPU seconds) 6939 
 
According to Table 5-9, the average gap between heuristic 1?s objective 
function and the objective function of the best solution found by Xpress was 2.62%, 
and 3.08% with the best bound found by Xpress. The gap, therefore, is still in the 
acceptable range. In addition, the running time of heuristic 1 was much more than 
Category 2; however, it was much less than that of Xpress. As a result, the proposed 
heuristic performs well in this category. 
 
 133 
 
5.6.4. Category 4 
The number of facility locations in this category is the same as Category 3; 
however, its fleet size is larger and it has more commodity types than Category 3. 
Table 5-10 shows the main characteristics of Category 4. This category of scenarios 
contains 61141 constraints and 1,189,923 decision variables. In other words, the 
problem is medium size. Five scenarios with different input data were generated in 
this category to be solved with Xpress 7.1 and heuristic 1. The results are reported in 
Table 5-11. 
Table 5-10. Main characteristics of Category 4 
Criterion Value 
Number of Plants 2 
Number of Bottlers 3 
Number of Retailers 15 
Number of Commodity Types 3 
Number of Available TPL Contracts 2 
Number of Owned Trucks in the Upper Level 4 
Number of Rental Trucks in the Upper Level 3 
Number of Owned Trucks in the Lower Level 4 
Number of Rental Trucks in the Lower Level 3 
Number of Time Steps 3 
Number of Constraints 61,141 
Number of Decision Variables 1,189,923 
 
 
Table 5-11. Comparison of results of Xpress and Heuristic 1 on Category 4 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 147348 145667 1.14 1.87 8333 20505 
2 142034 141410 0.43 0.43 3501 13819 
3 142503 139972 1.77 1.83 38038 25458 
4 164400 162589 1.10 1.49 11870 13636 
5 164721 164954 -0.14 0.17 10151 7201.8 
 
 134 
 
In this category, only scenario 2 was solved optimally by Xpress. This shows 
that the complexity of the problem is sensitive to the number of commodity types as 
well as fleet size. The running time of heuristic 1 increases remarkably, in 
comparison to the previous categories. If running time for Xpress is compared to 
Category 3, it shows a decrease in running time despite the fact that the problems are 
larger than the problems in Category 3. This is because the models were stopped 
earlier than in the previous category: After the gap between the solution of Xpress 
and the best bound became less than 0.8%, the model was stopped?whereas models 
in previous categories were executed longer to find smaller gaps. The running time 
for heuristic 1 was much longer than in previous categories, confirming that the size 
of this category is significantly larger than previous categories. The main point of 
Table 5-11 is that in the last case, the proposed heuristic found a better solution than 
that found by Xpress. Table 5-12 summarizes the information reported in Table 5-11.  
Table 5-12. Criteria for comparison of Xpress and Fix & Run based on Category 4 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
1.16 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
0.64 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
0.86 
Variance of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress 
0.53 
Average of Xpress Running Time (CPU seconds) 14378 
Average of the Heuristic 1 Running Time (CPU seconds) 16124 
 
According to Table 5-12, the average gap between heuristic 1?s objective 
function and the objective function of the best solution found by Xpress was less than 
1%, and with the best bound found by Xpress was 1.16%. The gap, therefore, is very 
small, but the running time for heuristic 1 was much more than in Category 3. The 
 135 
 
proposed heuristic needs to run, on average, more than 4 hours to find a good feasible 
solution. This is still acceptable, but would probably increase significantly for larger 
problems, which results in its becoming impractical. 
 
5.6.5. Evaluation of Improvement Phases? Impact on Final Solutions 
As mentioned in Section 5.6.4, the running time of the fix-and-run algorithm grows 
significantly as the problem size increases. The fix-and-run algorithm has two main 
components: general heuristic steps, which find a feasible solution, and improvement 
phases, which try to make a final solution better. In this section, the impact of 
improvement phases is analyzed, because the first two phases are especially time-
 consuming.  
Categories 2, 3, and 4 were selected for this analysis. Two scenarios from 
Category 2, eight scenarios from Category 3, and all scenarios from Category 4 were 
considered for evaluation of the impact of  improvement phases on the final solution. 
The objective function after each improvement phase, therefore, was considered as a 
base for calculations. Table 5-13 shows the results of this evaluation. 
 
 
 
 
 
 
 
 136 
 
Table 5-13. Impact of different improvement phases on the objective function (%) 
Category Scenario Phase 1 Phase 2 Phase 3 
2 
5 0.35 0.96 0.40 
6 0.12 0.42 0.46 
3 
1 0.03 0.00 1.43 
4 0.02 0.00 1.02 
5 0.00 0.00 0.36 
6 0.00 0.00 0.35 
7 0.13 0.00 0.14 
8 0.36 0.00 1.74 
9 0.07 0.00 0.41 
10 0.13 0.00 1.34 
4 
1 0.00 0.00 0.68 
2 0.10 0.00 0.88 
3 0.23 0.05 1.04 
4 0.05 0.00 0.31 
5 0.00 0.00 0.01 
Average 0.11 0.10 0.71 
 
According to Table 5-13, the first and second phases improve the objective 
function 0.11% and 0.10%, respectively. Phase 3 has the best performance among the 
three phases, with 0.71% improvement of the objective-function. As mentioned 
earlier, the first two phases take a long time to execute; however, the output gets 
better, to around 0.1%. On the other hand, phase 3 is a very fast procedure with 
considerable improvement. As a result, the first two phases are only efficient for 
small problems, while the third phase has a remarkable effect on even large problems. 
In other words, applying the base of the fix-and-run algorithm and the third phase 
provides a quality solution in a reasonable amount of running time. For larger 
categories, therefore, the first and second phases of improvement can be eliminated. 
 
 137 
 
5.6.6. Category 5 
Category 5 has more retailers than Category 4. In addition, another TPL contract has 
been added to the model. Table 5-14 shows the main characteristics of Category 5. 
 
Table 5-14. Main characteristics of Category 5 
Criterion Value 
Number of Plants 2 
Number of Bottlers 3 
Number of Retailers 18 
Number of Commodity Types 3 
Number of Available TPL Contracts 3 
Number of Owned Trucks in the Upper Level 4 
Number of Rental Trucks in the Upper Level 3 
Number of Owned Trucks in the Lower Level 4 
Number of Rental Trucks in the Lower Level 3 
Number of Time Steps 3 
Number of Constraints 86,059 
Number of Decision Variables 1,875,966 
 
According to Table 5-14, this category of scenarios contains 86,059 
constraints and 1,875,966 decision variables, which confirms that this category?s 
problems are large size. Five scenarios with different input data were generated in this 
category to be solved with Xpress 7.1 and heuristic 1. The results are reported in 
Table 5-15. 
Table 5-15. Comparison of results of Xpress and Heuristic 1 on Category 5 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 126274 114358 9.44 10.17 34287 34689 
2 147278 146294 0.67 1.54 61888 28574 
3 157349 155822 0.97 1.46 32610 23522 
4 144202 142855 0.93 1.48 24915 15837 
5 145404 143457 1.34 1.80 41285 21806 
 
 138 
 
In this category, except for the gap for scenario 1, which is high, other 
scenarios? gaps are less than 2% and, in some cases, less than 1%. Variances of gap 
between heuristic 1?s objective function and the objective function of the best 
solution and the best bound are very high due to high value for gaps of scenario 1. 
Improvement of phases 1 and 2 was not executed on problems in this category. 
Empirically, they can reduce the gap, especially for the first scenario; however, they 
were removed from the framework for heuristic 1 algorithm for large problems due to 
their expensive running time. Table 5-16 summarizes information reported in Table 
5-15.  
Table 5-16. Criteria for comparison of Xpress and fix-and-run based on Category 5 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
3.29 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
14.81 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
2.67 
Variance of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress 
14.37 
Average of Xpress Running Time (CPU seconds) 38997 
Average of the Heuristic 1 Running Time (CPU seconds) 24885 
 
According to Table 5-16, the average gap between heuristic 1?s objective 
function and the objective function of the best solution found by Xpress is less than 
3%, and with the best bound found by Xpress less than 3.5%. Therefore, the gap for 
this category of large problems is in an acceptable range. Heuristic 1 needed to run an 
average of 7 hours to find a feasible solution, while Xpress needed to run for a longer 
time. 
 
 139 
 
5.6.7. Category 6 
Category 6 has more facility locations in both levels and a larger fleet size than 
Category 5. Table 5-17 shows the main characteristics of Category 6. 
Table 5-17. Main characteristics of Category 6 
Criterion Value 
Number of Plants 3 
Number of Bottlers 4 
Number of Retailers 20 
Number of Commodity Types 3 
Number of Available TPL Contracts 3 
Number of Owned Trucks in the Upper Level 4 
Number of Rental Trucks in the Upper Level 4 
Number of Owned Trucks in the Lower Level 4 
Number of Rental Trucks in the Lower Level 4 
Number of Time Steps 3 
Number of Constraints 152,049 
Number of Decision Variables 4,421,770 
 
Similar to the previous category, five scenarios with different input data were 
generated to be solved with Xpress 7.1 and heuristic 1. The results are shown in Table 
5-18. 
Despite the fact that the size of problems in this category is larger than 
Category 5, the running time is shorter. The reason is that Xpress uses the dual 
simplex as a solver for large problems by default; however, dual simplex is not 
always efficient. Two tests on a relaxed problem in this category, in which the first 
one was solved by dual simplex and the second by primal simplex, show that dual 
simplex found the optimal solution after 600 seconds; primal simplex took 90 
seconds. The solver, therefore, was changed manually for all problems in this 
category, which resulted in shorter running time.  
 
 140 
 
Table 5-18. Comparison of results of Xpress and Heuristic 1 on Category 6 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 176600 175932 0.37 1.60 43823 14161 
2 182435 182312 0.07 1.17 30124 10232 
3 184701 184845 -0.08 1.35 36585 11771 
4 181661 180829 0.46 0.92 65168 6377 
5 178979 178336 0.36 0.87 52403 6834 
 
The gap for problems in this category is less than 2%, which is very 
promising. Moreover, the running time for heuristic 1 was remarkably shorter than 
that of Xpress. Xpress needed to run more than 10 hours while heuristic 1 took 4 
hours at most. Table 5-19 summarizes the information shown in Table 5-18.  
Table 5-19. Criteria for comparison of Xpress and fix-and-run based on Category 6 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
1.18 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
0.09 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
0.24 
Variance of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress 
0.05 
Average of Xpress Running Time (CPU seconds) 45620 
Average of the Heuristic 1 Running Time (CPU seconds) 9875 
 
As Table 5-19 shows, the average gap between objective functions of heuristic 
1 and Xpress is very small. Xpress found better solutions but in longer running times 
most of the time. In addition, heuristic 1 found a better solution than Xpress in 
Scenario 3. As a result, fix-and-run heuristic performance on this large-scale category 
is both good and fast. 
 141 
 
5.6.8. Category 7 
Category 7 has the same number of facility locations as Category 6 but with a longer 
planning horizon, covering 5 time steps instead of 3. The last two scenarios in 
Category 7 include two more vehicles in both levels. Table 5-20 shows main 
characteristics of Category 7. 
Table 5-20. Main characteristics of Category 7 
Criterion Value 
Number of Plants 3 
Number of Bottlers 4 
Number of Retailers 20 
Number of Commodity Types 3 
Number of Available TPL Contracts 3 
Number of Owned Trucks in the Upper Level 4 
Number of Rental Trucks in the Upper Level 4 
Number of Owned Trucks in the Lower Level 4 
Number of Rental Trucks in the Lower Level 4 
Number of Time Steps 5 
Number of Constraints 300,451 
Number of Decision Variables 8,892,749 
Number of Owned Trucks in the Upper Level (in the Last 2 Scenarios) 5 
Number of Rental Trucks in the Upper Level (in the Last 2 Scenarios) 5 
Number of Owned Trucks in the Lower Level (in the Last 2 Scenarios) 5 
Number of Rental Trucks in the Lower Level (in the Last 2 Scenarios) 5 
Number of Constraints (in the Last 2 Scenarios) 314,978 
Number of Decision Variables (in the Last 2 Scenarios) 9,215,024 
 
Problems in this category cannot be solved by Xpress due to their large size, 
as described in Section 4.2.6. A fix-and-run algorithm was tested to solve the same 
problem and results are shown in Table 5-21. It found a feasible solution after 4 days? 
running time for all scenarios. Table 5-22 summarizes the information shown in 
Table 5-21.  
 
 
 
 
 142 
 
Table 5-21. Comparison of results of Xpress and Heuristic 1 on Category 7 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Gap of the Heuristic 1 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 1 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 N.A. 268836 N.A. 3.61 N.A. 4 days 
2 N.A. 272568 N.A. 3.79 N.A. 4 days 
3 N.A. 276753 N.A. 3.31 N.A. 4 days 
4 N.A. 390395 N.A. 3.87 N.A. 4.5 days 
5 N.A. 398105 N.A. 3.63 N.A. 4.5 days 
 
 
Table 5-22. Criteria for comparison of Xpress and fix-and-run based on Category 7 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress (%) 
3.64 
Variance of Gap between Heuristic 1 Solution and the Best Bound 
Found by Xpress 
0.04 
Average of Gap between Heuristic 1 Solution and the Best Solution 
Found by Xpress (%) 
N.A. 
Average of Xpress Running Time (CPU seconds) N.A. 
Average of the Heuristic 1 Running Time (CPU seconds) 4 days 
 
According to Table 5-22, the average gap between heuristic 1?s objective 
function and the objective function of the best bound found by Xpress is 3.64%. Since 
Xpress was not able to find a feasible solution or a bound for these problems, the 
objective function of the relaxed problem was considered as a base to calculate the 
gap. The real gap with the best bound, therefore, is definitely smaller than 3.64%, 
because the relaxed problem solution is not the best infeasible solution. Although the 
gap with the optimal solution is less than 3.64%, if it is considered as the gap it still is 
in an acceptable range and is small. As a result, the proposed heuristic performs better 
than Xpress in providing a good and accurate feasible solution for large problems 
with reasonable distance from the optimal solution. The only problem with heuristic 1 
 143 
 
for large problems is its high running time. It needs to run for 4 days to find a solution 
for the whole planning horizon; however, the proposed heuristic can find a solution 
for the first time step after 1.5 days. Also, the solution for the second time step was 
found after 2.5 days. In other words, the algorithm does not necessarily need to run to 
the end to provide a solution for the first time step. It finds the solution for the first 
time step and then continues to the second time step. Therefore, it can deliver the 
solution of the first time step before starting execution of the second time step. This 
capability of the algorithm makes this method more practical for large problems. 
 
5.7. Summary 
In this chapter, a new heuristic algorithm based on a fix-and-run algorithm was 
proposed to solve the problem under study. This heuristic algorithm is based on 
relaxation of the original problem and fixing integer values for integer variables for 
one time step sequentially. After all integer variables of the time step have been fixed 
to integer values, the algorithm runs the same processes on the next time step. The 
main point of this method is that in the process of decision-making for one time step, 
its impact on future time steps is considered as well as the effect of future decision 
variables on current time-step variables. The algorithm runs faster when it gets close 
to the last time steps, since it has already fixed variables for previous time steps. 
Moreover, three improvement phases were developed to increase the solution 
found by heuristic 1. Two are related to TPL contracts, and the third saves tour cost.   
Finally, seven category problems in this chapter were designed to test the 
proposed heuristic and compare its results to those of Xpress. The sizes of the 
 144 
 
categories varied from small to large problems, and each category included several 
scenarios. Scenarios for each category had the same characteristics, such as the 
number of facility locations, fleet size, the number of final products, and the number 
of time steps; however, input data for the parameters of the scenarios were different 
and were generated randomly, based on the normal distributions described in Chapter 
4.  
Figures 5-9 and 5-10 compare the performance of Xpress and heuristic 1 in 
different categories from the standpoints of gap and running time, respectively. 
According to Figure 5-9, on the average Xpress found better solutions than heuristic 
1; however, it was not able to find feasible solutions for problems in Category 7, 
while heuristic 1 found good feasible solutions for them with acceptable gaps from 
the complete relaxed problem. 
Figure 5-10 compares the running times of Xpress and the proposed heuristic 
in different categories. In all categories, heuristic 1 ran much faster than Xpress, and 
in most categories, it ended after a reasonable amount of computation time. As 
mentioned, Xpress did not find a feasible solution for problems in Category 7. The 
running times for heuristic 1 for problems of Category 7 were very high; however, it 
delivered a plan for the first time step after 1.5 days and for the second time step after 
2.5 days.  
 
 145 
 
 
Figure 5-9. Average gap of the heuristic 1 solution with Xpress outputs in different categories 
 
 
In other words, it is not necessary to wait 4 days to get a solution; the 
algorithm delivers a plan for the time steps gradually. This capability and the 
advantage of providing quality solutions, therefore, make the algorithm attractive for 
large problems. If heuristic 1 is changed to become faster, it will also be more 
practical for real-world problems. This change will be discussed in Chapter 6.   
 
 146 
 
 
Figure 5-10. Average running time for heuristic 1 and Xpress in different categories 
 
The variance of gap between the solution of heuristic 1 and the best solution 
or best bound found by Xpress indicated that in most of categories heuristic 1 
provided consistent solutions. In other words, the difference between gaps in 
scenarios belonging to the same category is not significant except Category 5 that the 
first scenario has higher gap in compare to other scenarios. It confirms that heuristic 1 
performs consistently over different scenarios with the same main characteristics.   
 147 
 
Chapter 6:  The Second Heuristic Approach 
 
 
In this chapter, the second heuristic algorithm is proposed to solve the problem under 
study. This approach is based on the first heuristic method described in Chapter 5, 
with some changes to make it faster. The main problem with the first heuristic 
method is its long running time for some large problems. The algorithm provides a 
quality solution with a small gap from the upper bound in a reasonable amount of 
computation time, which for small and medium size problems is short. Some large 
problems can also be solved by heuristic 1 in a reasonable timeframe. For a particular 
category for which Xpress is not able to find even a feasible solution, however, the 
running time is long. Although heuristic 1 does not need to wait until the end to 
deliver distribution plans for earlier time steps, some parts of it have been changed in 
this chapter to improve the algorithm?s running time. The final output is known as the 
second heuristic algorithm. Section 6.1 explains the changes that were made to the 
first heuristic approach. The results of applying the new heuristic to different 
categories are discussed in Section 6.2. Finally, Section 6.3 summarizes the 
advantages and disadvantages of the second heuristic approach. 
 
 148 
 
6.1. Changes Applied to the First Approach 
As mentioned, the new heuristic method is based on the first approach. The main 
framework, therefore, is the same as the first heuristic. Some steps of heuristic 1 have 
been changed, which are described in this section. 
 
6.1.1. Fixing the Whole Path for Every Vehicle in Steps 4 and 5 
In steps 4 and 5 of heuristic 1, in each iteration for every used vehicle only one link is 
chosen randomly to be fixed. The heuristic, therefore, spends a lot of time routing 
vehicles, but the final solution is accurate enough. In the second heuristic proposed in 
this study, these steps have been changed to make the new heuristic faster. In Step 4 
of heuristic 2, all rental vehicles are first excluded from the fleet of the upper level. 
The new model is then solved by Xpress optimally. Figure 6-1 shows an output of 
Xpress for a problem.  
According to Figure 6-1, two vehicles are used in the upper level; each one 
goes to bottlers through two separate tours, which is not feasible in the original 
problem. For every vehicle used, heuristic 2 recognizes the plant(s) visited. If a 
vehicle starts its tour from one plant, that plant is considered to be a source for the 
vehicle. If tours are begun from different plants, the plant of the link with a higher 
value for routing variable (XU) is considered to be a source. In addition, all bottlers 
visited by a vehicle are recognized and grouped in one category. The final path must 
go to all bottlers in the category. As a result, heuristic 2 finds the shortest tour 
connecting the source to bottlers in the category and returns to the same plant. The 
heuristic, therefore, fixes the routing variable of links on the tour to one. The measure 
 149 
 
of the shortest-tour algorithm used in the heuristic is the summation of travel time 
costs and shipping costs.  
 
 
Figure 6-1 A sample of Xpress output after relaxing routing variables in heuristic 2 
 
Therefore, heuristic 2 selects plant 10 as a source of vehicle 1 and plant 11 as 
a source of vehicle 2. In addition, vehicle 1 must visit bottlers 7 and 8 and vehicle 2 
must visit bottlers 8 and 9. Figure 6-2 presents the output of Xpress after heuristic 2 
fixes links for these two vehicles. 
 150 
 
 
Figure 6-2 The output of Xpress after step 4 of heuristic 2 
 
If a rental vehicle is added to the fleet of the upper level in the next steps, the 
same process is applied to find a tour for the rental vehicle. Moreover, Step 5 of 
heuristic 2 has the same changes as Step 4. In other words, for every owned or rental 
vehicle used in the lower level, a tour is designed in one iteration according to the 
solution of Xpress after relaxation of the routing variables. This change saves 
significant running time for the routing process, and since heuristic 2 repeats this 
process several times, the algorithm?s running time is greatly decreased.  
  
6.1.2. Sending more vehicles in Step 6 
As explained in Section 5.4.6, heuristic 1 calculates shortages and inventory levels of 
a time step in Step 6 and, based on the values of these indexes, and according to 
 151 
 
different scenarios, decides whether another vehicle should be added to either the 
upper or lower level. Only one vehicle, therefore, is added to the fleet in each 
iteration. Heuristic 2 decides the number of added vehicles more intelligently. It takes 
the shortage amounts and inventory levels, as well as average vehicle capacity, into 
account and calculates how many vehicles the model needs to serve unsatisfied 
demands. The number of vehicles needed in the upper level is calculated using 
Equation 6-1. 
                                                                                                   (6-1) 
Where: 
Vui: The number of needed vehicles in the upper level in time step i; 
Xi: The shortage of products for retailers in time step i; 
Yi: The inventory levels for bottlers in time step i; and 
Zu: The average capacity of vehicles in the fleet of the upper level. 
The number of vehicles added to the upper level is then calculated based on Equation 
6-2. 
                                                                                           (6-2) 
Where: 
NUi: The number of vehicles added to the upper level in time step i; 
f(Vui): The function that rounds up the value of Vui; and 
Ai: The number of available vehicles in the upper level in time step i. 
Similarly, the number of vehicles needed in the lower level can be calculated 
according to Equation 6-3. 
                                                                                                            (6-3) 
uiii ZYXVu /)(
 ),)(( iii AVufMinNU
 wii ZXVw /
 152 
 
Where: 
Vwi: The number of needed vehicles in the lower level in time step i; 
Xi: The shortage of products for retailers in time step i; 
Zw: The average capacity of vehicles in the fleet of the lower level. 
The number of vehicles added to the lower level is then calculated according to 
Equation 6-4. 
                                                                                           (6-4) 
Where: 
NWi: The number of vehicles added to the lower level in time step i; 
f(Vwi): The function that rounds up the value of Vwi; and 
Ai: The number of available vehicles in the lower level in time step i. 
As a result, heuristic 2 adds vehicles to the upper and lower levels according to 
Equations 6-2 and 6-4, respectively. The routing process for added vehicle(s) is the 
same as the process described in Section 6.1.1. The entire algorithm of heuristic 2 can 
be described as follows:  
Step 1: Set t=1. Relax all integer decision variables and solve the model 
optimally. 
Step 2: Find all w decision variables in all time steps, which are less than 1/M. 
Step 3: Add a constraint for each w decision variable found in previous step to 
fix that variable to zero.  
Step 4: Do the rest of algorithm for time step t. 
Step 5: Find all w decision variable(s) which are greater than 1/M and less 
than one. 
),)(( iii AVwfMinNW
 153 
 
Step 6: If only one w is found, add a constraint to the model and fix that w to 
one. Run the new relaxed model and go to Step 5. 
Step 7: If more than one w is found, find the w which has the maximum value. 
Add a constraint to the model to fix this w to one. Run the new relaxed model and go 
to Step 5. 
 Step 8: For each pair of a retailer and a TPL contract, check the associated TN 
decision variable (TN1) to see if it is integer or not. If it is not integer go to Step 9, 
otherwise go to Step 12. 
 Step 9: If the set of Fix_TN includes another TN decision variable for the same 
retailer but with different TPL contract, add TN1 to Exclude_TN; otherwise add TN1 to 
Fix_TN. 
 Step 10: Add one constraint for each TN decision variable in Fix_TN and fix it 
to one. 
 Step 11: Add one constraint for every TN decision variable in Exclude_TN and 
fix it to zero. 
 Step 12: Go to Step 8 and do the same process for another pair of a retailer 
and a TPL contract. 
Step 13: If Added_Rental_Upper set is empty and Counter = 0, exclude all 
rental vehicles from the fleet of the upper level. 
Step 14: Solve the new relaxed model optimally. 
Step 15: Find all non-integer XU in the optimal solution of the relaxed model. 
Step 16: Find vehicles used in the optimal solution of the relaxed model. 
Step 17: For every vehicle used, find the first plant as a source of the vehicle. 
 154 
 
Step 18: For every vehicle used, find all bottlers visited by different tours of 
the vehicle in the optimal solution. 
Step 19: Find the shortest tour which starts from the source found in Step 17 
and visits all bottlers found in Step 18. The criterion in the shortest tour is the 
summation of travel time and shipping costs. 
Step 20: Add constraints to the model fixing routing variable (XU) of the 
selected links in Step 19 to one. 
Step 21: Solve the new relaxed model optimally. 
Step 22: If there is any non-integer XU in the optimal solution, go to Step 15. 
Step 23: If Added_Rental_Lower set is empty and Counter = 0, exclude all 
rental vehicles from the fleet of the lower level. 
Step 24: Solve the new relaxed model optimally. 
Step 25: Find all non-integer XW in the optimal solution of the relaxed model. 
Step 26: Find vehicles used in the optimal solution of the relaxed model. 
Step 27: For every vehicle used, find the first bottler as a source of a vehicle. 
Step 28: For every vehicle used, find all retailers visited by different tours of 
the vehicle in the optimal solution. 
Step 29: Find the shortest tour which starts from the source found in Step 27 
and visits all bottlers found in Step 28. The criterion in the shortest tour is the 
summation of travel time and shipping costs. 
Step 30: Add constraints to the model fixing routing variable (XW) of the 
selected links in Step 29 to one. 
Step 31: Solve the new relaxed model optimally. 
 155 
 
Step 32: If there is any non-integer XW in the optimal solution, go to Step 25. 
Step 33: Calculate the shortage in retailers and inventory level at bottlers for 
every commodity type. 
Step 34: Calculate number of vehicles needed in the upper level according to 
equation 6-2. 
Step 35: Calculate number of vehicles needed in the lower level according to 
equation 6-4. 
Step 36: If inventory level>0 and shortage> 0 and inventory level=>shortage 
go to Step 37; otherwise go to Step 38. 
Step 37: If there is unused rental vehicles in the fleet of the lower level, sort 
them decreasingly based on fixed and operational costs. Choose needed number of 
them calculated in Step 35 and add them to the Added_Rental_Lower set.  
Step 38: If shortage> inventory level and inventory level)> 0 go to Step 39; 
otherwise go to Step 41. 
Step 39: If there is unused rental vehicles in the fleet of the lower level, sort 
them decreasingly based on fixed and operational costs. Choose needed number of 
them calculated in Step 35 and add them to the Added_Rental_Lower set.  
Step 40: If there is unused rental vehicles in the fleet of the upper level, sort 
them decreasingly based on fixed and operational costs. Choose needed number of 
them calculated in Step 34 and add them to the Added_Rental_Upper set.  
Step 41: If shortage> inventory level and inventory level= 0 go to Step 42; 
otherwise go to Step 44. 
 156 
 
Step 42: If there is unused rental vehicles in the fleet of the upper level, sort 
them decreasingly based on fixed and operational costs. Choose needed number of 
them calculated in Step 34 and add them to the Added_Rental_Upper set.  
Step 43: If there is unused rental vehicles in the fleet of the lower level, sort 
them decreasingly based on fixed and operational costs. Choose needed number of 
them calculated in Step 35 and add them to the Added_Rental_Lower set.  
Step 44: If Added_Rental_Upper set is not empty go to Step 14. Otherwise, if 
Added_Rental_Upper set is not empty go to Step 24. 
Step 45: For every used rental vehicles in the upper level, add constraints to 
fix its variables of fixed and operational costs to one. 
Step 46: For every used rental vehicles in the lower level, add constraints to 
fix its variables of fixed and operational costs to one. Run the new relaxed model. 
Step 47: If a vehicle has not been used by the model in the upper level, add it 
to Exclude_Upper set. Add a constraint to the model for each vehicle in 
Exclude_Upper set to fix its XU over all links of the upper level to zero. 
Step 48: If a vehicle has not been used by the model in the lower level, add it 
to Exclude_Lower set. Add a constraint to the model for each vehicle in 
Exclude_Lower set to fix its XW over all links of the lower level to zero. 
Step 49: Solve the new relaxed model optimally. 
Step 50: If the algorithm is in the last time step, it terminates; otherwise, set 
t=t+1 and go to the Step 4. 
Figure 6-3 shows the flow chart of the proposed heuristic for the first time 
step.  
 157 
 
Is there any 
0.001<w<1? 
Yes 
Is there any 
0<XU<1? 
No 
A E 
  
Start 
Solve the relaxed model 
Fix all w<0.001 to 0 for all time steps 
Solve the relaxed model 
IIs t 
Find the 
maximum 
w and fix 
it to 1 
Fix all TN>0 to 1 
Fix all XU for rental vehicles to 0 
Solve the relaxed model 
Put all non-integer XU in set ku 
For each vehicle k in a set ku, find its plant 
and all bottlers visited by vehicle k 
Solve the relaxed model 
IIs t 
Yes 
No 
Figure 6-3 The flow chart of heuristic 2 in the first time step 
Find the shortest tour for each vehicle k connecting the plant to bottlers 
 158 
 
Is there any 
0<XW<1? 
Yes 
shortage>0 & Inventory>0 & 
Shortage<=inventory? 
IIs t 
A 
B 
No 
No 
Is there any 
unused rental 
vehicle in the 
lower level? 
Yes 
Yes 
No 
C D 
E 
Calculate number of vehicles 
needed in the upper level Vu and 
the lower level Vw 
 
 
  Fix all XW for rental vehicles to 0 
Solve the relaxed model 
Put all non-integer XW in set kw 
Solve the relaxed model 
IIs t 
Calculate shortage at retailers 
and inventory level at bottlers 
IIs t 
Add Vw rental 
vehicle(s) to the 
lower level based on 
the cost 
Add Vw rental 
vehicle(s) to the 
lower level based on 
the cost 
Figure 6-3 The flow chart of heuristic 2 in the first time step (Cont?d) 
For each vehicle k in a set kw, find its bottler 
and all retailers visited by vehicle k 
Find the shortest tour for each vehicle k 
connecting the plant to bottlers 
 159 
 
B 
Inventory>0 & 
Shortage>inventory? 
Is there any 
unused rental 
vehicle in the 
lower level? 
C 
Yes 
Yes 
inventory=0 & 
shortage(c)>inventory(c)]? 
No 
No 
Is there any 
unused rental 
vehicle in the 
upper level? 
No 
D 
Yes 
No 
Yes 
Is there any 
unused rental 
vehicle in the 
upper level? 
Is there any 
unused rental 
vehicle in the 
lower level? Yes 
Yes 
Yes 
Yes 
No No 
 
 
 
  
IIs t 
IIs t 
IIs t 
IIs t 
Add Vu rental 
vehicle(s) to the 
upper level based on 
the cost 
Fix variables related to costs of rental vehicles 
Fix variables of unused vehicles to 0 
Do the same processes on the next time step 
until the last time step is reached 
Keep the solution as the best solution of the 
algorithm (BS) 
Figure 6-3 The flow chart of heuristic 2 in the first time step (Cont?d) 
IIs t IIs t 
 160 
 
6.2. Numerical Results 
In this section, the results obtained by solving different scenarios with heuristic 2 are 
presented and described in detail. As mentioned, for better comparison of heuristics 1 
and 2, the same categories and scenarios are solved in this section. Therefore, in the 
next sections, heuristic 2?s outputs are discussed but details of categories are not 
explained. 
6.2.1. Category 1 
The first category?s scenarios were solved by heuristic 2; the results are presented in 
Table 6-1. Also, Table 6-2 summarizes the information presented in Table 6-1. 
Table 6-1. Comparison of results of Xpress and Heuristic 2 on Category 1 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Gap of the Heuristic 2 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 2 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 49330 48678 1.32 1.32 771 59 
2 49105 47564 3.13 3.24 9473 19 
3 49330 47382 3.94 3.94 152 33 
4 49356 48704 1.32 1.32 204 58 
5 45088 44971 0.25 0.25 23 69 
6 47877 46312 3.27 3.27 318 63 
7 45726 44759 2.11 2.14 79040 60 
8 45088 44064 2.27 2.27 98 58 
9 44841 44494 0.77 0.77 30 72 
10 46299 45447 1.84 1.99 1530 53 
 
 
 
 
 
 
 
 
 161 
 
Table 6-2. Criteria for comparison of Xpress and Heuristic 2 based on Category 1 scenarios 
Criterion Value 
Average of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress (%) 
2.05 
Variance of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress 
1.39 
Average of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress (%) 
2.02 
Variance of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress 
1.36 
Average of Xpress Running Time (CPU seconds) 9164 
Average of the Heuristic 2 Running Time (CPU seconds) 54 
 
According to Tables 6-1 and 6-2, the average gap between the heuristic 2 
solution?s objective function and the Xpress solution?s objective function is around 
2%, which is higher than the gap for heuristic 1. This result is consistent with 
expectations because in the routing part of heuristic 2, all decisions are made 
simultaneously; however, in heuristic 1 the algorithm makes decisions gradually, 
based on the model?s reaction to every decision that has been made. As Table 6-2 
shows, the average running time for heuristic 2 is much less than that of Xpress; 
however, it is more than that of heuristic 1, which contradicts the expectation. There 
are two possibilities for this unexpected outcome: First, since the problems were 
small after a few links had been fixed in heuristic 1, the rest of the selected links in 
the solution of the model became integers and the heuristics found paths quickly. 
Second, the RAM of the machine running heuristic 2 was full, which affected the 
heuristic?s speed and solution time. Despite this contradiction, heuristic 2 found 
appropriate solutions with acceptable gaps in reasonable running time. 
 
 162 
 
6.2.2. Category 2 
The results of solving scenarios in the second category are reported in Tables 6-3 and 
6-4.  
Table 6-3. Comparison of the results of Xpress and Heuristic 2 on Category 2 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Gap of the Heuristic 2 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 2 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 80170 79042 1.40 1.40 42615 423 
2 79901 77759 2.68 2.71 21570 269 
3 80122 79120 1.25 1.65 4482 300 
4 80129 78791 1.67 1.95 9283 501 
5 80239 79483 0.99 1.22 19755 339 
6 81656 80522 1.39 1.54 9897 414 
7 82998 82062 1.13 1.23 25387 398 
8 82681 81371 1.58 1.58 36195 367 
9 81235 78971 2.79 3.49 17306 349 
10 80455 78557 2.36 3.07 61521 419 
 
 
Table 6-4. Criteria for comparison of Xpress and Heuristic 2 based on Category 2 scenarios 
Criterion Value 
Average Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress (%) 
1.98 
Variance Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress 
0.66 
Average Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress (%) 
1.72 
Variance Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress 
0.42 
Average Xpress Running Time (CPU seconds) 24801 
Average the Heuristic 2 Running Time (CPU seconds) 378 
 
The gaps between heuristic 2 solutions and Xpress solutions were greater than 
the gaps of heuristic 1 and Xpress. The running time, however, improved in this 
category, as expected. This confirms that heuristic 2 sacrifices accuracy to find a 
 163 
 
solution in a shorter time. The outcome of heuristic 2 is still acceptable and has a 
reasonable gap with Xpress results.  
 
6.2.3. Category 3 
Tables 6-5 and 6-6 show the results of applying the second heuristic to the scenarios 
of Category 3. 
 
Table 6-5. Comparison of the results of Xpress and Heuristic 2 on Category 3 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Gap of the Heuristic 2 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 2 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 118019 116709 1.11 1.61 38656 4200 
2 89067 87475 1.79 2.84 12029 4380 
3 115753 103173 10.87 11.30 53738 3762 
4 118047 115176 2.43 2.88 29160 3974 
5 122439 120602 1.50 1.76 18072 2077 
6 113127 111795 1.18 1.55 50871 2328 
7 109817 109369 0.41 1.01 25023 2950 
8 111336 109523 1.63 2.01 29228 2544 
9 121530 120336 0.98 1.47 13021 3315 
10 109682 108498 1.07 1.07 12217 2946 
 
 
Table 6-6. Criteria for comparison of Xpress and Heuristic 2 based on Category 3 scenarios 
Criterion Value 
Average of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress (%) 
2.75 
Variance of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress 
9.43 
Average of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress (%) 
2.30 
Variance of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress 
9.37 
Average of Xpress Running Time (CPU seconds) 28492 
Average of the Heuristic 2 Running Time (CPU seconds) 3248 
 164 
 
According to Table 6-6, the gap between heuristic 2 and Xpress solutions as 
well as the bound has improved in comparison to heuristic 1. Moreover, the average 
running time for heuristic 2 is less than half of heuristic 1?s mean running time. This 
is the first category in which heuristic 2 performs better than heuristic 1. The 
difference between running time for heuristic 2 and Xpress is noticeable in this 
category. 
 
6.2.4. Category 4 
Outputs for heuristic 2 and Xpress on this larger category are presented in Tables 6-7 
and 6-8. This category includes 5 scenarios. 
Table 6-7. Comparison of the results of Xpress and Heuristic 2 on Category 4 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Gap of the Heuristic 2 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 2 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 147348 145018 1.58 2.31 8333 14274 
2 142034 140355 1.18 1.18 3501 9889 
3 142503 141544 0.67 0.73 38038 6254 
4 164400 163853 0.33 0.72 11870 7279 
5 164721 164838 -0.07 0.25 10151 6085 
 
Table 6-8. Criteria for comparison of Xpress and Heuristic 2 based on Category 4 scenarios 
Criterion Value 
Average of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress (%) 
1.04 
Variance of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress 
0.61 
Average of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress (%) 
0.74 
Variance of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress 
0.43 
Average of Xpress Running Time (CPU seconds) 14378 
Average of the Heuristic 2 Running Time (CPU seconds) 8756 
 165 
 
As mentioned in Section 5.6.4, the solver was stopped after finding a solution 
with a gap of less than 0.8% between the best solution and the best bound. As a result, 
the reported running time in Table 6-7 is not comparable to running times for other 
categories. Despite this fact, heuristic 2 has a lower running time compared to Xpress, 
and its average gap is around 1% with the best bound. Similar to results for Category 
3, heuristic 2 found better solutions than heuristic 1 for scenarios in this category; 
however, their objective functions were very close to each other. 
 
6.2.5. Category 5 
Tables 6-9 and 6-10 present the outputs of heuristic 2 and Xpress for five 
scenarios in Category 5. In this category, the first and second improvement phases 
were eliminated from heuristic 2; thus, it contains only the third improvement phase. 
This policy will be applied to larger categories as well.  
Comparison of the results provided by heuristics 1 and 2 shows that heuristic 
2 had a smaller average gap than heuristic 1; however, in four scenarios heuristic 1 
found better solutions. In other words, the output of heuristic 1 for the first scenario 
was far from that of the Xpress solution (the gap was more than 9%), which ruined 
the average gap. Similar to its performance in previous categories, heuristic 2 was 
much faster than heuristic 1. 
 
 
 
 
 166 
 
Table 6-9. Comparison of the results of Xpress and Heuristic 2 on Category 5 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Gap of the Heuristic 2 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 2 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 126274 122726 2.81 3.61 34287 11224 
2 147278 145009 1.54 2.40 61888 11991 
3 157349 154862 1.58 2.07 32610 9706 
4 144202 142616 1.10 1.64 24915 9400 
5 145404 142043 2.31 2.77 41285 10577 
 
 
Table 6-10. Criteria for comparison of Xpress and Heuristic 2 based on Category 5 scenarios 
Criterion Value 
Average of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress (%) 
2.49 
Variance of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress 
0.56 
Average of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress (%) 
1.87 
Variance of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress 
0.46 
Average of Xpress Running Time (CPU seconds) 38997 
Average of the Heuristic 2 Running Time (CPU seconds) 10580 
 
 
6.2.6. Category 6 
Tables 6-11 and 6-12 present the outputs for heuristic 2 and Xpress for five 
scenarios of Category 5. In this category, heuristic 1 has better performance in terms 
of a gap with Xpress solutions; however, the average gap of heuristic 2 is less than 
4%, which means that heuristic 2 has found good solutions. On the other hand, the 
average running time of heuristic 2 is almost half of heuristic 1. In other words, 
heuristic 2 delivers good solutions in a short time especially when it is compared to 
Xpress which needs to run more than 10 hours without finding an optimal solution. 
 167 
 
Table 6-11. Comparison of the results of Xpress and Heuristic 2 on Category 6 scenarios 
Scenario 
Xpress 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Gap of the Heuristic 2 
Objective Function with 
Xpress 
Running 
Time 
(CPU 
seconds) 
Heuristic 2 
Running 
Time 
(CPU 
seconds) 
The Best 
Solution 
(%) 
The Best 
Bound (%) 
1 176600 170574 3.41 4.60 43823 5967 
2 182435 174194 4.52 5.56 30124 4832 
3 184701 178886 3.15 4.53 36585 4926 
4 181661 180722 0.52 0.97 65168 3791 
5 178979 172230 3.77 4.27 52403 4048 
 
 
Table 6-12. Criteria for comparison of Xpress and Heuristic 2 based on Category 6 scenarios 
Criterion Value 
Average of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress (%) 
3.99 
Variance of Gap between Heuristic 2 Solution and the Best Bound 
Found by Xpress 
3.08 
Average of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress (%) 
3.07 
Variance of Gap between Heuristic 2 Solution and the Best Solution 
Found by Xpress 
2.30 
Average of Xpress Running Time (CPU seconds 45620 
Average of the Heuristic 2 Running Time (CPU seconds 4712 
 
 
6.2.7. Category 7 
Category 7 is a category for which Xpress is not able to find a feasible 
solution. Heuristic 1 delivered a feasible solution with appropriate gap with the best 
bound but in long running times. Tables 6-13 and 6-14 show the performance of both 
heuristics on 5 scenarios of this category. According to Tables 6-13 and 6-14, 
heuristic 1 provided better solutions than heuristic 2 with a smaller gap with the 
objective function value of relaxed problems. Since Xpress could not find even a 
feasible solution for the scenarios in this category, the objective function value of a 
 168 
 
relaxed problem was considered as an upper bound. Based on the outputs of other 
categories and scenarios, there was a better upper bound than a relaxed objective 
function. As a result, the real value of a gap reported in Table 6-13 is smaller.  
 
Table 6-13. Comparison of the results of Heuristic 1 and Heuristic 2 on Category 7 scenarios 
Scenario 
Heuristic 
1 
Objective 
Function 
($) 
Heuristic 
2 
Objective 
Function 
($) 
Gap of 
Heuristic 
1 with 
Relaxed 
Problem 
Gap of 
Heuristic 
2 with 
Relaxed 
Problem 
Heuristic 1 
Running 
Time (CPU 
seconds) 
Heuristic 2 
Running 
Time (CPU 
seconds) 
1 268836 266011 3.61 4.62 4 days 41305 
2 272568 268903 3.79 5.08 4 days 36960 
3 276753 273169 3.31 4.56 4 days 41365 
4 390395 387270 3.87 4.64 4.5 days 69467 
5 398105 394026 3.63 4.61 4.5 days 67265 
 
 
Table 6-14. Criteria for comparison of Heuristics 1 and 2 based on Category 7 scenarios 
Criterion Value 
Average of Gap between Heuristic 1 Solution and the Relaxed 
Problem Objective Function (%) 
3.64 
Variance of Gap between Heuristic 1 Solution and the Relaxed 
Problem Objective Function 
0.04 
Average of Gap between Heuristic 2 Solution and the Relaxed 
Problem Objective Function (%) 
4.70 
Variance of Gap between Heuristic 2 Solution and the Relaxed 
Problem Objective Function 
0.04 
Average of the Heuristic 1 Running Time (CPU seconds) 4 days 
Average of the Heuristic 2 Running Time (CPU seconds) 51272 
 
On the other hand, heuristic 2?s running time was significantly shorter than 
that of heuristic 1. This is the main advantage of heuristic 2, which provides good 
solutions in a reasonable amount of computation time. In other words, heuristic 2 
sacrifices accuracy to find an appropriate solution in an acceptable running time. 
 
 169 
 
6.3. Summary 
In this chapter, another heuristic algorithm based on the first heuristic algorithm was 
proposed to solve the problem. Heuristic 2, which uses a fix-and-run algorithm as a 
background, is the same as heuristic 1 except for changes in some of the steps. The 
motivation for developing heuristic 2 was heuristic 1?s long running time for large 
problems. Heuristic 2 solves problems significantly faster, which is its main 
advantage.  
The same scenarios as those in Chapter 5 were solved by heuristic 2 to 
evaluate its performance. Figures 6-4 and 6-5 compare the performances of heuristics 
1 and 2 in different categories from the standpoints of gap and running time, 
respectively. According to Figure 6-4, in four categories heuristic 1 provided better 
solutions than heuristic 2. As explained in Section 6.2.5, in four scenarios of Category 
5 heuristic 1 delivered better solutions than heuristic 2; however, the gap for the 
solution of another scenario was very high, which caused the average gap of heuristic 
1 to be higher than heuristic 2.  
Moreover, the variance of gap between the solution of heuristic 2 and the best 
solution or best bound found by Xpress is acceptable in most of categories except 
Category 3. As a result, similar to heuristic 1, heuristic 2 performs consistently over 
different scenarios with the same main characteristics. 
 170 
 
 
Figure 6-4 Average gaps of heuristics 1 and 2 solutions with Xpress outputs in different categories 
 
 
Figure 6-5 shows the most important characteristics of heuristic 2. This 
heuristic is much faster than heuristic 1, which provides good solutions in acceptable 
running time. Since the average running times for heuristics 1 and 2 for Category 7 
scenarios are significantly higher than other numbers in Figure 6-5, they have not 
been shown to scale. According to Figure 6-5, heuristic 2 was able to find appropriate 
solutions for the problems in Category 7. Xpress was not able to find feasible 
solutions for those problems, and heuristic 1 required around 4 days to deliver 
solutions. Also, the running times for Category 1 are not shown due to their small 
values. 
 171 
 
 
Figure 6-5 Average running time for heuristics 1 and 2 in different categories 
 
As a result, heuristic 1 looks more accurate than heuristic 2, while heuristic 2 
is sufficiently precise. If running time is not a concern, heuristic 1 is the better 
approach, since it is more likely to provide a better solution than heuristic 2. If a 
solution is necessary in a shorter time, heuristic 2 is the appropriate method to use; it 
delivers reliable results in a reasonable running time. In addition, both heuristics beat 
Xpress for very large-sized problems and provide a feasible solution, whereas Xpress 
is not able to do this.    
  
 172 
 
Chapter 7:  Level Decomposition 
 
 
One of the characteristics of the research problem is integrating different activities of 
the supply chain. This problem consists of the transportation of raw material from 
sources (plants) to factories (bottlers), production of final products in factories 
(bottlers), and shipping of final commodities to consumption locations (retailers). The 
problem, therefore, includes two levels and integrating these levels increases the 
complexity of the problem significantly. Another approach to approximately solve 
this problem is to decompose the two levels and solve them separately. In other 
words, the model for the upper level is solved first. Some output of the first model 
becomes input for the second model, which solves the lower part of the original 
model. Besides the fact that this solution provides another heuristic approach, it 
demonstrates by how much the integration of levels will increase a company?s profit. 
Section 7.1 provides more detail as to the mathematical formulation of the level-
 decomposition approach, and Section 7.2 presents the results of solving different 
problems with this method. Section 7.3 concludes with a discussion of the benefits 
and disadvantages of the level-decomposition approach.  
  
7.1. Mathematical Formulation for Level Decomposition 
In this section, the mathematical formulation for this approach is presented. Since this 
approach uses most of the constraints described in Section 3.4.5, only constraints that 
 173 
 
have been changed are explained and the rest of constraints are shown with their 
equation in Section 3.4.5. Similarly, sets and parameters are the same as in Chapter 3, 
and the new parameters and decision variables are introduced. 
 
7.1.1. The Upper-Level Model 
In the upper-level problem, syrup concentrate must be delivered to bottlers to produce 
final products. Bottlers? demand is based on retailers? orders. Bottlers are not 
consumption locations; they play an intermediate role in the supply chain between 
plants and retailers. In the original model, this relationship between plants and 
retailers through bottlers was defined by connecting different levels. This information 
transmission from lower-level components to the upper-level model must be 
considered.  
As a result, retailers? orders must be transferred to bottlers to be used in the 
upper-level model. Since there are multiple locations for bottlers, the assignment of 
retailers to bottlers affects the final objective function. The best measure for this 
assignment is the travel time between retailers and bottlers. In other words, a 
retailer?s order is assigned to the demand of the closest bottler. Figure 7-1 shows the 
process of assignment of retailers to bottlers. 
 174 
 
 
Figure 7-1. Assignment of retailers? orders to the demands of bottlers 
 
In the upper-level model, the role of bottlers is the same as retailers in the 
original model. In other words, demand for different products, product price, and 
shortage penalties are defined for bottlers in the upper-level model. Bottlers? demand 
for and price of a commodity type are calculated as shown in Figure 7-1. Retailers 
assigned to a bottler are used as a base for demand, product price, and shortage-
 penalty calculation. The average price of a commodity type for retailers assigned to a 
bottler is considered to be the price of that particular product for the same bottler. 
Similarly, the same calculation is applied for a shortage penalty, whereas the original 
value of a bottler?s warehouse capacity remains in the model. As a result, the 
mathematical formulation of the upper-level model can be written as flows: 
 175 
 
 
 
 
WPj
 ijkt TtGVUkWPiXU
 ?
 ? ,,1
              (7-3) 
WPi WPm
 jmktijkt TtGVUkWjXUXU
 ? ?
 ,,0
                     (7-4) 
GVUkPiXUXU
 Wj Tt
 jikt
 Wj Tt
 ijkt ,0
                                   (7-5) 
TtGVUkXU
 Pi PWj
 ijkt ,1
 ?
                                  (7-6) 
WiXU
 GVUk Tt
 iikt 0
                                                    (7-7) 
TtGVUk
 TTSFuCXUTLUUXUTLU
 PWi PWj
 ukijiikt
 PWi PWj
 iikt
 ,
 )1(
 ? ?? ?
                    (7-8) 
0
 PWi Tt
 iJKtXU
 ?
                                     (7-9) 
TtkiLnulGVUkPWiCkuQua k
 Ss Pm Wn
 mn
 lskts ),,(,,
 1
 ?
      (7-10) 
TtSsGVUkWi
 QuQuQu
 kiLeul Pm
 mi
 lskt
 kiLeul Pm Wn
 mn
 lskt
 kiLnul Pm Wn
 mn
 lskt
 ,,,
 ),(),(),(
        
(7-11) 
TtPmiQu
 mi
 kiLnul Wn GVUk Ss
 mn
 lskt ,,0
 ),(
                                   (7-12) 
)17(
 Wi Ss Tt
 isist
 VUk Tt
 ktkt
 VUk Tt
 ktkt
 Wi Ss Tt
 sitist
 Pi Wj LNl Ss GVUk Tt
 ij
 ij
 lskt
 ijkt
 PWi PWj GVUk Tt
 ijk
 Wi Ss Tt
 istsit
 PdCostPdVZuEPCVu
 UuFCVuShelenQu
 XUCSFuDEPcMax
 ? ?
 ..ts
 )27(,,0)1( TtSsWiDEPdII ististtsisit
 176 
 
TtSsGVUkPminWniQuQu
 kiLeul
 mn
 lskt
 kiLnul
 mn
 lskt ,,,),(,
 ),(),(
  
                             (7-13) 
TtSsWi
 Pd
 ScQu
 Ss s
 ist
 ist
 kiLeul Pm GVUk
 mi
 lskt ,,0 1
 ),( 2 2               
(7-14) 
TtSsWiCAPPd sitist ,,
                 
(7-15) 
TtSsWiSHCSc sitist ,, 1
               
(7-16) 
TtSsWiHCI sitsit ,,
                (7-17) 
TtSsWiDMDE istist ,,
                (7-18)  
TtSsWiDMDEe ististist ,,
                  (7-19) 
TtSsWiDMde ististtis ,,)1(
                 (7-20) 
SsWiI si ,00
                             (7-21) 
SsWieis ,00
                             (7-22) 
TtGVUkPWjiXUMQu ijkt
 jlNE
 kiLnul Pm Wn Ss
 mn
 lskt ,,,
 )(
 ),(
 ?
             
(7-23)
  
TtVUkVZuMXU kt
 PWi PWj
 jikt ,
 ? ?
               (7-24) 
TtVUkUuVZuVZuIf tkkttk ,11 )1()1(                          
(7-25) 
VUkUuMVZu kk 11                                     
(7-26)  
0
 ,,,,,
 istist
 istististsit
 mn
 lskt
 PdandSc
 DMDEeIQu                      Real-valued decision variable             (7-27) 
1,0,,, ktktijkt UuVZuXU
                          Binary integer variables                      (7-28) 
 
 177 
 
Equation 7-1 is the objective function of the upper level, calculating the profit 
of the company. As mentioned, in this model bottlers act like retailers did in the 
original model. Therefore, they have determined their order for each commodity type, 
and sell products based on the price that is equal to the average of the prices for the 
same retailers assigned to the bottler. As a result, the first term in Equation 7-1 shows 
the revenue received from selling the final products to bottlers. The second and third 
terms are the travel time costs and the shipping costs in the upper level, which are 
calculated the same as in the original model. The fourth term in Equation 7-1 is the 
shortage penalty cost at bottlers. The sixth and seventh terms indicate the fixed and 
operational costs of rental vehicles, and the last term is production cost. Since TPLPs 
are not used in the upper level, its objective function does not include the TPL cost. 
Constraints of the upper-level model come from the original model, except 
constraint 3-17 which has been replaced by Equation 7-2. Variables of Qu and TW in 
Equation 3-17, which are lower-level decision variables, are replaced by DE, which 
has the same implicit meaning and function. The output of the upper-level model 
includes the syrup concentrate delivery plan in the upper level and delivery amounts 
to a group of retailers from each bottler (decision variable DE), which is an input to 
the lower-level model described in next section. 
 
7.1.2. The Lower Level Model 
The mathematical formulation of the lower-level model is shown below. 
 
 
 
 178 
 
)297(
 Wi Rj TPq Ss Tt
 s
 ij
 sqt
 TPq Li Ss Tt
 qistsqi
 VWk Tt
 ktkt
 VWk Tt
 ktkt
 Ri Ss Tt
 sitsit
 Ri Ss Tt
 sitist
 Wi Rj LNl Ss GVWk Tt
 ij
 ij
 lskt
 RWi RWj GVWk Tt
 ijktijk
 Ri Ss Tt
 istsit
 WRZ
 wCTVZwEPCVwUwFCVw
 hIShelenQw
 XWCSFwDEPcMax
 ? ? ?
  
s.t. 
TtSsWi
 TWQwDESol
 Rj TPq Tm
 ij
 stmq
 kiLnwl GVWk Rm
 im
 lsktist
 ,,
 _
 ),(
                            
(7-30) 
Rj
 ijkt TtGVWkWiXW ,,1
                    (7-31) 
WRj TPq
 iqtijkt TtGVWkRiTNXW
 ?
 ,,1
                    (7-32) 
WRi WRm
 jmktijkt TtGVWkRjXWXW
 ? ?
 ,,0
                    (7-33) 
GVWkWiXWXW
 Rj Tt
 jikt
 Rj Tt
 ijkt ,0
                                (7-34) 
TtGVWkXW
 Wi RWj
 ijkt ,1
 ?
                                 (7-35) 
RiXW
 GVWk Tt
 iikt 0
                                                     (7-12) 
TtGVWk
 TTSFwCXWTLUWXWTLW
 RWi RWj
 wkijiikt
 RWi RWj
 iikt
 ,
 )1(
 ? ?? ?
                
(7-36) 
0
 RWi Tt
 iJKtXW
 ?
                                   (7-37) 
TtSsRi
 DETWQwII ist
 Wj TPq Tm
 ji
 smtq
 kiLewl GVWk Wm
 mi
 lskttsisit
 ,,
 ),(
 )1(                              (7-38) 
 179 
 
TtkiLnwlGVWkRWiCkwQua k
 Ss Wm Rn
 mn
 lskts ),,(,,?
     (7-39) 
TtSsGVWkRi
 QwQwQw
 kiLewl Wm
 mi
 lskt
 kiLewl Wm Rn
 mn
 lskt
 kiLnwl Wm Rn
 mn
 lskt
 ,,,
 ),(),(),(
                         
(7-40) 
TtWmiQw
 mi
 kiLnwl Rn GVWk Ss
 mn
 lskt ,,0
 ),(
                                      (7-41) 
TtSsGVWkWminRniQwQw
 kiLewl
 mn
 lskt
 kiLnwl
 mn
 lskt ,,,),(,
 ),(),(
  
                             (7-42) 
TtPWiQw
 kiLnul Wm Rn GVWk Ss
 mn
 lskt ,0
 ),(
 ?
                                   (7-43) 
TtSsRWiHCI sitsit ,,?
                         (7-44) 
TtSsRiDMDE istist ,,
                               (7-45)  
TtSsRiDMDEe ististist ,,
                               (7-46) 
TtSsRiDMde ististtis ,,)1(
                               (7-47) 
SsRWiI si ,00 ?
                                   (7-48) 
SsRieis ,00
                                           (7-49) 
TtGVWkRWjiXWMQw ijkt
 jlNE
 kiLnwl Wm Rn Ss
 mn
 lskt ,,,
 )(
 ),(
 ?
              
(7-50) 
TtVWkVZwMXW kt
 RWi RWj
 jikt ,
 ? ?
                            (7-51) 
TtVWkUwVZwVZwIf tkkttk ,11 )1()1(                                   
(7-52) 
VUkUwMVZw kk 11                                                
(7-53) 
TtTPqRjTNMTW jqt
 Wi Ss Tm
 ij
 smtq ,,                               
(7-54) 
 180 
 
TtTPqRiTNTWNB iqt
 Wj Ss Tm
 ji
 smtqiq ,,                          
(7-55)
   
 
TtSsLiTPqwMTLBTW qistsqi
 Wm Rn Tp
 mn
 stpq ,,,              
(7-56)
  
tmTmtTW
 TPq Wi Rj Ss
 ij
 stmq ,0
                                        
(7-57) 
TmSsTPqRjWiTWmnZ
 Tn
 ij
 smnq
 ij
 sqm ,,,,)(
               
(7-58) 
0,,,,,, ijsqm
 ij
 stmqistististsit
 mn
 lskt ZTWDMDEeIQw
        Real-valued decision variable   (7-59) 
1,0,,, qistitktktijkt wandTNUwVZwXW
             Binary integer variables            (7-60)  
 
Equation 7-29 presents the objective function of the lower-level model, which 
includes components of Equation 3-1 related to the lower level. Since TPLP is an 
option for shipping and warehousing in the lower model, it exists in the objective 
function of this level. Most of the constraints are the same as the constraints in the 
original model. Equation 7-30, which is a replacement for constraint 3-17 in the 
original model, makes a relation between the upper- and lower-level models. Sol_DE 
in the lower model is a constant and is equal to decision variable DE of the upper-
 level model. In other words, DE is found by the upper-level model and, according to 
its value, the lower model decides how to distribute the quantity of DE (known as 
Sol_DE) between retailers.  
The output of the lower level model is a delivery plan between bottlers and 
retailers. The plan for the upper level is provided by the upper-level model. As a 
result, combining the results of the two models yields a plan for shipping and 
warehousing for the entire network; however, the company?s profit is not equal to 
 181 
 
summation of the objective functions of the two models. The company?s total profit 
can be easily calculated based on components of the objective functions of the upper- 
and lower-level models. Use of this approach for different scenarios and comparison 
of its efficiency with the other heuristic methods proposed in this study are discussed 
in next section. 
 
7.2. Numerical Results 
In this section, the results obtained by solving different scenarios with the new 
heuristic approach described in this chapter are presented. As explained in the 
previous section, the level-decomposition approach divides the model into two 
separate problems. The upper-level model is solved first; one of its outputs becomes 
an input to the second model; solving the lower-level problem. 
Some scenarios from the categories explained in Chapter 5 have been selected 
randomly to evaluate the performance of the level-decomposition approach. Table 7-1 
shows the results of solving these scenarios with the level-decomposition approach.  
According to Table 7-1, all upper-level models have been solved optimally, 
while most lower-level models have a gap with the best bound. This gap, for some of 
them, is considerable with regard to their long running time. Table 7-2 compares the 
performance of the level-decomposition method to that of Xpress, heuristic 1, and 
heuristic 2 on the same scenarios shown in Table 7-1. 
 
  
 182 
 
Table 7-1. Solutions using the level-decomposition approach on some scenarios 
Category Scenario 
Level 
Decomposition 
Objective 
Function ($) 
Upper 
Model 
Running 
 Time (s) 
Lower 
Model 
Running 
 Time (s) 
Upper 
Model 
Gap 
(%) 
Lower 
Model 
Gap 
(%) 
1 1 48709.6 0 3213 0 0 
1 8 44433.9 0.3 850.7 0 0 
2 5 79189 13.2 362.3 0 0 
2 7 81664.6 9.9 101.8 0 0 
2 9 80934.9 2.6 23525 0 0.03 
3 3 114584.5 0.5 34773.1 0 0.63 
3 7 109326.8 0.7 9524.1 0 0 
3 9 121175 1.7 53805.4 0 0.22 
3 10 108945.6 24.6 42048 0 0.16 
4 4 163396 201.1 68496.2 0 0.19 
4 5 162755 764.2 12834.5 0 0.41 
5 1 111062 0.1 13272.2 0 0.86 
6 1 166814 74 46164.5 0 0.61 
7 1 256056 114 48174.3 0 0.95 
 
Table 7-2. Comparison of the performances of different heuristic methods 
Category 
- 
Scenario 
Level 
Decomposition 
Objective 
Function ($) 
Xpress 
Objective 
Function 
($) 
Heuristic 1 
Objective 
Function 
($) 
Heuristic 2 
Objective 
Function 
($) 
Xpress 
Improvement in 
compare to 
Decomposition 
Approach (%) 
1-1 48709.6 49330 48875 48678 1.26 
1-8 44433.9 45088 44486 44064 1.45 
2-5 79189 80239 79763 79438 1.31 
2-7 81664.6 82998 82470 82062 1.61 
2-9 80934.9 81235 79062 78971 0.37 
3-3 114584.5 115753 109276 103173 1.01 
3-7 109326.8 109817 108639 109369 0.45 
3-9 121175 121530 119689 120336 0.29 
3-10 108945.6 109682 107916 108498 0.67 
4-4 163396 164400 162589 163853 0.61 
4-5 162755 164721 164954 164838 1.19 
5-1 111062 126274 114358 122726 12.05 
6-1 166814 176600 175932 170574 5.54 
7-1 256056 N.A. 268836 266011 N.A. 
 
 
According to Table 7-2, the objective function of the original model is better 
than the model using level decomposition approach. It shows that integrating levels is 
 183 
 
more beneficial than decomposing levels. Moreover, the level-decomposition method 
performs better for small categories than large categories. In some scenarios, it found 
better solutions than heuristics 1 and 2?but in most cases, heuristics 1 and 2 
performed better, especially in large problems. Moreover, the running time for the 
level-decomposition approach was much higher than for heuristics 1 and 2 and did 
not necessarily generate better solutions. This method solved category 7 scenarios 
that were not solved by Xpress; however, the gap with the relaxed problem objective 
function was more than 8%. Heuristic 2 delivers a solution with less than a 5% gap 
with the relaxed problem objective function and in shorter running time. 
 
7.3. Summary 
In this chapter, another heuristic method was developed to solve the problem. This 
heuristic decomposes the problem into two levels and solves them separately; 
however, an output of the upper-level model is considered as an input to the lower-
 level model. The main point of this method is to decrease the size of a problem by 
decomposition, which, for some large problems, makes it solvable with Xpress. 
However, the original model which integrates both levels finds a better solution with 
higher company?s profit. Two mathematical formulations for the upper- and lower-
 level problems were proposed in this chapter, which are obtained by modification of 
the original model described in Chapter 3. 
The numerical results of solving several problems with this method and 
comparison of its results with other heuristics? solutions indicate that although 
constraints and decision variables are categorized into two groups, making each 
 184 
 
problem smaller than the original one, the gap with the best found solution is higher 
than that of heuristics 1 and 2, especially in large problems. Moreover, the running 
time for this method is higher than the other heuristics proposed in this study. Finally, 
the level-decomposition method uses the branch-and-bound algorithm as a solver for 
its mixed-integer models. Therefore, by increasing the size of categories, there is a 
good chance that it will not provide a feasible solution; however, heuristics 1 and 2 
relax the model and can support larger problems. As a result, heuristics 1 and 2 
perform better than the level-decomposition method especially for large problems. 
 
 
 
  
 185 
 
Chapter 8: Sensitivity Analysis 
 
 
Some parameters of the model have a significant impact on the solution and behavior 
of the model. In fact, if the values of these parameters change, the output of the model 
will change drastically. Choosing the correct values for these parameters, therefore, is 
essential?but, on the other hand, difficult. Moreover, the values of some parameters 
depend on different factors such as the economy, conditions of rivals, and even 
political issues. As a result, analysis of the sensitivity of a solution to these 
parameters provides a better vision of the model?s potential outcome in different 
situations.  
 
8.1. The Base Scenario 
The base scenario is the model that is considered the benchmark for sensitivity 
analysis. Therefore, the results, after changing a parameter of the model, are 
compared to the solution of the base scenario. This scenario cannot be very large due 
to its long running time. On the other hand, considering a small base scenario misses 
the real effects of some parameters. Table 8-1 presents the main characteristics of the 
base scenario. In addition, Table 8-2 illustrates the output of Xpress for this problem. 
  
 186 
 
Table 8-1. Main characteristics of the base scenario 
Criterion Value 
Number of Plants 2 
Number of Bottlers 3 
Number of Retailers 10 
Number of Commodity Types 1 
Number of Available TPL Contracts 2 
Number of Owned Trucks in the Upper Level 3 
Number of Rental Trucks in the Upper Level 3 
Number of Owned Trucks in the Lower Level 3 
Number of Rental Trucks in the Lower Level 3 
Number of Time Steps 3 
Number of Constraints 13,874 
Number of Decision Variables 149,006 
 
Table 8-2. General output information for the best solution of base scenario 
Criterion Value 
Objective Function ($) 41522.4 
Running Time (CPU Seconds) 41588 
Total Unsatisfied Demand (unit) 0 
Commodity Quantity Stored in Retailers? Storage (unit) 6 
Number of Rental Vehicles Used in the Upper Level 1 
Number of Rental Vehicles Used in the Lower Level 1 
Number of TPLP Contracts Selected 1 
Commodity Quantity Delivered by TPLP (unit) 1233 
Commodity Quantity Stored in TPLP?s Warehouse (unit) 0 
Total Production of all Commodity Types in Bottlers (unit) 3191 
 
According to Tables 8-1 and 8-2, the model has used one rental vehicle in 
each level and has satisfied all demands. One TPL contract has been selected for 
shipping only, and no commodity is stored in a TPLP warehouse. The base scenario 
includes more than 13,000 constraints and 149,000 decision variables, confirming 
that the problem is large enough to consider different factors. Sensitivity analysis on 
some parameters is discussed in the following sections. 
 187 
 
8.2. Vehicle Capacity   
Vehicle capacity is the first parameter selected for sensitivity analysis. Increase in 
fleet capacity may cause the model to use fewer vehicles for delivery. In fact, the 
number of tours in both levels may decrease due to increase in vehicle capacity. On 
the other hand, a decrease in fleet capacity may result in using more vehicles to 
operate more generated tours. The key point is that this change does not have a linear 
relation with increased (or decreased) capacity. In other words, it may be that 
although increasing fleet capacity incurs a certain cost, this change may bring benefits 
to the company that outweigh its expenses. It should be noted that the cost of 
increasing capacity (for example, by buying a new fleet) is a capital cost and is paid 
once; however, the benefits accrue to the company daily. As a result, the small 
amount of benefit to be gained from a longer planning horizon may compensate the 
large amount of capital cost. The aim of this section is to see how this model reacts to 
an increase or decrease in vehicle capacity. 
Four scenarios are considered for sensitivity analysis of vehicle capacity. In 
two scenarios it is increased, and in two it is decreased. Each scenario was solved by 
Xpress 7.1 and its output for all scenarios is shown in Table 8-3.  
As Table 8-3 shows, objective function increases as vehicle capacity 
increases. The result is consistent with what was expected because by increasing 
vehicle capacity, each truck delivers more syrup concentrate or final products, which 
results in generating fewer tours. The total cost, therefore, goes down, causing higher 
objective function. The total unsatisfied demand is equal to zero for four scenarios, 
while there is an unsatisfied demand in the case with the lowest vehicle capacity.  
 188 
 
Table 8-3. Criteria from the best solution found by Xpress for different scenarios of vehicle capacity 
Criterion 
Scenarios 
50% 
Decrease 
25% 
Decrease 
Original 
Value 
25% 
Increase 
50% 
Increase 
Objective Function ($) 32035.4 41121.1 41522.4 41771.1 41897.3 
Total Unsatisfied Demand 
(unit) 
884 0 0 0 0 
Commodity Quantity 
Stored in Retailers? 
Storage (unit) 
0 27 6 0 78 
Number of Rental 
Vehicles Used in the 
Upper Level 
3 3 1 1 0 
Number of Rental 
Vehicles Used in the 
Lower Level 
1 0 1 0 0 
Number of TPLP 
Contracts Selected 
2 2 1 1 1 
Commodity Quantity 
Delivered by TPLP (unit) 
1471 1893 1233 1233 1233 
Commodity Quantity 
Stored in TPLP?s 
Warehouse (unit) 
0 493 0 390 449 
Total Production of all 
Commodity Types in 
Bottlers (unit) 
2730 3191 3191 3191 3191 
 
This output should be analyzed with the number of rental vehicles used in 
both levels. When the capacity of vehicles is decreased, the model has used more 
rental vehicles, especially in the upper level. Three rental vehicles in the upper level 
are enough to compensate for vehicle capacity when it is decreased by 25%; however, 
in the lowest-capacity case, adding all three available rental vehicles cannot deliver 
enough syrup concentrate to bottlers to produce enough final products to fill retailers? 
orders. This is the main reason for unsatisfied demand in the first case, and explains 
the differences in TPLP shipping volumes in different scenarios. As expected, by 
decreasing vehicle capacity, TPLP?s share in shipping of products in the lower level 
 189 
 
is increased. In the first scenario, however, fewer final products are produced by 
bottlers. Therefore, there are fewer final products available for shipping, which 
affects TPLP?s share of transportation in the lower level. Figure 8-1 shows the 
objective functions and number of rental vehicles used in both levels in different 
scenarios. The objective function drops significantly after the vehicle capacity is 
decreased by 50%. 
 
Figure 8.1 Sensitivity of objective function and number of rental vehicles used in both levels to vehicle 
capacity change 
 
 
 
8.3. Inventory Cost   
One of the factors affecting the solution is the inventory cost for retailers. The base 
scenario stores 6 units by retailers, showing that the current values for inventory costs 
do not allow the model to store more products by retailers. Increase in the inventory 
 190 
 
cost may cause the model not to store even this small amount in retailers? 
warehouses, while a decrease in the cost may lower total cost and provide a solution 
with a higher objective function. Table 8-4 presents the output by Xpress for different 
scenarios. Three scenarios in addition to the base case have been considered in order 
to analyze sensitivity of the model to inventory cost. 
Table 8-4. Criteria from the best solution found by Xpress for different scenarios for inventory cost 
Criterion 
Scenarios 
50% 
Decrease 
25% 
Decrease 
Original 
Value 
25% 
Increase 
Objective Function ($) 41527.9 41524.2 41522.4 41518.8 
Total Unsatisfied Demand 
(unit) 
0 0 0 0 
Commodity Quantity 
Stored in Retailers? 
Storage (unit) 
60 54 6 6 
Number of Rental 
Vehicles Used in the 
Upper Level 
1 1 1 1 
Number of Rental 
Vehicles Used in the 
Lower Level 
1 1 1 1 
Number of TPLP 
Contracts Selected 
1 1 1 1 
Commodity Quantity 
Delivered by TPLP (unit) 
1233 1233 1233 1233 
Commodity Quantity 
Stored in TPLP?s 
Warehouse (unit) 
0 0 0 0 
Total Production of all 
Commodity Types in 
Bottlers (unit) 
3191 3191 3191 3191 
 
According to Table 8-4, the objective function increases as the inventory cost 
decreases; however, output is the same from the standpoint of number of rental 
vehicle used, quantity of products delivered by TPLP, and unsatisfied demand. In 
cases with less inventory cost, the model stores more products by retailers, which is 
 191 
 
the main reason for the objective-function improvement. The model keeps more 
products in retailers? warehouses at less cost to save the tours cost of future time 
steps. On the other hand, the last scenario, with higher inventory cost than the others, 
has the lowest objective function, while other outputs, such as the quantity of 
products stored in retailers? warehouses or number of rental vehicles used in both 
levels, are the same as the base scenario. 
 
Figure 8.2 Sensitivity of objective function to inventory-cost change 
 
According to Figure 8-2, the impact of an inventory cost decrease (or 
increase) of 50% on the objective value is less than 1%. This result is reasonable due 
to the small proportion of inventory cost in the total cost. Moreover, the different 
trend-line slopes in Figure 8-2 indicate that an increase of 25% in inventory cost 
affects the objective function more than a decrease of 25% in inventory cost. 
 192 
 
8.4. Production Cost   
In this section, sensitivity analysis of the production cost is discussed. Many factors 
influence production cost, such as syrup concentrate price, labor costs, equipment, 
and utility expenses. Tracking all factors is outside the scope of this study; however, 
their effects can be considered together as a change in the final cost of production.  
Five scenarios, in addition to the base scenario, are considered in which each scenario 
has its own production cost. According to the Xpress results for these scenarios, most 
of the output components?such as unsatisfied demand, inventory level at retailers, 
number of rental vehicles used, and even production quantity?are the same in 
different scenarios. Figure 8-3 shows objective function value and its change over 
different scenarios. 
 
Figure 8.3 Sensitivity of objective function to change in production cost  
 
 193 
 
According to Figure 8-3, objective function changes when production cost is 
increased or decreased. This suggests that objective-function change is less than 
production-cost variation. For instance, as the production cost decreases by 50%, the 
objective function improves by 38%. Similarly, the company?s profit declines by 57% 
when production cost increases by 75%. Other factors also affect the company?s 
profits, which cancel out a portion of the increase or decrease in production cost. 
 
8.5. Contract and Warehousing Cost of TPLP   
One of the most important factors that significantly affect the solution and delivery 
plan for the company is TPLP. The company can outsource shipping and 
warehousing to TPLP with curtain costs. If the cost of the TPLP contract or TPLP 
warehousing changes, the company?s profit will be altered due to its dependency on 
TPLP. Variation in the cost of TPLP contracts and holding costs may occur because 
of changes in the TPLP?s policy, fuel prices, and market situation. In this section, the 
costs of TPLP contracts and of storing products in their warehouses are changed to 
see their impact on the objective function and the company?s delivery plan. Table 8-5 
presents Xpress solutions for different scenarios generated by this sensitivity analysis. 
In these cases, a change is applied to the cost of TPLP contracts and warehousing 
cost. In other words, in the case that experiences a 25% increase, the costs of 
contracts and warehousing by each TPLP are also increased by 25%. 
  
 194 
 
Table 8-5. Criteria from the best solution found by Xpress for different scenarios of TPLP cost 
Criterion 
Scenarios 
50% 
Decrease 
25% 
Decrease 
Original 
Value 
25% 
Increase 
50% 
Increase 
Objective Function ($) 41899 41680.8 41522.4 41412.2 41324.5 
Total Unsatisfied Demand 
(unit) 
0 0 0 0 0 
Commodity Quantity 
Stored in Retailers? 
Storage (unit) 
38 38 6 6 216 
Number of Rental 
Vehicles Used in the 
Upper Level 
1 1 1 1 1 
Number of Rental 
Vehicles Used in the 
Lower Level 
0 0 1 1 1 
Number of TPLP 
Contracts Selected 
2 2 1 1 1 
Commodity Quantity 
Delivered by TPLP (unit) 
1893 1893 1233 1091 1091 
Commodity Quantity 
Stored in TPLP?s 
Warehouse (unit) 
226 226 0 307 97 
Total Production of all 
Commodity Types in 
Bottlers (unit) 
3191 3191 3191 3191 3191 
 
As Table 8-5 shows, the number of selected TPLP contracts is increased as 
their price goes down. Moreover, the quantity of products shipped or stored by TPLP 
in scenarios with lower TPLP cost is higher than in cases with higher TPLP cost. In 
addition, TPLP cost affects the number of rental vehicle used in the lower level. As 
expected, by increasing TPLP deliveries, the model needs fewer rental vehicles in the 
lower level, such that in the first and second scenarios, the model found that the 
owned and TPLP fleets are enough for delivery. In cases with more expensive TPLP 
cost, the model found that outsourcing was still beneficial. Although it rented one 
vehicle in the lower level, it preferred delivery by TPLP to adding another rental 
 195 
 
vehicle to the fleet of the lower level. Figure 8-4 presents the sensitivity of the 
objective function to TPLP shipping and warehousing cost variation. 
 
Figure 8.4 Sensitivity of objective function to TPLP shipping and warehousing cost change 
 
According to Figure 8-4, the impact of TPLP cost on the company?s profit is 
less than 1%. Variation in the cost of TPLP does not affect the objective function 
considerably, because TPLP is an option of the company and the company has other 
choices, such as owned and rental vehicles. When the cost of TPLP contracts is 
increased, the model can choose to use rental vehicles for delivery instead of 
outsourcing shipping. Similarly, the cost of using owned vehicles is less than the first 
scenario in this section, which has the minimum TPLP cost. The model, therefore, 
outsources shipping of products that are delivered by rental vehicles in the base 
scenario, while owned vehicles are used at their full capacity. As a result, the impact 
 196 
 
of change in TPLP cost on objective function is less than the variation in TPLP cost 
due to availability of other options to replace TPLP. 
 
8.6. Fuel Price   
Fuel price is one of the most important factors affecting the company?s profit and 
delivery plan. The history of fuel price in North of America over past 10 years shows 
that the price of gas and diesel fluctuates considerably due to several factors. As a 
result, sensitivity analysis of fuel price is essential and provides a useful insight on 
what happens if the price of fuel changes during the planning horizon. In the 
objective function of this study, shipping cost is separated from other costs related to 
transportation such as driver cost or fixed costs for rental vehicles. In this section, 
therefore, these objective-function items have been altered to reflect changes in fuel 
price. 
Five scenarios have been considered for fuel price; it is assumed that fuel 
price does not change by more than 50% of its current value. In addition, a decrease 
in fuel price has been considered?which, however, may not happen. Table 8-6 
shows Xpress outputs for different scenarios in this section. 
 
  
 197 
 
Table 8-6. Criteria from the best solution found by Xpress for different scenarios of fuel price 
Criterion 
Scenarios 
50% 
Decrease 
25% 
Decrease 
Original 
Value 
25% 
Increase 
50% 
Increase 
Objective Function ($) 42779 42126.8 41522.4 40937.5 40377.7 
Total Unsatisfied Demand 
(unit) 
0 0 0 0 0 
Commodity Quantity 
Stored in Retailers? 
Storage (unit) 
6 6 6 11 55 
Number of Rental 
Vehicles Used in the 
Upper Level 
1 1 1 2 1 
Number of Rental 
Vehicles Used in the 
Lower Level 
1 1 1 0 0 
Number of TPLP 
Contracts Selected 
1 1 1 2 2 
Commodity Quantity 
Delivered by TPLP (unit) 
1091 1233 1233 1699 1893 
Commodity Quantity 
Stored in TPLP?s 
Warehouse (unit) 
307 0 0 779 226 
Total Production of all 
Commodity Types in 
Bottlers (unit) 
3191 3191 3191 3191 3191 
 
As Table 8-6 shows, the objective function decreases by increase in the fuel 
price. Moreover, the model stores more products in retailers? warehouses in scenarios 
with higher fuel price to save on tours at future time steps. In addition, the number of 
rental vehicles used in the lower level is decreased as the fuel price is increased. More 
products are delivered by TPLPs to save on fuel because in these scenarios, the TPLP 
costs are the same as in the base scenario. This is the main reason that in scenarios 
with more expensive fuel, more TPLP contracts have been selected. 
  
 198 
 
 
Figure 8.5 Sensitivity of objective function and quantity of products delivered by TPLP to change in 
fuel price 
 
Figure 8-5 shows the effect of fuel price on objective function and TPLP 
delivery quantity. As shown, if the fuel price is decreased by 25%, TPLP ships the 
same amount of products?while a 25% increase in fuel price causes TPLPs to carry 
466 units more, which is around 38% of TPLP delivery in the base scenario. The next 
step increase in the fuel price (from 25% to 50%) affects TPLP delivery quantity less 
than in the previous case. In the fifth scenario, the quantity of delivery by TPLP is 
increased by 11.4% compared to the fourth scenario. The objective function decreases 
linearly as fuel price increases, which is shown in Figure 8-5. 
 
 199 
 
8.7. Product Price   
Another factor that impacts the company?s profit significantly is the products? price 
for retailers. Many factors affect the final price, including production cost and 
transportation cost; however, in this section it is assumed that these costs are fixed 
and that other factors are affecting the price of products; this section is designed to 
demonstrate the effect of product price on the company?s profit and delivery plan. 
Since price has a significant impact on buyers and may cause customers to shift to 
another brand, it cannot vary widely. The change in product price, therefore, is 
limited to 25% more or less than the current value. Similar to previous cases, four 
scenarios in addition to the base scenario were generated and solved by Xpress; 
results are shown in Figure 8-6. 
 
Figure 8.6 Sensitivity of objective function to change in product price 
 
 200 
 
According to Figure 8-6, the percentage of objective-function change is more 
than product-price change. For instance, the price of product increases 25%, while the 
objective function goes up 46%. The reason is that increase in product price improves 
revenue; however, revenue is only one component of the objective function. In fact, 
other costs that are also components of the objective affect the objective function to 
become less than revenue. Therefore, an increase in product price increases revenue, 
and eventually the objective function equally. Since the final value of the objective 
function is compared to its previous value, variation in the objective function is more 
than product-price change.  
 
8.8. The Value of Information 
The model considers information about future time steps to find an optimal solution 
for the entire planning horizon. More accurate time-step data results in better final 
solution. Some of the information needed by the model is estimated based on 
historical data. As a result, variation in the data is possible due to lack of information 
about the future. Orders by retailers are the input of the model, which significantly 
affect the company?s profit and the delivery plan. On the other hand, accuracy in 
retailers? orders is not 100% guaranteed, meaning that they can change during the 
operation. This section analyzes the value of information fed to the model to see how 
much they affect the company?s profit if they vary.  
Imagine that retailers? orders in the third time step increase by 10% during the 
operation. The delivery plan, therefore, does not change, and vehicles deliver 
products to retailers based on outputs of the model for the base scenario. As a result, 
 201 
 
the added demand goes unsatisfied, and a shortage penalty is applied to the objective 
function. A total of 114 units of the product are not satisfied in different retailers. 
According to the shortage penalty at each facility location, the penalty is equal to 
$348.33, which decreases the objective function from $41522.4 to $41174.7, which is 
equal to a 0.83% loss. If retailers? orders increase by 20%, the loss is equal to 1.66%, 
indicating that loss has a linear relation with changes in retailers? orders. This can be 
interpreted the value of information about retailers? orders. It helps managers of a 
beverage company considerably to face any uncertainty of information. In other 
words, preparing for a 10% variation in orders entails a certain cost, which should be 
compared to a 0.83% loss. Different management policies encountered in this case are 
not a concern of this study. The goal of this section is introducing the model?s 
capability to provide valuable information that helps managers make appropriate 
decisions. 
 
8.9. The Effect of a Longer Planning Horizon on the Objective Function  
One of the main characteristics of this model is that it integrates several properties. 
For instance, this model is multi-level, multi-location, and multi-product. One 
question that arises is whether this integrity improves the objective function. 
Considering different factors definitely increases the complexity of the model; 
heuristic methods are required to solve large problems. As a result, if a factor does 
not improve the company?s profit, it can be removed or simplified in the model to 
make the main model simpler. 
 202 
 
In Chapter 7, levels of the model were decomposed and two separate models 
were generated. The analyses performed in Chapter 7 indicated that considering two 
levels together in the model led to a better solution with higher profit. Even for large 
problems, for which Xpress was not able to find a feasible solution, the proposed 
heuristics provided a better solution than the third method, which decomposed the 
model.  
This section analyzes the impact of planning horizon length on the final 
output. A longer planning horizon forces the model to consider more details and 
opportunities to improve the quality of the final solution; however, it may not 
necessarily be successful. Considering a longer planning horizon improves the 
company?s profit when the decisions of earlier time steps can assist in the operation 
of later time steps. To make this clear, an example is designed that has the same 
number of facility locations, number of time steps, and fleet size as the base scenario; 
however, its retailers? orders are different. This scenario is solved using two different 
approaches: In the first approach, the mathematical formulation proposed in Chapter 
3 is applied to the entire planning horizon. The model used in this approach is called 
Model 1. In the second method, the problem is decomposed to two models:  
1. This model includes the first and second time steps of the original 
model and is called Model 2. 
2. This model includes only the third time step of the original model and 
is called Model 3. 
The proposed mathematical formulation in this study is applied to both 
Models 2 and 3 and they are solved by Xpress. The key point in this approach is that 
 203 
 
some outputs of Model 2 must be considered as input to Model 3. For instance, if the 
final solution of Model 2 has unsatisfied demand, it must be added to the demands of 
Model 3. Similarly, the inventory level in facility locations must be transferred from 
Model 2 to Model 3. Table 8-7 presents the output of these two approaches applied to 
the scenario. 
According to Table 8-7, the company?s profit in the second approach, which 
breaks up the planning horizon, is decreased by 35% in comparison to the first 
approach. The reason is that a large portion of demands in the third time steps are not 
satisfied in the second approach. In fact, orders of the third time step are more than 
bottlers? production capacity; however, Model 1 sends more products to retailers in 
time step 2 and stores them for the third time step order, while Model 2?which does 
not consider the third time step?satisfies the demand of the first and second time 
steps. As a result, commodities produced in the third time step can meet a portion of 
retailers? orders, although bottlers use their production capacity fully.  
This example shows the impact of a longer planning horizon on the problem, 
especially when demands change in later time steps significantly. The longer planning 
horizon allows the model to make ready for future demands by storing in retailers? 
warehouses in earlier time steps. It depends on the inventory cost, shortage penalty, 
and shipping cost. The model selects different policies for different scenarios for 
these costs; however, if the planning horizon gets shorter, the model may not be able 
to meet future demands appropriately.  
  
 204 
 
Table 8-7. Comparison of considering the entire planning horizon and breaking it up 
Criterion 
The First 
Approach 
The Second Approach 
Change in 
2nd 
Approach 
(%) Model 1 Model 2 Model 3 Combined 
Objective Function 
($) 
70532.3 26722.7 18737.3 45460 -35.54 
Unsatisfied 
Demand in Time 
Step 1 (unit) 
0 0 N.A. 0 0 
Unsatisfied 
Demand in Time 
Step 2 (unit) 
0 0 N.A. 0 0 
Unsatisfied 
Demand in Time 
Step 3 (unit) 
220 N.A. 1800 1800 +718.18 
Commodity 
Quantity Stored in 
Retailers? Storage 
in Time Step 1 
(unit) 
594 77 N.A. 77 -87.03 
Commodity 
Quantity Stored in 
Retailers? Storage 
in Time Step 2 
(unit) 
1373 0 N.A. 0 -100.00 
Commodity 
Quantity Stored in 
Retailers? Storage 
in Time Step 3 
(unit) 
0 N.A. 0 0 0 
Production 
Quantity in Time 
Step 1 (unit) 
1820 1170 N.A. 1170 -35.71 
Production 
Quantity in Time 
Step 2 (unit) 
1820 890 N.A. 890 -51.09 
Production 
Quantity in Time 
Step 3 (unit) 
1820 N.A. 1820 1820 0 
 
As the number of time steps increases, the complexity of the problem grows 
drastically, because all decision variables have an index of time. On the other hand, 
 205 
 
considering a longer planning horizon improves the quality of the solution. There is a 
tradeoff, therefore, between the accuracy of the solution and the complexity of the 
problem. The nature of the input data affects the final solution significantly. For 
instance, if input data have a strong variation during a planning horizon, the model 
should consider more time steps to react to variation; otherwise, dividing a planning 
horizon into shorter segments provides an acceptable solution in reasonable running 
time. 
Table 8-8 presents the performance of heuristics 1 and 2 on the same problem. 
As shown in Table 8-8, these heuristics have found better solutions than the second 
approach proposed in this section. The heuristics consider the entire planning horizon 
and send more products in earlier time steps. This opportunity is not available for an 
approach that uses a shorter planning horizon. Figure 8-7 illustrates the differences 
between the objective functions of different approaches and the objective function of 
Xpress. The running time for each method is also shown in Figure 8-7. Although 
heuristics did not provide a solution as good as that of Xpress, they found solutions 
that were much better than the approach that divides the planning horizon into several 
pieces. Also, heuristics found solutions in shorter execution time.   
  
 206 
 
 
Table 8-8. Comparison of the method breaking down the planning horizon and heuristics 
Criterion 
The First 
Approach 
The Second 
Approach 
Heuristic 1 Heuristic 2 
Objective Function ($) 70532.3 45460 58684.5 63105.6 
Unsatisfied Demand in 
Time Step 1 (unit) 
0 0 219 61 
Unsatisfied Demand in 
Time Step 2 (unit) 
0 0 0 0 
Unsatisfied Demand in 
Time Step 3 (unit) 
220 1800 850 588 
Commodity Quantity 
Stored in Retailers? 
Storage in Time Step 1 
(unit) 
594 77 205 521 
Commodity Quantity 
Stored in Retailers? 
Storage in Time Step 2 
(unit) 
1373 0 516 703 
Commodity Quantity 
Stored in Retailers? 
Storage in Time Step 3 
(unit) 
0 0 0 0 
Production Quantity in 
Time Step 1 (unit) 
1820 1170 1190 1820 
Production Quantity in 
Time Step 2 (unit) 
1820 890 1820 1820 
Production Quantity in 
Time Step 3 (unit) 
1820 1820 1820 1452 
 
  
 207 
 
 
 
Figure 8.7 Comparison of variation in the objective function and running time in different approaches 
used to solve the problem 
 
8.10. Summary 
In this chapter, sensitivity of the model to various parameters and input data was 
analyzed. Analyses were performed to illustrate the model?s capabilities to react to 
variation in input data. Different components of input data, such as vehicle capacity, 
inventory cost, production cost, TPLP cost, fuel price, and product price for retailers, 
were selected and changed to show their impact on the final solution. Besides their 
effect on the objective function, their influence on other decision variables was 
discussed in detail. For instance, an increase in vehicle capacity causes the model to 
select fewer rental vehicles due to the larger quantity of products delivered by owned 
Different Approaches 
 208 
 
vehicles, and an increase in fuel price forces the model to outsource more shipping to 
TPLPs.  
The useful information gained in each section of this chapter is the response 
of the objective function to a change in each parameter. In other words, a change in 
one element of the input data increases or decreases the objective function. Some 
changes are desirable because they improve the company?s profit; however, their 
effect on the objective function may not be found beneficial in comparison to the cost 
of the change. In other words, a 50% change in one parameter entails a certain cost, 
while it improves the company?s profit by an amount that is less than the capital cost 
needed for the change. Since the model is defined in an operational level, saving in 
costs or improvement in the objective function should be considered over a very long 
period to compare with the capital cost. For instance, a 25% increase in the capacity 
of vehicles due to replacing current vehicles with new ones increases the company?s 
profit by about 0.6% in a 3-day operation. The cost of fleet renovation is expensive; 
however, if a 0.6% savings is realized every 3 days for the lifetime of a vehicle, it 
may be beneficial. As a result, the analyses in this chapter provide valuable 
information that will help the managers of a beverage company in the decision-
 making process. 
Another section of this chapter yielded valuable information by analyzing 
retailers? orders in detail. Uncertainty about future information, such as changes in 
retailers? orders, must be considered in the daily operation of the company. If the 
variation in orders is reported to the beverage company soon enough, the model can 
be executed again with the new data to update the delivery plan; however, sometimes 
 209 
 
these changes are received late, in which case the company may have to pay a penalty 
for unsatisfied demands. This analysis can be defined as a finding of a value of 
information. This value for some parameters is very high, forcing managers to 
respond to changes as much as possible?while for some others, they may prefer to 
keep the original plan. For instance, a variation of 10% in retailers? orders reduces the 
company?s profit by 0.83%. Interpretation of this value depends on many factors that 
are beyond the scope of this study, but this model is capable of delivering this 
information for different parameters. 
The last part of this chapter analyzed the impact of a long planning horizon on 
the final solution. The number of time steps affects running time significantly. If a 
model with a long planning horizon is not solved by Xpress, due to the size of the 
problem and number of constraints and decision variables, it may be solved by 
optimization packages after dividing it into smaller models; each one covers a small 
part of the planning horizon. In fact, the time-step index has the highest influence on 
model size of all indexes. As a result, dividing a planning horizon into several 
segments and running the model on each segment is an approach to resolve the 
impossibility of executing large-sized problems with optimization packages. This 
approach can be practical if storing products in retailers? warehouses is not beneficial. 
In other words, by breaking down the planning horizon, the model loses the 
possibility of sending more products to retailers in advance and keeping them in 
retailers? warehouses for their future demand. As shown in Section 8.10, in some 
cases this policy brings lots of benefits to the company; by dividing the planning 
horizon, the company loses this opportunity. This method can reduce the company?s 
 210 
 
profit by 35%, which is a considerable amount. As a result, running the model on a 
longer planning horizon provides more benefits for the company, and if Xpress and 
other optimization packages are not able to solve the problem, the proposed heuristic 
methods can find a good delivery plan with an acceptable gap with the upper bound. 
Heuristics 1 and 2 can be executed once in a week to determine distribution 
plan for the following week; however, if there is a potential fluctuation in orders of 
retailers, it can be run every day. In this case, the rolling horizon method is applied to 
the heuristic such that every day the model is solved by new and updated information. 
 
 
  
 211 
 
Chapter 9: Summary, Conclusions, and Recommendations for 
Future Research 
 
 
9.1. Summary 
In this research, the inventory control and transportation of syrup concentrate and 
final products for one bottling company working for a beverage company is studied. 
Inventory management and transportation are two key planning issues in supply-chain 
management. Inventory management includes activities such as production, ordering, 
holding, and shortage of products. Transportation includes shipping raw materials and 
final products between sources, factories, warehouses, and retailers. 
Theoretically, there are some benefits in the integration of inventory control 
and transportation, and especially when product demand is high and the costs 
associated with inventory and transportation are significant. Inventory-allocation 
decisions are based on routing-cost information and marginal profit for each customer 
in the set. On the other hand, the delivery cost for each customer depends on the 
location of the facility servicing it and the vehicle?s route to that customer. This 
interrelationship between inventory management and transportation is the main 
reason researchers cite for integrating these two major supply-chain activities. 
In the problem for this study, the bottling company has its own 
nonhomogeneous fleet for transportation of syrup concentrate from plants to bottlers 
and final products from bottlers to retailers. The bottling company knows retailers? 
 212 
 
immediate future demands for a timeframe of several days. If the demand is not 
satisfied, a penalty is applied to the bottling company?s total cost based on quantity of 
unmet demand and shortage cost. Retailers can store final products for future demand 
at a specific holding cost.  
The bottling company may not satisfy all demands due to small fleet size, 
which is not able to cover all deliveries in the right timeframe. In this case, in addition 
to the do-nothing alternative, the bottling company has other options, such as sending 
more products to retailers in advance, adding rental vehicles to the fleet, and 
outsourcing delivery of some retailers to TPLPs. Moreover, TPLPs are able to store 
products if the bottling company finds it beneficial.  
Thus, the company must get raw materials from plants, produce final products 
at bottlers? factories, and ship them to retailers. It must also optimize its profit, taking 
into consideration inventory control in warehouses?both its own and retailers??and, 
when necessary, store products in TPLP warehouses. Finally, it must deliver final 
products to retailers using different vehicles, including owned, rental, and TPLP.  
The mathematical formulation to solve the problem was presented in Chapter 
3 and considers all details and opportunities and must be solved by optimization 
packages. This linear model, which is a mixed-integer program, maximizes the 
company?s profit subject to several constraints. The performance of the model was 
verified in Chapter 4 by solving different scenarios. These scenarios were generated 
to show the model?s capabilities in different situations. Results confirmed the 
accuracy of the model and its performance under different conditions. Outputs of 
Xpress from these scenarios also demonstrate that the model is very complex and that 
 213 
 
even medium size scenarios cannot be solved optimally. Moreover, the model is very 
sensitive to some parameters, such as length of planning horizon, fleet size, and 
number of commodity types. The model?s complexity, therefore, increases 
significantly as these parameters grow. As a result, not only is Xpress incapable of 
solving large problems; it is also unable to deliver a feasible solution. Therefore, 
development of a heuristic method to find a good feasible solution in reasonable 
running time is essential. Chapters 5 and 6 proposed two heuristic methods for this 
problem, which are based on fix-and-run algorithm. Three improvement phases were 
also developed to enhance the final solution of heuristics. Moreover, performance of 
the two proposed heuristics was verified by solving several categories of scenarios. 
According to the results, heuristic 1 generally finds a better solution than heuristic 2; 
however, heuristic 2 is much faster than heuristic 1. Solutions of both heuristics have 
acceptable gaps from either an optimal solution or upper bound.  
In the real world, retailers are clustered into groups and each group is assigned 
to one bottler. Although retailers are grouped based on their distances from bottlers, 
the output is not the optimal necessarily. In the mathematical formulation and 
heuristic methods proposed in this study, the model assigns retailers to bottlers based 
on their contributions to the objective function. In other words, retailers are connected 
to bottlers according to different factors considered in the objective function. The 
final assignment, therefore, is more beneficial than clustering which happens in the 
real world and is based on distance only. 
Chapter 7 proposed another method to solve large problems approximately, 
which is based on decomposition of the model?s levels. This method is much easier 
 214 
 
than the proposed heuristics; however, the accuracy of the heuristics and running time 
are superior to level decomposition approach. Moreover, a branch-and-bound 
algorithm is used in level decomposition method, which causes it to be incapable of 
solving larger problems; heuristics, however, are able to find good feasible solutions 
for them. Finally, in Chapter 8, the model?s sensitivity to some parameters and input 
data is analyzed. The outputs of these analyses will be valuable for managers of the 
bottling company as they make decisions in different situations.  
9.2. Conclusions 
The problem of this study is IRP with some new features, such as options for rental 
vehicle and TPLPs. Moreover, the model proposed in this study includes several time 
steps in which a decision in one time step can affect future time steps. The model is 
also multi-tier, multi-plant, multi-warehouse, and multiproduct, with a 
nonhomogeneous fleet, which increases its complexity significantly.  
Numerical results indicated that the model is very sensitive to some 
parameters such as fleet size, number of commodity types, and length of planning 
horizon. In fact, increase in any of these parameters grows the complexity and 
running time exponentially. Moreover, tracking of vehicles and commodity flow in 
the network brings more complexity to the model. For this purpose, many constraints 
must be added to the formulation as well as defining a lot of indices in decision 
variables. However, they are inevitable if capacity of vehicles is considered in the 
model. In addition, having more than one facility location in each tier makes the 
model complicated especially when heuristic algorithms are developed. In fact, the 
 215 
 
flexibility of the model is expanded drastically, which makes control of these 
flexibilities very difficult in developing a heuristic. 
Different approaches to develop a heuristic can be considered. In some 
methods, the entire formulation is used by a heuristic and assumptions such as 
relaxation of binary variables help the heuristic run faster. On the other hand, some 
methods decompose the model and solve smaller problems sequentially. Two of these 
decomposition techniques were studied in this research: decomposition of levels and 
planning horizon. Both approaches found solution worse than heuristics proposed in 
this research. In other words, integrating different aspects and considering the entire 
model in developing the heuristic provides better solution than other heuristics which 
separate the problem into several smaller models.  
Analyzing the sensitivity of the model to its parameters showed that the model 
is very sensitive to production cost, product price, and vehicle capacity. For instance, 
50% increase in production cost decreases the profit of the company by 30%. Also, it 
showed that change in fuel price impacts less on the profit of the company and more 
on the quantity of commodity shipped by TPLP.  
Finally, the value of information was studied in this research. Since most of 
needed information for this problem is predicted for the near future, there is a high 
chance of error in prediction. For instance, demand of retailers can be different from 
the original estimation. This research calculated the loss due to incorrect predictions. 
Reaction to this loss depends on management policies and is out of scope of this 
study; however, calculation of potential loss or gain is valuable information 
considered in this study. 
 216 
 
 
9.3. Recommendations for Future Research 
There are some recommendations for future studies which are described in this 
section. 
 
1- Considering Stochastic Parameters 
Some parameters used in this study have a stochastic nature, such as retailer 
demand and travel time of the links. In other words, finding exact values for such 
parameters is difficult. As shown in the sensitivity analyses, variation in retailers? 
orders affects the objective function, which was explained as a value of information. 
A more accurate approach is to consider this variation in the mathematical 
formulation. In this study, it was assumed that all information that the model needs is 
known; however, in some parameters and input data, uncertainty is inherent. Adding 
the concept of stochasticity to the model improves the quality of the solution and 
provides a more robust solution for the problem. This suggestion will increase the 
complexity of the model significantly.  
 
2- Development of Other Heuristic Methods 
The heuristic methods proposed in this study use Xpress as a background 
solver: They make decisions and add new constraints to the model, which is solved 
by Xpress optimally. The strength of these heuristics, therefore, is limited to Xpress 
capabilities. For instance, Xpress limits the number of constraints and decision 
variables, even for relaxed models. The heuristics, therefore, cannot solve models 
 217 
 
which pass those limits. This is a weak point for the heuristics. In addition, the fix-
 and-run algorithm, which is at the core of the heuristic methods, fixes integer 
variables time step by time step. Therefore, when applying this algorithm to time step 
t, decision variables of future time steps are relaxed. As a result, if there are large 
variations in the input data in the future time steps, the algorithm may not find a good 
solution to the problem. Modification of the fix-and-run algorithm or finding another 
heuristic method may be useful in solving this problem. Meta-heuristic methods, such 
as Tabu Search, Genetic Algorithm, and Ant Colony, can be independent from Xpress 
and may resolve the second weak point of the heuristics proposed in this research. 
 
3- Reformulation in Mathematical Formulation 
The mathematical formulation proposed in this research includes many 
decision variables, most of which concern the flow of commodities in links. These 
decision variables are naturally integer; however, because demands are integer, they 
can be assumed to be continuous. Since one of the goals of this study is tracking 
vehicles and the capacity of vehicles has been considered, the number of flow-
 decision variables increases rapidly as the model?s parameters such as the number of 
facility locations, the fleet size and the number of time steps increase. Analysis of the 
proposed mathematical formulation is recommended, to see whether there is any way 
to reformulate this model with fewer decision variables while holding constant the 
model?s functionality and capabilities. 
 
 
 218 
 
4- Considering TPLPs in the Upper Level 
In the current study, TPLPs exist in the lower level; however, they can be used 
in the upper level to transport syrup concentrate between plants and bottlers. The 
same TPLP, in other words, could contract with the bottling company for delivery in 
both levels.  
 
5- Considering Tradeoff between Fuel and TPLP Costs 
In the sensitivity analysis section of this research, the fuel price was changed 
while the cost of TPLP was constant. In the reality, there is a tradeoff between these 
two costs. In fact, by increase in the fuel price, cost of TPLP contract increases and it 
affect the delivery distribution plan. Considering this tradeoff between costs of fuel 
and TPLP contract is another recommendation for the future research. 
 
6- Considering Different Values for Transferred Unsatisfied Demand Parameter 
As mentioned in Chapter 3, this research assumed the unsatisfied demand is 
transferred to the next time step completely. ? is the parameter indicating the portion 
of unsatisfied demand transferred and it can vary from zero to one. Different values 
of ? impact on the final solution and the objective function. Another research, 
therefore, can focus on possible values of ? and their effect on the objective function.  
 
  
 219 
 
References 
 
Andersson, H., Hoff, A., Christiansen, M., Hasle, G., & Lokketangen, A. (2010). 
Industrial Ascpects and Literature Survey: Combined Inventory Management 
and Routing. Computer and Operations Research. 
Ashenbaum, B., Martz, A., & Rabinovich, E. (2005). Studies of Trends in Third Party 
Logistics Usage. What Can We Conclude? Transportation Journal, Vol. 
44(3), 39-49. 
Bard, J. F., & Nananukul, N. (2010). A Branch-and-Price Algorithm for an Integrated 
Production and Inventory Routing Problem. Computers and Operations 
Research, 37, 2202-2217. 
Beamon, B. M. (1998). Supply Chain Design and Analysis: Models and Methods. 
International Journal of Production Economics, Vol. 55, Issue 3, 281-294. 
Bertazzi, L., Paletta, G., & Speranza, M. G. (2002). Deterministic Orde-uo-to Level 
Policies in an Inventory Routing Problem. Transportation Science, Vol. 36, 
No. 1, 119-132. 
Boyson, S., Corst, T., Dresner, M., & Rabinovich, E. (1999). Managing Effective 
Third Party Logistics Relationships: What Does It Take? Journal of Business 
Logistics, Vol. 20(1), 73-100. 
Campbell, A. M., & Savelsbergh, M. W. (2004). A Decomposition Approach for the 
Inventory-Routing Problem. Transportation Science, Vol. 38, No. 4, 488-502. 
Carbone, V., & Stone, M. A. (2005). Growth and Relational Strategies Used by the 
European Logistics Service Providers: Ratinale and Outcomes. Transportation 
Research Part E, Vol. 41, 495-510. 
Chandra, P. (1993). A Dynamic Distribution Model with Warehouse and Customer 
Replenishment Requirements. Journal of Operational Research Society, Vol. 
44, No. 7, 681-692. 
Chen, F. Y., Hum, S. H., & Sun, J. (2001). Analysis of Third-Party Warehousing 
Contracts with Commitments. European Journal of Operational Research, 
Vol. 131, 603-610. 
Chien, T. W., Balakrishnan, A., & Wong, R. T. (1989). An Integrated Inventory 
Allocation and Vehicle Routing Problem. Transportation Science, Vol. 23, No 
2. 
Dhaenens-Flipo, C., & Finke, G. (2001). An Integrated Model for an Industrial 
Prodiction-Distribution Problem. IIE Transactions, Vol. 33, 705-715. 
Eksioglu, B. (2002). Network Algorithm for Supply ChainOptimization Problems. 
University of Florida. 
Evangelista, P., & Sweeney, E. (2006). Technology Usage in the Supply Chain: The 
Case of Small 3PL's. The International Journal of Logistics Management, Vol. 
17(1), 55-74. 
Gaur, V., & Fisher, M. L. (2004). A Periodic Inventory Problem at a Supermarket 
Chain. Operations Research, Vol.52, No. 6, 813-822. 
Greaver II, M. F. (1999). Strategic Outsourcing: A Structured Approach to 
Outsourcing Decision and Initiatives. New York: AMACOM. 
 220 
 
Haghani, A., & Oh, S.-C. (1996). Formulation and Solution of a Multi-commodity, 
Multi-modal Network Flow Model for Disaster Relief Operations. 
Transportation Research Part A: Policy and Practice, 231-250. 
Hall, R. W. (1987). Consolidation Strategy: Inventory, Vehicles and Terminals. 
Journal of Business Logistics, Vol. 8(2), 57-73. 
Jang, Y.-J., Jang, S.-Y., Chang, B.-M., & Park, J. (2002). A Combined Model of 
Network Design and Production/Distribution Planning for Supply Network. 
Computer & Industrial Engineering, 43, 263-281. 
Kenemeyer, A. M., Corsi, T. M., & Murphy, P. R. (2003). Logistics Outsourcing 
Relationships: Customer Perspectives. Journal of Business Logistics, Vol. 
24(1), 77-109. 
Kim, J.-U., & Kim, Y.-D. (2000). A Lagranxian Relaxation Approach to Multi-period 
Inventory/Distribution Planning. Journal of Operational Research Society, 
Vol. 51, 364-370. 
Ko, H. J., & Evans, G. W. (2007). A Genetic Algorithm-Based Heuristic for the 
Dynamic Integrated Forward/Reverse Logistics Network for 3PLs. Computer 
and Operations Research, Vol. 34, 346-366. 
La Londe, B. J., & Masters, J. M. (1994). Emerging Logistics Strategies: Blueprints 
for the Next Century. International Journal of Physical Distribution & 
Logistics Management, Vol. 24, Issue 7, 35-47. 
Laarhoven, P. V., Berglund, M., & Peters, M. (2000). Third-Party Logistics in 
Europe-Five Years Later. International Journal of Physical Distribution & 
Logistics Management, Vol. 30(5), 425-442. 
Lai, K. H., Ngai, E., & Cheng, T. (2005). Information Technology Adoption in Hong 
Kong's Logistics Industry. Transportation Journal, Vol. 44(4), 1-9. 
Lee, C.-G., Bozer, Y. A., & White III, C. C. (2003, May 6). A Heuristic Approach 
and Properties of Optimal Solutions to the Dynamic Inventory Routing 
Problem. Toronto, Ontario, Canada. 
Lei, L., Liu, S., Ruszczynski, A., & Park, S. (2006). On the Integrated Production, 
Inventory, and Distribution Routing Problem. IIE Transactions, Vol. 38, 955-
 970. 
Lewis, I., & Talalayevsky, A. (2000). Third-Party Logistics: Leveraging Information 
Technology. Journal of Business Logistics, Vol. 21(2), 173-185. 
Lieb, R. C. (1992). The Use of Third-Party Logistics Sevices by Large American 
Manufacturers. Journal of Business Logistics, Vol. 13(2), 29-42. 
Lieb, R. C., & Bentz, B. A. (2004). The Use of Third-Party Logistics Services by 
Large American Manufacturers: The 2004 Survey. Transportation Journal, 
Vol. 2, 5-15. 
Lim, W. S. (2000). A Lemon Market? An incentive Scheme to Induce Truth-Telling 
in Third Party Logistics Providers. European Journal of Operational 
Research, Vol. 125, 519-525. 
Lynch, C. F. (2004). Logistics Outsourcing: A Management Guide. Memphis: CFL 
Publishing. 
Maloni, M. J., & Carter, C. R. (2006). Opportunities for Research in Third-Party 
Logistics. Transportation Journal, Vol. 45(2), 23-28. 
 221 
 
Marasco, A. (2008). Third-Party Logistics: A Literature Review. International 
Journal of Production Economics, Vol. 113, 127-147. 
Moin, N. H., & Salhi, S. (2007). Inventory Routing Problems: A Logistival 
Overview. Journal of Operational Research Society. 
Moore, K. R., & Cunningham III, W. A. (1999). Social Exchange Behavior in 
Logistics Relationships: A Shipper Perspective. International Journal of 
Physical Distribution & Logistics Management, Vol. 29(2), 103-121. 
New, S. J., & Payne, P. (1995). Research Frameworks in Logistics: Three Models, 
Seven Dinners and a Survey. International Journal of Physical Distribution & 
Logistics Management, Vol. 25, Issue 10, 60-77. 
Razzaque, M. A., & Sheng, C. C. (1998). Outsourcing of Logistics Functions: A 
Literature Survey. International Journal of Physical Distribution & Logistics 
Management, Vol. 28(2), 89-108. 
Rusdiansyah, A., & Tsao, D.-b. (2005). An Integrated Model of the Periodic Delivery 
Problems for Vending-Machine Supply Chains. Journal of Food Engineering, 
Vol. 70, 421-434. 
Savelsbergh, M., & Song, J.-H. (2008). An Optimization Algorithm for the Inventory 
Routing Problem with Continuous Moves. Computers & Operations 
Research, Vol. 35, 2266-2282. 
Schmidt, G., & Wilhelm, W. E. (2000). Strategic, Tactical, and Operational Decisions 
in Multi-national Logistics Netwroks: A Review and Decision of Modeling 
Issues. International Journal of Production Research, Vol. 38, No. 7, 1501-
 1523. 
Scott, C., & Westbrook, R. (1991). New Strategic Tools for Supply Chain 
Management. International Journal of Physical Distribution & Logistics 
Management, Vol. 21, Issue 1, 23-33. 
Simchi-Levi, D., Kaminsky , P., & Simchi-Levi, E. (2003). Designing and Managing 
the Supply Chain: Concepts, Strategies and Case Studies. New York: 
Irwin/McGraw-Hill. 
Tan, K. C. (2001). A Framework of Supply Chain Management Literature . European 
Journal of Purchasing & Supply Management, Vol. 7, 39-48. 
Tyan, J. C., Wang, F.-K., & Du, T. C. (2003). An Evaluation of Freight Consolidation 
Policies in Global Third Party Logistics. The International Journal of 
Management Science, Vol. 31, 55-62. 
Valluri, H., Nahata, S., Jangalwa, A., & Sethi, G. R. (n.d.). The Coca-Cola Company 
2010. Retrieved from Scribd: 
http://www.scribd.com/doc/37483762/Organizational-Structure-of-The-Coca-
 Cola-Company#outer_page_14 
Wan, X., Evers, P. T., & Dresner, M. E. (2012). Too much of a good thimg: The 
impact of product variety on operations and sales performance. Journal of 
Operations Management, Vol. 30, 316-324. 
Wilding, R., & Juriado, R. (2004). Customer Perceptions on Logistic Outsourcing in 
the European Consumer Goods Industry. International Journal of Physical 
Distribution & Logistics Management, Vol. 34(7/8), 628-644. 
Yeung, J., Selen, W., Sum, C. C., & Huo, B. (2006). Linking Financial Performance 
to Strategic Orientation and Operational Priorities. An Empirical Study of 
 222 
 
Third-Party Logistics Providers. International Journal of Physical 
Distribution & Logistics Management, Vol. 36(3), 210-230. 
Yu, Y., Chen, H., & Chu, F. (2008). A New Model and Hybrid Approach for Large 
Scale Inventory Routing Problem. European Journal of Operational 
Research, Vol. 189, 1022-1040. 
Zapfel, G., & Wasner, M. (2002). Planning and Optimization of Hub-and-Spoke 
Transportation Networks of Cooperative Third-Party Logistics Providers. 
International Journal of Production Economics, Vol. 78, 207-220. 
Zineldin, M., & Bredenlow, T. (2003). StrategicAlliance: Synergies and Challenges: 
A Case of Strategic Outsourcing Relationship "Sour". International Journal of 
Physical Distribution & Logistics Management, Vol. 33(5), 449-464.