Last Mile Delivery and Route Optimization

The short answer

Last mile delivery software decides how a vehicle serves a set of stops in a day. It plans routes, sequences stops, manages delivery time windows, dispatches drivers, supports the driver mobile application and electronic proof of delivery, notifies customers, and in more capable systems re-plans during the day as conditions change. The mathematics underneath is the vehicle routing problem, a generalization of the traveling salesman problem that is NP-hard, which means no algorithm produces a provably optimal answer at realistic scale in useful time. Commercial systems use heuristics and metaheuristics that produce good solutions, and vendor claims of optimal routes are imprecise rather than dishonest. The practical consequence is that solution quality is usually determined by the accuracy of your service times, travel times, and addresses rather than by the solver, which is where evaluations should concentrate.

What does last mile software do, and where does a TMS end?

The functional scope covers route planning and optimization, dynamic re-routing during the day, territory and zone design, delivery time window and appointment management, the driver mobile application and electronic proof of delivery, customer notification and tracking, and dispatch. Some products also handle capacity planning across a week and the reconciliation of driver hours and pay. The common thread is that everything concerns the movement of one vehicle among many stops within a working day.

A transportation management system answers a different question. It plans and executes the movement of freight between facilities: it holds contracted rates, selects carriers and modes, builds loads, tenders shipments, and tracks them through the network. Its unit of work is a shipment moving from one node to another. Last mile software's unit of work is a stop in a sequence. The two meet where freight arrives at a delivery depot and is broken down for local distribution, and a complete estate integrates them, but they are not substitutes and a product strong at one is rarely deep at the other. SCR covers transportation management systems in a separate guide.

Two capabilities sit at the boundary and cause most scoping confusion. Parcel networks blur it because a parcel carrier performs both functions internally and presents a single service to the shipper, so a business shipping exclusively by parcel may need neither category and only a rate shopping and label generation capability. And appointment scheduling appears in both categories with different meanings: in freight it concerns dock slots at a facility, in last mile it concerns a promise to a consumer at a residence. Requirements documents that use the word without qualifying it produce proposals that are not comparable.

Why can no software promise an optimal route?

The problem has a name and a well-documented history. Dantzig and Ramser formalized the truck dispatching problem in 1959, generalizing the traveling salesman problem to a fleet of vehicles serving customers from a depot. Clarke and Wright published the savings algorithm in 1964, which remains a useful construction heuristic. The problem was established as NP-hard, which in practical terms means the time required to guarantee an optimal solution grows faster than any polynomial in the number of stops. For the handful of stops in a textbook example, exact methods work. For a few hundred stops with time windows, they do not.

Figure 1. The escalation. A single tour is the traveling salesman problem. Adding a fleet and capacity gives the vehicle routing problem, already NP-hard. Adding time windows, traffic-dependent travel times, and the possibility that nobody is home moves the problem well beyond anything solvable to proven optimality in an operating window.

What commercial systems actually do is apply metaheuristics: local search, tabu search, large neighborhood search, genetic and evolutionary methods, and various hybrids, sometimes with an exact method solving small subproblems. These find good solutions quickly and improve them until time runs out. They do not certify that no better solution exists. A well-built solver on a well-specified problem will usually land within a few percent of the best known solution, which is more than sufficient for an operation, and that is the accurate way to describe it.

The variants matter because they describe what a product can actually model. The capacitated problem adds vehicle capacity limits. The problem with time windows adds a permitted arrival interval per stop, which is the variant most consumer delivery operations actually face. Pickup and delivery variants handle collections alongside deliveries and any precedence between them. Multi-depot variants allow vehicles to originate from several locations. Dynamic and stochastic variants handle information arriving during the day and uncertainty in travel and service times. Each addition makes the problem harder, and a product that models one well may model another poorly.

Table 1. The main variants. A useful evaluation question is which of these a product models natively rather than approximates, because the difference shows up on the exceptions rather than on the demonstration data.

What determines route quality: the algorithm or the inputs?

Usually the inputs, and by a wide margin. Four data problems defeat good solvers routinely. Service time estimation is the first and most underrated: if the system assumes four minutes at every stop and the real distribution runs from two minutes to twenty depending on the property, the sequence will be plausible and the day will not work. Service times should be estimated by segment, learned from actual arrival and departure data where the driver application captures it, and reviewed as the customer mix changes.

Travel time estimation is the second. Distance is not time, and time varies by hour of day and day of week. A system routing on straight-line distance or on unweighted road distance will produce routes that look efficient and cannot be driven. What matters in an evaluation is whether the product uses time-dependent travel matrices and where that data comes from, since the underlying traffic data is frequently licensed from a third party and its quality varies by geography.

