Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands

We consider the problem of finding the optimal routing of a single vehicle that delivers K different products to N customers according to a particular customer order. The demands of the customers for each product are assumed to be random variables with known distributions. Each product type is stored in its dedicated compartment in the vehicle. Using a suitable dynamic programming algorithm we find the policy that satisfies the demands of the customers with the minimum total expected cost. We also prove that this policy has a specific threshold-type structure. Furthermore, we investigate a corresponding infinite-time horizon problem in which the service of the customers does not stop when the last customer has been serviced but it continues indefinitely with the same customer order. It is assumed that the demands of the customers at different tours have the same distributions. It is shown that the discounted-cost optimal policy and the average-cost optimal policy have the same threshold-type structure as the optimal policy in the original problem. The theoretical results are illustrated by numerical examples.     

A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands

This article introduces a new exact algorithm for the capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSD can be formulated as a set partitioning problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme. Computational experiments show promising results.     

A multi-space sampling heuristic for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. This paper proposes a simple yet effective heuristic approach that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set partitioning formulation to sample the solution space and find high-quality solutions for the problem. Computational experiments on benchmark instances from the literature show that the proposed approach is competitive with the state-of-the-art algorithm for the problem in terms of both accuracy and efficiency. In experiments conducted on a set of 40 instances, the proposed approach unveiled four new best-known solutions (BKSs) and matched another 24. For the remaining 12 instances, the heuristic reported average gaps with respect to the BKS ranging from 0.69 to 0.15 % depending on its configuration.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Experience with a framework for developing heuristics for solving rich vehicle routing problems

According to Cordeau et al. (J Oper Res Soc 53(5):512–522, 2002) a good VRP heuristic should fulfill four criteria: accuracy, speed, simplicity, and flexibility. In this paper we report experience with a heuristic framework for solving rich vehicle routing problems (RVRP), which is based on rather simple heuristics. This heuristic framework has been implemented as flexible software framework. The user-friendly design enables flexible customization of problem-specific solvers. Our computational study on five RVRP reveals that the heuristic approach is rather robust with respect to parameterization and that the solvers which have been customized from the framework can compete with state-of-the-art special purpose developments.     

Algorithms for solving inverse geophysical problems on parallel computing systems

For solving inverse gravimetry problems, efficient stable parallel algorithms based on iterative gradient methods are proposed. For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, a parallel matrix sweep algorithm, a square root method, and a conjugate gradient method with preconditioner are proposed. The algorithms are implemented numerically on a parallel computing system of the Institute of Mathematics and Mechanics (PCS-IMM), NVIDIA graphics processors, and an Intel multi-core CPU with some new computing technologies. The parallel algorithms are incorporated into a system of remote computations entitled “Specialized Web-Portal for Solving Geophysical Problems on Multiprocessor Computers.” Some problems with “quasi-model” and real data are solved.     

A generalized crossing local search method for solving vehicle routing problems

In this paper, we propose a generalized crossing local search method for solving vehicle routing problems. This method is a generalization of the string crossing method described in the literature. To evaluate the performance of the proposed method, extensive computational experiments on the proposed method applied to a set of benchmark problems are carried out. The results show that the proposed method, when coupled with metaheuristics such as simulated annealing, is comparable with other efficient heuristic methods proposed in the literature.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.     

A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

Vehicle routing with stochastic demands and restricted failures

This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the lastk customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, whenk=1 the SVRP with recourse reduces to a single TSP.     

A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands

We develop methods to estimate and exactly calculate the expected cost of a priori policies for the multi-compartment vehicle routing problem with stochastic demands, an extension of the classical vehicle routing problem where customer demands are uncertain and products must be transported in separate partitions. We incorporate our estimation procedure into a cyclic-order-based simulated annealing algorithm, significantly improving the best-known solution values for a set of benchmark problems. We also extend the updating procedure for a cyclic order’s candidate route set to duration-constrained a priori policies.     

Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs

