J. Fabian Meier The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of … Read more
A variety of formulations for the Travelling Salesman Problem as Mixed Integer Program have been proposed. They contain either non-binary variables or the number of constraints and variables is large. We want to give a new formulation that consists solely of binary variables; the number of variables and the number of constraints are of order … Read more
The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The … Read more
Transport networks with hub structure organise the exchange of shipments between many sources and sinks. All sources and sinks are connected to a small number of hubs which serve as transhipment points, so that only few, strongly consolidated transport relations exist. While hubs and detours lead to additional costs, the savings from bundling shipments, i.e. … Read more
The usability of hub location models heavily depends on an appropriate modelling approach for the economies of scale. Realistic hub location models require more sophisticated transport cost structures than the traditional flow-independent discount. We develop a general modelling scheme for such problems allowing the definition of complicated (non-linear) costs and constraints; its structure allows an … Read more
This paper proposes a new lower bounding procedure for the Uncapacitated Single Allocation p-Hub Median Problem based on Lagrangean relaxation. For solving the resulting Lagrangean subproblem, the given problem structure is exploited: it can be decomposed into smaller subproblems that can be solved efficiently by combinatorial algorithms. Our computational experiments for some benchmark instances demonstrate … Read more
Hub location problems are strategic network planning problems. They formalise the challenge of mutually exchanging shipments between a large set of depots. The aim is to choose a set of hubs (out of a given set of possible hubs) and connect every depot to a hub so that the total transport costs for exchanging shipments … Read more