We propose solution strategies for hard Mixed Integer Programming (MIP) problems,
with a focus on distributed parallel MIP optimization. Although our proposals are
inspired by the Less-than-truckload (LTL) freight routing problem, they are more
generally applicable to hard MIPs from other domains. We start by developing an Integer
Programming model for the Less-than-truckload (LTL) freight routing problem,
and present a novel heuristic for solving the model in a reasonable amount of time
on large LTL networks. Next, we identify some adaptations to MIP branching strategies
that are useful for achieving improved scaling upon distribution when the LTL
routing problem (or other hard MIPs) are solved using parallel MIP optimization.
Recognizing that our model represents a pseudo-Boolean optimization problem
(PBO), we leverage solution techniques used by PBO solvers to develop a CPLEX
based look-ahead solver for LTL routing and other PBO problems. Our focus once
again is on achieving improved scaling upon distribution. We also analyze a technique
for implementing subtree parallelism during distributed MIP optimization. We
believe that our proposals represent a significant step towards solving big-data driven
optimization problems (such as the LTL routing problem) in a more efficient manner. / Thesis / Doctor of Philosophy (PhD) / Less-than-truckload (LTL) freight transportation is a vital part of Canada's economy,
with revenues running into billions of dollars and a cascading impact on many
other industries. LTL operators often have to deal with large volumes of shipments,
unexpected changes in traffic conditions, and uncertainty in demand patterns. In an
industry that already has low profit margins, it is therefore vitally important to make
good routing decisions without expending a lot of time.
The optimization of such LTL freight networks often results in complex big-data
driven optimization problems. In addition to the challenge of finding optimal solutions
for these problems, analysts often have to deal with the complexities of big-data driven
inputs. In this thesis we develop several solution strategies for solving the LTL freight
routing problem including an exact model, novel heuristics, and techniques for solving
the problem efficiently on a cluster of computers.
Although the techniques we develop are inspired by LTL routing, they are more
generally applicable for solving big-data driven optimization problems from other
domains. Experiments conducted over the years in consultation with industry experts
indicate that our proposals can significantly improve solution quality and reduce
time to solution. Furthermore, our proposals open up interesting avenues for future
research.
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/25846 |
| Date | January 2020 |
| Creators | Tamvada, Srinivas |
| Contributors | Hassini, Elkafi, Computational Engineering and Science |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0022 seconds