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.     

A unified heuristic for a large class of Vehicle Routing Problems with Backhauls

The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the literature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented, and a unified model is developed that is capable of handling most variants of the problem from the literature. The unified model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Backhauls for the individual customers or vehicles.     

A methodology to solve large-scale cooperative transportation planning problems

In this paper, we suggest a methodology to solve a cooperative transportation planning problem and to assess its performance. The problem is motivated by a real-world scenario found in the German food industry. Several manufacturers with same customers but complementary food products share their vehicle fleets to deliver their customers. After an appropriate decomposition of the entire problem into sub problems, we obtain a set of rich vehicle routing problems (VRPs) with time windows for the delivery of the orders, capacity constraints, maximum operating times for the vehicles, and outsourcing options. Each of the resulting sub problems is solved by a greedy heuristic that takes the distance of the locations of customers and the time window constraints into account. The greedy heuristic is improved by an appropriate Ant Colony System (ACS). The suggested heuristics to solve the problem are assessed within a dynamic and stochastic environment in a rolling horizon setting using discrete event simulation. We describe the used simulation infrastructure. The results of extensive simulation experiments based on randomly generated problem instances and scenarios are provided and discussed. We show that the cooperative setting outperforms the non-cooperative one.     

Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm

In this paper, the dynamic capacitated location-routing problem with fuzzy demands (DCLRP-FD) is considered. In the DCLRP-FD, facility location problem and vehicle routing problem are solved on a time horizon. Decisions concerning facility locations are permitted to be made only in the first time period of the planning horizon but, the routing decisions may be changed in each time period. Furthermore, the vehicles and depots have a predefined capacity to serve the customers with altering demands during the time horizon. It is assumed that the demands of customers are fuzzy variables. To model the DCLRP-FD, a fuzzy chance-constrained programming is designed based upon the fuzzy credibility theory. To solve this problem, a hybrid heuristic algorithm (HHA) with four phases including the stochastic simulation and a local search method are proposed. To achieve the best value of two parameters of the model, the dispatcher preference index (DPI) and the assignment preference index (API), and to analyze their influences on the final solution, numerical experiments are carried out. Moreover, the efficiency of the HHA is demonstrated via comparing with the lower bound of solutions and by using a standard benchmark set of test problems. The numerical examples show that the proposed algorithm is robust and could be used in real world problems.     

A multi-level composite heuristic for the multi-depot vehicle fleet mix problem

The problem of simultaneously allocating customers to depots, finding the delivery routes and determining the vehicle fleet composition is addressed. A multi-level composite heuristic is proposed and two reduction tests are designed to enhance its efficiency. The proposed heuristic is tested on benchmark problems involving up to 360 customers, 2 to 9 depots and 5 different vehicle capacities. When tested on the special case, the multi-depot vehicle routing, our heuristic yields solutions almost as good as those found by the best known heuristics but using only 5 to 10% of their computing time. Encouraging results were also obtained for the case where the vehicles have different capacities.     

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.     

Open vehicle routing problem with driver nodes and time deadlines

In this paper, we consider a variant of the open vehicle routing problem in which vehicles depart from the depot, visit a set of customers, and end their routes at special nodes called driver nodes. A driver node can be the home of the driver or a parking lot where the vehicle will stay overnight. The resulting problem is referred to as the open vehicle routing problem with driver nodes (OVRP-d). We consider three classes of OVRP-d: with no time constraints, with a maximum route duration, and with both a maximum route duration as well as time deadlines for visiting customers. For the solution of these problems, which are not addressed previously in the literature, we develop a new tabu search heuristic. Computational results on randomly generated instances indicate that the new heuristic exhibits a good performance both in terms of the solution quality and computation time.     

A stochastic dynamic traveling salesman problem with hard time windows

Just-in-time (JIT) trucking service, i.e., arriving at customers within specified time windows, has become the norm for freight carriers in all stages of supply chains. In this paper, a JIT pickup/delivery problem is formulated as a stochastic dynamic traveling salesman problem with time windows (SDTSPTW). At a customer location, the vehicle either picks up goods for or delivers goods from the depot, but does not provide moving service to transfer goods from one location to another. Such routing problems are NP-hard in deterministic settings, and in our context, complicated further by the stochastic, dynamic nature of the problem. This paper develops an efficient heuristic for the SDTSPTW with hard time windows. The heuristic is shown to be useful both in controlled numerical experiments and in applying to a real-life trucking problem.     

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

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

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

带时间窗分车运输同时收发车辆路径问题及其启发式算法

