OPTIMIZATION AND SCHEDULING OF
A POOLED LOG TRANSPORT SYSTEM
Except where reference is made to the work of others, the work described in this thesis is
my own or done in collaboration with my advisory committee. This thesis does not
include proprietary or classified information.
___________________________
Karunakaran Haridass
Certificate of Approval:
____________________________ ____________________________
Jeffrey S. Smith Jorge Valenzuela, Chair
Professor Associate Professor
Industrial and Systems Engineering Industrial and Systems Engineering
____________________________ ____________________________
Timothy McDonald George T. Flowers
Associate Professor Dean
Biosystems Engineering Graduate School
OPTIMIZATION AND SCHEDULING OF
A POOLED LOG TRANSPORT SYSTEM
Karunakaran Haridass
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
August 10, 2009
iii
OPTIMIZATION AND SCHEDULING OF
A POOLED LOG TRANSPORT SYSTEM
Karunakaran Haridass
Permission is granted to Auburn University to make copies of this thesis at its discretion,
upon request of individuals or institutions and at their expense. The author reserves all
publication rights.
_________________________
Signature of Author
_________________________
Date of Graduation
iv
VITA
Karunakaran Haridass, son of Haridass and Lakshmidevi was born on May 19th,
1985, in Coimbatore, India. He entered Sri Krishna College of Engineering and
Technology and graduated from the Department of Mechanical Engineering with a
bachelor?s degree in April 2006. In January 2007, he entered Auburn University to
pursue a Master?s degree in Industrial and Systems Engineering. During his years at
Auburn University, he served as a graduate research assistant in the Department of
Industrial and Systems Engineering. He has also worked in an aerospace project in
association with the Department of Aviation and Supply chain management and the
Society of Satellite Professional International Organization.
v
THESIS ABSTRACT
OPTIMIZATION AND SCHEDULING OF
A POOLED LOG TRANSPORT SYSTEM
Karunakaran Haridass
Master of Science, August 10, 2009
(B.E., Anna University, 2006)
105 Typed Pages
Directed by Jorge Valenzuela
The log truck scheduling problem (LTSP) under capacity constraints and time
window constraints which is an NP-hard problem, involves the design of a set of best
possible routes for a set of trucks starting and ending the day at a hub serving a set of
loggers and mills. The objective is to minimize the unloaded miles traveled by trucks by
pooling all the trucks owned by the trucking companies and optimizing the routes of the
trucks. The other constraints include the speed limit, shift duration of the drivers and
mandatory return of trucks to the hub at the end of the day. A deterministic simulator is
developed using a C program which emulates any set of routes and gives total unloaded
miles as an output besides other performance metrics. A simulated annealing algorithm is
vi
used to generate an initial feasible solution and thereby improve the solution using
various search operators functioning in the neighborhood. A sensitivity analysis is made
to reduce the number of trucks needed to meet the demand for the day. For a small
problem, the algorithm produces very close results to the optimum solution. A large
practical problem with 68 trucks, 22 loggers and 13 mills is solved to find the best set of
routes using the developed algorithm. Finally an economic analysis is made to find the
impact of the location of loggers and mills on the solution. Computational results show
that the number of unloaded miles is reduced by 28% and the number of trucks needed to
serve the loads is reduced by 17%. The results are further verified by feeding the set of
routes as input to the simulator.
vii
ACKNOWLEDGEMENTS
I would like to express my humble gratitude to Dr. Jorge Valenzuela, my advisor
and committee chair, for his support, motivation, patience and insightful guidance
throughout my research work. I would like to thank my committee members Dr. Jeffrey
S. Smith and Dr. Timothy McDonald for taking time out of their schedules to be on my
committee. I am grateful to my parents and my sister for their love and continuous
encouragement. Last but not the least, I take this opportunity to thank God for blessing
me in completing the course work and research successfully.
viii
Computer software used: Microsoft Word 2003, Microsoft Excel 2003, Google Earth,
C Language
ix
TABLE OF CONTENTS
LIST OF TABLES????????........................................................................xi
LIST OF FIGURES?????????????????????????.xii
CHAPTER 1. INTRODUCTION????????????????????..1
CHAPTER 2. LITERATURE REVIEW?????????????????...7
CHAPTER 3. RESEARCH BACKGROUND???????????????20
CHAPTER 4. PROPOSED APPROACHES???????????????...26
4.1. ASSUMPTIONS??????????????????????..27
4.2. INTEGER PROGRAMMING APPROACH???????????...28
4.2.1. Formulation?????????????????????...28
4.2.2. Demerits of integer programming?????????????.31
4.3. SIMULATED ANNEALING APPROACH????????????31
4.3.1. Simulated annealing implementation???????????....34
4.3.2. Construction heuristics?????????????????..34
4.3.3. Improvement heuristics?????????????????.38
4.3.4. Conditions for accepting a bad solution??????????....45
4.4. DESCRIPTION OF THE SMALL PROBLEM??????????...47
4.4.1. Solution using integer programming model??????..???47
4.4.2. Solution using simulated annealing algorithm????????..48
x
CHAPTER 5. DETERMINISTIC SIMULATOR??????????????50
5.1. BASIC MODEL OF SIMULATOR???????????????.50
5.2. INITIALIZATION OF PERFORMANCE PARAMETERS???............53
5.3. SIMULATION OF THE EVENTS???????????????...54
5.4. ADVANTAGES AND USES OF THE SIMULATOR?????............57
CHAPTER 6. EXPERIMENTAL RESULTS OF ACTUAL SYSTEM?????..59
6.1. DESCRIPTION OF THE ACTUAL PROBLEM??????????.59
6.2. FINISHING TIME OF TRUCKS????????????????.60
6.3. IMPROVEMENT IN PERFORMANCE METRICS???????.......62
CHAPTER 7. SENSITIVITY ANALYSIS????????????????..68
7.1. REDUCTION OF TRUCKS??????????????????.68
7.2. SCENARIO ANALYSIS???????????????????..74
7.3. MARGINAL CONTRIBUTION OF LOGGERS AND MILLS????..78
CHAPTER 8. CONCLUSION AND DISCUSSION????????????...83
REFERENCES???????????????????????????.87
APPENDIX 1. LOGGER AND MILL NOTATION????????????...89
APPENDIX 2. DISTANCE MATRIX BETWEEN LOGGERS AND MILLS??...91
APPENDIX 3. DEMAND MATRIX BETWEEN LOGGERS AND MILLS???.92
xi
LIST OF TABLES
4.1 Solution using integer programming approach?????????...?...48
4.2 Solution using simulated annealing approach????????????48
6.1 Improvement in performance metrics???????????????63
6.2 Average waiting time at logger locations?????????????..65
6.3 Average waiting time at mill locations??????????????..66
7.1 Results of marginal contribution of loggers??????.??????..80
7.2 Results of marginal contribution of mills???????.??????..81
xii
LIST OF FIGURES
3.1 Location of loggers and mills in the map???????..??????.21
3.2 Tracking data given by the company???????????????.24
4.1 Pseudo code for simulated annealing???????????????.36
4.2 Decrease operator being applied to cut short the route length?????...39
4.3 Increase operator being applied to increase the route length??????.40
4.4 Stop operator being applied to stop the truck????????????.41
4.5 Transfer operator being applied to trucks? routes??????????..42
4.6 Interchange operator being applied to trucks? routes?????????.44
5.1 Basic model of a simulator???????????????????.50
5.2 A simulator following a truck?s route???????????????52
5.3 Schematic diagram of the simulator???????????????...54
5.4 Pseudo code for working of simulator??????????????...55
6.1 Finishing time of trucks in the existing system???????????..61
6.2 Comparison of finishing time of trucks between real data
and the best solution?????????????????????62
xiii
7.1 Finishing time of 68 trucks from the optimal solution????????...69
7.2 Sensitivity analysis for reduction of trucks from 67 trucks
to 62 trucks????????????????????????..69
7.3 Sensitivity analysis for reduction of trucks from 62 trucks
to 56 trucks????????????????????????..70
7.4 Finishing time of trucks for 68 trucks and 56 trucks?????????..71
7.5 Time taken to find the solution with reduction in number
of trucks?????????????????????????...72
7.6 Proportion of trucks with maximum utilization???????????.73
7.7 Six sample scenarios showing uniform distribution of
loggers, mills and hub????????????????????..75
7.8 Histogram of loaded miles percentage for 175 scenarios???????...76
7.9 Sample scenario for loaded mile 46%??.????????????...77
7.10 Sample scenario for loaded mile 66%???????????.???...78
1
CHAPTER 1
INTRODUCTION
The log truck scheduling problem (LTSP) has been discussed widely in the
literatures of transportation and routing management. In forestry, nearly 40% of the costs
are involved in road planning and in transportation operations and management.
Monetary savings can be realized if some improvement is made to the existing logistics
system.
In the southern US, trees are harvested using what is termed a ?Tree-length?
approach. The felled trees are first moved to a deck for processing using skidders.
Processing (removal of remaining limbs and tops) is done either manually by capable log
makers or by using sophisticated machines. From there, the tree-length logs are
transported to the specific mills such as saw mills and paper mills.
The wood products industry in southern US is facing increasing pressure from
cheaper wood imports. The need to reduce transportation costs has been felt very acutely
among loggers and mill owners. The logging capacity has always been in excess of
demand and it is essential for the logger owner to reduce costs in order to survive in
business.
In the existing system, the logging company owns a group of trucks and operates
between a particular set of mills to satisfy the demand. Some group of trucks
2
takes more time to meet the loads exceeding the time windows for the loggers and mills.
A few other truck groups take less time to meet the demand and finish well within the
time window. Some logger owners subcontract trucks to meet the demand. Very often,
the trucks reach the supply point before the earliest time of operation at supply points and
wait for the supplier to begin operations at the supplier site. The truck driver?s working
hours are not properly utilized and he spends a lot of time in just waiting for the truck to
be loaded at the supplier?s site.
All the upstream and downstream operations depend on the timely pick-up and
delivery of wood by the trucks. The inter arrival time of trucks should be as uniform as
possible with less variance to ensure smooth inventory level at the pick up point and
delivery point. If trucks don?t reach the pick up point at the right time, the inventory level
at the logger reaches maximum and the logging process gets blocked due to the
unavailability of stocking space. Similarly, at the location of mills, there should be
sufficient logs available to carry the cutting and other shaping operations. In case of non-
availability of logs, the cranes and machines would be idling causing low utilization of
equipment. To prevent this, the truck needs to deliver the loads at uniform intervals to
ensure the smooth operation of mills.
If a group of trucks arrive together at the same destination or supplier point, they
have to wait in line for a longer time to get the services of cranes for loading and
unloading purposes. There is huge savings when less time is being spent in waiting and
cranes are made to work all the time. This ensures continuous operation at upstream
logging stations and downstream mills.
3
The location of loggers and mills decides the feasibility of opting for a shared
transport system. If the mills and loggers are located very close to each other then no
appreciable improvement can be made in sharing the trucks and delivering the loads.
The role of log transport manager is to form a demand matrix of the loads to be
delivered and a distance matrix which contains the shortest path between any two
locations. The mills and loggers furnish the requirements and trucks available for
transport one day in advance. Then the manager works up a schedule to meet all the loads
and gives it to the truck drivers to execute the schedule. Though the trucks are shared in
the existing system, the routing is not optimized and leads to a large percentage of
unloaded miles, more waiting time and inability to meet the demand within the time
window.
In the proposed system, all the operations of the trucks are brought under a
centralized ownership and the transport manager prepares a schedule taking into
consideration the demand matrix of all the loggers and mills situated in that region. The
centralized scheduler feeds the demand matrix and distance matrix into the computer and
gets the best set of routes for all the trucks for the following day. The routes are designed
in such a way that the trucks end the day before shift ends and travel fewer unloaded
miles than the existing system. The income generated by the entire group of trucks is
shared among the truck owners proportionately. By this way, more income is generated
within a shorter period of time.
The trucks begin the day either as loaded or unloaded from the hub. They travel
through a series of loggers and mills and return back to the hub at the end of the day. The
4
basic objective is to minimize the unloaded miles and to meet all the demands within the
time window. Since there are a large number of trucks available to meet the demand, the
number of trips is actually restricted so that all the trucks are completely utilized within
the time window to deliver the loads. There is loading and unloading time at each logger
and at each mill site.
The truck routing problem is a complex combinatorial problem and few
approaches to solve the problem have been proposed in literature. There are many
heuristic approaches like tabu search, column generation, branch and bound heuristics to
solve the general vehicle routing problem where the destinations are visited only once.
But in case of the log truck scheduling problem multiple visits to a single mill or logger
are required to meet the demand. Since this involves repeated visits to the customer sites,
it can?t be easily solved using the existing heuristic approaches.
A simulator and a main program which successfully outputs the best set of routes
using a simulated annealing algorithm have been developed. Basically, the simulator is a
C program consisting of data structures which simulates the movement of trucks as per
the set of routes given as input to the system and gives output as total unloaded miles,
unmet loads and finishing time of trucks for that input.
The main program which gives the best routes as output incorporates the
simulator and simulated annealing algorithm. The input given to the main program is the
number of trucks, demand matrix, distance matrix and maximum number of trips allowed
for the trucks. The program builds an initial feasible solution and goes on to find the best
5
solution by searching and improvising at various stages of the algorithm. The program is
run one day in advance and actual demand to be satisfied is known one day in advance.
The logger locations and mill locations are geographically defined and the
shortest distance between the loggers and mills is found using Google Earth and verified
using data extracted from the data analysis of a practical case. It was found that there is
only one shortest path to travel between any two customer locations.
The trucks available are enough to meet the demand requirements for the day. The
trucks should not be under utilized and at the same time should not be over utilized.
Therefore the number of trips traveled by the trucks is restricted to a specific value. There
is a lower bound and an upper bound for the starting time and ending time for truck
drivers which is fully respected. The truck is fully loaded at each logger. Hence there is
no room for loading at another logger site before delivering the carrying load. The main
activities performed by the trucks are to transport the loads from logger to the mill apart
from starting and ending the day at the hub. The costs involved are the transportation
costs between loggers and mills. The unloaded miles traveled by the trucks increases the
unwanted cost.
The simulated annealing algorithm developed consists of 2 stages. In the first
stage, an initial solution generated is made feasible by meeting all the demands for the
day. The solution is then improved using improvement operators like transfer, exchange,
interchange and stop operators. There is no particular stopping criterion employed to stop
the algorithm relative to the solution change. The algorithm is allowed to run for the
entire temperature steps.
6
The algorithm produced close results when tested against a small problem whose
optimum value is known. The same algorithm without any modification is used to solve
the practical case of a big problem where there are comparatively more trucks, loggers
and mills. Total unloaded miles and number of trucks needed to meet the loads are taken
as the measures of comparison between the existing practical system and proposed
pooled transport system. It is found that the unloaded miles are reduced by 28% and the
number of trucks needed to serve the loads is reduced by 17%.
The percentage of total loaded miles to the total miles traveled is a measure of the
efficiency of the proposed system. In order to find the distribution and statistical mean of
loaded miles percentage, the loggers and mills locations are randomly generated within a
square region in a particular scenario and loaded miles percentage is calculated. This is
repeated for 175 different scenarios and a distribution is obtained.
Finally the impact of individual loggers, mills and hub on the solution is found
using economic analysis.
7
CHAPTER 2
LITERATURE REVIEW
The majority of work done previously discusses solving the vehicle-routing
problem rather than a log-truck scheduling problem. Relevant literatures are being
reviewed in this chapter.
Gerdesson [1] has made an attempt to solve the vehicle-routing problem with
trailers. The vehicle consists of a trailer and a truck. The vehicle always starts from a
depot and ends the day in the depot. The vehicle starts serving the customers one by one
with both trailer and truck. After reaching a parking spot, the vehicle leaves the trailer in
the parking spot and serves the nearby places with the truck alone thereby reducing the
time taken to serve the customers near the parking spot. The truck returns to the parking
spot, reattaches the trailer with it and serves the rest of the customers with the complete
vehicle.
The problem is solved in two phases. Construction heuristics are first used to
obtain a feasible solution and then improvement heuristics are used to obtain an improved
solution from the initial solution.
Under construction heuristics, the number of vehicles needed to serve the loads is
first calculated. Three different heuristics were used to get a good initial feasible solution.
In the first heuristic, the customer locations were allocated disproportionately to the
vehicles and also had the disadvantage of selecting a parking place very early. In the
8
second heuristic, however the locations were allocated proportionately but still the
parking place was allocated very early. In the third heuristic, the parking place was not
allotted and hence it provided huge potential for the improvement of the feasible solution
by moving the parking place around.
At last, the improvement heuristic is used to get a good solution by exchanging
customer sites between a truck?s route and a vehicle?s route, two truck routes, and two
vehicle routes. Also some improvement is made by disconnecting the links at some
location and connecting them at other customer sites.
Chao [2] models a truck and trailer routing problem [TTRP] and uses the tabu
search heuristic to solve the problem. The customers are assigned to the trucks by
relaxing the integrality constraint and obtaining a linear initial solution. The three types
of routes namely pure vehicle route, pure truck route and complete vehicle route are
constructed in the next step using the cheapest insertion heuristic. In the descent
improvement step, the initial infeasible solution obtained is then converted to a feasible
initial solution by exchanging one or two customers at a time and by changing the
parking place without exceeding the capacity of trailer and truck.
Finally, the whole solution is improved by using the tabu search heuristic coupled
with the deviation concept. In order to escape local optima and to prevent a too strict tabu
restriction, intensification and diversification strategy under aspiration criteria were used
to effectively search the solution space. Clean-up and stopping rules are used to improve
the solution locally and the global stopping rule was used to stop the search procedure.
9
Sumichrast et al. [3] have compared the solutions obtained by heuristic with that
of lower bound integer programming solution from LINDO, a commercial solver. The
problem size used in the paper was small in terms of demand met for the day and in the
number of trucks used to meet the demand.
In the search heuristic, the solution was improved by exchanging plants within the
truck?s route and also by exchanging trucks used to meet the demand. In order to
incorporate the entire network, the duplication of the depot was carried out.
The paper has proved that the heuristic method can produce the results in less than
a second whereas it took more than 67 seconds to solve using LINDO. Also the gap
between heuristic solution and lower bound was found to be less than 5% for a small or
medium sized problem whereas it was approximately 8% for slightly bigger problems.
No practical case is presented and compared in terms of improvement in objective
constraints and also there were no time windows.
Thangiah et al. [4] have developed a heuristic for the vehicle routing problem
with backhauls and time windows (VRPBTW). The returning vehicle after delivering the
loads to the customers visits the supplier and carries the raw material along with it to the
depot. In this paper, the earliest and latest time were defined which indicates the lower
bound and upper bound at the customer?s site. The loading time, unloading time and
waiting time were exclusively accounted for when calculating the total route time of the
trucks.
The construction heuristic starts by assigning a truck to serve a seed customer
initially and then including all other customers one by one without exceeding the time
10
windows. Then the routes for all other trucks are designed in the same fashion. When
doing the above, the capacity constraints and backhaul constraints were taken into
consideration.
After constructing the routes, the ?-interchange procedure is performed to
improve the solution either by first improvement (or) best improvement strategy. Also,
the 2-opt exchange procedure is done to further bring the solution close to optimal
solution by paying attention to feasibility since inserting back haul customers within line
haul customers would spoil feasibility. Finally it was found that the heuristic produced a
solution which differs from the optimum only by 2.5%.
Czech et al. [5] have used parallel simulated annealing algorithm to solve vehicle
routing problem with time window (VRPTW) without any backhauling. The waiting
time, service time, earliest time and latest time were all taken into consideration while
solving the problem. The objective function had to minimize the number of vehicles used
as well as to reduce the total distance traveled. The truck could only serve customers
whose total demand is less than the total capacity of the truck in one trip.
The paper also discusses the criterion to select the initial temperature and also the
termination criteria of when the search should be stopped. Excellent conclusions on what
should be done to get good optimization results were summarized. Proper care should be
taken when selecting initial temperature for annealing, cooling schedule, number of
annealing steps executed at each temperature, along with relative importance of number
of routes against the travel distance.
11
Ronnquist [6] describes the scope for optimization in various stages of forestry
beginning with harvesting, bulking, crew scheduling, road building, fleet management,
truck scheduling and ending with production planning. Solution methods such as
dynamic programming, L.P. methods, branch and bound methods, heuristics and column
generation were used for optimization.
In the transportation and routing stage, transportation planning was done in one of
three ways. Either the individual truck owners decide the routing or routing is carried out
by the harvesting people once the wood accumulates. The third case is the integration of
all the truck owners under a centralized system, and combined routing of all the trucks is
carried out by a single virtual owner.
The paper clearly points out the difference between general vehicle routing
problems and routing problems in forestry. The difference is that in case of routing in
forestry, there are many supply and demand points. The supply and demand locations are
to be visited more than once unlike the case of general vehicle routing problems. Usually
the solution time is 5 seconds for truck dispatching and 1 day for truck scheduling. The
solution approach here consisted of both heuristics and optimization.
Bent et al. [7] have modeled the dynamic vehicle routing with stochastic service
times and customer locations using Multiple Plan Approach (MPA) and Multiple
Scenario Approach (MSA). Multiple plan approach?s main idea is to generate and
maintain all possible sets of routing plans along with the main routing plan. The random
customer requests are ranked according to a priority. The requests are checked against the
12
available plans. If they match one of the available plans, it is accepted; otherwise it is
rejected.
In case of multiple scenario approach, the requests are sampled from a general log
normal distribution and the routing plans are generated according to sampled requests.
Hence the future customer requests are accommodated by switching from the main
routing plan to the available plan. As an improvement to this, the multiple scenario
approach with loosely constrained problems (MSA-LC) were modeled. In this type, the
trucks delay the departure from the customer location anticipating any request from the
nearby customers. This approach yielded good results. Finally, the consensus model is
evolved which generates routes according to MPA and MSA-LC and executes the plan
which yields the best results.
Weintraub et al. [8] discusses the need to centralize ownership of the trucks in
order to schedule the trips efficiently. The paper explains that the trucks should start and
end the day from a place which is very near to the driver?s home. To achieve this, the
supply point for the first trip and the demand point for the last trip were selected near to
the driver?s home. The demand for one of the product types can be satisfied by any of the
supply points and this relaxation has imparted a large amount of flexibility in meeting the
demand. The scheduling is designed in such a way that the inter-arrival time is almost
uniform for all the trucks so that the production and the harvesting operations are done
smoothly at either end without excess inventory or a lack of inventory.
Scheduling is done every 1 hour taking into consideration the waiting time of the
trucks, idle times of the cranes at the source and at the destination, and also the trucks
13
that will be idle during and after 1 hour. This method will help in reducing competition
among the truck drivers in competing for loads and also ensures equal income to all the
truck owners. The paper mainly aims at meeting the demand and did not take into
consideration any optimization or heuristic approach to reduce the unloaded miles
traveled.
Palmgren et al. [9] proposed a solution approach based on column generation and
pseudo branch and price for the log-truck scheduling problem. A cluster of customer
locations near the starting point are only considered for destination in that trip. Also the
truck is allowed to visit all the supply points until it is fully loaded before beginning to
deliver the loads to the demand locations. The truck operates in two 8-hour shifts with
time allocated for lunch break. The sub-problem of designing a route for the truck was
solved using the shortest path method.
The solution approach starts with generating an initial set of feasible routes
followed by pricing using dual variables in order to reduce the cost of the routes. While
solving the sub-problem using k-shortest path method, a series of shortest path routes are
generated so that if the first one is not feasible, the next shortest path is automatically
adopted. Also the solution for the sub problem sets a lower bound for the problems after
interrupting the optimality with a fixed number of iterations. Finally the column
generator is combined with fast heuristics to produce efficient routes for the log-truck
scheduling problem.
Hirsch et al. [10] have used four different tabu search approaches and a few post
optimization heuristics to solve the timber transport vehicle routing problem (TTVRP).
14
The first three approaches were intended for small problems while the fourth one is
meant for big problems. In the case of small problems, the approaches differ in terms of
search in the neighborhood. One standard tabu search (TS) approach searches a large
neighborhood whereas the tabu search with limited neighborhood (TSLN) approach
searches a very limited neighborhood. The third approach is a combination of the above
two approaches with full neighborhood search done after a fixed number of limited
neighborhood searches.
Though every approach?s objective is to minimize the empty truck movements,
the tabu search with large problem instance (TSLP) attempts to solve larger problems by
limiting the task allocation to 4. By doing this, the constraint of time window is satisfied
at all customer and destination locations. Even though all approaches produce good
results, it was found that the solution got stuck to local optima most of the time. Hence a
post-optimization improvisation heuristic, namely 2-opt, was done to produce a much
better solution. It was observed that the heuristics produced a result closer to the lower
bound produced by other CPLEX solvers.
Bent et al. [11] discuss the importance of solving vehicle routing problems with
time windows (VRPTW) and capacity constraints in a two stage hybrid manner. It was
found that when minimizing the dual objective of travel cost and the number of routes,
the algorithm is succeeding only in minimizing the travel cost.
While minimizing the number of routes, traditional move operators like 2-
exchange, or-exchange, relocation, crossover, and exchange were used. The operators
and customers to be operated upon were chosen randomly. The objective function is
15
modified so that the solutions that have routes with more customers and routes with fewer
customers are more favored over solutions that have routes with equal distribution of
customers. The limited discrepancy search (LDS), a strategy which explores the search
tree in waves allowing the heuristic to make more mistakes is used in minimizing the
travel cost. This strategy yielded a good optimal solution after appreciable iterations. The
results were then compared with the standard Solomon benchmarks. The 2-stage
algorithm produced matching or better results 97% of the time, the best percentage of
improvement being 2%.
Osman [12] has investigated three different algorithms namely descent, hybrid
simulated annealing with tabu search and tabu search algorithms for their performance in
solving vehicle routing problem (VRP) with capacity and the distance constraints. The
well known Clarke and Weight savings procedure was used to find an initial feasible
solution. The ?-Interchange generation mechanism was used to search the neighborhood
of the current solution. The mechanism consists of the shift operator and the interchange
operator. The first improvement (FI) and the best improvement (BI) strategy were used to
select alternative solutions. The ?-interchange descent algorithm has a major limitation of
dependence of the final solution on the initial feasible solution. Hence the final solution
obtained may be far away from the global optimum. The best available selection (BA)
strategy and the first best available selection strategy (FBA) have been used to select
alternative solutions. A special data structure was created for the best available selection
strategy. This has helped in reducing the computational time by 50%. The simulated
annealing algorithm produced results better than descent algorithm but the variance of the
16
quality of the solution and that of the computational time was found to vary significantly.
Tabu Search was the best of all algorithms used but it requires a lot of storage space for
selection of the alternative solution.
Valenzuela et al. [13] have designed a transportation scheduling system for silvi-
cultural projects considering project due dates, precedence relationship and transportation
costs. There were five different classes of resources (trucks) and each had their own
routes. The solution approach consists of 2 stages starting with simulating the network
and then improving the solution using search heuristics. The simulation model outputs
the completion time for tasks and also the distance traveled by the resources. Under
simulated annealing, the search operators engaged in the search technique are the switch
operator and the transfer operator. The objective of minimizing the project duration and
minimizing the travel distance was considered separately and dually as well. Sensitivity
analysis was done by varying the penalty cost for minimizing project durations and the
penalty cost for transportation. Under resource capacity planning, marginal analysis was
being done to find the increase or decrease in cost by adding or removing one resource
from each of the resource class one at a time.
McDonald et al. [14] have compared the efficiency of a shared transport system
with that of the existing traditional log transport system. The paper dealt with issues of
potential savings, scale of operations and dispersion pattern of loggers and mills. The
total unloaded miles were used as a measure of efficiency between logger-controlled
transport system and pooled transport system. In the case of a logger-controlled transport
17
system, the unloaded miles constitute just half the total distance traveled by the trucks.
The speed constraints and the shift duration constraints were brought into the model.
A test case with 16 loggers and 2 mills randomly distributed over a square region
of 250 miles was used. It was found that a minimum number of loggers was needed to
achieve maximum efficiency above which the savings remained unchanged. Also when
the mills were located a bit far away, more loggers were needed to achieve maximum
efficiency.
A linear increase in the transportation efficiency was observed when the range of
logging sites increased. Also an increase in the range of distribution of loggers increased
the average of efficiency gained but the variance was very high which may possibly
reduce the benefits gained.
Simulated annealing is a meta-heuristic algorithm used for optimizing
combinatorial problems. It is mainly used to solve truck routing, school bus routing,
scheduling etc. The name comes from the annealing process in the heat treatment of
solids to reduce defects and to reach a configuration with reduced internal energy. Before
heating the solid, the atom possesses high internal energy in the solid. When it is heated,
the atoms are free to move and wander inside the solid. The solid is allowed to cool
slowly and the atoms occupy a desired state with lower internal energy.
Similarly, in the case of combinatorial problems, the objective is to reach the
global optimum which is assumed to be a state of lower internal energy than the existing
state. For routing problems, the trucks are allowed to move freely during the initial stages
of high temperature. They are then allowed to settle down with the best possible routes by
18
searching through the neighborhood during the later stages of the simulated annealing
algorithm.
The algorithm searches for a good solution throughout the feasible region during
the initial stages without getting stuck to the local optimum. This ensures that the part of
the region which contains the global optimum value is not missed. But as the temperature
goes down, the ability to search and find a solution close to the global optimum also goes
down since it gets stuck in some neighborhood. The rate of cooling is critical in helping
the algorithm to achieve the optimum solution.
An evaluation function is used to find a value corresponding to the new solution
generated. The function decides how good or bad the alternative solution is. At high
temperatures, even a small increase in the value of the evaluation function is accepted
with a probability that depends on the value of the temperature and the difference in the
value of the evaluation function. The acceptability of a bad solution goes down with
reduction in temperature. It means that the bad solution is rarely accepted at lower
temperatures. The majority of search towards the end is oriented towards finding a good
solution around the global optimum.
The simulated annealing algorithm is very flexible and can accommodate any
non-linear model and difficult constraints applicable to any problem. The algorithm is
very robust and capable of approaching the global optimum value. Depending on the
nature of the problem, proper selection and execution of the search heuristics are
possible. The algorithm is designed to look for solutions to the problems rather than
modeling it.
19
The closeness of the results obtained from simulated annealing to the global
optimum depends on the computational time. The more time it takes to compute a
solution, the closer is the solution to the optimum value. Care should be taken to properly
define the constraints in the algorithm. The penalties involved in the evaluation function
and the parameters for the annealing process should be defined after a trial and error
method. The algorithm does not take with it the knowledge obtained after searching.
Instead, it searches for a good solution in the entire feasible region. The algorithm cannot
be used whenever there is an equality constraint. Also the algorithm is not useful when
our interest is to find a best solution in more than one feasible region separated by an
infeasible region.
Integer programming can be used to solve the routing problem but the time taken
to solve the problem increases exponentially with the size of the problem. Nevertheless,
integer programming can still be used to find a good lower bound for the optimum
solution. The lower bound can be compared with the solution obtained using the
simulated annealing algorithm to find out the efficiency of the algorithm. Still integer
programming needs strong formulation and any error in it may lead to an infeasible
solution. More time is spent on modeling the problem rather than solving it. Even with
advances in the processing speed, the time to solve the problem has not come down
appreciably. It still takes more than one or two days to solve the problem and to obtain
the best set of routes. Industry people expect good solutions not necessarily the optimum
within 10 min so that the decisions can be made accordingly.
20
CHAPTER 3
RESEARCH BACKGROUND
This research was motivated by an existing log truck transport system covering a
couple of southern states in the US. There were high costs involved in transportation
from logger to mill. The current system was less inefficient with more trucks being used
to transport logs. The drivers work for more than 12 hours to meet the demand leading to
overtime and causing more expense for the management. The trucks were made to wait
for a long time in queue and, thus, were not properly utilized in spending more time in
transporting logs to the mill. Due to improper planning of the routes, the trucks travel
more unloaded miles which must be reduced to increase the profit of the operation.
The existing system has 22 loggers, 13 mills and 2 hubs spread in and around
Louisiana and Mississippi. Figure 3.1 shows the distribution of loggers and mills on the
map. The balloon shaped lettered ones are the mills and the flag shaped numbered ones
are the loggers. The loads are required to be transported from the loggers and delivered to
the mills. The trucking company own about 68 trucks that carry the loads and meet the
demand in any particular day. The main problem with this system is that trucks always
serve a particular closed set of loggers and mills. For example, a truck will serve the
loads only between logger 1 and mills 1, 2 & 3 and never really serves the loads between
remaining loggers and mills.
21
Figure 3.1: Location of loggers and mills in the map.
As a result, some trucks which have fairly fewer loads to meet remain idle most of
the time, whereas other trucks which should transport more loads take extra time and
travel much longer distances in order to meet the loads and with more unloaded miles and
improper resource utilization.
The route optimization is done for all the trucks under pooled transport system to
bring an optimal solution thereby reducing the unloaded miles and avoiding excess time
by properly utilizing the trucking resources. The trucks always start from the hub and end
the day at the hub. In the existing system, though the average ending time is 7 hours, the
highest ending time of all the trucks is 18.5 hours, indicating high variance. Maximum
number of trips allowed is 7 which is very high. The truck drivers are paid for overtime
Headquarters
(Hub)
Loggers
Mills
22
hours exceeding the normal shift duration. The trucks were found to be spending more
time waiting at logger and mill sites.
Our main objective is to reduce the cost associated with the existing system. The
costs are incurred in the form of more unloaded miles, excess time taken to meet the
demand and in usage of more trucks than needed.
A truck should always start from the hub and end the day at the hub. The truck
can be either loaded or unloaded depending on the ending status of the truck on the
previous day. Due to the shift duration of 8 hours, the truck may end the previous day as
loaded. Hence it should start the following day as loaded and move towards the mill as
the first destination to deliver the load. Then the truck visits the logger to load the truck
and the cycle continues thereafter. Most of the trucks start the day as unloaded. The
unloaded trucks would have delivered the load at the mill before returning to the hub on
the previous day and would proceed first to a logger to be loaded. Then the truck moves
on to the mill and the cycle continues.
The maximum number of trips is restricted to five to account for the time window
of the driver?s shift hours, and the starting time and the closing time at the loggers and
mills. This would allow for all the trucks to be utilized efficiently for the full time of
operation.
The shift duration is restricted to 8 hours so that the drivers return to the hub in
time and the cranes at the logger and mill sites can finish the operations well within the
time window. The truck is always fully loaded at the logger. Hence there is no chance to
load for the second time before unloading the current load. The speed of the truck is
23
limited to 50 miles/hour. The truck can choose any mill as its destination starting from
the logger provided there is an unmet load requirement between the selected pair of the
mill and logger.
In a single trip, a truck can visit one logger and a mill at a time. After delivering
the loads in the mill, it can then choose to load at any logger provided there are loads to
be carried from that particular logger to any mill. The total number of loads delivered
between the logger and mills should be exactly equal to the load requirement between the
loggers and mills at the end of the day. In short, there should be no unmet loads or over
served loads.
It is assumed that all the trucks have to return to the hub at the end of the day.
There are 2 hubs located very close to each other. In this problem 2 hubs are combined
into one since the distance separating them is less than 2 miles.
The trucks are loaded and unloaded at the customer locations based on first in first
out servicing. The truck has to follow a queue if there is one at the logger and mill before
getting access to the logger or mill. The waiting time of trucks in queue is unwanted and
must be minimized or eliminated completely so that the truck?s time can be better utilized
in transporting logs from the loggers to the mills.
The mills may need several different types of wood from the loggers. Trucks are
required to deliver those specific types of wood to the mills. This is actually taken into
consideration when drawing up a demand matrix which addresses the number of loads of
different types of wood that are to be transported to the mill. The size of the truck is
sufficient to transport all types of wood between a logger and a mill.
24
The trucks are assumed to be homogeneous and can have access to any logger and
mill irrespective of the location of loggers and mills in the region. This assumption
breaks the restriction imposed on the traditional management system which is more
inclined to operate the trucks between a particular set of loggers and mills.
Figure 3.2: Tracking data given by the company.
The trucking company provided the data which contains the movement of the
trucks from the loggers to the mills in a single day for all the 68 trucks as shown in figure
3.2. The truck?s movement is tracked by the satellite through the GPS equipment
provided with all the trucks. Whenever a truck stops in a particular place for more than 2
25
minutes, its position is recorded and posted to the Excel file. The data contains the
departure time, arrival time, travel time, waiting time and loading/unloading time at the
site. The statistics associated with this data will be very useful when we develop a
simulator and test it with a practical case to check for the output from the simulator. The
demand matrix and the distance matrix for the research were extracted from the given
data. The addresses of the loggers, mills and the hub were extracted and then located
precisely in a map using Google Earth software. After scanning through the tracking
information, it was found that the trucks were repeatedly operated between a particular
set of the loggers and the mills. Hence our main aim is to reduce the total unloaded miles
traveled by the truck by making the truck to serve all possible loggers and mills.
26
CHAPTER 4
PROPOSED APPROACHES
In a pooled transport system, all the loggers and the mills are brought under the
centralized leadership of a single owner. The owner plans and schedules the movement of
the trucks to meet the demand on any given day. The network consists of a hub, a series
of loggers and the mills distributed near the hub. The loggers are the locations where the
cut down trees are temporarily stored, and serve as the supply points of wood. The mills
require loads of wood for further processing and they form the demand points.
a) CUSTOMERS:
The loggers and mills are the customers for the trucks. They are located far away
from each other. Good planning is required to meet the transportation requirements
between them.
b) VEHICLE:
The vehicles used are the trucks. They visit the loggers and the mills by traveling
the shortest possible distances, and delivering the loads in the quickest time. The truck is
driven by a driver who takes the truck at the beginning of the shift, and leaves the truck in
the hub at the end of the shift.
27
c) ROUTING PLAN:
The routing plan consists of a set of routes assigned to all the trucks. Each truck
has to follow the route given to it in picking up and delivering the loads. The routes
should be designed in such a way that the truck travels a minimum of unloaded miles and
at the same time should meet all the loads at the end of the day.
d) TIME WINDOW:
The normal duration of a shift is 8 hours. The truck driver and the operators at the
logger and mill locations are required to work within the time window. Hence the loads
have to be delivered within this time window to all the loggers and the mills. This is
specifically done to overcome the labor costs associated with the overtime duty.
4.1 ASSUMPTIONS:
The locations of the loggers and mills are assumed to be vertices in a Euclidean
space. They can be represented by the x-distance and the y-distance in a two dimensional
space. The time taken to travel the distance between a logger and a mill is proportional to
the distance between that particular logger and the mill. All the trucks have to start from
the hub and should return to the hub at the end of the day. There is no parking space near
the customer?s site. For the ease of the routing and management of the trucks, the trucks
will end the day in the hub.
Any truck can serve any customer and a customer can be served by more than one
truck on any day depending on the load requirement for that customer. The customer can
have one or more demands for the load or may require more loads to be delivered to other
28
customers. All the trucks are assumed to have an identical capacity. The trucks always
travel between the customer locations as fully loaded or as empty.
Two approaches were actually followed to solve the problem. They are
1. Integer programming approach
2. Simulated annealing approach
4.2 INTEGER PROGRAMMING APPROACH:
The integer programming approach is used to find an optimal solution to the
problem. It is very useful to solve small size problems.
4.2.1 FORMULATION:
It is necessary to understand the terms used and their representation in order to
understand the formulation of the objective function and their constraints.
NOMENCLATURE
T - Number of trucks
M - Number of mills
L - Number of loggers
N - Number of trips
I - Denotes truck i (i=1,?, T)
m - Denotes mill m (m=1,?, M)
l - Denotes logger l (l=1,?, L)
j - Denotes trip j (j=1,?, N)
Lilmj - Equal to one when truck ?i? goes from the logger ?l? to mill ?m? during trip ?j?
Uilmj - Equal to one when truck ?i? goes from the mill ?m? to logger ?l? during trip ?j?
29
Dlm - Distance between logger ?l? and mill ?m?.
Slm - Load requirement between logger ?l? and mill ?m?.
1) Objective formulation:
The main aim of the objective function is to reduce the total unloaded miles
traveled by the truck. It can be formulated as
Min Z = ????
= = = =
T
i
L
l
M
m
N
j
lmilmj DU
1 1 1 1
2) Constraint formulation:
There are basically six constraints which define the problem space and should
not be violated in solving the problem.
a) On any single trip, the truck can travel to the mill only once.
? ?
= =
?
T
l
M
m
ilmjL
1 1
1 for all i=1?T and j=1?N
b) On any single trip, the truck can travel to the logger only once.
? ?
= =
?
L
l
M
m
ilmjU
1 1
1 for all i=1?T and j=1?N
c) The truck can travel from a logger to any mill independent of the mill
where it is coming from.
? ?
= =
?
L
k
L
k
ikmjimkj LU
1 1
for all i=1?T, l=1?L, m=1?..M and j=1?N
30
d) The truck can travel from a mill to any logger independent of the logger
where it is coming from.
??
==
+ ?
M
k
iklj
M
k
jilk UL
11
)1( for all i=1?.T, l=1?L and j=1?..(N-1)
e) The number of loads transported by all the trucks between a logger ?l? and
mill ?m? must be equal to the load requirement between a logger ?l? and
mill ?m? during the optimization period.
??
= =
=
T
i
N
j
lmimlj SL
1 1
for all l=1?L, m=1?.M.
f) The average speed of the trucks is calculated as 50 mph. Therefore, since
there is a shift duration of 8 hours, the truck can cover a maximum
distance of 360 miles with the average speed.
???
= = =
?+
L
l
M
m
N
j
lmilmjilmj dUL
1 1 1
400)( for all i=1?.T
g) Lilmj and Uimlj are the binary variables (0,1)
The formulation of the objective function and the constraints is with reference to
McDonald et al. [14].
The hub is neither a logger nor a mill. It is just a parking place for all the trucks.
All the loggers and the mills are located at a particular distance from the hub. The
distance between all the loggers and the mills is fixed and is taken as input to the
problem. Also the distances between the hub and the customer locations are known.
31
On a particular day, the loads that are to be transported between the loggers and
mills are fixed. The routes are to be designed in such a way that all the required loads are
transported between the loggers and the mills.
The trucks should be utilized to the maximum extent possible. The routing must
be designed in such a way as to reduce the number of trucks used. Fewer trucks with high
utilization is better than more trucks with low utilization. Also the total distance traveled
by all the trucks should be minimized. This happens only when we can reduce the total
unloaded miles since the total loaded miles is fixed. The routing plan consists of
assigning a predecessor and a successor to each customer location in the truck?s route.
4.2.2 DEMERITS OF INTEGER PROGRAMMING:
Integer programming is mainly used to solve small problems within a reasonable
time. In the case of large problems, the time taken to solve the problem increases
exponentially with the size of the problem. Consequently, it takes days to solve the truck
routing problem which is prohibitive for the industrial people. The people working in the
industry need solutions not necessarily an optimum one but are happy to have a solution
very close to the optimum value within a short time. The solutions obtained using the
meta-heuristics like the simulated annealing algorithm are very close to the optimum
value and can be found within a short time period of 5 minutes. Hence the truck routing
problem is solved using the simulated annealing approach.
4.3 SIMULATED ANNEALING APPROACH:
Simulated annealing (S.A) is a meta-heuristic algorithm which is used to solve
complex large problems having a large solution space producing results close to the
32
global optimum value in a short period of time. The heuristic is inspired by nature and is
derived from statistical mechanics. The simulated annealing algorithm was first invented
by Metropolis et al. in 1953 to generalize the Monte Carlo method to determine the
equations of state and also to determine frozen states of the n-body systems. In the later
part of the 20th century, the concept of simulated annealing was put forward
independently by S. Kirkpatrick, C. D. Gellat and M.P Vecchi in 1983 and also by
V.Cerny in 1985. A detailed explanation can be found in Reeves (1995).
The simulated annealing algorithm is generally used to solve combinatorial
optimization problems. The term annealing is associated with the heat treatment of solids.
The solids are initially heated to a high temperature and then it is allowed to cool down
slowly in order to impart hardness to the solid. As the solid is heated, the atoms are
dislodged from their positions and allowed to roam freely inside the solid. During the
cooling process, the solid is allowed to stay at that state for a sufficient amount of time at
all temperatures. Hence this allows the atoms to move around freely and occupy a
comfortable position. When the atoms are free to occupy any position inside the solid,
then that solid achieves its maximum hardness. Finally when the solid is completely
cooled, the atoms stick to that position inside the solid which gives maximum hardness to
the solid.
The analogy between the annealing process used in heat treatment, and the
simulated annealing (S.A) algorithm used to solve combinatorial optimization problem is
best explained below. In S.A, the process starts at high temperature with an initial
solution. The temperature is decremented step by step, and at each temperature search is
33
done for a particular number of iterations. Here the number of iterations is similar to the
amount of time the solid is allowed to stay at that temperature. The best solution found so
far is close to the optimal solution and is compared to the best configuration that the
atoms can take in the solid which gives maximum hardness to the solid. The solid state at
each temperature is similar to the feasible solution that is obtained at each temperature
step.
The objective is to reach the global optimum value in the case of the simulated
annealing algorithm whereas it is to reach a solid state with maximum energy in the case
of the heat treatment. Rapid quenching is synonymous with the local optimization.
The S.A. algorithm consists of the following steps:
STEP 1: An initial solution is generated using the construction heuristics. The algorithm
starts by fixing the temperature T=Initial temperature. To start with, the initial
solution is accepted as the best solution.
STEP2: The solution?s neighborhood is searched using the different search operators in
the improvement heuristics.
STEP 3: The new solution is fed as an input to the simulator to get the performance
measures and the value of the fitness function is calculated using these
measures.
STEP 4: Depending on the value of the fitness function, the new solution is adopted as a
better solution. Even if the newly obtained solution is bad, it is still accepted
with a probability which depends on the current temperature and the difference
34
in fitness function between the bad solution and the previously accepted
solution.
STEP 5: The best solution obtained so far is kept in memory and is compared with the
new solution. If the new solution is better than the best solution obtained so far,
then the new solution is adopted as the best solution.
STEP 6: The value of the temperature is decremented by a small step. The value of the
temperature is checked against final temperature for it has reached its final
value. If not, then go to STEP 2 and the steps from 2 to 6 are repeated.
STEP 7: When the final temperature is reached, the best possible solution is obtained
which is very close to the optimal solution.
4.3.1 SIMULATED ANNEALING IMPLEMENTATION:
The simulated annealing algorithm consists of two main heuristics. An initial
solution is first generated using the construction heuristics and then improved further
using the improvement heuristics to obtain a best possible solution.
The parameters for the simulated annealing process for our system are as follows
a) Initial temperature = 100
b) Number of searches = 2000
c) Decrementing factor (alpha) = 0.9
d) Final Temperature (beta) = 0.1
4.3.2 CONSTRUCTION HEURISTICS:
The construction heuristics involve random filling of the routes of the
trucks with the loggers and the mills. The number of loggers, mills, trucks and the
35
maximum number of trips are well known. There are two kinds of trucks: the loaded and
the unloaded trucks. The loaded trucks always start the day by going towards the mill and
unloaded trucks start the day by visiting a logger. Hence the first trip should always be a
mill for a loaded truck and it should be a logger for an unloaded truck. Once a truck
visits a logger, it would then visit the mill and then logger and so on. The loggers and the
mills repeat each other alternately one after the other in the route of the truck.
Figure 4.1 contains the pseudo code for the simulated annealing meta heuristic
algorithm. There are two types of matrices, namely the route logger matrix and the route
mill matrix with the number of rows equal to the number of trucks and the number of
columns equal to the maximum number of the trips. The route logger matrix and the route
mill matrix collectively form the routes of all the trucks, the initial solution to start the
algorithm. The route logger matrix is filled by the uniform random sampling of the
loggers, and similarly the route mill matrix is filled by the uniform random sampling of
the mills for each truck. The last trip of the trucks is filled with the hub since all the
trucks should return to the hub at the end of the day.
36
For the loaded trucks, there is a restriction that the truck should move to a
particular mill depending on the truck ID and the destination of the carrying load.
Pseudo code for simulated annealing
1. Get the number of loggers, mills, trucks, demand matrix and the distance matrix as input
2. Initialize the starting temperature, final temperature, steps of temperature decrements and
number of searches at each temperature step
3. Generate a set of routes as the initial solution
4. Lowest search=Best solution=Next solution=Initial solution.
5. Temperature=Initial temperature
6. While(Temperature > Final temperature) then do
7. For Search = 1 to No. of searches
a. Run simulator with the initial set of routes and generate the unserved loads,
overserved loads and the total unloaded miles
/*Generating feasibility using construction heuristics*/
b. If (Unserved loads!=0) then
i. If (Overserved loads>0), generate a new solution by decreasing the route
length
Else if (Unserved loads>0), generate a new solution by increasing the route
length
c. If (Unserved loads= = 0) && (Overserved loads! = 0), generate new solution by
decreasing route length
d. If [(Unserved loads==0)&&(Overserved loads= =0)&&(Trucks that have not
completed the trips>0), generate new solution by abruptly stopping a random truck
/*Improving the feasible solution towards optimal solution using the improvement
heuristics*/
e. If (Unserved loads == 0 && Overserved loads = = 0)
i. If (0< Rand () <0.7, generate a new solution by interchanging the trips
between trucks
ii. If (0.7 0, then the new solution is adopted as the lowest search solution
Even if ? < 0, the new solution is adopted as the lowest search solution with a probability
that depends on the current temperature and the difference in the fitness value (?).
4.3.4 CONDITION FOR ACCEPTING A BAD SOLUTION:
The condition for accepting a bad solution is given by
Random (0, 1) < (T+ ?)/T
If the above condition is not satisfied, then the bad solution is rejected and the
current solution is adopted as the lowest search. Meanwhile the solution with lowest
fitness found so far is kept in memory as the best solution. Every time a new solution is
found, its fitness value is compared with that of the best solution apart from comparing it
with the lowest search fitness. At each temperature, the neighborhood is searched for a
fixed number of iterations to get the new solution.
Best solution - Solution which has the lowest fitness all through the
annealing process
Lowest search - Current solution whose neighborhood is searched for
improvement
46
New solution - The solution found in the neighborhood of the lowest search
by applying the search operator to the lowest search solution.
After searching the neighborhood for a fixed number of iterations, the temperature
is decremented by multiplying the temperature with a factor ?. The factor ? is fixed and
remains constant throughout the process. The above process is repeated until the
temperature reaches the final temperature value. During the initial few steps of the
temperature, simulated annealing does not get stuck to the local optima and moves freely
around all neighborhoods to get a good solution. As the temperature reaches the end, the
solution gets stuck in the local optima.
At the end of the annealing process, the best solution found is printed out. It
contains the best set of routes that the trucks should take in order to deliver the loads with
fewer unloaded miles, less waiting time and less time duration to complete the trips. The
best solution obtained is very close to the global optimum solution. The time taken to find
a good solution is less than 1 min when simulated annealing is used whereas it takes days
to find a good solution using a standard solver.
The set of routes is then given as an input to the simulator along with the
description of the problem. The simulator emulates the movement of the trucks and
outputs all the performance metrics such as total unloaded miles, total waiting time, total
time duration to complete the trips. These performance metrics are used to calculate the
value of the fitness function for that solution.
In the beginning, a small problem is tried using integer programming. The
constraints of the problem are mathematically modeled and the objective function is
47
formulated. It is then solved using the branch and bound algorithm programmed using
Excel software. The results are tabulated and value of the objective function is noted. The
small problem is described as follows.
4.4 DESCRIPTION OF THE SMALL PROBLEM:
T- Number of trucks = 4
M-Number of mills = 2
L-Number of loggers = 3
N-Number of trips = 4
Distance Matrix = {70, 67,
65, 76,
45, 51}
Demand Matrix = {1, 2,
2, 3,
2, 1}
In this problem, all the trucks are unloaded and our objective is to minimize the
total unloaded miles traveled by all the trucks.
4.4.1 SOLUTION USING INTEGER PROGRAMMING MODEL:
The above description of the number of trucks, trips, mills and loggers are fed as
an input to the programming model. Also the demand matrix and the distance matrix are
defined into the system. The model is solved using the branch and bound algorithm and
gives the set of routes for all the trucks and the total unloaded miles as its output as
shown in Table 4.1
48
Table 4.1: Solution using integer programming approach.
Total unloaded miles = 399
4.4.2 SOLUTION USING SIMULATED ANNEALING ALGORITHM:
The above problem is now solved using simulated annealing heuristic algorithm
and the results are compared for the degree of closeness of the heuristic method with that
of the integer programming model. The simulated annealing algorithm is integrated with
the simulator. Hence the best set of routes found using the algorithm is given as an input
to the simulator to find the total unloaded miles traveled by the truck as shown in table
4.2. It is found that the value of the objective function is same for the two models. The
total unloaded miles found using simulated annealing algorithm is 399 miles and it
matched exactly with that obtained using the integer programming model.
Table 4.2: Solution using simulated annealing approach.
Truck No. Logger Mill Logger Mill Logger Mill Logger Mill
Truck 1 2 1 2 2 1 2 Hub Hub
Truck 2 1 1 1 2 2 2 Hub Hub
Truck 3 2 2 1 2 Hub Hub Hub Hub
Truck 4 2 1 3 1 3 1 Hub Hub
Total Unloaded Miles =399
By comparing the two solutions obtained using the integer programming model
and the simulated annealing algorithm, it can be found that though the value of the
Truck No. Logger Mill Logger Mill Logger Mill Logger Mill
Truck 1 2 2 1 2 Hub Hub Hub Hub
Truck 2 2 1 3 1 3 2 Hub Hub
Truck 3 2 1 2 2 1 2 Hub Hub
Truck 4 1 1 3 1 2 2 Hub Hub
49
objective function is the same, the set of routes for the trucks is different. The problem
contains more than one optimal solution.
In the case of small problems, the solution is obtained within a fraction of a
second using the heuristics algorithm and obtained in less than 5 seconds using the
branch and bound algorithm in the integer programming model. But in the case of large
problems, it is possible to obtain the solution within 1 min using S.A. whereas it takes
hours to solve using the standard algorithms available with integer programming model.
50
CHAPTER 5
DETERMINISTIC SIMULATOR
A simulator collects information regarding a truck?s routing based on the input
given to it. It is a program which emulates the movement of trucks during the day. The
simulator keeps track of all the performance metrics as the truck takes its route through
hub, loggers and mills. The simulation carried out here is deterministic since the events
are derived from the routes of the trucks which are known already and given as input.
5.1 BASIC MODEL OF SIMULATOR:
Figure 5.1: Basic model of a simulator.
SIMULATOR
(DISCRETE
EVENT
SIMULATION)
No. of Trucks, Loggers
and Mills
Distance
Load
Routes of all
Trucks
Total Unloaded Miles
Total Unserved Loads
Total Waiting Time
INPUT OUTPUT
51
Figure 5.1 above shows the basic model of the simulator. The total number of
trucks used and number of loggers and mills are fed to the simulator as standard input
along with the distance matrix and load requirement matrix. Also the routes followed by
each truck on any given day should be entered into the simulator. The simulator emulates
the movement of the trucks according to the routes given and gives the output in the form
of total unloaded miles of the truck, total unserved loads and total waiting time of all the
trucks in the various customer locations. For example, any truck?s route can be defined as
follows,
The truck starting from the hub goes to a series of customer locations like logger
1, mill 2, logger 3, and mill 1 and finally ends the day by returning to the hub. The
simulator keeps track of the total unloaded miles as the truck moves from mill to logger.
Similarly whenever the truck proceeds from logger to mill, the total loaded miles is
incremented by the distance between the logger and mill. So at the end of the day, after
emulating the movement of the trucks, statistics of total loaded miles and total unloaded
miles are obtained. The mills and loggers are the customers for the trucks. The cranes are
the servers at the customer locations. The working of a simulator is shown using a truck?s
route in figure 5.2.
Truck 2 = {1, 3
2, 1}
52
Figure 5.2: A simulator following a truck?s route.
Whenever there is a queue at the customer location, the truck has to wait before
getting served by the cranes at logger and mill locations. Hence the total waiting time is
calculated as the sum of the waiting times of all the individual trucks at all customer
locations.
STARTING POINT
(HUB)
Unloaded Miles
LOGGER 1
MILL 2
LOGGER 3
MILL 1
ENDING POINT
(HUB)
(Loading Event)
(Unloading Event)
Unloaded Miles
Unloaded Miles
(Load delivered to mill 1
from logger 3)
53
The truck delivers the loads from the logger to the mill. As the loads are
delivered, the served load matrix is incremented by one every time. At last, the served
load matrix is compared with the load requirement matrix. The total difference between
the load requirement matrix and the served load matrix gives the unserved loads at the
end of the day.
5.2 INITIALIZATION OF PERFORMANCE PARAMETERS:
All the statistics are initialized to zero during the beginning of the simulation. The
trucks can start the day as loaded or unloaded which depends on the previous day?s
ending condition. Hence the starting condition of the trucks is given as an input in the
beginning.
Discrete event simulation is used to emulate the movement of trucks. The
departure and arrival from hub, mill and logger are considered as events. The events are
enlisted in the main linked list according to the time at which the event must be emulated.
There is time associated with the loading and unloading event. The simulator will first
enlist an initial set of events in the list at time zero and starts executing it one by one. The
clock is incremented by the time duration of the event taking place.
At times, the server may be busy serving the truck that has already arrived. The
new trucks which have just arrived should be put in the queue. Hence a separate queuing
list is created to keep track of the trucks waiting in the queue. Also the status of the server
is changed from busy to idle whenever a truck leaves a customer location. First in first
out (FIFO) strategy is implemented during the queuing process.
54
The time of the event that is executed currently is adopted as the current updated
time. Since the events are inserted in the list along with the time at which they are
executed, it becomes easier to adopt an event?s execution time as the current time. The
main list and queuing lists are filled with null character to indicate the end of the list. The
servers at the logger and mill locations are set to idle status in the beginning with no
queue in front of them.
5.3 SIMULATION OF THE EVENTS:
hub
Departure from processLoading LoggerArrival to LoggerRelease
process
UnloadingArrival to Mill Release Mill Arrival to hub
0
0
Figure 5.3: Schematic diagram of the simulator.
The simulation starts at time zero. At that time the served load matrix between the
loggers and mills is set to zero. The total distance traveled, loaded miles and unloaded
miles are set to zero in the beginning. An event namely an arrival or a departure event
consists of truck number, logger number, mill number, trip number and the time. For all
the trucks, the first event is the departure of the truck from the hub.
The next destination for any truck is obtained from the set of routes given as the
input. A schematic diagram of the simulator is shown in figure 5.3. The destination may
be a logger if the truck is an unloaded truck and would be a mill if the truck is loaded.
The destination along with the arrival time and truck number is inserted as an arrival
55
event in the main event list. Arrival time at the destination is calculated based on the
current time plus the traveling time calculated based on the distance between the hub and
the destination divided by the speed.
At time zero, all the trucks are dispatched to the corresponding destinations. As
soon as the truck reaches a logger or a mill, the status of the server at the destination is
checked for idleness. In the beginning of the day, the servers will be idle until a truck
approaches it for service. The first truck to reach the destination gets direct access to the
Pseudo code for simulator:
1. Feed the set of the routes and the simulation end time as input to the simulator
2. Initialize all the parameters including unloaded miles to zero
3. Execute the departure event of the trucks from the hub based on the destination
4. while [TNOW(Current time) < Simulation end time] do
a. Route the loaded trucks to the mills
b. Route the unloaded trucks to the loggers
c. Update the TNOW and distance traveled as the trucks reach the loggers and the
mills
d. If [server at logger (mill) = = Busy], wait in the queue. Queue++
e. Else access the server and set server = Busy
f. Update TNOW for the loading and the unloaded process.
g. Release the server and set server = Idle. Queue- -
5. Repeat the loop by updating unloaded miles as the trucks travel according to the set of the
routes and until TNOW = = Simulation end time
6. Print out the total unloaded miles, total time taken, total waiting time for all the trucks for
the given set of routes as input
Figure 5.4: Pseudo code for working of simulator.
56
server without waiting in the queue and is served immediately with a service time of 6
min for loading or unloading process. When the truck is being served by the server, the
status of the server is set to busy. All the other trucks which arrive when the server is
busy will be put in a queue based on a first in first out (FIFO) strategy.
The queuing time is the difference between the time at which the server starts
serving the truck and the time at which the truck arrives at the location. The simulator
sums up the waiting time of all the trucks in the system throughout the day.
The status of the server will be switched back to idle after serving a truck. The
first truck from the queue is pulled up from the queuing event list and will be served
changing the status of the server to busy again. This process is repeated throughout the
day. There is time associated with the loading and the unloading process both at the
logger and the mill locations. The duration of the loading and unloading process are
assumed to be fixed.
The arrival time is incremented by the sum of the waiting time and the service
time and inserted as an event for the release of the server to serve other trucks. Upon
releasing the server, the next destination for the truck is inserted as an event along with
the time the truck takes to reach the destination. The loaded miles are updated when the
truck reaches the mill, and similarly, the unloaded miles are updated when the truck
reaches the logger.
While releasing the server, the trip is incremented by one when the truck has
visited an equal number of the loggers and the mills. Depending on the distance traveled,
the trucks may vary in the number of trips taken to cover the distance. During the last trip
57
of all the trucks, the trucks should be forced to return to the hub. Hence the last
destination for all the trucks is the hub. The destination is checked every time the truck
arrives to a mill or a logger. If the destination is the hub, the truck?s movement is stopped
and all the statistics like the miles traveled and the waiting time are calculated for that
particular truck.
The simulation end time, the time until which the simulation should be executed,
is given as an input in the beginning. As soon as the current time reaches the simulation
end time, the simulation is stopped and all the remaining events are listed out. If there are
no events remaining, it indicates that the trucks have completed all the trips in the route
assigned to it. On the other hand, if there are any events remaining, it means that the
trucks take more time to serve the loads. At last, all the statistics namely the unmet loads,
total loaded miles, total unloaded miles and the total waiting time are printed out.
5.4 ADVANTAGES AND USES OF THE SIMULATOR:
The simulator is a useful tool to track the movement of any single truck
throughout its route as it moves from a logger to a mill and vice versa. Given any single
truck?s ID as input, the simulator prints out the sequence of events the truck is following
along with the time spent at various locations.
The potential of the simulator lies in the successful execution of the events in the
main event list, thereby tracking the movement of the trucks from one location along with
the simultaneous collection of the distance related and the time related statistics.
The output from the simulator is analyzed to find the proportion of the total
loaded miles to the total miles traveled. A good set of routes always results in the total
58
loaded miles greater than the total unloaded miles. Also, the total time wasted by all the
trucks in queuing is calculated by the simulator. These statistics are used as a mode of
comparison with the statistics obtained using a different set of routes.
Apart from the regular output of statistics, the simulator also gives information
about the trucks which take more time to complete the trips than the simulation end time.
For each truck, there is an end time at which it reaches the hub after serving all the loads.
The end time for all the trucks is given as an output with which we can sort out the trucks
which take more time to complete the trips apart from the trucks which takes less time to
complete the trips.
Even if a different set of the routes is given as an input, the simulator recalculates
the statistics and gives a different output. Hence the simulator can be used any number of
times to calculate the statistics for any set of input given to it. A fitness function is
defined at the end of simulation which allocates a penalty to each unloaded mile, each
unmet load and each hour of waiting time and calculates a value corresponding to the set
of routes given as an input. The value of the fitness function determines the efficiency of
the set of the routes.
The main advantage of the simulator is that it is very fast and returns the output
within a fraction of a second. Also it is very robust and can be used to simulate routes
consisting of a large number of trucks, trips and the customer locations.
59
CHAPTER 6
EXPERIMENTAL RESULTS OF ACTUAL SYSTEM
The existing log truck transportation in the states of Louisiana and Mississippi
states is quite big compared to the known problem discussed while comparing the
efficiency of the simulated annealing algorithm with that of the integer program. The data
regarding the existing system is provided by the Department of Forestry in an Excel file.
The recording system tracks the movement of the trucks as they move between the hub,
loggers and mills and records the data along with the duration of the stoppage, distance
traveled, time taken, loading time and the unloading time etc.
The data is well analyzed to find the load requirement matrix, distance matrix
between loggers and mills. Also the number of trucks, loggers, mills and trips are
extracted along with the set of routes taken by each truck during the delivery of the load
all through the day. The set of routes is then fed to the simulator to get the total unloaded
miles, total waiting time, total time duration to serve the loads etc. It is necessary to
obtain these performance metrics to evaluate the fitness function and also to compare it
with the performance metrics of the improved system. The problem can be described as
follows.
6.1 DESCRIPTION OF THE ACTUAL PROBLEM:
T- Number of trucks = 68
M-Number of mills = 13
60
L-Number of loggers = 22
N-Number of trips = 7
Loaded trucks = 10
Unloaded trucks = 58
The number of trips taken to deliver the loads is found to be seven for the existing
system but in order to complete the trips within an 8 hour time duration, the number of
trips is reduced to five to get a better solution.
The above parameters along with the demand matrix and distance matrix are
given as an input to the simulated annealing program to get the best set of routes that can
be followed by the trucks in delivering the loads. The output from the simulated
annealing algorithm combined with the simulator is compared against the performance
metrics in the existing system.
6.2 FINISHING TIME OF TRUCKS:
The finishing time of trucks is an efficient metric to analyze the utilization of the
trucks. Also it is an estimate to find whether all the trucks have finished within the time
window of 8 hours.
61
Figure 6.1: Finishing time of trucks in the existing system.
The figure 6.1 shows the finishing time of trucks in the existing system obtained
from simulator by giving the current set of routes as input. The mean finishing time of
trucks is 7.21 hours with standard deviation of 3.61 hours. It is observed that the last
truck goes to the hub only after 18 hours. There are about 34 trucks which take more than
8 hours to deliver the loads. Also there are about 7 trucks which are not used to deliver
the loads.
It can be understood that the existing system is very inefficient since it takes more
time than the shift duration to deliver the loads; therefore, drivers, crane operators at the
loggers and mills have to be paid more. All the trucks are not utilized properly. Some of
the trucks are underutilized and some are over utilized.
62
Figure 6.2: Comparison of finishing time of trucks between
real data and the best solution.
The figure 6.2 shows the ending time of trucks in the improved solution and in the
real data. From the figure it is evident that all the trucks finish the job within 8 hours
when compared to the ending time of 19 hours for trucks in the existing system from real
data. The mean finishing time of trucks is 5.76 hours with standard deviation of 2.28
hours. The standard deviation is very small when compared to the existing system and the
majority of the trucks are effectively utilized. But there are still 28 trucks finishing the
day within 6 hours but 5 trucks are not used for the day to serve the loads and stay at the
hub throughout the day.
6.3 IMPROVEMENT IN PERFORMANCE METRICS:
The first and foremost aim is to reduce the unloaded miles traveled by all the
trucks. Also the trucks should deliver all the loads within the time duration of 8 hours
63
with less waiting time at the logger and mill locations. It is necessary to compare the
performance metrics of the existing system with that of the best solution obtained using
simulated annealing to calculate the improvement percentage.
Table 6.1: Improvement in performance metrics.
Existing system Optimal system Improvement (%)
Total Miles 20630 17127 17.00
Loaded Miles 10028 9509 5.17
Unloaded Miles 10602 7618 28.14
% Loaded Miles(L.M/T.M) 48.60 55.54 14.28
% Unloaded Miles 51.39 44.48 13.72
Total Waiting time (hours) 21.00 13.88 33.90
a) TOTAL DISTANCE TRAVELED:
It is found that the total distance traveled by the trucks is reduced from 20,630
miles to 17,127 miles. The percentage of improvement is 17%. Since the total distance
traveled is reduced, the trucks are able to meet the schedule within the 8 hour duration. It
saves overtime pay for the truck owners, logger owners and mill owners.
b) LOADED MILES TRAVELED:
The loaded miles in the existing system is 10,028 miles which was improved by
5.17% to 9,509 miles in the newly found best solution using S.A. There is almost no
scope for improvement in loaded miles since fixed loads are to be delivered between
source logger and destination mill and the trucks follow the same route in delivering the
loads. The small difference in improvement of loaded miles is due to the fact that there is
64
a difference in the number of trucks that end the day as loaded in the hub. There are many
fewer trucks than in the existing system which end the day as loaded. Hence there is a
small improvement in the loaded miles percentage.
c) UNLOADED MILES TRAVELED:
A truck is said to record unloaded miles when it is traveling from a mill to the
logger. There is ample scope for improving the unloaded miles since the truck can always
go to the logger nearest to the previous mill visited so that it can reduce the total
unloaded distance traveled. The improvement heuristic plays an important role in
improving the solution by reducing the unloaded miles. The solution has shown a
tremendous improvement by reducing the total unloaded miles from 10,602 to 7,618 with
an improvement percentage of 28.14%. By reducing the total unloaded miles traveled by
the trucks, fuel cost is saved and moreover the time wasted in traveling unnecessary
unloaded miles is reduced.
d) RATIO OF LOADED MILES TO TOTAL MILES:
The ratio of loaded miles to total miles is known as loaded miles percentage. This
is an industry standard to measure the efficiency of the proposed system. The loaded
miles percentage improved from 49% to 56% showing an improvement of 14.28%. It is
considered to be a poor model whenever the loaded miles percentage is less than 50%.
Since in the solution obtained, the loaded miles percentage is 56%, it is said to be a good
model.
65
e) TOTAL WAITING TIME:
The total waiting time of all the trucks is reduced from 21 hours to 13.88 hours. In
other words, on an average the waiting time of trucks has been reduced from 18.53
minutes per truck to 12.25 minutes per truck with the percentage of improvement being
34%.
Table 6.2: Average waiting time at logger locations.
Logger No. Total Number of loads Average Waiting Time (min)
1 6 10.00
2 7 1.37
3 11 0.00
4 14 10.71
5 5 0.00
6 3 0.00
7 7 4.29
8 9 4.00
9 5 0.00
10 12 0.50
11 2 0.00
12 18 9.00
13 13 3.97
14 2 0.00
15 1 0.00
16 13 6.92
17 3 0.00
18 6 0.00
19 15 0.00
20 14 4.54
21 3 2.00
22 3 6.00
66
The average waiting time of trucks at each logger location is given in Table 6.2.
The trucks have to wait more at logger 4, where the average waiting time is 10.71
minutes since the logger 4 has 14 loads associated with it. Though there are only 6 loads
supplied from the logger 1, the truck has to wait for 10 minutes on an average to get
loaded. Trucks arrive at regular intervals at logger 19 and hence there is no waiting time
even though there are 15 loads to be supplied from the logger.
Table 6.3: Average waiting time at mill locations.
Mill No. Total No. of loads Average Waiting Time (min)
1 15 2.40
2 38 3.36
3 38 8.80
4 4 0.48
5 23 1.36
6 6 0.32
7 39 6.80
8 0 0.00
9 5 0.40
10 2 0.00
11 1 0.00
12 1 0.00
13 0 0.00
The average waiting time at each mill location is shown in Table 6.3. Unlike the
waiting times at logger locations, the waiting time at mills are proportional to the number
of loads that are to be carried to the mills. The mills 3 and 7 have higher waiting times of
8.80 minutes and 6.80 minutes on an average since both the mills require a higher
number of nearly 38 loads to be delivered it. At the same time, the trucks arrive at equal
67
intervals to the mill 3 and hence we have a lower waiting time of 3.36 minutes on an
average.
68
CHAPTER 7
SENSITIVITY ANALYSIS
Sensitivity analysis is carried out to find the marginal effect of removing a truck,
the effect of the distribution of loggers and mills and also the effect of location of
individual logger and mill on the solution. Sensitivity analysis is done to find ways to
reduce the cost associated with the operation and management of the log truck and
thereby increasing the profit to the truck owners. It also helps in better designing of the
locations of loggers and mills to meet the demand with less cost and time in the future.
7.1 REDUCTION OF TRUCKS:
There is huge savings associated with the reduction of trucks in the form of
maintenance and rental savings per day for trucks not used and also in the form of wages
for drivers.
The existing system consists of 68 trucks and looking into the best solution
obtained from S.A as shown in figure 7.1, it is evident that all trucks finish the routing
within 8 hours. Still there are 5 trucks which are not used to serve the loads. Also there
are 15 trucks which work for less than 5 hours to serve the loads. Hence there is scope to
reduce the number of trucks used and thereby to increase the utilization of the used
trucks. It is necessary to check the effect of the reduction of the trucks on the total time
taken to serve the loads, unloaded miles, time taken to find the optimal solution etc.
69
Figure 7.1: Finishing time of 68 trucks from the optimal solution.
Figure 7.2: Sensitivity analysis for reduction of trucks from 67 trucks to 62 trucks.
70
Figure 7.3: Sensitivity analysis for reduction of trucks from 62 trucks to 56 trucks.
The figures 7.2 and 7.3 show the sensitivity analysis for the reduction of trucks
from 67 to 56 trucks. It is observed from the graph that as the trucks are reduced from 67
to 56, the finishing time of trucks is more concentrated towards the maximum of 8 hours.
The higher the finishing time, maximum is the utilization of the trucks.
71
Figure 7.4: Finishing time of trucks for 68 trucks and 56 trucks.
When 56 trucks are used to serve the loads, it is found that no truck was left idle
and except for 2 trucks and almost all trucks are active more than 5.5 hours. The figure
7.4 shows the finishing time of 68 trucks and 56 trucks. The total time of 8 hours is
sufficient to meet the demand and there was no appreciable increase or decrease found in
the percentage of unloaded miles. But as the trucks are reduced, the simulated annealing
algorithm takes more time to find the solution for the problem.
72
Figure 7.5: Time taken to find the solution with reduction in number of trucks.
The time taken to find the solution is approximately 2 min for 68 trucks through
62 trucks. This can be clearly seen in figure 7.5. As the trucks are further reduced, the
relationship between the number of trucks and time taken to solve the problem was found
to be inversely proportional and linear. The solving time increased from 2 min to 15 min
for 56 trucks due to the fact that as the resources are reduced, the simulated annealing
algorithm is taking more time to find a solution to the problem.
73
Figure 7.6: Proportion of trucks with more than 80% utilization.
When the system was run with 68 trucks, half of the trucks were utilized for more
than 6.5 hours in 8 hours shift. This can be seen from the line of best fit plotted between
proportion of trucks with more than 80% utilization and number of trucks shown in the
figure 7.6. As the number of trucks is reduced, a larger proportion of trucks was utilized
for more than 6.5 hrs. When the system was finally reduced to 56 trucks, more than 70%
of the numbers of trucks were utilized for more than 6.5 hours.
74
7.2 SCENARIO ANALYSIS:
It is necessary to understand the distribution of loaded miles percentage in order
to find the expected value of loaded miles percentage. The percentage of loaded miles
varies with the geographical distribution of location of loggers, mill and hub. The
distribution of loaded miles percentage gives us an estimate of the minimum value of
loaded miles with a certain probability. The people working in the industry are more
interested to find that value which can ensure at least a basic profit margin for the
operating day.
Locations of all the loggers, mills and hub are marked on the map using Google
Earth and an imaginary smallest possible rectangle is drawn over them so that its
boundaries enclose the loggers, mills and the hub. The length and breadth of the
rectangle is converted into distance in miles. Now the sides of the rectangle form the x-
axis and y-axis for generating the locations of loggers and mills randomly. The length of
the x-axis is 139 miles and that of y-axis is 110 miles. The loggers, mills and hub are
located in a rectangular region by sampling the x-distance and y-distance.
A total of 175 scenarios are generated to extract the percentage of loaded miles
for each scenario. The figure 7.7 shows six sample scenarios of uniform distribution of
loggers, mills and hub. For each scenario, the loggers and mills are randomly located in
the rectangular region. The distance between the loggers and mills is found by using the
diagonal distance between the loggers and mills. For nearby locations, the diagonal
distance is directly taken as the shortest distance of travel. In case of farther locations, the
diagonal distance is multiplied by a factor up to 1.2 to obtain the shortest travel distance.
75
Figure 7.7: Six sample scenarios showing uniform distribution
of loggers, mills and hub.
The distance matrix is different for each scenario and hence it is generated and fed
each time to the simulated annealing algorithm. The simulated annealing algorithm tries
to find an optimal solution for the scenario and the simulator calculates the percentage of
loaded miles for the best solution generated by the simulated annealing algorithm. This
76
procedure is repeated for all the 175 scenarios and the percentage of loaded miles from
each scenario is plotted to get the distribution of the loaded miles percentage.
Figure 7.8: Histogram of loaded miles percentage for 175 scenarios.
The figure 7.8 shows the percentage of loaded miles for 175 scenarios. The mean
loaded miles percentage is 57% with standard deviation of 3.7% and variance of 0.001.
There were 4 scenarios where loaded miles were less than 50%.For these scenarios, the
loggers and mills were located far away from each other. The main reason for the low
percentage of loaded miles is that it spends most of the time in finding a feasible solution
rather than improving it. For those cases, the number of searches at each temperature is
increased so that the algorithm runs a little longer than 2 minutes to find a good solution.
77
Sample scenario (Loaded mile 46%)
0
20
40
60
80
100
120
0 20 40 60 80 100 120 140 160
LOGGER LOCATION MILL LOCATION HUB LOCATION
Figure 7.9: Sample scenario for loaded mile 46%.
The sample scenario where the model results in a low percentage of loaded miles
is shown in Figure 7.9. The possible reasons being that the hub is located at one end of
the rectangular region and also that the loggers are concentrated in the center of the
region. Most of the loggers and mills are located far away from the hub. Since the trucks
have to start the day from the hub, they travel more unloaded miles in reaching the logger
in the beginning of the day. Similarly, after delivering the last load to the mill, the trucks
have to travel more without carrying load to reach the hub.
78
Sample scenario (Loaded mile 66%)
0
20
40
60
80
100
120
0 20 40 60 80 100 120 140 160
LOGGER LOCATION MILL LOCATION HUB LOCATION
Figure 7.10: Sample scenario for loaded mile 66%.
The sample scenario where the model results in high percentage of loaded miles is
shown in Figure 7.10. Since the hub is located in the center of the region, the trucks travel
less unloaded miles in reaching the loggers from the hub in the beginning of the day.
Similarly during the end of the day, the trucks travel less unloaded miles from the mills to
the hub. Also, the loggers and mills are uniformly distributed over the whole region.
7.3 MARGINAL CONTRIBUTION OF LOGGERS AND MILLS:
The loggers, mills and the hub are located far away from each other. Each pair of
loggers and mills has its own set of demand and is different when compared to other
existing pair of loggers and mills. It is important to know the marginal contribution of
every logger and mill on the entire system.
The marginal contribution of all the loggers and mills is calculated by removing
one logger or one mill from the system every time. As the logger is removed from the
79
system, the demand matrix and distance matrix is updated to reflect the changes in the
system. This new system is now fed to the simulated annealing algorithm to find the best
possible set of routes for the trucks and the total unloaded miles.
The marginal contribution of the customer sites can be tabulated in terms of cost
savings by comparing the ratio of unloaded miles to total loads between the old system
and new system. Old system is one which has all the loggers and mills. New system is
one in which one specific logger or mill is removed from the system. Cost is associated
with the additional unloaded miles that the trucks have to travel to meet the demand
associated with the logger or mill.
a) WITH LOGGER/MILL:
b) WITHOUT LOGGER/MILL:
c) COST SAVINGS:
A logger or mill is said to be beneficial to the system when the trucks travel more
unloaded miles to meet the demand without that particular logger or mill. In other words,
the ratio of K2 should be greater than that of K1 for a logger to be beneficial.
80
Table 7.1: Results of marginal contribution of loggers.
With Logger
K1=Unloaded miles/
total loads
($/Load)
Without Logger
K2=Unloaded miles/
total loads
($/load)
Cost Savings
(K2-K1)/K2
(%)
Log 1 44.29 44.70 0.91
Log 2 44.29 45.16 1.92
Log 3 44.29 49.60 10.71
Log 4 44.29 43.03 -2.93
Log 5 44.29 45.22 2.06
Log 6 44.29 44.38 0.21
Log 7 44.29 44.32 0.07
Log 8 44.29 44.01 -0.63
Log 9 44.29 43.27 -2.36
Log 10 44.29 45.16 1.93
Log 11 44.29 43.12 -2.72
Log 12 44.29 42.10 -5.19
Log 13 44.29 47.38 6.52
Log 14 44.29 45.11 1.82
Log 15 44.29 47.74 7.23
Log 16 44.29 44.38 0.20
Log 17 44.29 42.75 -3.60
Log 18 44.29 44.74 1.01
Log 19 44.29 46.84 5.44
Log 20 44.29 43.99 -0.68
Log 21 44.29 44.18 -0.26
Log 22 44.29 45.85 3.41
Results of marginal contribution of all the loggers are shown in Table 7.1. Based
on the cost savings, logger 3 is found to be the most beneficial logger since the
81
percentage of cost savings in 10.71. A few of the other beneficial loggers are logger 13,
logger 15 and logger 19. Logger 12 and logger 17 increases the cost associated with
meeting the demand since they have negative cost savings.
Table 7.2: Results of Marginal contribution of mills.
With Mill
K1=Unloaded miles/
total loads
($/Load)
Without mill
K2=Unloaded miles/
total loads
($/Load)
Cost Savings
(K2-K1)/K2
(%)
Mill 1 44.29 55.25 19.84
Mill 2 44.29 52.99 16.41
Mill 3 44.29 47.66 7.08
Mill 4 44.29 45.32 2.27
Mill 5 44.29 47.22 6.21
Mill 6 44.29 44.80 1.13
Mill 7 44.29 40.24 -10.06
Mill 8 44.29 44.85 1.24
Mill 9 44.29 44.07 -0.50
Mill 10 44.29 44.11 -0.42
Mill 11 44.29 45.40 2.45
Mill 12 44.29 44.69 0.89
Mill 13 44.29 44.29 0.00
Similarly, the marginal contribution of mills is done by removing one mill at a
time from the system. The marginal contribution of mills is shown in Table 7.2. Mill 1
and Mill 2 are few of the beneficial mills since they yield a positive cost savings of 19.84
and 16.41 respectively when included in the system. Mill 7, Mill9 and Mill 10 gave
negative cost savings and hence by including them, the ratio of unloaded miles per unit
load for serving the demand increases.
82
In the future, if there is a need to include more loggers or mills into the system,
profitability and feasibility of the system can be found by doing a marginal analysis for
the new mills and loggers. If the cost savings turns out positive for a particular customer
site, then that beneficial logger or mill can be included to increase profit.
83
CHAPTER 8
CONCLUSION AND DISCUSSION
The goal of this research was to develop a system which can produce a solution
with less time than the integer programming approach but very close to the optimal
solution for the log truck scheduling problem with capacity and time window constraints.
A system was developed using simulated annealing algorithm to solve the problem with
solving time of less than 2 minutes and a solution much better than the existing one is
obtained. The system was developed using C program and solved using a computer with
Intel Pentium 4 processor having 2.40 GHz of processing speed and 1.5 GB RAM. More
time is spent in searching the neighborhood to improve the solution. The simulator takes
less time in simulating the movement of trucks.
Construction heuristics randomly insert the customer sites in the trucks? routes to
find an initial solution. The initial solution which might be feasible or non-feasible is
slowly turned to a feasible solution using improvement heuristics by manipulating the
customer sites in the routes of the trucks.
The developed system was tested against a small problem with optimum solution
obtained using branch and bound integer programming algorithm. The performance
parameter of total unloaded miles obtained by using simulated annealing approach was
84
found to be exactly the same as that obtained by integer programming approach even
though the solutions were different.
The initial temperature for the annealing process is set at 100 degrees. The
temperature above 100 degrees was found to have no impact on the solution except that it
takes more time to find the solution. When the temperature was reduced below 100
degrees, there were more chances to restrict the solution to its local optima.
The number of local searches is fixed at 2000 at each temperature in our research.
It should be increased when there are fewer trucks available for routing with high
demand. The algorithm is allowed to proceed until the final temperature since the whole
process takes less than 2 minutes.
There is an absolute necessity for timed deliveries of truck loads which are
expected to increase in the future. Hence this research is very useful to meet the
requirements of the forest supply chain.
Future research should be focused more towards generating a solution in limited
and guaranteed time with fixed parameter setup and should be insensitive to changes in
load requirements and the availability of trucks. The simulator can easily be made
stochastic by generating and using random samples of the loading time, unloading time,
traveling speed etc, which can produce a more practical solution. In the current research,
the output from GPS system is entered into an Excel spreadsheet and then filtered data is
fed to the program to generate a solution. Down the line, the program should be
interfaced with the GPS system to directly process the data and deliver the solution. The
85
model then becomes sophisticated and requires advanced optimization techniques to find
a solution.
The model should be made more dynamic accommodating future requests during
plan execution. The tool would come in handy when there is an immediate additional
requirement of loads to be delivered or when the truck serving the loads breaks down
midway. In this case, the unavailable truck?s responsibilities should be shared by other
trucks. Sometimes due to weather uncertainties, the whole routing has to be altered.
The process of finding a minimum number of trucks required to meet the loads for
the day is very complicated. One way of doing this is to reduce the number of vehicles to
the point until the solution can be found within 10 minutes. If the tool takes more than 10
min to find the solution which is not desirable, the number of trucks is slightly increased
by one and then solved to find the solution. The classification of a good logger or mill
purely based on location can be done by allocating unit demand to all the loggers and
mills.
The participating truck companies are required to make organizational changes in
the method of operations to incorporate centralized decision making in a pooled log
transport system. From an environmental point of view, fuel is saved since the truck
travels fewer unloaded miles than needed and as a result more savings are realized in
terms of fuel cost.
The demand matrix should be given to the centralized route scheduler early
morning. The scheduler feeds the demand matrix to the program, and generates a best set
of routes for the trucks. Truck drivers obtain the route and proceeds accordingly.
86
The system has been developed to increase the utilization of trucks, obey the shift
duration of drivers, and to respect the time window at the logger and mill sites. The type
of loading used here is hot loading since there is a loading and unloading time of 6
minutes.
The model can be used even when there is no hub by fixing the distance between
the customer sites and the hub as zero. The logger sites, where the trucks first pick up the
loads become the starting points and the mills, where the trucks delivers the load at the
end of the shift becomes the ending point.
The program receives the demand requirements one hour prior to shift start time.
The loads that are available only after few hours into the shift are most probably
delivered by the trucks which would finish the given routing early or delivered the next
day.
87
REFERENCES
[1] Johanna C. Gerdessen 1996, ?Theory and Methodology Vehicle routing problem
with trailers?, European Journal of Operational Research 93 (1996) 135-147
[2] I-Ming Chao 2002, ?A tabu search method for the truck and trailer routing
problem?, Computers & Operations Research 29 (2002) 33-51
[3] Robert T. Sumichrast and Ina S. Markham 1995, ?A heuristic and lower bound for
a multi-depot routing problem?, Computers Ops Res. Vol.22, No.10, pp.1047-
1056, 1995
[4] Sam R. Thangiah, Jean-Yves Potvin and Tong Sun 1996, ?Heuristic approaches to
vehicle routing with backhauls and time windows?, Computers Ops Res. Vol.23,
No.11, pp.1043-1057, 1996
[5] Zbigniew J. Czech and Piotr Czarnas 2001, ?Parallel simulated annealing for the
vehicle routing problem with time windows?, Research grant BK-280-Rau2-2001
[6] Mikael Ronnqvist 2003, ?Optimization in forestry?, Math. Program., Ser. B
97:267-284 (2003)
[7] Russell Bent and Pascal Van Hentenryck, ?Dynamic vehicle routing with
stochastic requests?
[8] Andres Weintraub, Rafael Epstein, Ramiro Morales, Jorge Seron and Pier
Traverso, 1996, ?A truck scheduling system improves efficiency in the forest
88
industries?, Institute for Operations Research and the Management Sciences,
Interfaces 26: 4 July- August 1996 (pp.1-12)
[9] M.Palmgren, M.Ronnqvist and P.Varbrand 2004, ?A near-exact method for
solving the log-truck scheduling problem?, International Transactions in
Operations Research 11(2004) 447-464
[10] Patrick Hirsch and Manfred Gronalt, ?Tabu search based solution methods for
scheduling log-trucks?
[11] Russell Bent and Pascal Van Hentenryck, ?A Two-stage hybrid local search for
the vehicle routing problem with time windows?
[12] Ibrahim Hassan Osman 1993, ?Metastrategy simulated annealing and tabu search
algorithms for the vehicle routing problem? Annals of Operations Research 41
(1993) 421-451
[13] Jorge F.Valenzuela, H.Hakan Balci and Timothy McDonald 2003, ?A
Transportation-scheduling system for managing silvicultural projects? Journal of
Forest Engineering 2003
[14] Tim McDonald, Jorge Valenzuela ?Optimizing Log Transport in the US South?
89
APPENDIX 1
LOGGER AND MILL NOTATION
Table A1.1-Notation of loggers.
Notation Name of the logger
1 Logger 1
2 Logger 2
3 Logger 3
4 Logger 4
5 Logger 5
6 Logger 6
7 Logger 7
8 Logger 8
9 Logger 9
10 Logger 10
11 Logger 11
12 Logger 12
13 Logger 13
14 Logger 14
15 Logger 15
16 Logger 16
17 Logger 17
18 Logger 18
19 Logger 19
20 Logger 20
21 Logger 21
22 Logger 22
90
Table A1.2-Notation of mills.
Notation Name of the mill
K Mill 1
M Mill 2
B Mill 3
C Mill 4
S Mill 5
T Mill 6
H Mill 7
O Mill 8
D Mill 9
G Mill 10
Q Mill 11
P Mill 12
F Mill 13
91
APPENDIX 2
DISTANCE MATRIX BETWEEN LOGGERS AND MILLS
Mill
Log
K M B C S T H O D G Q P F Hub
1 58 40 42 19 34 48 96 78 71 65 17 110 33 41
2 15 35 62 83 90 56 45 143 82 39 81 41 88 33
3 35 54 74 102 109 67 18 138 102 52 100 36 107 52
4 96 74 90 57 30 98 127 108 28 97 62 141 31 76
5 94 71 78 45 17 84 125 100 33 94 50 139 19 73
6 100 127 63 85 109 61 135 30 168 153 83 180 112 128
7 79 56 110 97 60 116 109 156 29 42 96 88 58 58
8 89 65 85 56 30 93 119 109 20 89 60 133 26 67
9 55 69 102 116 123 96 77 190 116 40 115 21 121 67
10 42 51 7 36 66 13 72 54 99 84 35 97 69 49
11 76 60 46 19 49 39 128 27 103 86 13 131 52 61
12 88 65 85 56 30 93 119 110 20 89 60 133 26 68
13 75 59 45 12 19 51 115 76 63 85 17 130 22 60
14 98 75 97 63 42 135 129 110 30 98 68 143 38 77
15 19 32 66 80 87 59 41 102 80 30 79 43 85 30
16 28 52 28 56 73 31 47 67 99 70 55 75 73 50
17 167 118 129 101 67 128 198 101 99 167 98 212 69 146
18 20 40 67 87 94 61 35 148 87 38 86 36 92 38
19 39 63 2 35 65 8 70 48 110 81 34 95 68 61
20 84 108 46 66 88 45 112 0 147 134 40 165 91 84
21 17 30 63 78 85 57 39 100 77 30 76 45 83 28
22 53 37 45 20 34 46 93 78 80 63 18 108 33 38
Hub 15 2 54 50 60 62 56 109 53 34 48 70 58 0
92
APPENDIX 3
DEMAND MATRIX BETWEEN LOGGERS AND MILLS
Mill
Log
K M B C S T H O D G Q P F
1 1 0 3 0 2 0 0 0 0 0 0 0 0
2 4 0 0 0 0 0 3 0 0 0 0 0 0
3 0 9 0 0 0 0 2 0 0 0 0 0 0
4 0 4 9 0 0 1 0 0 0 0 0 0 0
5 0 1 3 1 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 3 0 0 0 0 0 0
7 0 7 0 0 0 0 0 0 0 0 0 0 0
8 0 2 0 0 3 0 0 0 4 0 0 0 0
9 0 4 0 0 0 0 0 0 0 0 0 1 0
10 0 4 2 0 0 0 6 0 0 0 0 0 0
11 0 0 2 0 0 0 0 0 0 0 0 0 0
12 2 0 0 3 9 0 4 0 0 0 0 0 0
13 0 4 2 0 8 0 0 0 0 0 0 0 0
14 0 1 0 0 0 0 0 0 1 0 0 0 0
15 0 0 0 0 0 0 1 0 0 0 0 0 0
16 1 0 4 0 0 3 5 0 0 0 0 0 0
17 0 1 0 0 2 0 0 0 0 0 0 0 0
18 6 0 0 0 0 0 0 0 0 0 0 0 0
19 0 0 9 0 0 2 4 0 0 0 0 0 0
20 0 0 4 0 0 0 10 0 0 0 0 0 0
21 0 1 0 0 0 0 2 0 0 0 0 0 0
22 0 0 0 0 0 0 0 0 0 2 1 0 0