We address a single commodity Pickup and Delivery Vehicle Routing Problem from the literature. A network of customer nodes is given with both travel times and costs. A fleet of vehicles of limited capacity is exploited to satisfy node demands, and a set of routes must be found such that the vehicle capacities are never exceeded, each route does not exceed time resource, and cost is minimized. The demands of both pickup and delivery nodes can be split, and each node can be visited more than once. We provide new theoretical insights. We propose a new formulation where routes are decomposed into sequences of simpler substructures called clusters, mitigating the combinatorial explosion of feasible solutions. We introduce valid inequalities, and design a branch-and-price algorithm, exploiting ad hoc pricing routines and branching strategies, and embedding a rounding heuristic to speed up pruning. An extensive experimental analysis shows our method to offer simultaneously more modelling flexibility and more computational effectiveness than previous attempts from the literature. Our investigation opens also interesting insights into the use of route decomposition strategies.
A route decomposition approach for the single commodity Split Pickup and Split Delivery Vehicle Routing Problem
2019-07-10
Article (Journal)
Electronic Resource
English
DDC: | 000 |
The split-demand one-commodity pickup-and-delivery travelling salesman problem
Online Contents | 2015
|Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads
Online Contents | 2014
|MULTIPLE DEPOT VEHICLE ROUTING PROBLEM WITH SPLIT DELIVERY
TIBKAT | 2020
|