News from PhD Programme of KEDGE: Daniil Khachai, a student from the first intake defended his thesis in the field of Business Administration

This thesis focuses on algorithmic design for three combinatorial optimization problems related to transportation, logistics and production research with specific types of indus- trial constraints. First, we consider the Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP). This problem is an extension of two well-known combinatorial optimization problems — the Generalized Traveling Salesman Problem (GTSP) and the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), whose path version is known as the Sequential Ordering Problem (SOP).

Similarly to the classic GTSP, the goal of the PCGTSP is to find for a given input digraph and partition of its node set into clusters a minimum cost cyclic route (tour) visiting each cluster in a single node. In addition, as in the PCATSP, feasible tours are restricted to visit the clusters with respect to the given partial order. Unlike the GTSP and SOP, to the best of our knowledge, the PCGTSP still remain to be weakly studied both in terms of polyhedral theory and algorithms. In this thesis, for the first time for the PCGTSP, we propose several families of valid inequalities, establish dimension of the PCGTS polytope and prove sufficient conditions ensuring that the extended Balas’ pi- and sigma-inequalities become facet-inducing. Relying on these theoretical results and existing algorithmic approaches for the PCATSP and SOP, we introduce a family of MILP-models and several variants of the branch-and-cut algorithm for the PCGTSP. We study their performance on the instances of the public benchmark library PCGTSPLIB, a known adaptation of the classic SOPLIB to the problem in question. The obtained results show the eciency of the algorithm. The paper was published in European Journal of Operational Research.

Our second research topic is related to a specific industrial application of the PCGTSP - the discrete Cutting Path Problem (CPP). In this problem, we aimed to find an optimal path for a cutting tool, in order to minimize the total processing cost including cutting, air-motion, piercing, and other expenses, subject to constraints induced by industrial cutting restrictions. It is convenient to consider such restrictions in terms of precedence constraints. We introduce a general solution framework for CPP that includes: (i) the universal reduction approach for numerous variants of this problem to the Precedence Constrained Generalized Traveling Salesman Problem; (ii) methodological support for finding (sub-) optimal solutions of this problem on the basis of branch-and-cut algorithm and PCGLNS meta-heuristic. The results of computational experiments show the efficiency of the proposed framework for solving industrial instances of the problem. The paper was submitted to International Journal of Production Research.

Finally, we tackle the Capacitated Vehicle Routing Problem (CVRP). CVRP is strongly NP-hard (even on the Euclidean plane), hard to approximate in general case and APX-complete for an arbitrary metric. However, for the geometric settings of the problem, there is a number of known quasi-polynomial and even polynomial time approximation schemes. Among these results, the well-known Quasi-Polynomial Time Approximation Scheme (QPTAS) proposed by A. Das and C. Mathieu appears to be the most general. In this thesis, we propose the first extension of this scheme to a more wide class of metric spaces. Actually, we show that the metric CVRP has a QPTAS any time when the problem is set up in the metric space of any fixed doubling dimension d > 1 and the capacity does not exceed polylog(n). The paper was published in Journal of Global Optimization.