We propose exact solution approaches for a lateral transhipment problem which, given a pre-specified sequence of customers, seeks an optimal inventory redistribution plan considering travel costs and profits dependent on inventory levels. Trip-duration and vehicle-capacity constraints are also imposed. The same problem arises in some lot sizing applications, in the presence of setup costs and equipment re-qualifications. We introduce a pure dynamic programming approach and a branch-and-bound framework that combines dynamic programming with Lagrangian relaxation. Computational experiments are conducted to determine the most suitable solution approach for different instances, depending on their size, vehicle capacities and duration constraints. The branch-and-bound approach, in particular, solves problems with up to 50 delivery locations in less than ten seconds on a modern computer.
The problem is also very relevant on its own, as a case of routing optimization with a-priori routes @cite_8 . In practical routing applications, retaining some fixed route fragments can lead to a better operational and computational tractability for companies, as well as efficiency gains through driver learning. The corresponding subproblem is called the evaluation problem for a-priori routes, and efficient solution methods are needed to quickly react to changing environments. We also show that the same model encompasses several lot sizing applications with re-qualification costs.
@cite_8
1984143531 1965882376 2031722814 2070311542
We consider a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic. Given only a probabilistic description of the demand we need to design routes for the VRP. Motivated by applications in strategic planning and distribution systems, rather than resolving the problem when the demand becomes known, we propose to construct an a priori sequence among all customers of minimal expected total length. We analyze the problem using a variety of theoretical approaches. We find closed-form expressions and algorithms to compute the expected length of an a priori sequence under general probabilistic assumptions. Based on these expressions we find upper and lower bounds for the probabilistic VRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We propose heuristics and analyze their worst case performance as well as their average behavior using techniques from probabilistic analysis. Our results suggest that our approac... The vehicle routing problem with multiple routes consists in determining the routing of a fleet of vehicles when each vehicle can perform multiple routes during its operations day. This problem is relevant in applications where the duration of each route is limited, for example when perishable goods are transported. In this work, we assume that a fixed-size fleet of vehicles is available and that it might not be possible to serve all customer requests, due to time constraints. Accordingly, the objective is first to maximize the number of served customers and then, to minimize the total distance traveled by the vehicles. An adaptive large neighborhood search, exploiting the ruin-and-recreate principle, is proposed for solving this problem. The various destruction and reconstruction operators take advantage of the hierarchical nature of the problem by working either at the customer, route or workday level. Computational results on Euclidean instances, derived from well-known benchmark instances, demonstrate the benefits of this multi-level approach. This paper considers the vehicle routing problem with time windows, where the service of each customer must start within a specified time interval. We consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear programming for solving the associated Lagrangian dual problem. This algorithm creates easier constrained shortest path subproblems because less negative cycles are introduced and it leads to faster multiplier convergence due to a stabilization of the dual variables. We have embedded the stabilized cutting-plane algorithm in a branch-and-bound search and introduce strong valid inequalities at the master problem level by Lagrangian relaxation. The result is a Lagrangian branch-and-cut-and-price (LBCP) algorithm for the VRPTW. Making use of this acceleration strategy at the master problem level gives a significant speed-up compared to algorithms in the literature based on traditional column generation. We have solved two test problems introduced in 2001 by Gehring and Homberger with 400 and 1000 customers respectively, which to date are the largest problems ever solved to optimality. We have implemented the LBCP algorithm using the ABACUS open-source framework for solving mixed-integer linear-programs by branch, cut, and price. Recent advances in both computational power and communications technologies have created novel opportunities for research in combinatorial optimizations. Many applications in routing, scheduling, and networking raise exciting challenges, in particular in uncertainty. These applications are often online optimization problems, where the input is not known a priori, but characterized by a probabilistic model, and where decisions are made under severe time constraints. This thesis presents an online stochastic optimization framework whose goal is to maximize expected profit. It presents two algorithms, consensus and regret, designed to operate under severe time constraints. Theoretical results show that the framework and algorithms provide strong guarantees on solution quality under reasonable assumptions about the input distribution). Moreover, experimental results on a variety of applications in packet scheduling, vehicle dispatching, and vehicle routing indicate that the approach provides significant improvements in quality of service, even under severe time constraints. The framework is also shown to be robust even when the distribution itself is unknown. Finally, a large neighborhood search that hybridizes constraint programming and local search in novel ways is presented for its success in online vehicle routing problems.