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

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

The Clustered Orienteering Problem

In this paper we study a generalization of the Orienteering Problem (OP) which we call the Clustered Orienteering Problem (COP). The OP, also known as the Selective Traveling Salesman Problem, is a problem where a set of potential customers is given and a profit is associated with the service of each customer. A single vehicle is available to serve the customers. The objective is to find the vehicle route that maximizes the total collected profit in such a way that the duration of the route does not exceed a given threshold. In the COP, customers are grouped in clusters. A profit is associated with each cluster and is gained only if all customers belonging to the cluster are served. We propose two solution approaches for the COP: an exact and a heuristic one. The exact approach is a branch-and-cut while the heuristic approach is a tabu search. Computational results on a set of randomly generated instances are provided to show the efficiency and effectiveness of both approaches.     

Exact algorithms for routing problems under vehicle capacity constraints

The solution of a vehicle routing problem calls for the determination of a set of routes, each performed by a single vehicle which starts and ends at its own depot, such that all the requirements of the customers are fulfilled and the global transportation cost is minimized. The routes have to satisfy several operational constraints which depend on the nature of the transported goods, on the quality of the service level, and on the characteristics of the customers and of the vehicles. One of the most common operational constraint addressed in the scientific literature is that the vehicle fleet is capacitated and the total load transported by a vehicle cannot exceed its capacity.     

A multi-depot period vehicle routing problem arising in the utilities sector

This paper considers the resource planning problem of a utility company that provides preventive maintenance services to a set of customers using a fleet of depot-based mobile gangs. The problem is to determine the boundaries of the geographic areas served by each depot, the list of customers visited each day and the routes followed by the gangs. The objective is to provide improved customer service at minimum operating cost subject to constraints on frequency of visits, service time requirements, customer preferences for visiting on particular days and other routing constraints. The problem is solved as a Multi-Depot Period Vehicle Routing Problem (MDPVRP). The computational implementation of the complete planning model is described with reference to a pilot study and results are presented. The solution algorithm is used to construct cost-service trade-off curves for all depots so that management can evaluate the impact of different customer service levels on total routing costs.     

A heuristic algorithm for the asymmetric capacitated vehicle routing problem

