In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem . Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions . In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.

Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method that can generate all rational compromises between the objectives. This paper proposes two distinct bound set-based branch-and-cut algorithms for general bi-objective combinatorial optimization problems based on implicit and explicit lower-bound sets. The algorithm based on explicit lower-bound sets computes, for each branching node, a lower-bound set and compares it with an upper-bound set. The other fathoms branching nodes by generating a single point on the lower-bound set for each local nadir point. We outline several approaches for fathoming branching nodes, and we propose an updating scheme for the lower-bound sets that prevents us from solving the bi-objective linear programming relaxation of each branching node. To strengthen the lower-bound sets, we propose a bi-objective cutting-plane algorithm that adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy “Pareto branching.” We prove the effectiveness of the algorithms through extensive computational results.