Address and geocoding quality is the third, and the least glamorous. An address that geocodes to a street centroid rather than a building, or to the wrong side of a divided road, produces a stop in the wrong place and a driver who wastes minutes finding it. In operations serving new developments, rural addresses, or apartment complexes, geocoding failure rates are a real and measurable cost. Ask a vendor how the product handles geocoding failures and whether corrections persist, since a correction that must be repeated every time the address recurs is not a correction.

Constraint modeling is the fourth. Real operations carry constraints that are obvious to a dispatcher and invisible to a model: vehicles that cannot access certain streets, drivers qualified for particular equipment or licensed for specific goods, customers who will only accept delivery from a known driver, and legal limits on driving and working hours. A solver that cannot express a constraint will produce routes that violate it, and dispatchers will then override the system manually, which is how organizations end up with an expensive optimizer and a manual planning process running alongside it.

What actually drives last mile cost?

Drop density dominates. The cost of a delivery is largely the cost of the driver's time and the vehicle's time, and both are consumed by travel between stops rather than by the delivery itself. An operation making twenty stops per mile and one making two stops per mile have different economics regardless of software, which is why urban and rural delivery are effectively different businesses and why comparing a cost per stop across them is meaningless. The most powerful lever available to most operations is therefore not routing efficiency but demand consolidation: delivering to the same area on the same day rather than spreading deliveries across the week.

The failed first delivery attempt is the second major driver, and its cost compounds because it consumes a stop on one route, generates a second attempt on another, and frequently triggers customer service contact. It is also the driver most amenable to non-routing solutions: accurate notification with a narrow predicted arrival window, safe place instructions, neighbor delivery, and collection point alternatives all reduce failures without touching the optimizer. Figures for the cost of a failed attempt circulate widely and originate with vendors; the concept is sound and the specific numbers should be treated as estimates.

Time window width is the lever most often pulled in the wrong direction. A narrow promised window is a marketing asset and an operational cost: every constraint removes routing freedom, and the effect is not linear, since narrow windows on scattered stops can force a vehicle to cross its own territory repeatedly. Organizations rarely quantify this trade-off, and it is one of the more valuable things a routing system can be used to measure: run the same demand with different window policies and observe the vehicle requirement.

Table 2. The drivers and levers. The first two rows account for most of the achievable improvement in most operations, and neither is primarily a routing algorithm question.

How does the delivery model change what I need?

An own fleet operation needs the full stack: planning, dispatch, driver application, proof of delivery, and the management reporting that connects routes to cost. It also carries the compliance burden directly, including hours of service and electronic logging obligations where they apply, though many local delivery operations fall within short-haul exceptions to those rules. The requirement to check rather than assume matters here, because the exception depends on operating radius and duty time rather than on vehicle type alone.

A contracted carrier model shifts the planning question. If the carrier plans its own routes, you need visibility, proof of delivery, and performance measurement rather than an optimizer. If you plan and the carrier executes, you need the optimizer and a way to transmit plans and receive status. The distinction should be settled before evaluating products, because it changes which half of the category you are buying.

Gig and crowdsourced models change the problem more fundamentally. Capacity is not fixed, so the planning question becomes matching and offer pricing rather than routing a known fleet, and the system needs to handle drivers declining work, arriving late, or not arriving. Service consistency is harder to manage and driver classification questions carry legal exposure that varies by jurisdiction. Products built for a fixed fleet and products built for a flexible pool differ substantially, and one rarely does the other well.

Parcel network delivery requires almost none of this. The carrier performs the routing internally, and the shipper needs rate shopping, label generation, manifesting, and tracking. Many organizations discover during an evaluation that their actual requirement is parcel execution rather than route optimization, which is a much smaller purchase. The fair case for buying more deserves stating: for a buyer coming from spreadsheets and dispatcher intuition, even an unsophisticated commercial optimizer usually delivers large and immediate improvement, and the distinction between optimal and near-optimal is irrelevant to that decision. The mathematics caveat in section 03 matters most when choosing between mature products, and least when replacing chaos.

Frequently asked questions

Is last mile delivery software the same as a TMS?

No. A transportation management system moves freight between facilities, holding rates, selecting carriers and modes, and tendering shipments. Last mile software decides how one vehicle serves a set of stops in a day. They integrate at the delivery depot and are not substitutes.

What does optimal route actually mean?

In mathematics it means no better solution exists. Because the vehicle routing problem is NP-hard, commercial systems cannot certify that at realistic scale, so they produce high-quality heuristic solutions instead. Near-optimal is the accurate description and is entirely sufficient operationally.

Why is the vehicle routing problem considered hard?

Because the number of possible route combinations grows explosively with the number of stops, so the time needed to guarantee the best answer grows faster than any polynomial. Adding time windows, capacities, and traffic-dependent travel times makes it harder still.

