A worst-case analysis for the split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.     

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     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

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.     

A goal programming approach to vehicle routing problems with soft time windows

The classical vehicle routing problem involves designing a set of routes for a fleet of vehicles based at one central depot that is required to serve a number of geographically dispersed customers, while minimizing the total travel distance or the total distribution cost. Each route originates and terminates at the central depot and customers demands are known. In many practical distribution problems, besides a hard time window associated with each customer, defining a time interval in which the customer should be served, managers establish multiple objectives to be considered, like avoiding underutilization of labor and vehicle capacity, while meeting the preferences of customers regarding the time of the day in which they would like to be served (soft time windows). This work investigates the use of goal programming to model these problems. To solve the model, an enumeration-followed-by-optimization approach is proposed which first computes feasible routes and then selects the set of best ones. Computational results show that this approach is adequate for medium-sized delivery problems.     

A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers

The purpose of this article is to propose a perturbation metaheuristic for the vehicle routing problem with private fleet and common carrier (VRPPC). This problem consists of serving all customers in such a way that (1) each customer is served exactly once either by a private fleet vehicle or by a common carrier vehicle, (2) all routes associated with the private fleet start and end at the depot, (3) each private fleet vehicle performs only one route, (4) the total demand of any route does not exceed the capacity of the vehicle assigned to it, and (5) the total cost is minimized. This article describes a new metaheuristic for the VRPPC, which uses a perturbation procedure in the construction and improvement phases and also performs exchanges between the sets of customers served by the private fleet and the common carrier. Extensive computational results show the superiority of the proposed metaheuristic over previous methods.     

Optimal fleet replacement: A case study on a Spanish urban transport fleet

Optimizing the average annual cost of a bus fleet has become an increasing concern in transport companies management around the world. Nowadays, there are many tools available to assist managerial decisions, and one of the most used is the cost analysis of the life cycle of an asset, known as “life cycle cost”. Characterized by performing deterministic analysis of the situation, it allows the administration to evaluate the process of fleet replacement but is limited by not contemplating certain intrinsic variations related to vehicles and for disregarding variables related to exigencies of fleet use. The main purpose of this study is to develop a combined model of support to asset management based in the association of the life cycle cost tool and the mathematical model of Monte Carlo simulation, by performing a stochastic analysis considering both age and average annual mileage for optimum vehicle replacement. The utilized method was applied in a Spanish urban transport fleet, and the results indicate that the use of the stochastic model was more effective than the use of the deterministic model.     

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.     

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.     

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances.     

Prototype fleet optimization model

Product development in the automotive industry is a complex process that involves extensive testing of components, subsystems, systems and full vehicles. A fleet of unique individually manufactured vehicles must be built and scheduled amongst different major system activities to be used in comprehensive testing programs. In this paper we present a multi-stage mathematical programming model, set covering plus scheduling, that has been used to restructure the development of the prototype fleet and the assignment of tests to specific vehicles. A basic version of the model implemented on a complex vehicle program produced a 25% reduction in fleet size as compared to the forecast originally made by the company. In addition, the model was the driver for the restructuring of the prototype planning process. In presenting this model, we will describe: (a) the model development process including structuring of the input and output to meet customer needs, (b) model structure, (c) keys to implementation success, and (d) the system's overall impact on the prototype planning process.     

A tabu search heuristic for the vehicle routing problem with private fleet and common carrier

This paper describes a tabu search heuristic for a vehicle routing problem where the owner of a private fleet can either visit a customer with one of his vehicles or assign the customer to a common carrier. The owner’s objective is to minimize the variable and fixed costs for operating his fleet plus the total costs charged by the common carrier. The proposed tabu search is shown to outperform the best approach reported in the literature on 34 benchmark instances with a homogeneous fleet.     

突发事件应急医疗物资调度的随机算法

传统的车辆路径问题(VRP)是为车辆设计将物资从仓库运送到各个需求客户的路线,使得总的运输费用(或时间)最小。在本文中,我们更关心的是使得未满足的需求量和总的物资延误时间最小。这个模型的一个非常重要的应用就是当大规模突发事件发生以后如何有效的将应急医疗物资运送到各个医疗单位,例如自然灾难,恐怖袭击之后,各个医院的医疗物资有限,需要从应急中心调集所需物资,在这种情况下,从应急中心分发应急物资过程中的运输费用就不再是最主要的考查因素,而更重要的是考虑物资到达医院的时间以及到达量,因为这两个因素直接与病人生命息息相关。本文的主要工作是改进了已有的局部搜索算法,通过引入随机算法的思想设计了求解模型的改进随机算法,可以得到模型更优的解,并通过计算机模拟案例说明了算法是行之有效的。     

A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints

