On unidirectional cyclic layouts, Hamiltonian circuits, capacitated vehicle routes and minimal spanning trees

Abstract

This thesis consists of four major parts. The first part is on the Unidirectional Cyclic Layout Problem (UCLP). First, new efficient heuristics for the UCLP are proposed based on the ideas originally proposed for two well-known combinatorial optimization problems: The Asymmetric Traveling Salesman Problem (ATSP) and the Linear Ordering Problem (LOP). Then, we particularly consider the balanced case of the UCLP's satisfying the additional conservation of flow assumption: the material flow is conserved at every workstation and we develop a Branch and Bound algorithm for the Balanced UCLP (BUCLP). In the second part, we propose new extended ATSP formulations with O(n3) constraints and we analyze the strengths of their linear programming (LP) relaxation both analytically and experimentally. It is shown that the LP relaxation of one of the new formulations can have optimal objective value larger than the LP relaxation of the ATSP's multi-commodity flow formulations. In addition, we also propose new extended ATSP formulations with O(n2) constraints and compare their strengths with the ones of known ATSP formulations with O(n2) constraints. Finally, in the third and fourth parts, a new enhancement of the Clarke and Wright's savings heuristic for the Capacitated Vehicle Routing Problem and new enhancements of the Esau and Williams' savings heuristic for the Capacitated Minimal Spanning Tree Problem are respectively proposed.