We consider the Asymmetric Capacitated Vehicle Routing Problem (ACVRP[, a particular case of the standard asymmetric Vehicle Routing Problem arising when only the vehicle capacity constraints are imposed. ACVRP is known to be NP-hard and finds practical applications, e.g. in distribution and scheduling. In this paper we describe the extension to ACVRP of the two well-known Clarke-Wright and Fisher-Jaikumar heuristic algorithms. We also propose a new heuristic algorithm for ACVRP that, starting with an initial infeasible solution, determines the final set of vehicle routes through an insertion procedure as well as intea-route and inter-route arc exchanges. The initial infeasible solution is obtained by using the additive bounding procedures for ACVRP described by Fischetti, Toth and Vigo in 1992. Extensive computational results on several classes of randomly generated test problems involving up to 300 customers and on some real instances of distribution problems in urban areas, are presented. The results obtained show that the proposed approach favourably compares with previous algorithms from the literature.     

有时间窗的车辆路径问题的局部下降搜索算法

介绍了一个求解有时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)的启发式算法——基于λ-交换的局部下降搜索算法(Local search descent method based on λ-interchange).VRPTW是指合理安排车辆行驶路线,为一组预先设定有时间限制的客户运送货物,在不违反时间要求和车辆容量限制的条件下使得成本最小.它是一个典型的NP-难题,可以通过启发式算法获得近优解来解决.通过两个实验验证,显示了局部下降搜索算法的优良性能,取得了很好的效果,可以作为进一步研究复杂算法的基础.     

Vehicle routing in the 1-skip collection problem

In this paper, we consider a real problem, which we call the 1-skip collection problem, where a fleet of vehicles must collect a number of skips situated in different locations and transport them to one among different plants chosen on the basis of the kind of waste contained in the skip. Each vehicle has a capacity of one skip and it starts and ends its tour at the depot. Each time a vehicle collects a skip, it has to go to a plant and empty it. A number of constraints are imposed, which involve time windows for the customers and the plants, shift-time, different kinds of skips, number of drivers available to carry out the service and priorities assigned to the customers who have to be served. The objective is to minimize the total cost of the service given by the fixed cost of the drivers engaged to carry out the service, the cost of the extra time and the penalty cost paid if a customer is not served. A heuristic algorithm to solve the real problem is presented. The algorithm first constructs a feasible solution by means of the nearest-neighbour algorithm. Then, if it finds a feasible solution, it improves it. The computational results show that the solution of the algorithm is much better than the solution applied by the firm that carries out the service since it serves a higher number of skips with a smaller number of drivers.     

A column generation algorithm for the vehicle routing problem with soft time windows

The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visited in a specified time window. We consider the case in which time window constraints are relaxed into “soft” constraints, that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. We present a branch-and-price algorithm which is the first exact optimization algorithm for this problem.     

The multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This paper concerns a generalization of the traveling salesman problem (TSP) called multi-commodity one-to-one pickup-and-delivery traveling salesman problem (m-PDTSP) in which cities correspond to customers providing or requiring known amounts of m different commodities, and the vehicle has a given upper-limit capacity. Each commodity has exactly one origin and one destination, and the vehicle must visit each customer exactly once. The problem can also be defined as the capacitated version of the classical TSP with precedence constraints. This paper presents two mixed integer linear programming models, and describes a decomposition technique for each model to find the optimal solution. Computational experiments on instances from the literature and randomly generated compare the techniques and show the effectiveness of our implementation.     

Integer linear programming models for a cement delivery problem

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods.     

Large scale stochastic inventory routing problems with?split delivery and service level constraints

A stochastic inventory routing problem (SIRP) is typically the combination of stochastic inventory control problems and NP-hard vehicle routing problems, which determines delivery volumes to the customers that the depot serves in each period, and vehicle routes to deliver the volumes. This paper aims to solve a large scale multi-period SIRP with split delivery (SIRPSD) where a customer??s delivery in each period can be split and satisfied by multiple vehicle routes if necessary. This paper considers SIRPSD under the multi-criteria of the total inventory and transportation costs, and the service levels of customers. The total inventory and transportation cost is considered as the objective of the problem to minimize, while the service levels of the warehouses and the customers are satisfied by some imposed constraints and can be adjusted according to practical requests. In order to tackle the SIRPSD with notorious computational complexity, we first propose an approximate model, which significantly reduces the number of decision variables compared to its corresponding exact model. We then develop a hybrid approach that combines the linearization of nonlinear constraints, the decomposition of the model into sub-models with Lagrangian relaxation, and a partial linearization approach for a sub model. A near optimal solution of the model found by the approach is used to construct a near optimal solution of the SIRPSD. Randomly generated instances of the problem with up to 200 customers and 5 periods and about 400 thousands decision variables where half of them are integer are examined by numerical experiments. Our approach can obtain high quality near optimal solutions within a reasonable amount of computation time on an ordinary PC.     

A memetic algorithm for the Multi Trip Vehicle Routing Problem

We consider the Multi Trip Vehicle Routing Problem, in which a set of geographically scattered customers have to be served by a fleet of vehicles. Each vehicle can perform several trips during the working day. The objective is to minimize the total travel time while respecting temporal and capacity constraints.     

Exact solution of the soft-clustered vehicle-routing problem

The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We show that even with all the recent acceleration techniques (e.g., partial pricing, bidirectional labeling, decremental state space relaxation) available for SPPRC labeling algorithms, the solution of the subproblem remains extremely difficult. The main contribution is the modeling and solution of the subproblem using a branch-and-cut algorithm. The conducted computational experiments prove that branch-and-price equipped with this integer programming-based approach outperforms sophisticated labeling-based algorithms by one order of magnitude. The largest SoftCluVRP instances solved to optimality have more than 400 customers or more than 50 clusters.     

Probabilistic analysis of a capactiated vehicle routing problem—I

A fleet of vehicles located at a service center must serve the demands of a set of customers. The amount delivered by each vehicle cannot exceed its capacity and a customer’s demand may not be split over more than one vehicle. In our model, customers locations, as well as their demands are independent identically distributed. Simchi-Levi and Bramel [10] determined the asymptotic value of the optimal solution in this model. We prove here a sharp rate of convergence to the asymptotic value     

线形网络上单台车辆分群调度问题

本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化时间表长。该问题分两种形式:返回型和不返回型。返回型的时间表长定义为机器服务完所有客户后返回其初始位置的时间;不返回型的时间表长则定义为所有客户的最大完工时间。我们的结果是:对每个客户服务时间为零的情形,证明了两种形式均可在O(n²) 时间内解决;对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了16/9和13/7近似算法。     

The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.     

A tabu search algorithm for the multi-trip vehicle routing and scheduling problem

This paper describes a novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers' schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.     

Branch and price for the vehicle routing problem with discrete split deliveries and time windows

The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) consists of designing the optimal set of routes to serve, at least cost, a given set of customers while respecting constraints on vehicles’ capacity and customer time windows. Each customer can be visited by more than one vehicle since each customer’s demand, discretized in items, can be split in orders, i.e., feasible combinations of items. In this work, we model the DSDVRPTW assuming that all feasible orders are known in advance. Remarkably, service time at customer’s location depends on the delivered combination of items, which is a modeling feature rarely found in literature. We present a flow-based mixed integer program for the DSDVRPTW, we reformulate it via Dantzig-Wolfe and we apply column generation. The proposed branch-and-price algorithm largely outperforms a commercial solver, as shown by computational experiments on Solomon-based instances. A comparison in terms of complexity between constant service time vs delivery-dependent service time is presented and potential savings are discussed.     

Modelling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems

Many research papers have presented mathematical models for vehicle scheduling. Several of these models have been embedded in commercial decision support systems for intra-city vehicle scheduling for launderies, grocery stores, banks, express mail customers, etc. Virtually all of these models ignore the important issue of time-dependent travel speeds for intra-city travel. Travel speeds (and times) in nearly all metropolitan areas change drastically during the day because of congestion in certain parts of the city road network. The assumption of constant (time-independent) travel speeds seriously affects the usefulness of these models. This is particularly true when time windows (earliest and latest stop time constraints) and other scheduling issues are important. This research proposes a parsimonious model for time-dependent travel speeds and several approaches for estimating the parameters for this model. An example is presented to illustrate the proposed modelling approach. The issue of developing algorithms to find near-optimal vehicle schedules with time-dependent travel speeds is also discussed. The modelling approach presented in this paper has been implemented in a commercial courier vehicle scheduling system and was judged to be ‘very useful’ by users in a number of different metropolitan areas in the United States.     

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.