Integrated location, routing and scheduling problems: Models and algorithms

In this research, we investigate location, routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. The problem considers the interdependency between facility location and vehicle routing decisions and also allows the assignment of multiple routes to a single vehicle, resulting in a solution that requires fewer vehicles. We refer to this integrated problem, which is in the complexity class NP-hard, as the location routing and scheduling problem (LRSP).;For a version of this problem with capacitated facilities and time- and capacity-limited vehicles, we present two formulations, one graph-based and one set partitioning-based. We derive the theoretical relationship between these two formulations by applying Dantzig-Wolfe decomposition to the graph-based formulation. We show the equivalence of the set partitioning-based model and the reformulation of the graph-based formulation obtained by Dantzig-Wolfe decomposition. In addition, we computationally compare the bounds yielded by the LP relaxations of the different formulations of the LRSP and demonstrate the strength of the LP relaxation of the set partitioning-based model and some simple valid inequalities introduced for this model.;By adopting a column generation approach derived from the set partitioning-based formulation of the problem, we provide exact and heuristic solution algorithms for the problem. We describe two versions of a branch-and-price algorithm, a standard one-stage version and a two-stage version. The two-stage version is an extended variant of the one-stage algorithm based on the idea of "restart." It has an initialization phase that provides a good upper bound and a pool of effective columns. We evaluate and computationally demonstrate the performance of the algorithms we design using instances up to 40 customers and various parameter settings. We extend our computational study in order to assess the benefit of integrating optimization of facility location, vehicle routing and vehicle scheduling decisions by comparing the LRSP with some variations of the sequential optimization of these decisions. We obtain results confirming our interest in solution of the LRSP.;We extend the branch-and-price algorithm to include methods for dynamically generating valid inequalities. We investigate classes of inequalities valid for polytopes related to the LRSP polytope; discuss their validity for the problem and their integration into the branch-and-price algorithm. In addition, we explore possible ways of adapting the approach of generating valid inequalities using the disjunctive procedure. We provide a methodology to derive disjunctive inequalities in a branch-and-price algorithm and describe some implementations of the methodology for our algorithm. We computationally compare these valid inequalities and discuss their effect to the performance of the branch-and-price algorithm.;Finally, we discuss how we can modify the presented solution approaches for a location and routing problem (LRP), which is a special case of the LRSP. We present computational results for instances up to 40 customers and for instances of certain special cases previously considered in the literature to demonstrate the effectiveness of the solution approach empirically.