Branch-and-Price Approaches for Real-Time Vehicle Routing with Picking, Loading, and Soft Time Windows
Wölck M, Meisel S
Zusammenfassung
We propose and evaluate branch-and-price approaches for vehicle routing
problems with picking, loading, and soft time windows. This general type
of vehicle routing problem is of particular relevance in the same-day
delivery context, in which fast routing algorithms are required because
of the commitment to real-time delivery in the presence of high customer
order frequencies. To boost the performance of the branch-and-price
algorithms, we introduce the new method of tree-compatible labeling with
nondominance trees. This method represents cost functions by a fixed
number of breakpoints and uses a specialized tree-based data structure
to store Pareto-optimal labels. We prove the theoretical soundness of
the new method and evaluate its performance numerically with respect to
pricing, column generation, and branch-and-price. Our numerical results
show that the method yields substantial performance gains. In
particular, we show that, with the new method, branch-and-price is able
to reliably generate within a few minutes close to optimal solutions for
problem instances with 50 customers. By additional experiments with
classic vehicle routing problems with hard time windows, we show that
the performance gains of our method result from its ability to handle
cost functions in the pricing step. Our approach is the first
branch-and-price approach for vehicle routing with picking, loading, and
soft time windows. As such, it represents an exact routing algorithm
that is able to reliably satisfy the runtime requirements of real-time
delivery services.
Schlüsselwörter
branch-and-price; vehicle routing; same-day delivery; last-mile delivery