A dynamic vehicle routing problem with multiple delivery routes

This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.     

The multi-trip vehicle routing problem

The basic vehicle routing problem is concerned with the design of a set of routes to serve a given number of customers, minimising the total distance travelled. In that problem, each vehicle is assumed to be used only once during a planning period, which is typically a day, and therefore is unrepresentative of many practical situations, where a vehicle makes several journeys during a day. The present authors have previously published an algorithm which outperformed an experienced load planner working on the complex, real-life problems of Burton's Biscuits, where vehicles make more than one trip each day. This present paper uses a simplified version of that general algorithm, in order to compare it with a recently published heuristic specially designed for the theoretical multi-trip vehicle routing problem.     

The grocery superstore vehicle scheduling problem

Scheduling the deliveries from a regional distribution centre (RDC) to large stores of a major retailer of fast moving consumer goods includes every possible vehicle routeing complexity. Usual constraints, like the size of the vehicle and the length of the driving day, apply. More importantly, loading feasibility is a major factor, with frozen goods being at the front, produce and perishable products in the middle, and groceries at the tail of the rear end loading vehicle. Moreover, these three product types have different time windows, determined store by store. Items like medium movers and alcoholic drinks may only be stocked at particular hub depots, from where they must be collected and then delivered to the retail outlets. Collections of salvage are made from the stores and goods from suppliers are backhauled to an RDC, which may not be the vehicle base. Then there may be trunking between RDCs. In this case study, deliveries and collections by vehicles at an RDC are presently scheduled by updating daily a basic plan prepared every 6 months, using the skills of an experienced distribution professional. A simulated annealing-based algorithm has been developed to speed up the process by circumventing the need for the skeletal schedule. In the application tested, the solution produced by the algorithm requires the same number of vehicles as actually used, although the total delivery time is slightly longer. Further improvements, particularly in the quality of the initial solution, may be possible by exploiting the problem structure in recognizable ways.     

The pyramidal capacitated vehicle routing problem

This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

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 dynamic frequency assignment problem

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.     

The vehicle routing problem: A book review

We review the recent book, edited by Paolo Toth and Daniele Vigo, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications 2002, ISBN: 0-89871-498-2, price: 95 USD.     

The distance constrained multiple vehicle traveling purchaser problem

In the Distance Constrained Multiple Vehicle Traveling Purchaser Problem (DC-MVTPP) a fleet of vehicles is available to visit suppliers offering products at different prices and with different quantity availabilities. The DC-MVTPP consists in selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the distance traveled by each vehicle does not exceed a predefined upper bound. The problem generalizes the classical Traveling Purchaser Problem (TPP) and adds new realistic features to the decision problem. In this paper we present different mathematical programming formulations for the problem. A branch-and-price algorithm is also proposed to solve a set partitioning formulation where columns represent feasible routes for the vehicles. At each node of the branch-and-bound tree, the linear relaxation of the set partitioning formulation, augmented by the branching constraints, is solved through column generation. The pricing problem is solved using dynamic programming. A set of instances has been derived from benchmark instances for the asymmetric TPP. Instances with up to 100 suppliers and 200 products have been solved to optimality.     

The open vehicle routing problem with time windows

In this paper, we consider the open vehicle routing problem with time windows (OVRPTW). The OVRPTW seeks to find a set of non-depot returning vehicle routes, for a fleet of capacitated vehicles, to satisfy customers’ requirements, within fixed time intervals that represent the earliest and latest times during the day that customers’ service can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns. The model is solved using a greedy look-ahead route construction heuristic algorithm, which utilizes time windows related information via composite customer selection and route-insertion criteria. These criteria exploit the interrelationships between customers, introduced by time windows, that dictate the sequence in which vehicles must visit customers. Computational results on a set of benchmark problems from the literature provide very good results and indicate the applicability of the methodology in real-life routing applications.     

The vehicle routing problem with coupled time windows

