![]() |
![]() |
![]() |
![]() |
The four finalists of the 2021 EURO Doctoral Dissertation Award are:
Alexandre Florio, University of Vienna
Models and Solution Methods for Stochastic Vehicle Routing Problems
This thesis investigates what is known in the transportation literature as stochastic vehicle routing problems (SVRPs). SVRPs arise whenever vehicle routes must be planned, but the full setting where routing is to take place is not known with certainty. The first studied problem is a new SVRP variant, in which the availability of customers for receiving deliveries is uncertain. This new SVRP is motivated by attended home delivery, in particular, the delivery of e-commerce orders. Next, the focus becomes the classical vehicle routing problem with stochastic demands (VRPSD). The problem is regarded under a priori optimization and optimal restocking. The first contribution is a mixed-integer linear model for the single-vehicle version, which allows solving exactly small problem instances. In addition, a heuristic method to find good quality solutions in larger instances is proposed. The VRPSD with multiple vehicles is then extensively studied. First, a state-of-the-art branch-price-and-cut algorithm for the VRPSD is introduced.
This is the first method that is able to solve instances with few customers per vehicle, which are the most relevant instances concerning the value of stochastic solution. Following that, the VRPSD is considered under probabilistic duration constraints instead of the usual capacity-based constraints. These alternate constraints are more realistic whenever routes must finish within some prescribed time limit (e.g., due to working hours regulations). Under this new set of constraints, the VRPSD becomes considerably more difficult. The problem is solved exactly for the first time by a novel branch-and-price algorithm, which combines different strategies for evaluating route feasibility. The last contribution is a Bayesian model for the VRPSD with positively correlated demands, along with an optimal restocking policy for this case. This is an important step towards addressing one of the current challenges in stochastic routing: developing models and algorithms that can handle statistical dependence among uncertain parameters.
Set Packing, Location and Related Problems
This work is a study on discrete location and set packing, and their application to different domains. In the first part, set packing formulations are investigated. Set packing problems are a paradigmatic example within Combinatorial Optimization, and have applications in many subfields, including Locational Analysis. The thesis proposes and studies two new variants of a well-known discrete location problem, which are formulated as set packings. The second part is devoted to different combinatorial problems arising in a wide range of disciplines---namely, Computational Biology, Cartography, and Network Analysis---, which are related to discrete location and set packing. The first part of the dissertation focuses on the polyhedral study of set packing models.
An emphasis is placed on deriving valid inequalities, facets and lifting techniques, together with the computational tools that allow to exploit these theoretical results. The main goal is to obtain better mathematical programming formulations for set packing problems. Another objective is to study new discrete location problems arising when additional constraints are considered on user allocation. This part of the dissertation can be divided into three blocks. The first of them concerns general aspects of set packing, including the proof of a new theorem for facet lifting. The other two study particular instances of the set packing arising in the context of Locational Analysis. Namely, two novel variants of the Uncapacitated Facility Location Problem, also known as Simple Plant Location Problem (SPLP), are proposed and studied. More precisely, two previously overlooked scenarios of the SPLP are introduced, namely when users cannot be served by the same center, or when double assignment is considered and some pairs of users must be assigned to the same facility.
The common methodology to derive new valid inequalities and facets for these two variants is completed by implementing separation algorithms that allow to incorporate the new inequalities to standard solution techniques. Our computational experience demonstrate the practical relevance of the devised inequalities and algorithms, achieving a significant improvement when compared to a commercial solver or alternative formulations. The second part of the thesis exposes the interplay between Locational Analysis and other disciplines, and aims at the study of combinatorial problems of these disciplines that are related to the first part. These are haplotyping of diploid organisms, optimal map design, and identification of key members in social networks. For each of these problems, mathematical programming formulations are proposed, possible enhancements are studied, tailored algorithms are designed and implemented, and computational tests are conducted. The methodology would be that customary for this kind of approaches, including proposing decision variables and constraints to model the problem--- which is in our case a non-trivial step---, deriving valid inequalities to improve the resulting formulation and possible comparison with other existing models. Furthermore, specific solving techniques are implemented when needed. In the context of haplotype phasing, we study root graph reconstruction from the graph that encodes genetic consistency relations between a set of individuals.
This reconstruction sometimes requires overlooking some of the consistency relations, that is, deleting some edges of the mentioned graph. The combinatorial problem is then to decide which edges to delete so that the root graph reconstruction is allowed while the graph encoding consistency relations is altered as little as possible. Our main contribution consists of disclosing the connection between this problem and the discrete location problems of the first part, and proposing several alternative formulations and different families of valid inequalities for the problem. We explore the relation between formulations and provide both theoretical and computational comparative analysis. On the other hand, the main goal when tackling map labeling is the automatic design of less ambiguous maps. Different models are proposed, which are inspired by ordered median problems in the context of Locational Analysis. The effectiveness of the proposed formulations is validated through computational tests on maps of the Region of Murcia in Spain.
The readability of our solutions significantly improves that of the solutions obtained with other existing models. Finally, the study of key nodes in a network focuses on adapting the eigenvector centrality measure to the problem of group relevance. Similarly to p-median models, nodes are clustered and each cluster is assigned to the same median, i.e. the most relevant node. In our approach, eigenvector computation is embedded in the clustering procedure. As a result, a mathematical formulation that uncovers the group of key nodes together with their communities is proposed. Modeling this idea with mathematical optimization variables involves highly non-linear equations, which are linearised to produce a mixed-integer linear programming formulation for the problem. Experiments on real-life networks of small size show interesting results that reveal previously unnoticed key members. Our computational experience on larger synthetic networks demonstrates an adequate scalability of the method, which is able to find optimal solutions for networks of hundreds of nodes and thousands of links.
E-Commerce warehousing: Order fulfillment in modern retailing
E-commerce led to drastic changes in end consumer behavior over the last decades. As a consequence, today's retailers often need to provide online channels to stay attractive and competitive. However, behind the online front-end, logistic processes are needed, capable of smoothly shipping small orders, picked from a large assortment in little time. These processes are complex and differ from classical warehousing processes to a large extend. The dissertation project presented summarizes today's challenges, surveys common implementations of e-commerce warehousing systems as well as related literature, and identifies new planning problems in modern e-commerce warehouses.
A selection of novel planning problems from different domains and warehousing systems is investigated further. Based on mathematical models and complexity analyses, suited, tailor-made solution procedures are suggested, helping to tackle operational problems in these complex environments. In additional computational studies and simulation runs, strategic and tactical decision support is provided, considering feedback from the operational planning steps optimized. Managerial implications are part of each chapter, therefore. Additionally, problems are set in relation to classical warehousing operations. Emphasizing the differences to classical approaches, valuable insights into modern warehousing are given to researchers and practitioners.
New trends in algebraic equivalent transformation of the central path and its applications
The aim of the thesis is to propose, develop and analyse new interior-point algorithms (IPA)s. We also investigate the possibility of extending some IPAs from linear optimization (LO) to more general problems, such as linear complementarity problems (LCPs) and symmetric optimization (SO) problems. A large amount of articles have been published in this area. This is due to the fact, that these problems have a wide range of applications in different fields. It has been proven that the Nash equilibria of a bimatrix game are the same as the solutions of an appropriate LCP. The Karush-Kuhn-Tucker conditions of non-convex quadratic optimization problems lead to LCP, too. Moreover, LCP can also be used for testing copositivity of matrices. The Arrow-Debreu competitive market equilibrium problem with linear and Leontief utility functions can also be given as LCP. In general, LCP belongs to the class of NP-complete problems. However, Kojima et al. showed that if the problem’s coefficient matrix has a special property, called P∗(κ)-property, IPAs for LCP have polynomial iteration complexity in the size of the problem and in the special parameter κ, called the handicap of the problem’s matrix.
The SO problem is a convex optimization problem, which minimizes a linear function over the intersection of an affine subspace and a symmetric cone. Note that SO includes semidefinite optimization (SDO) and second-order cone optimization (SOCO) and it has a lot of applications in physics, finance, etc. In this thesis new results are included related to different areas of mathematical optimization, such as LO, LCP and SO. The leading thread through this work is the algebraic equivalent transformation (AET) technique in the context of IPAs. This method plays an important role in the theory of IPAs, because using it the representation of the central path is significantly modified, and this changes the location and the neighbourhood of the target points compared to the target points and neighbourhood corresponding to the original representation of the central path. As a consequence, we can define new search directions that yield new IPAs. The method of AET consists of applying a continuously differentiable and invertible function on the centering equation of the central path system.
To our best knowledge, the broadest class of function used in the AET technique is due to Haddou et al., who introduced a family of smooth concave functions for monotone LCPs. One of the novelties of this thesis is that we apply the new function φ(t) = t − √t on the centering equation of the system defining the central path. This function does not belong to the class of concave functions proposed by Haddou et al. We also show that the barrier associated to the introduced function cannot be derived from a usual kernel function. Therefore, we introduce a new notion, namely the concept of the positive-asymptotic kernel function. We also present the relationship of the AET technique to other approaches to determine search directions.
Furthermore, we present four IPAs for solving different types of optimization problems that use this function in the AET technique in order to determine the new search directions. The first one is a classical primal-dual algorithm for LO. The second IPA is a predictor-corrector (PC) IPA for solving LO problems. The third new algorithm is also a PC IPA [1] for solving P∗(κ)-LCPs. In this part of our work we also give a unified framework of the Newton systems and scaled systems in case of PC IPAs for solving P∗(κ)-LCPs. The fourth new IPA solves SO problems and uses the same function in the AET technique in order to obtain the new search directions. In all four cases we present the complexity analysis of the proposed IPAs and we show that the methods retain the best known polynomial iteration complexity.
Several questions remain open for future work. For instance, it would be very interesting task to find a general class of functions φ for AET which includes the function φ(t) = t−√t and which gives IPAs with the best known complexity results for solving LO, P∗(κ)-LCPs and SO problems. Furthermore, we would like to extend our PC IPAs to more general problems, such as the general LCPs in the existentially polytime-sense and to sufficient LCPs over Cartesian product of symmetric cones.
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 International License and the GNU Free Documentation License (unversioned, with no invariant sections, front-cover texts, or back-cover texts).