2.30 Split Solving

Split solve is a divide-and-conquer strategy for the solver. Instead of solving one large scenario as a single optimisation problem, it partitions the scenario into several independent sub-scenarios, solves each one independently, and then combines the sub-solutions into one final solution.

Partitioning is done via time-window overlap. Orders and vehicles are grouped into categories whose maximal time windows overlap; groups that don’t overlap in time end up in separate sub-scenarios, because they can never share a vehicle’s route.

Split solve may be beneficial primarily due to the reduction in combinatorial complexity. A scenario which is twice as large may take more than twice the time to solve. Partitioning a large scenario into independent sub-scenarios means each solver searches a much smaller space, and the sum of these small searches finishes far faster than one search over the whole. Additionally, the sub-scenarios may be solved concurrently, so there may be additional wall-clock gain in addition to the search-space gain.

2.30.1 Example

A regional carrier runs a fleet doing two disjoint shifts. Consider a day-plus-night operation: a morning depot has  40 delivery orders all with time windows between 06:00 and 12:00, served by a set of vehicles whose shifts also sit in the morning. A separate batch of  40 orders has windows between 18:00 and 23:00, served by an evening fleet whose shifts sit in the evening. There’s a midday gap where nothing overlaps.

Here the time windows partition cleanly into a morning sub-scenario and an evening sub-scenario with no intersection.