Insertion Heuristics for a Class of Dynamic Vehicle Routing Problems

We consider a simple family of dynamic vehicle routing problems, in which we have a fixed fleet of identical vehicles, and customer requests arrive during the route-planning process. For this kind of problem, it is natural to use an insertion heuristic. We test several such heuristics computationally, on two different variants of the problem. It … Read more

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 … Read more

Routing and resource allocation in non-profit settings with equity and efficiency measures under demand uncertainty

Motivated by food distribution operations for non-profit organizations, we study a variant of the stochastic routing-allocation problem under demand uncertainty, in which one decides the assignment of trucks for demand nodes, the sequence of demand nodes to visit (i.e., truck route), and the allocation of food supply to each demand node. We propose three stochastic … Read more

Minimizing earliness-tardiness costs in supplier networks – A Just-in-time Truck Routing Problem

We consider a routing problem where orders are transported just-in-time from several suppliers to an original equipment manufacturer (OEM). This implies that shipments cannot be picked up before their release date when they are ready at the supplier and should be delivered as close as possible to their due date to the OEM. Every shipment … Read more

A new family of route formulations for split delivery vehicle routing problems

We propose a new family of formulations with route-based variables for the split delivery vehicle routing problem with and without time windows. Each formulation in this family is characterized by the maximum number of different quantities of demand that can be delivered to a customer during a vehicle visit. The larger that this number is, … Read more

Effective Exact Solution Framework for Routing Optimization with Time Windows and Travel Time Uncertainty

We consider a vehicle routing problem with time windows under uncertain travel times where the goal is to determine routes for a fleet of homogeneous vehicles to arrive at the locations of customers within their stipulated time windows to the maximum extent, while ensuring that the total travel cost does not exceed a prescribed budget. … Read more

Heuristic approaches for split delivery vehicle routing problems

We propose a matheuristic approach to solve split delivery variants of the vehicle routing problem (VRP). The proposed method is based on the use of several mathematical programming components within an Iterated Local Search metaheuristic framework. In addition to well-known VRP local search heuristics, we include new types of improvement and perturbation strategies that are … Read more

Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm

We study the multi-depot split-delivery vehicle routing problem (MDSDVRP) which combines the advantages and potential cost-savings of multiple depots and split-deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the … Read more

Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) problem with Uncertainties

The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategical fleet-sizing, tactical assignment, operational vehicle routing and scheduling subproblems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a two-stage stochastic mixed-integer linear programming model for … Read more

Decomposition strategies for vehicle routing heuristics

Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterisation of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: we discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight … Read more