本文结合汽车零部件第三方物流的实际背景,提出了带时间窗的可分车运输同时收发车辆路径问题(简称SVRPSPDTW),并给出了问题的数学模型,同时提出两个求解该问题的启发式算法,最后进行了数值试验.由于没有可以利用的算例,本文在Solomn测试基准库的基础上构建了针对新问题的算例.计算结果表明,所有算例计算时间均不超过1秒,且算法1无论是从车辆的使用数还是从车辆行驶的路径总长度上都明显优于算法2,从而说明算法1是寻找SVRPSPDTW问题初始可行解的较为有效的算法.     

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.     

Validating vehicle routing zone construction using Monte Carlo simulation

The primary purpose of this paper is to validate a clustering procedure used to construct contiguous vehicle routing zones (VRZs) in metropolitan regions. Given a set of customers with random demand for pickups and deliveries over the day, the goal of the design problem is to cluster the customers into zones that can be serviced by a single vehicle. Monte Carlo simulation is used to determine the feasibility of the zones with respect to package count and tour time. For each replication, a separate probabilistic traveling salesman problem (TSP) is solved for each zone. For the case where deliveries must precede pickups, a heuristic approach to the TSP is developed and evaluated, also using Monte Carlo simulation. In the testing, performance is measured by overall travel costs and the probability of constraint violations. Gaps in tour length, tour time and tour cost are the measure used when comparing exact and heuristic TSP solutions.     

A practical solution approach for the cyclic inventory routing problem

Vendor managed inventory (VMI) is an example of effective cooperation and partnering practices between up- and downstream stages in a supply chain. In VMI, the supplier takes the responsibility for replenishing his customers’ inventories based on their consumption data, with the aim of optimizing the over all distribution and inventory costs throughout the supply chain. This paper discusses the challenging optimization problem that arises in this context, known as the inventory routing problem (IRP). The objective of this IRP problem is to determine a distribution plan that minimizes average distribution and inventory costs without causing any stock-out at the customers. Deterministic constant customer demand rates are assumed and therefore, a long-term cyclical approach is adopted, integrating fleet sizing, vehicle routing, and inventory management. Further, realistic side-constraints such as limited storage capacities, driving time restrictions and constant replenishment intervals are taken into account. A heuristic solution approach is proposed, analyzed and evaluated against a comparable state-of-the-art heuristic.     

A zero-inventory production and distribution problem with a fixed customer sequence

In this paper, we study the zero-inventory production and distribution problem with a single transporter and a fixed sequence of customers. The production facility has a limited production rate, and the delivery truck has non-negligible traveling times between locations. The order in which customers may receive deliveries is fixed. Each customer requests a delivery quantity and a time window for receiving the delivery. The lifespan of the product starts as soon as the production for a customer’s order is finished, which makes the product expire in a constant time. Since the production facility and the shipping truck are limited resources, not all the customers may receive the delivery within their specified time windows and/or within product lifespan. The problem is then to choose a subset of customers from the given sequence to receive the deliveries to maximize the total demand satisfied, without violating the product lifespan, the production/distribution capacity, and the delivery time window constraints. We analyze several fundamental properties of the problem and show that these properties can lead to a fast branch and bound search procedure for practical problems. A heuristic lower bound on the optimal solution is developed to accelerate the search. Empirical studies on the computational effort required by the proposed search procedure comparing to that required by CPLEX on randomly generated test cases are reported.     

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.     

Integrated production and distribution scheduling with lifespan constraints

We consider an integrated production and distribution scheduling problem in a make-to-order business scenario. A product with a short lifespan (e.g., perishable or seasonal) is produced at a single production facility with a limited production rate. This means that the product expires in a constant time after its production is finished. Orders are received from a set of geographically dispersed customers, where a demand for the product and a time window for the delivery is associated with each customer for the planning period. A single vehicle with non-negligible traveling times between the locations is responsible for the deliveries. Due to the limited production and distribution resources, possibly not all customers may be supplied within their time windows or the lifespan. The problem consists in finding a selection of customers to be supplied such that the total satisfied demand is maximized. We extend the work by Armstrong et al. (Annals of Operations Research 159(1):395–414, 2008) on the problem for fixed delivery sequences by pointing out an error in their branch and bound algorithm and presenting a corrected variant. Furthermore, we introduce model extensions for handling delays of the production start as well as for variable production and distribution sequences. Efficient heuristic solution algorithms and computational results for randomly generated instances are presented.     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

2-Facility manifold location routing problem

The location routing problem (LRP), known to be the combination of the facility location and vehicle routing problems, is solved in the literature by either assuming planar or spherical surfaces. In this work, the manifold location routing problem (MLRP), that is an LRP on Riemannian manifold surfaces, is explained for the 2-facility (2-MLRP) case with the corresponding heuristic algorithm solution. The 2-MLRP problem is a mixed integer non-linear programming problem that is determined to be NP-hard. Special cases of MLRP include LRP on planar surfaces, when the manifold’s curvature is 0, and LRP on spherical surfaces when the curvature of the manifold is 1.