Predicting well does not mean deciding well
Three requests arrive together at a logistics service. An AI model estimates how long each vehicle would take to reach each customer. In our first example, the estimates are even exact. Is repeatedly choosing the nearest vehicle–customer pair sufficient? No: assigning a vehicle to one request makes it unavailable to others. A choice that looks good alone can consume a resource that would be much more valuable elsewhere. The problem need not lie in the predictive model, but in the rule converting its estimates into actions.
Abstract. We construct a reproducible case on a line, compare greedy choice with minimum-cost assignment and prove optimality using a checkable lower bound. We then add a vehicle–request incompatibility that turns a locally sensible choice into a dead end, and study how cost errors can change the decision. The goal is to distinguish prediction, optimization and feasibility. No data come from real fleets or customers; we measure neither an AI model’s performance nor business savings.
An example small enough to check
Imagine a straight road that can be travelled in both directions. Vehicles V1, V2 and V3 are at kilometres 0, 3 and 8. Requests A, B and C are at kilometres 1, −2 and 10. The negative sign simply denotes a position left of the origin. Assume constant speed of 1 km/min, no traffic and immediate service on arrival. Each vehicle receives exactly one request and each request exactly one vehicle. We are not building a multi-stop route.
To obtain pair cost cᵢⱼ, take the absolute distance between positions and divide by speed. At our chosen speed, distance in kilometres and time in minutes have the same numerical value. The following matrix contains all alternative times, not nine trips that will be performed. We will choose only three cells, one per row and one per column.
| Vehicle | A (min) | B (min) | C (min) |
|---|---|---|---|
| V1 | 1 | 2 | 10 |
| V2 | 2 | 5 | 7 |
| V3 | 7 | 10 | 2 |
Greedy choice and the cost of a missed opportunity
Define the local rule precisely: among all remaining pairs, take the cheapest, then remove that vehicle and request. This is greedy because it does not reconsider earlier choices. It starts with V1→A, cost 1, then selects V3→C, cost 2. V2 and B remain, costing 5. The total is 8 vehicle-minutes, the sum of the three travel times; this is not eight minutes of elapsed duration when vehicles travel concurrently.
Try V1→B, V2→A and V3→C instead: 2+2+2=6. The first assignment costs one extra minute but lets V2 reach A in two minutes rather than B in five. We pay one to save three, improving the total by two vehicle-minutes. This counterexample disproves “always choosing the local minimum produces the global minimum”; it does not show that every greedy decision is bad or that the same percentage improvement occurs in a real fleet.
Writing the problem exposes its constraints
Let xᵢⱼ equal 1 when vehicle i is assigned to request j, and 0 otherwise. We minimize the sum of selected-cell costs. Two sets of constraints prevent assigning a vehicle twice or leaving a request unserved:
Σ means sum over the indicated indices; ∀ means “for each”. In words, every row and column must contain exactly one choice. The objective is total time, not the worst-served customer’s time, profit or fairness. Changing the objective can change the solution. Although our six-unit plan also improves maximum time, that coincidence does not make sum and maximum interchangeable in general.
Three vehicles have 3!=6 complete assignments. The exclamation mark denotes factorial: three choices for the first vehicle, two for the second and one for the third. The program enumerates them all, finding costs 6, 8, 16, 18, 22 and 22. The minimum therefore does not depend on a lucky attempt. Enumeration costs O(n·n!) when n costs are summed per permutation: transparent for three vehicles, but not a strategy to transfer to large fleets.
How to prove that six really is the minimum
We can also provide a proof more compact than the full list. Give each vehicle a number uᵢ and each request a number vⱼ such that uᵢ+vⱼ never exceeds cᵢⱼ. These are not billed prices, but auxiliary mathematical quantities. For any complete plan, their sum is a lower bound on cost because each vehicle and request appears exactly once.
Check the first row: u₁+v gives [1,2,2], no larger than [1,2,10]. The second gives [2,3,3], below [2,5,7]; the third [1,2,2], below [7,10,2]. Every plan therefore costs at least 6. We already have one costing 6, so none can be better. Negative −1 is allowed because the auxiliary numbers are not physical travel times. This is a dual certificate: an optimality proof checked with nine comparisons and one sum, without trusting an algorithm’s name.
The certificate proves optimality for the written matrix and constraints. It does not prove that travel-time predictions are correct or that every business constraint was included. This matters when an AI agent calls a plan “optimal”: relative to which data, objective and allowed choices? A mathematical proof can be flawless while describing the wrong operational problem.
When a local choice leaves a request without a vehicle
Add a hypothetical constraint: V2 cannot serve B, for example because it lacks a technical requirement of that service. This incompatibility is a case parameter, not a judgment about a person. Imposing x₂B=0 is clearer than inventing a very large travel time and hoping the algorithm avoids it. A finite permitted cost may still be selected in a difficult instance.
Greedy still chooses V1→A and V3→C, then stops at the only remaining pair, now forbidden. The program reports an incomplete plan, not an infinite cost for an actually performed service. Yet V1→B, V2→A, V3→C remains feasible and costs 6. The failure concerns the sequence of irreversible choices, not the existence of a solution. Repair must be allowed to reassign earlier decisions.
If times are predicted, how much error changes the plan?
So far geometry produced exact times. For a separate sensitivity analysis, now treat times as predicted costs and change only V2→A, calling its new value λ minutes. We do not claim this isolated change follows from the same ideal road; it is an abstract forecast update with other cells fixed. The original greedy plan still costs 8. The plan swapping A and B costs λ+4. They tie at λ=4: below that threshold the swap wins; above it the other plan wins.
Read the plot by following the lower branch. The scan uses 101 values from 0 to 10 minutes in steps of 0.1 and checks every assignment, not only the two drawn. A small change may be irrelevant far from the crossing and decisive nearby. Mean time-prediction error alone therefore does not describe decision stability: what matters is where errors fall relative to near-equivalent alternatives.
A simple bound for errors across all pairs
Return to the original matrix. The best assignment costs 6 and the runner-up 8: gap Δ is 2 vehicle-minutes. Suppose each cost can now change by at most ε minutes in absolute value. A plan with n assignments changes by at most nε; comparing two plans, their difference changes by at most 2nε. A sufficient condition to preserve the winner is therefore:
The interpretation is conservative: if every error stays below one third of a minute, no competing assignment can close the whole gap under this bound. It is not a necessary threshold: we counted errors on pairs shared by two plans, which cancel in their comparison. A bound on every cost is also a strong assumption; low average error does not establish it. It must be verified or replaced by an appropriate uncertainty model.
The code sets ε=0.3 minutes and checks all 2⁹=512 extreme combinations of the nine errors, each +ε or −ε. The winner stays unchanged. A linear cost difference reaches its extremes over this uncertainty box at vertices, so the check has meaning for the stated model; it is not a random test on 512 customers. We estimate neither success probability nor a distribution of real errors.
From the teaching case to an operational system
Larger problems use assignment algorithms rather than factorial enumeration. SciPy 1.18.0 documents linear_sum_assignment for rectangular matrices too, using a modified Jonker–Volgenant method. We read its definition, constraints and API notes; we did not run SciPy or reproduce the referenced paper. Standard Python and the explicit certificate verify our result.
Requests arriving over time change the problem: waiting may improve matching but delay a customer. Multiple stops introduce routes and dependencies between trips. Capacity, time windows, charging, shifts and service constraints need additional formulations. An updated matrix is insufficient if a vehicle has already departed: modifiable decisions must be distinguished from executed commitments. Our analysis is a single assignment instant without these dynamic effects.
The answer and what the code lets us check
The nearest vehicle can be right for one customer and wrong for the group. In our case, giving up one minute locally avoids three elsewhere; with an incompatibility, it even avoids leaving a request unassigned. AI may estimate costs, but the system must also represent constraints and compare complete plans. Prediction quality and decision quality are connected through this step, not equivalent. A larger model is not required to fix an algorithm that ignores alternatives.
The short listing enumerates six plans and verifies the certificate. The full archive adds greedy selection, the forbidden pair, the λ scan and 512 perturbations. Tie ordering is deterministic; there is no random generation and no applicable seed. We retain every permutation, so representing them uses O(n·n!) memory, besides the O(n²) matrix. The graph comes from saved results, not generative cover imagery. Running the program checks both the best number and why alternatives fail.
Technical reference and reproducibility
SciPy 1.18.0 — scipy.optimize.linear_sum_assignment.
from itertools import permutations
C = [[1, 2, 10], [2, 5, 7], [7, 10, 2]]
plans = sorted((sum(C[i][j] for i, j in enumerate(p)), p)
for p in permutations(range(3)))
print(plans)
u, v = [2, 3, 2], [-1, 0, 0]
assert all(u[i] + v[j] <= C[i][j] for i in range(3) for j in range(3))
assert sum(u) + sum(v) == plans[0][0] == 6
Code, data, and instructions · JSON. Educational calculations executed with Python 3.14.0; figures with Matplotlib 3.11.2. AI-assisted analysis, without claiming peer review or human review. Original illustrative ImageGen cover: it does not document EL-AI people, premises, or installations. Sources accessed 3 October 2026.