Column generation-based solution approach for a stochastic vehicle routing problem with flexible deliveries

This paper introduces a stochastic vehicle routing problem with flexible delivery locations and soft time window constraints. In this problem, customers are served at one of their preferred delivery locations, and travel times are uncertain. We propose a mathematical model in which the objective is to minimize a weighted combination of operational costs and service-related costs. To obtain a solution to the problem, we develop a column generation-based solution approach that obtains efficient routes via the pricing subproblem which corresponds to an elementary shortest path problem with resource constraints. This subproblem is effectively solved by implementing the ng-route relaxation technique and a parallelized label correcting algorithm. The proposed method initializes a feasible solution for a set of routes, which is then used to construct the restricted linear programming master problem of column generation. The linear relaxation provides a lower bound when column generation terminates, and an upper bound is obtained by solving an integer programming model over all efficient routes obtained by the column generation. The computational experiments conducted on well-known problem instances demonstrate that the approach provides reasonable optimality gaps and computational times. We further adapt the solution approach for an extension that adds shared delivery locations resulting in cost savings. Overall, the results show that the proposed solution approach effectively balances cost efficiency and service reliability for flexible delivery routing in stochastic environment.