Artur Alves Pessoa This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more
In a cross-dock facility, goods are moved by forklift from incoming truck platforms (strip doors) to temporary holding areas and then to outgoing truck platforms (stack doors) or directly from strip doors to stack doors. Costs within the cross-dock may be minimized by appropriate assignment of strip doors to incoming trucks and stack doors to … Read more
The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … Read more
This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual … Read more
This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have distinct capacities and costs. The columns in the formulation are associated to q-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, which … Read more
This article presents techniques for constructing robust Branch-Cutand-Price algorithms on a number of Vehicle Routing Problem variants. The word “robust” stress the effort of controlling the worst-case complexity of the pricing subproblem, keeping it pseudo-polynomial. Besides summarizing older research on the topic, some promising new lines of investigation are also presented, specially the development of … Read more
In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … Read more
This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have various capacities and fixed costs. The columns in the formulation are associated to $q$-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, … Read more
A $k$-bit Hamming prefix code is a binary code with the following property: for any codeword $x$ and any prefix $y$ of another codeword, both $x$ and $y$ having the same length, the Hamming distance between $x$ and $y$ is at least $k$. Given an alphabet $A = [a_1,\ldots,a_n]$ with corresponding probabilities $[p_1,\ldots,p_n]$, the $k$-bit … Read more
This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to $q$-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence probem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. … Read more