CheapestInsertionTourPolicy

Put each new stop wherever it adds least travel, subject to precedence and capacity.

The default, and the standard heuristic for this problem. Every feasible pair of positions for the pickup and its set-down is tried and the cheapest kept; ties go to the earlier position, so the answer does not depend on the order the candidates happened to be generated in.

Cost is not a consideration: with a load capacity of c there are at most 2c stops, so the search is O(c^2) distance lookups against a precomputed matrix. At any capacity a real fleet has, that is nothing.

It degenerates to the obvious thing. Inserting into an empty tour gives pickup then set-down, which is exactly what a single-load transport has always been — so a fleet of capacity one plans the same tour it would have been given before this seam existed.

Constructors

Link copied to clipboard
constructor()

Functions

Link copied to clipboard
open override fun plan(context: TourContext, remaining: List<TourStop>, insert: List<TourStop>): List<TourStop>
Link copied to clipboard
open override fun toString(): String