10h30 - 10h55
Selective pricing in branch-and-price algorithms for vehicle routing problems
When solving VRPs by column generation, usually the set of feasible routes is enlarged with infeasible cyclic routes. Nevertheless, a lower bound is reached when no feasible route has negative reduced cost regardless of the cyclic route reduced costs. We explore this knowledge to improve the labeling algorithm used for pricing.
10h55 - 11h20
I2SUD: An improved integral simplex using decomposition algorithm
We propose I2SUD, an improved version of the Integral Simplex Using Decomposition algorithm (ISUD). We develop dynamic self-adjusted decompositions to find likely orthogonal descent directions at each iteration. We solve related subproblems in parallel to get an improved integer solution until optimality. We also present some strategies to speed-up I2SUD. Keywords: Integral Simplex Using Decomposition algorithm, dynamic self-adjusted decomposition, parallel computing, orthogonal descent directions.
11h20 - 11h45
An improved model for the integral simplex using decomposition algorithm
We introduce a new model that improves both quality and performance of the ISUD algorithm. The new model presents higher chances of finding the targeted integer solutions without branching. In our experimentation, optimal solutions are encountered, in less than a minute, for large instances with up to 570000 columns.
11h45 - 12h10
A general uncapacitated multiple allocation p-hub median problem
The uncapacitated multiple allocation p-hub median problem assumes that the triangle inequality applies on the edges of a complete graph. Hence the flow between any pair of nodes requires at most two hubs for the transfer process. Here we relax the triangle inequality restriction and present two new formulations that allow transfer through up to q hubs where q ≤ p is a given parameter. Some heuristic solution approaches are proposed and preliminary computational results given.