Linehaul Network Design with a Branch-and-Price Guided Search

linehaul network designThesis abstract
A company with an express delivery service transports small packages from origin to destination on time. Combining several packages in the same transportation vehicle on part of their routes can significantly reduce costs. The goal of this thesis is to minimize the total costs of such a transportation plan. To determine whether faster results can be obtained a Branch-and-price guided search is used. The plain BPGS algorithm does not yield better results than an exact solver (CPLEX) in the same amount of computation time. Therefore, several enhancements were considered: branching with a priority to hub arcs, introducing another objective of the pricing problem, using some local search methods, and temporarily excluding some packages. Using the local search methods resulted in a reduction of the average primal gap from 27.37% to 5.32%, but still no better solutions were obtained than the exact solver.

Read more:


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s