Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

Dynamic pickup and delivery problems

In the last decade, there has been an increasing body of research in dynamic vehicle routing problems. This article surveys the subclass of those problems called dynamic pickup and delivery problems, in which objects or people have to be collected and delivered in real-time. It discusses some general issues as well as solution strategies.     

An analytical bound on the fleet size in vehicle routing problems: A dynamic programming approach

We present an analytical upper bound on the number of required vehicles for vehicle routing problems with split deliveries and any number of capacitated depots. We show that a fleet size greater than the proposed bound is not achievable based on a set of common assumptions. This property of the upper bound is proved through a dynamic programming approach. We also discuss the validity of the bound for a wide variety of routing problems with or without split deliveries.     

A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。     

Dynamic vehicle routing: Status and prospects

Although most real-world vehicle routing problems are dynamic, the traditional methodological arsenal for this class of problems has been based on adaptations of static algorithms. Still, some important new methodological approaches have recently emerged. In addition, computer-based technologies such as electronic data interchange (EDI), geographic information systems (GIS), global positioning systems (GPS), and intelligent vehicle-highway systems (IVHS) have significantly enhanced the possibilities for efficient dynamic routing and have opened interesting directions for new research. This paper examines the main issues in this rapidly growing area, and surveys recent results and other advances. The assessment of possible impact of new technologies and the distinction of dynamic problems vis-à-vis their static counterparts are given emphasis.     

Applications of the vehicle routing problem with trailers and transshipments

The vehicle routing problem with trailers and transshipments (VRPTT) is a recent and challenging extension of the well-known vehicle routing problem. The VRPTT constitutes an archetypal representative of the class of vehicle routing problems with multiple synchronization constraints (VRPMSs). In addition to the usual task covering constraints, VRPMSs require further synchronization between vehicles, concerning spatial, temporal, and load aspects. VRPMSs possess considerable practical relevance, but limited coverage in the scientific literature. The purpose of the present paper is to describe how several important types of VRPMSs, such as multi-echelon location-routing problems and simultaneous vehicle and crew routing problems, can be modelled as VRPTTs.     

时变条件下带时间窗车辆调度问题的模拟退火算法

带时间窗车辆调度问题(VRPTW)是一类要求满足容积和时间窗约束的车辆路径优化问题,现 有大部分相关文献只考虑了车辆行驶速度恒定的情况,忽略了各种动态因素的影响.本文研究的时变条件下带时间窗车辆调度问题将车辆行驶速度考虑成时变分段函数,并利用模拟退火算法进行求解,最后通过实验结果说明算法的有效性.     

Probabilistic diversification and intensification in local search for vehicle routing

This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches. It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented in this article, too. The solutions of nearly forty problem instances of the literature have been improved.     

An integrated approach for collection network design,capacity planning and vehicle routing in reverse logistics

This study considers network design, capacity planning and vehicle routing for collection systems in reverse logistics. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the return demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport returns at demand points to the opened collection points and travel the opened collection points by vehicles. Unlike the location-routing problems, the integrated problem considered in this study has several features: multi-period dynamic model, capacity planning for collection points, maximum allowable collection distances, etc. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested, and their test results are reported. In particular, the efficiency of the integrated approach is shown by comparing the two algorithm types.     

A Queueing Framework for Routing Problems with Time-dependent Travel Times

Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.      

Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows

This note introduces a refinement to a previously proposed tabu search algorithm for vehicle routing problems with time windows. This refinement yields new best known solutions on a set of benchmark instances of the multi-depot, the periodic and the site-dependent vehicle routing problems with time windows.     

A period vehicle routing case study

The period vehicle routing problem is a multilevel problem assembling two classical problems: the assignment problem and the vehicle routing problem. Collection days have to be assigned to each customer and vehicle routes have to be designed for each day of the period (time horizon) so that the total distribution cost is minimised. The interaction between the temporal and spatial aspects turns the problem into one of the most challenging variations of vehicle routing. In this paper, we present the study of a real period vehicle routing system: the collection of recycling paper containers in the City Council of Almada, Portugal.     

Scheduling issues in vehicle routing

Scheduling often plays an important role in vehicle routing. This paper describes several applications in which the author has been involved in recent years. These arise in the dial-a-ride problem, speed optimization in routing problems, the pollution-routing problem, long-haul vehicle routing and scheduling with working hour rules, and synchronization in arc routing.     

A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows

We propose lifted versions of the Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows (TW). The constraints are valid for problems such as the travelling salesman problem with TW, the vehicle routing problem with TW, the generalized travelling salesman problem with TW, and the general vehicle routing problem with TW. They are corrected versions of the constraints proposed by Desrochers and Laporte (1991).     

A co-evolutionary approach using information about future requests for dynamic vehicle routing problem with soft time windows

This paper presents a technique for integrating information about future customer requests to improve decision making for dynamic vehicle routing. We use a co-evolutionary approach to generate better waiting strategies such that the expected number of late-request customers who are served is maximized. An empirical evaluation of the proposed approach is performed within a previously reported hybrid genetic algorithm for the dynamic vehicle routing problem with time windows. Comparisons with other heuristic methods demonstrate the potential improvement that can be obtained through the application of the proposed approach.     

Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence

In this paper we study the routing of a single vehicle that delivers products and picks up items with stochastic demand. The vehicle follows a predefined customer sequence and is allowed to return to the depot for loading/unloading as needed. A suitable dynamic programming algorithm is proposed to determine the minimum expected routing cost. Furthermore, the optimal routing policy to be followed by the vehicle’s driver is derived by proposing an appropriate theorem. The efficiency of the algorithm is studied by solving large problem sets.     

A unified tabu search heuristic for vehicle routing problems with time windows

This paper presents a unified tabu search heuristic for the vehicle routing problem with time windows and for two important generalizations: the periodic and the multi-depot vehicle routing problems with time windows. The major benefits of the approach are its speed, simplicity and flexibility. The performance of the heuristic is assessed by comparing it to alternative methods on benchmark instances of the vehicle routing problem with time windows. Computational experiments are also reported on new randomly generated instances for each of the two generalizations.     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。