Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach

We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Computational results obtained by experimenting with well-known problem instances are reported.     

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 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.     

Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.     

A two-phase hybrid metaheuristic for the vehicle routing problem with time windows

The subject of this paper is a two-phase hybrid metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The objective function of the VRPTW considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance (secondary criterion). The aim of the first phase is the minimization of the number of vehicles by means of a (μ,λ)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm. The two-phase hybrid metaheuristic was subjected to a comparative test on the basis of 356 problems from the literature with sizes varying from 100 to 1000 customers. The derived results show that the proposed two-phase approach is very competitive.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

Dynamic scheduling of recreational rental vehicles with revenue management extensions

The rental fleet scheduling problem (RFSP) arises in vehicle-rental operations that offer a wide variety of vehicle types to customers, and allow a rented vehicle to ‘migrate’ to a setdown depot other than the pickup depot.When there is a shortage of vehicles of a particular type at a depot, vehicles may be relocated to that depot, or vehicles of similar types may be substituted.The RFSP involves assigning vehicles to rentals so as to minimise the costs of these operations, and arises in both static and online contexts. The authors have adapted a well-known assignment algorithm for application in the online context. In addition, a network-flow algorithm with more comprehensive coverage of problem conditions is used to investigate the determination of rental pricing using revenue management principles. The paper concludes with an outline of the algorithms’ use in supporting the operations of a large recreational vehicle rental company.     

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.     

Robust vehicle routing problem with deadlines and travel time/demand uncertainty

In this article, we investigate the vehicle routing problem with deadlines, whose goal is to satisfy the requirements of a given number of customers with minimum travel distances while respecting both of the deadlines of the customers and vehicle capacity. It is assumed that the travel time between any two customers and the demands of the customer are uncertain. Two types of uncertainty sets with adjustable parameters are considered for the possible realizations of travel time and demand. The robustness of a solution against the uncertain data can be achieved by making the solution feasible for any travel time and demand defined in the uncertainty sets. We propose a Dantzig-Wolfe decomposition approach, which enables the uncertainty of the data to be encapsulated in the column generation subproblem. A dynamic programming algorithm is proposed to solve the subproblem with data uncertainty. The results of computational experiments involving two well-known test problems show that the robustness of the solution can be greatly improved.     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.     

Exact algorithms for the vehicle routing problem,based on spanning tree and shortest path relaxations

We consider the problem of routing vehicles stationed at a central facility (depot) to supply customers with known demands, in such a way as to minimize the total distance travelled. The problem is referred to as the vehicle routing problem (VRP) and is a generalization of the multiple travelling salesman problem that has many practical applications. We present tree search algorithms for the exact solution of the VRP incorporating lower bounds computed from (i) shortest spanningk-degree centre tree (k-DCT), and (ii)q-routes. The final algorithms also include problem reduction and dominance tests. Computational results are presented for a number of problems derived from the literature. The results show that the bounds derived from theq-routes are superior to those fromk-DCT and that VRPs of up to about 25 customers can be solved exactly.     

Swarm intelligence-based hyper-heuristic for the vehicle routing problem with prioritized customers

The vehicle routing problem (VRP) is a combinatorial optimization management problem that seeks the optimal set of routes traversed by a vehicle to deliver products to customers. A recognized problem in this domain is to serve ‘prioritized’ customers in the shortest possible time where customers with known demands are supplied by one or several depots. This problem is known as the Vehicle Routing with Prioritized Customers (VRPC). The purpose of this work is to present and compare two artificial intelligence-based novel methods that minimize the traveling distance of vehicles when moving cargo to prioritized customers. Various studies have been conducted regarding this topic; nevertheless, up to now, few studies used the Cuckoo Search-based hyper-heuristic. This paper modifies a classical mathematical model that represents the VRPC, implements and tests an evolutionary Cuckoo Search-based hyper-heuristic, and then compares the results with those of our proposed modified version of the Clarke Wright (CW) algorithm. In this modified version, the CW algorithm serves all customers per their preassigned priorities while covering the needed working hours. The results indicate that the solution selected by the Cuckoo Search-based hyper-heuristic outperformed the modified Clarke Wright algorithm while taking into consideration the customers’ priority and demands and the vehicle capacity.

     

Polyhedral study of the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495.     

An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls

In this article, a visual interactive approach based on a new greedy randomised adaptive memory programming search (GRAMPS) algorithm is proposed to solve the heterogeneous fixed fleet vehicle routing problem (HFFVRP) and a new extension of the HFFVRP, which is called heterogeneous fixed fleet vehicle routing problem with backhauls (HFFVRPB). This problem involves two different sets of customers. Backhaul customers are pickup points and linehaul customers are delivery points that are to be serviced from a single depot by a heterogeneous fixed fleet of vehicles, each of which is restricted in the capacity it can carry, with different variable travelling costs.     

The min-max multi-depot vehicle routing problem: heuristics and computational results

In the multi-depot vehicle routing problem (MDVRP), there are several depots where vehicles can start and end their routes. The objective is to minimize the total distance travelled by all vehicles across all depots. The min-max multi-depot vehicle routing problem (Min-Max MDVRP) is a variant of the standard MDVRP. The primary objective is to minimize the length of the longest route. We develop a heuristic (denoted by MD) for the Min-Max MDVRP that has three stages: (1) simplify the multi-depot problem into a single depot problem and solve the simplified problem; (2) improve the maximal route; (3) improve all routes by exchanging customers between routes. MD is compared with two alternative heuristics that we also develop and an existing method from the literature on a set of 20 test instances. MD produces 15 best solutions and is the top performer. Additional computational experiments on instances with uniform and non-uniform distributions of customers and varying customer-to-vehicle ratios and with real-world data further demonstrate MD’s effectiveness in producing high-quality results.     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

Exact algorithms for the chance-constrained vehicle routing problem

We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly \(\mathcal {NP}\)-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. We also demonstrate how our proposed methodologies can be adapted to solve a distributionally robust CCVRP problem. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices.     

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.