Search

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

A chance-constrained optimization problem involves constraints with random data that can be violated with probability bounded from above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas, such as finance and energy. Except under very special conditions, chance-constrained problems are extremely difficult. In "Bicriteria Approximation of Chance-Constrained Covering Problems," Xie and Ahmed study a class of chance-constrained covering problems. They propose a bicriteria approximation scheme. Their scheme finds a solution whose violation probability may be larger than but is within a constant factor of the specified risk parameter and whose objective value is within a constant factor of the true optimal value. They extend the approximation results to a setting in which the underlying distribution of the constraint data are not known; that is, they consider distributionally robust chance-constrained covering problems and provide bicriteria approximation results. A chance-constrained optimization problem involves constraints with random data that can be violated with probability bounded from above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas, such as finance, energy, service, and manufacturing. Except under very special conditions, chance-constrained problems are extremely difficult. There has been a great deal of elegant work on developing tractable approximations of chance constraints. Unfortunately, none of these approaches comes with a constant factor approximation guarantee. We show that such a guarantee is impossible by proving an inapproximability result. By contrast, for a large class of chance-constrained covering problems, we propose a bicriteria approximation scheme. Our scheme finds a solution whose violation probability may be larger than but is within a constant factor of the specified risk parameter and whose objective value is within a constant factor of the true optimal value. Key to our developments is the construction of a tractable convex relaxation of a chance-constrained problem and an appropriate scaling of a solution to this relaxation. We extend our approximation results to the setting in which the underlying distribution of the constraint data is not known. That is, we consider distributionally robust chance-constrained covering problems with convex moment and Wasserstein ambiguity sets and provide bicriteria approximation results. [ABSTRACT FROM AUTHOR]

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining (2-2/f) -approximation algorithms, provided that the set of precedence constraints has fractional dimension of at most f . Our approach yields the best-known approximation ratios for all previously considered special classes of precedence constraints, and it provides the first results for bounded degree and orders of interval dimension 2. On the negative side, we show that the addressed problem remains-hard even when restricted to the special case of NP interval orders. Furthermore, we prove that the general problem, if a fixed cost present in all feasible schedules is ignored, becomes as hard to approximate as vertex cover. We conclude by giving the first inapproximability result for this problem, showing under a widely believed assumption that it does not admit a polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

We study a reliable facility location problem wherein some facilities are subject to failure from time to time. If a facility fails, customers originally assigned to it have to be reassigned to other (operational) facilities. We formulate this problem as a two-stage stochastic program and then as a nonlinear integer program. Several heuristics that can produce near-optimal solutions are proposed for this NP-hard problem. For the special case where the probability that a facility fails is a constant (independent of the facility), we provide an approximation algorithm with a worst-case bound of 4. The effectiveness of our heuristics is tested by extensive computational studies, which also lead to some managerial insights. [ABSTRACT FROM AUTHOR]

We consider a particular bin packing problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the bin packing problem with conflicts, is of practical and theoretical interest because of its many real-world applications and because it generalizes both the bin packing problem and the vertex coloring problem. We present new lower bounds, upper bounds, and an exact approach, based on a set covering formulation solved through a branch-and-price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature. [ABSTRACT FROM AUTHOR]

We present a new algorithm that uses both local branching and Monte Carlo sampling in a multidescent search strategy for solving 0-1 integer stochastic programming problems. This procedure is applied to the single-vehicle routing problem with stochastic demands. Computational results show the effectiveness of this new approach to solving hard instances of the problem. [ABSTRACT FROM AUTHOR]