In classical routing problems concerning the delivery of goods, each customer is served exactly once. On the contrary, by allowing split deliveries, customers may be served by means of multiple visits. This potentially results in substantial savings in travel costs, like in the Split Delivery Vehicle Routing Problem (SDVRP), the variant of the Vehicle Routing Problem (VRP) in which split deliveries are allowed (see Archetti and Speranza (2012) and Irnich, Schneider, and Vigo (2014)).
Even if split deliveries are beneficial to the distributor, on the customer side several visits may be undesirable: At each visit the customer has to interrupt his primary activities and handle the delivery.
In order to mitigate the inconveniences to the customers, Gulczynski, Golden, and Wasil (2010) and Xiong et al. (2013) consider a variant of the SDVRP in which split deliveries are allowed only if a minimum fraction of the customer's demand is delivered at each visit.
To the same purpose, but with a different prospective, we investigate the possibility to embed synchronization constraints into the definition of the routing problem: All split deliveries occurring to a customer must take place in a time interval of a given duration. Since time dimension is relevant, we consider the SDVRP with Time Windows (SDVRPTW) and define the corresponding variant with synchronization constraints (S-SDVRPTW). We design a branch-and-cut algorithm able to solve both the SDVRPTW and the S-SDVRPTW, and report on computational results showing the impact of synchronization constraints.