Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery

We propose a branch-and-cut algorithm for the VRPSPD where the constraints that ensure that the capacities are not exceeded in the middle of a route are applied in a lazy fashion. The algorithm was tested in 87 instances with 50–200 customers, finding improved lower bounds and several new optimal solutions.     

A column generation approach for the split delivery vehicle routing problem

A column generation approach is presented for the split delivery vehicle routing problem with large demand. Columns include route and delivery amount information. Pricing sub-problems are solved by a limited-search-with-bound algorithm. Feasible solutions are obtained iteratively by fixing one route once. Numerical experiments show better solutions than in the literature.     

A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars

The purpose of this article is to propose a tabu search heuristic for the split delivery Vehicle Routing Problem with Production and Demand Calendars (VRPPDC). This new problem consists of determining which customers will be served by a common carrier, as well as the delivery routes for those served by the private fleet, in order to minimize the overall transportation and inventory costs. We first model this problem and then propose a simple decomposition procedure that can be used to provide a starting solution. Next, we introduce a new tabu search heuristic and we describe two new neighbor reduction strategies. Finally, we present the results of our extensive computational tests. According to these tests, our reduction strategies are efficient not only at reducing computing time but also at improving the overall solution quality.     

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.     

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.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil

In this paper, we consider a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries that occurs in a major Brazilian retail group. A single depot attends 519 stores of the group distributed in 11 Brazilian states. To find good solutions to this problem, we propose heuristics as initial solutions and a scatter search (SS) approach. Next, the produced solutions are compared with the routes actually covered by the company. Our results show that the total distribution cost can be reduced significantly when such methods are used. Experimental testing with benchmark instances is used to assess the merit of our proposed procedure.     

Maritime crude oil transportation - A split pickup and split delivery problem

The maritime oil tanker routing and scheduling problem is known to the literature since before 1950. In the presented problem, oil tankers transport crude oil from supply points to demand locations around the globe. The objective is to find ship routes, load sizes, as well as port arrival and departure times, in a way that minimizes transportation costs. We introduce a path flow model where paths are ship routes. Continuous variables distribute the cargo between the different routes. Multiple products are transported by a heterogeneous fleet of tankers. Pickup and delivery requirements are not paired to cargos beforehand and arbitrary split of amounts is allowed. Small realistic test instances can be solved with route pre-generation for this model. The results indicate possible simplifications and stimulate further research.     

Local search-based metaheuristics for the split delivery vehicle routing problem

The split delivery vehicle routing problem is a variant of the standard vehiclerouting problem where the single-visit assumption is waived and a customer mightbe served on more than one vehicle tour. In this article we report on a studywhere we have applied the standard local search-based metaheuristics usingadaptations of the most widely used inter-tour and intra-tour exchange operatorsfor solving the standard vehicle routing problem now allowing splitting andjoining of deliveries. As we will show we could find new best solutions for 51out of 57 benchmark instances, which have been defined for this problemclass.     

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.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

An empirical study on the benefit of split loads with the pickup and delivery problem

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has been shown to have benefit for both the classic Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP). However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin–destination pairs with a load requiring service, and the clustering of origin and destination locations. We find that the magnitude of benefit is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.     

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 note on branch-and-cut-and-price

In this paper, we propose a methodology for branch-and-cut-and-price when cuts and columns are generated simultaneously. The methodology is illustrated with two application cases: the Split Delivery Vehicle Routing Problem (SDVRP) and the Bus Rapid Transit Route Design Problem (BRTRDP).     

A branch-and-price algorithm for a vehicle routing with demand allocation problem

We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.     

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.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints

This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the capacitated VRP (CVRP) and the VRP with time windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the CVRP and VRPTW.     

Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery

The vehicle routing problem (VRP) with simultaneous pickup and delivery (VRPSPD) is an extension of the classical capacitated VRP (CVRP). In this paper, we present the saving heuristic and the parallel saving heuristic for VRPSPD. Checking the feasibility of a route in VRPSPD is difficult because of the fluctuating load on the route. In the saving heuristic, a new route is created by merging the two existing routes. We use a cumulative net-pickup approach for checking the feasibility when two existing routes are merged. The numerical results show that the performance of the proposed heuristics is qualitatively better than the existing insertion-based heuristics.