What is the difference between static and dynamic routing?

Static routing plans the day in advance from known orders. Dynamic routing re-plans during the day as new orders arrive, stops fail, or conditions change. Dynamic is substantially harder computationally and operationally, and many deployments that describe themselves as dynamic are doing periodic re-optimization rather than continuous.

How much can route optimization save us?

It depends almost entirely on your starting point, which is why published percentages are unreliable. An operation planning by hand can improve substantially; a mature operation with good data will see far less. Estimate it by running your own historical demand through a trial rather than by adopting a vendor figure.

What input data matters most?

Service time estimates, time-dependent travel times, geocoding accuracy, and the ability to express your real constraints. These determine route quality more than the choice of solver does, and they are also the areas where problems are cheapest to find during evaluation and most expensive to find after go-live.

What is drop density and why does it dominate cost?

It is stops per unit of distance. Because most delivery cost is driver and vehicle time consumed traveling between stops, density drives cost more than total mileage. It is also why cost per stop cannot be compared meaningfully between an urban and a rural operation.

Why do narrow delivery windows make routes less efficient?

Each window constrains when a vehicle may arrive, which removes freedom from the sequencing. The effect is not linear: narrow windows across scattered stops can force a vehicle to cross its territory repeatedly. It is worth measuring by running the same demand under different window policies.

How does gig or crowdsourced delivery change the requirement?

Capacity becomes variable, so the core problem shifts from routing a known fleet to matching and pricing offers, and the system must handle declines and no-shows. Driver classification also carries legal exposure that varies by jurisdiction. Products built for fixed fleets rarely handle this well.

Do our delivery drivers need electronic logging devices?

It depends on operating radius, duty time, and vehicle characteristics rather than on the fact of local delivery, and short-haul exceptions apply to many local operations. Check the current federal rules against your specific operation rather than assuming either way.

Method, sources, and where to go deeper

Method

The treatment of routing mathematics in section 03 follows the primary operations research literature, including the foundational formulations and the standard surveys, rather than vendor descriptions of their own algorithms.

Regulatory references follow the federal motor carrier regulator directly, including the exceptions that apply to many local delivery operations.

Vendor and delivery-operator material was consulted only to establish how the market frames cost drivers and is labeled as originating with interested parties.

Supply Chain Research is independent and vendor-neutral. We accept no payment from the vendors or categories covered, and this page names no products.

Caveats

SCR publishes no benchmark for mileage or cost savings from route optimization. Savings depend overwhelmingly on the baseline, and the percentages in circulation are vendor case studies without disclosed method. The most durable published figure is a single large carrier's self-reported result from its own routing program, which is that carrier's outcome rather than an industry benchmark.

The commonly quoted cost of a failed delivery attempt traces to a data quality vendor and is repeated inconsistently across sources. The concept is sound; the specific figure should be treated as an estimate, not a measurement.

The widely cited claim that the last mile represents a majority of shipping cost traces to a consultancy study whose methodology is not disclosed in the sources that repeat it. Attribute it rather than stating it as settled.

Figure 1, Table 1, and Table 2 are structural illustrations and decision aids rather than measured research findings.

Where to go deeper

Readers whose question concerns freight moving between facilities should read the SCR guide to transportation management systems, which covers the category boundary drawn in section 02. The supply chain network design guide covers depot placement and territory structure, which bound what any routing system can achieve. The order management guide covers how a delivery promise is made at the point of order, which determines the time window constraints routing then has to satisfy. Readers building a case should read the SCR software ROI method, since the benefit here must be estimated from your own demand rather than from published percentages.

Sources

Sources

1. Dantzig, G. B. and Ramser, J. H. The truck dispatching problem. Management Science, 1959. Peer reviewed. The founding formulation of the vehicle routing problem.
2. Solomon, M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987. Peer reviewed. The foundational treatment of the time-window variant.
3. Braekers, Ramaekers and Van Nieuwenhuyse. The vehicle routing problem: state of the art classification and review. Peer reviewed survey; covers the variant taxonomy and the complexity result.
4. University of Malaga. Vehicle routing problem academic resource. Academic reference resource on formulations and complexity.
5. Federal Motor Carrier Safety Administration. General information about the electronic logging device rule. Primary regulator source.
6. Federal Motor Carrier Safety Administration. Electronic logging device exemptions and waivers, including the short-haul exception. Primary regulator source; relevant to many local delivery operations.
7. GoBolt. Last mile delivery cost breakdown. Interested source: a delivery services vendor. Cited as an example of how cost figures circulate, not as a benchmark.
8. Locate2u. Discussion of last mile cost and density metrics. Interested source: a routing software vendor.