The two-dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) is a variant of the classical vehicle routing problem in which customers are served by a heterogeneous fleet of vehicles. These vehicles have different capacities, fixed and variable operating costs, length and width in dimension, and two-dimensional loading constraints. The objective of this problem is to minimize transportation cost of designed routes, according to which vehicles are used, to satisfy the customer demand. In this study, we proposed a simulated annealing with heuristic local search (SA_HLS) to solve the problem and the search was then extended with a collection of packing heuristics to solve the loading constraints in 2L-HFVRP. To speed up the search process, a data structure was used to record the information related to loading feasibility. The effectiveness of SA_HLS was tested on benchmark instances derived from the two-dimensional loading vehicle routing problem (2L-CVRP). In addition, the performance of SA_HLS was also compared with three other 2L-CVRP models and four HFVRP methods found in the literature.     

A survey of recent research on location-routing problems

The design of distribution systems raises hard combinatorial optimization problems. For instance, facility location problems must be solved at the strategic decision level to place factories and warehouses, while vehicle routes must be built at the tactical or operational levels to supply customers. In fact, location and routing decisions are interdependent and studies have shown that the overall system cost may be excessive if they are tackled separately. The location-routing problem (LRP) integrates the two kinds of decisions. Given a set of potential depots with opening costs, a fleet of identical vehicles and a set of customers with known demands, the classical LRP consists in opening a subset of depots, assigning customers to them and determining vehicle routes, to minimize a total cost including the cost of open depots, the fixed costs of vehicles used, and the total cost of the routes. Since the last comprehensive survey on the LRP, published by Nagy and Salhi (2007), the number of articles devoted to this problem has grown quickly, calling a review of new research works. This paper analyzes the recent literature (72 articles) on the standard LRP and new extensions such as several distribution echelons, multiple objectives or uncertain data. Results of state-of-the-art metaheuristics are also compared on standard sets of instances for the classical LRP, the two-echelon LRP and the truck and trailer problem.     

A min–max vehicle routing problem with split delivery and heterogeneous demand

In this article, we introduce a new variant of min–max vehicle routing problem, where various types of customer demands are satisfied by heterogeneous fleet of vehicles and split delivery of services is allowed. We assume that vehicles may serve one or more types of service with unlimited service capacity, and varying service and transfer speed. A heuristic solution approach is proposed. We report the solutions for several test problems.     

Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier

The problem reported in this paper is a variant of the classical vehicle routing problem, where customer requests for a transportation company can be served either by its private fleet of vehicles or assigned to an external common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economical to do so. Accordingly, the objective is to minimize the variable and fixed costs of the private fleet plus the costs charged by the common carrier. A tabu search heuristic with a neighbourhood structure based on ejection chains is proposed to solve this problem. It is empirically demonstrated that this algorithm outperforms the best approaches reported in the literature on a set of benchmark instances with both homogeneous and heterogeneous fleets.     

A sweep-based algorithm for the fleet size and mix vehicle routing problem

This paper presents a new sweep-based heuristic for the fleet size and mix vehicle routing problem. This problem involves two kinds of decisions: the selection of a mix of vehicles among the available vehicle types and the routing of the selected fleet. The proposed algorithm first generates a large number of routes that are serviced by one or two vehicles. The selection of routes and vehicles to be used is then made by solving to optimality, in polynomial time, a set-partitioning problem having a special structure. Results on a set of benchmark test problems show that the proposed heuristic produces excellent solutions in short computing times. Having a fast but good solution method is needed for transportation companies that rent a significant part of their fleet and consequently can take advantage of frequent changes in fleet composition. Finally, the proposed heuristic produced new best-known solutions for three of the test problems; these solutions are reported.     

Real-time management of vehicle breakdowns in urban freight distribution

This paper considers a problem in which an unexpected event immobilises a vehicle of a distribution fleet permanently, and the remaining vehicles are rerouted to serve some of the clients of the failed vehicle. We model this case as a variation of the Team Orienteering Problem (TOP), constraining all vehicle routes to an upper time, or distance, limit, and taking into account the limited capacity of the fleet vehicles. The problem requires an effective solution in almost real time. We propose a new heuristic to provide efficient solutions within this strict computational time constraint. To test the quality of the heuristic, we have developed and validated a Genetic Algorithm (GA) that obtains high quality (but computationally expensive) solutions. The solutions of the heuristic compare favorably to those obtained by the GA. The latter has also been tested successfully in a real-time fleet management system.     

An adaptive memory algorithm for the split delivery vehicle routing problem

The split delivery vehicle routing problem (SDVRP) relaxes routing restrictions forcing unique deliveries to customers and allows multiple vehicles to satisfy customer demand. Split deliveries are used to reduce total fleet cost to meet those customer demands. We provide a detailed survey of the SDVRP literature and define a new constructive algorithm for the SDVRP based on a novel concept called the route angle control measure. We extend this constructive approach to an iterative approach using adaptive memory concepts, and then add a variable neighborhood descent process. These three new approaches are compared to exact and heuristic approaches by solving the available SDVRP benchmark problem sets. Our approaches are found to compare favorably with existing approaches and we find 16 new best solutions for a recent 21 problem benchmark set.