GMU OR 680/SE 798
18 Mar 2009
Newspaper Production Process
Given a network approach, there are a number of potential algorithms
that could be used to solve the problem
§Exact
Optimization Methods
–Brute
force enumeration infeasible for >20 node networks
–Progressive
improvement algorithms support up to 200-225 node
networks
–Advanced
solutions (cutting plane) currently pushing 10,000+ node tours
but computationally stressing
§Constructive
Heuristic Methods
–Generate
path through greedy- or insertion- method (e.g., nearest
neighbor/insertion)
–Produces
fairly good tour*, with estimates ranging from 1.10x to 2x
optimal tour*
–*For
the newspaper problem, we do not need to return to the original IPC
(i.e., solving for path not tour)
–Certain
network arrangements result in far from optimal spanning paths under
this method
§Improvement
Heuristics
–k-opt
approaches start with an initial tour (e.g., developed through
constructive approach) and attempt to improve through removal and reconstruction
of k edges
–Simulated
annealing, genetic algorithms, and other artificial intelligence
techniques can be used to drive edge evaluation
–Similar
challenges with large networks due to combinatorial enumeration and
evaluation of all sub-tours
§Assessing
the Options
–In
each case, we can solve the linear optimization relaxation of
the integer problem to get an approximate estimate of
“goodness”
–The
results can be compared with an assessment of current
performance in the business case to determine acceptance
1) Luis
Goddyn,www.math.sfu.ca/~goddyn/Courses/820/heuristics.pdf, TSP Heuristics
2)
Christian Nilsson,
Link¨oping University, Heuristics
for the Traveling Salesman Problem
3) http://en.wikipedia.org/wiki/Traveling_Salesman_Problem#Heuristic_and_approximation_algorithms