Abstract: We study the Vehicle Routing Problem with Probabilistic Customers (VRP-PC), a two-stage optimization model, which is a fundamental building block within the broad family of stochastic routing problems. This problem is mainly motivated by logistics distribution networks in which customers receive frequent delivery services, and by the last mile problem faced by companies such as UPS and FedEx. In a first stage before customer service requests realize, a dispatcher determines a set of vehicle routes serving all potential customer locations. In a second stage occurring after observing all customer requests, vehicles execute planned routes skipping all locations of customers not requiring service. The objective is to minimize the expected vehicle travel cost assuming known customer realization probabilities. We propose a column generation framework to solve the VRP-PC to a given optimality tolerance. Specifically, we present two novel algorithms, one that under -approximates a solution's expected cost, and another that uses its exact expected cost. Each algorithm is equipped with a route pricing mechanism that iteratively improves the approximation precision of a route's reduced cost; this produces fast route insertions at the start of the algorithm and reaches termination conditions at the end of the execution. Compared to branch-and-cut algorithms for arc-based formulations, our framework can more readily incorporate sequence-dependent constraints, which are typically required in routing problems. We provide a priori and a posteriori performance guarantees for these algorithms, and demonstrate their effectiveness via a computational study on instances with realization probabilities ranging from 0.5 to 0.9.

Abstract: We study a Lagrangian decomposition algorithm recently proposed by Dan Bienstock and Mark Zuckerberg for solving the LP relaxation of a class of open pit mine project scheduling problems. In this study we show that the Bienstock-Zuckerberg (BZ) algorithm can be used to solve LP relaxations corresponding to a much broader class of scheduling problems, including the well-known Resource Constrained Project Scheduling Problem (RCPSP), and multi-modal variants of the RCPSP that consider batch processing of jobs. We present a new, intuitive proof of correctness for the BZ algorithm that works by casting the BZ algorithm as a column generation algorithm. This analysis allows us to draw parallels with the well-known Dantzig-Wolfe decomposition (DW) algorithm. We discuss practical computational techniques for speeding up the performance of the BZ and DW algorithms on project scheduling problems. Finally, we present computational experiments independently testing the effectiveness of the BZ and DW algorithms on different sets of publicly available test instances. Our computational experiments confirm that the BZ algorithm significantly outperforms the DW algorithm for the problems considered. Our computational experiments also show that the proposed speed-up techniques can have a significant impact on the solve time. We provide some insights on what might be explaining this significant difference in performance.