Earlier quoted context omitted.
The cost does not scale linearly with the #of packages. A table with 1 entry is not cheaper than a table with 1 million entries. The same routing algorithms have to run either they have one package or 1 million packages. Plus you need to keep the history of the operations for months if not years (meaning that you will store both holiday and random Tuesday data anyway). So where is this flexible cost exactly?
Ever heard of the traveling salesman problem because that is worse than linear, it is factorial. Granted, that is probably overkill for most people and my team (Not FedEx) just does NxN so it is only quadratic but it is definitely not constant nor even linear.
So for practical applications they are constant time.