Metaheuristic algorithms, such as simulated annealing and tabu search, are popular solution techniques for vehicle routing problems (VRPs). These approaches rely on iterative improvements to a starting solution, involving slight alterations to the routes (ie, neighbourhood moves), moving a node to a different part of a solution, swapping nodes or inverting sections of a tour, for example. When working with standard VRPs, where the costs of the arcs do not vary with advancing time, evaluating changes to the total cost following a neighbourhood move is a simple process: simply subtract the cost of the links removed from the solution and add the costs for the new links. When a time-varying aspect (eg, congestion) is included in the costs, these calculations become estimations rather than exact values. This paper focuses on a single vehicle routing problem, similar to the Travelling Salesman Problem, and investigates the potential for using estimation methods on simple models with time-variant costs, mimicking the effects of road congestion.     

Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet

This paper discusses the two-dimensional loading capacitated vehicle routing problem (2L-CVRP) with heterogeneous fleet (2L-HFVRP). The 2L-CVRP can be found in many real-life situations related to the transportation of voluminous items where two-dimensional packing restrictions have to be considered, e.g.: transportation of heavy machinery, forklifts, professional cleaning equipment, etc. Here, we also consider a heterogeneous fleet of vehicles, comprising units of different capacities, sizes and fixed/variable costs. Despite the fact that heterogeneous fleets are quite ubiquitous in real-life scenarios, there is a lack of publications in the literature discussing the 2L-HFVRP. In particular, to the best of our knowledge no previous work discusses the non-oriented 2L-HFVRP, in which items are allowed to be rotated during the truck-loading process. After describing and motivating the problem, a literature review on related work is performed. Then, a multi-start algorithm based on biased randomization of routing and packing heuristics is proposed. A set of computational experiments contribute to illustrate the scope of our approach, as well as to show its efficiency.     

A parallel stochastic method for solving linearly constrained concave global minimization problems

A parallel stochastic algorithm is presented for solving the linearly constrained concave global minimization problem. The algorithm is a multistart method and makes use of a Bayesian stopping rule to identify the global minimum with high probability. Computational results are presented for more than 200 problems on a Cray X-MP EA/464 supercomputer.     

A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems

This paper considers a transportation problem for moving empty or laden containers for a logistic company. Owing to the limited resource of its vehicles (trucks and trailers), the company often needs to sub-contract certain job orders to outsourced companies. A model for this truck and trailer vehicle routing problem (TTVRP) is first constructed in the paper. The solution to the TTVRP consists of finding a complete routing schedule for serving the jobs with minimum routing distance and number of trucks, subject to a number of constraints such as time windows and availability of trailers. To solve such a multi-objective and multi-modal combinatorial optimization problem, a hybrid multi-objective evolutionary algorithm (HMOEA) featured with specialized genetic operators, variable-length representation and local search heuristic is applied to find the Pareto optimal routing solutions for the TTVRP. Detailed analysis is performed to extract useful decision-making information from the multi-objective optimization results as well as to examine the correlations among different variables, such as the number of trucks and trailers, the trailer exchange points, and the utilization of trucks in the routing solutions. It has been shown that the HMOEA is effective in solving multi-objective combinatorial optimization problems, such as finding useful trade-off solutions for the TTVRP routing problem.     

A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service

This paper addresses the two-echelon capacitated vehicle routing problem (2E-CVRP) with stochastic demands (2E-CVRPSD) in city logistics. A stochastic program with recourse is used to describe the problem. This program aims to minimize the sum of the travel cost and the expected cost of recourse actions resulting from potential route failures. In a two-echelon distribution system, split deliveries are allowed at the first level but not at the second level, thereby increasing the difficulty of calculating the expected failure cost. Three types of routes with or without split deliveries are identified. Different methods are devised or adapted from the literature to compute the failure cost. A genetic-algorithm-based (GA) approach is proposed to solve the 2E-CVRPSD. A simple encoding and decoding scheme, a modified route copy crossover operator, and a satellite-selection-based mutation operator are devised in this approach. The numerical results show that for all instances, the expected cost of the best 2E-CVRPSD solution found by the proposed approach is not greater than that of the best-known 2E-CVRP solution with an average relative gap of 2.57%. Therefore, the GA-based approach can find high-quality solutions for the 2E-CVRPSD.