Search

Classic vehicle routing models usually treat fuel cost as input data, but fuel consumption heavily depends on the travel speed, which leads to the study of optimizing speeds over a route to improve fuel efficiency. In this paper, we propose a joint vehicle routing and speed optimization problem to minimize the total operating cost including fuel cost. The only assumption made on the dependence between fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integer convex optimization solver. We propose a novel set-partitioning formulation and a branch-cut-and-price algorithm to solve this problem. We introduce new dominance rules for the labeling algorithm so that the pricing problem can be solved efficiently. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time. [ABSTRACT FROM AUTHOR]

We study a variant of the capacitated vehicle routing problem where the cost over each arc is defined as the product of the arc length and the weight of the vehicle when it traverses that arc. We propose two new mixed-integer linear programming formulations for the problem: an arc-load formulation and a set partitioning formulation based on q-routes with additional constraints. A family of cycle elimination constraints are derived for the arc-load formulation. We then compare the linear programming (LP) relaxations of these formulations with the two-index one-commodity flow formulation proposed in the literature. In particular, we show that the arc-load formulation with the new cycle elimination constraints gives the same LP bound as the set partitioning formulation based on 2-cycle-free q-routes, which is stronger than the LP bound given by the two-index one-commodity flow formulation. We propose a branch-and-cut algorithm for the arc-load formulation, and a branch-cut-and-price algorithm for the set partitioning formulation strengthened by additional constraints. Computational results on instances from the literature demonstrate that a significant improvement can be achieved by the branch-cut-and-price algorithm over other methods. [ABSTRACT FROM AUTHOR]

We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and set packing problems with random coefficients. We propose a problem formulation in its original space based on the so-called probabilistic covers. We focus our solution approaches on the special case in which the uncertainty is represented by a finite number of scenarios. In this case, the problem can be formulated as an integer program by introducing a binary decision variable to represent feasibility of each scenario. We derive a computationally efficient coefficient strengthening procedure for this formulation, and demonstrate how the scenario variables can be efficiently projected out of the linear programming relaxation. We also study how methods for lifting deterministic cover inequalities can be leveraged to perform approximate lifting of probabilistic cover inequalities. We conduct an extensive computational study to illustrate the potential benefits of our proposed techniques on various problem classes. [ABSTRACT FROM AUTHOR]