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. Summary of Contribution: In this paper, we propose the first branch-and-price approaches for a general class of vehicle routing problems with picking, loading, and soft time windows. This problem class is of particular importance for real-time delivery services, for which customers expect to be served within only a few hours after their order has been placed. We provide a problem formulation that takes into account that short runtimes of routing algorithms are required, that the upper bounds of the customers’ time windows may be violated at a certain cost, and that a significant part of the delivery time window is consumed by picking orders from a warehouse and loading orders into vehicles. Solving the problem with branch-and-price requires the use of cost functions as elements of the labels in the pricing step. We propose a method that approximates these cost functions and leverages the computational performance of nondominance tree data structures for solving the pricing problem. We prove the theoretical soundness of this new method for exact branch-and-price, and we show numerically that the method leads to a significant performance increase of branch-and-price. The paper lies at the intersection of computing and operations research, in particular because our algorithms are designed to leverage the computational performance of advanced data structures for solving a combinatorial optimization problem.

We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and maximization of the number of visited customer locations. Experiments are based on a large set of specifically designed problem instances with different characteristics and it is shown that local search techniques focusing on one of the objectives only improve the performance of the evolutionary algorithm in terms of both objectives. The analysis also shows that local search techniques are capable of sending locally optimal solutions to foremost fronts of the multi-objective optimization process, and that these solutions then become the leading factors of the evolutionary process.

This paper proposes a simulated annealing variant for optimization problems in which the solution quality can only be estimated by sampling from a random distribution. The aim is to find the solution with the best expected performance, as, e.g., is typical for problems where solutions are evaluated using a stochastic simulation. Assuming Gaussian noise with known standard deviation, we derive a fully sequential sampling procedure and decision rule. The procedure starts with a single sample of the value of a proposed move to a neighboring solution and then continues to draw more samples until it is able to make a decision to accept or reject the move. Under constraints of equilibrium detailed balance at each draw, we find a decoupling between the acceptance criterion and the choice of the rejection criterion. We derive a universally optimal acceptance criterion in the sense of maximizing the acceptance probability per sample and thus the efficiency of the optimization process. We show that the choice of the move rejection criterion depends on expectations of possible alternative moves and propose a simple and practical (albeit more empirical) solution that preserves detailed balance. An empirical evaluation shows that the resulting approach is indeed more efficient than several previously proposed simulated annealing variants.

We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.