In this article we introduce the vehicle routing problem with coupled time windows (VRPCTW), which is an extension of the vehicle routing problem with time windows (VRPTW), where additional coupling constraints on the time windows are imposed. VRPCTW is applied to model a real-world planning problem concerning the integrated optimization of school starting times and public bus services. A mixed-integer programming formulation for the VRPCTW within this context is given. It is solved using a new meta-heuristic that combines classical construction aspects with mixed-integer preprocessing techniques, and improving hit-and-run, a randomized search strategy from global optimization. Solutions for several randomly generated and real-world instances are presented.     

The multi-depot vehicle routing problem with inter-depot routes

This article addresses an extension of the multi-depot vehicle routing problem in which vehicles may be replenished at intermediate depots along their route. It proposes a heuristic combining the adaptative memory principle, a tabu search method for the solution of subproblems, and integer programming. Tests are conducted on randomly generated instances.     

The inverse maximum dynamic flow problem

We consider the inverse maximum dynamic flow (IMDF) problem. IMDF problem can be described as: how to change the capacity vector of a dynamic network as little as possible so that a given feasible dynamic flow becomes a maximum dynamic flow. After discussing some characteristics of this problem, it is converted to a constrained minimum dynamic cut problem. Then an efficient algorithm which uses two maximum dynamic flow algorithms is proposed to solve the problem.     

The plane dynamic problem of coupled thermoelasticity

A method of solving two-dimensional inner and outer boundary-value problems of coupled thermoelasticity, taking into account the finite propagation velocity of heat pulses, is proposed, based on constructed fundamental solutions of the corresponding equations. An estimate is given of the coupling of thermomechanical fields in these problems, and the hyperbolic and parabolic models of thermal conductivity are compared. It is shown that the effect of the finite propagation velocity of heat is unimportant even for very short periods of the duration of the processes (comparable with the relaxation time of the heat flux).     

The dynamic shortest path problem with anticipation

Mobile communication technologies enable truck drivers to keep abreast of changing traffic conditions in real-time. We assume that such communication capability exists for a single vehicle traveling from a known origin to a known destination where certain arcs en route are congested, perhaps as the result of an accident. Further, we know the likelihood, as a function of congestion duration, that congested arcs will become uncongested and thus less costly to traverse. Using a Markov decision process, we then model and analyze the problem of constructing a minimum expected total cost route from an origin to a destination that anticipates and then responds to changes in congestion, if they occur, while the vehicle is en route. We provide structural results and illustrate the behavior of an optimal policy with several numerical examples and demonstrate the superiority of an optimal anticipatory policy, relative to a route design approach that reflects the reactive nature of current routing procedures.     

Disruption management of the vehicle routing problem with vehicle breakdown

This paper introduces a new class of problem, the disrupted vehicle routing problem (VRP), which deals with the disruptions that occur at the execution stage of a VRP plan. The paper then focuses on one type of such problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs. Two Tabu Search algorithms are developed to solve the problem and are assessed in relation to an exact algorithm. A set of test problems has been generated and computational results from experiments using the heuristic algorithms are presented.     

On a periodic vehicle routing problem

This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation.     

The effects of triangle inequality on the vehicle routing problem

Routing problems often utilize experimental networks to represent real world scenarios. However most ignore the inclusion of triangle inequality violations, a phenomenon resulting from delays or rounding errors within a network. This work evaluates the effect of both frequency – the number of violations – and severity – the degree of intensity of a violation – of triangle inequality and evaluates both solution quality and solution time based on Simulated Annealing, Ant Colony Optimization and Savings Algorithm methods. Findings indicate that while both frequency and severity degrade solution quality, increased levels of frequency and severity together result in significant adverse affects to solution quality. Solution time, however, is not impacted by the presence of triangle inequality violations within the network. This information should encourage practitioners to identify delays and maintain the presence of triangle inequality violations in a network to ensure accuracy of solution quality.