Save this video free

ISE 754 (Fall 2026) 5.3 Vehicle Routing

Michael G. Kay · 12:17 · Watch on YouTube

Part of North Carolina State University ISE 754. See all 22 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

Overview

Michael G. Kay explains how vehicle routing extends earlier routing methods by adding constraints such as vehicle capacity, maximum route cost, time windows, and hours of service. The central technique sets a route's cost to infinity whenever a route-level constraint is violated, allowing methods such as Clarke-Wright savings and minimum insertion to reject infeasible routes; the lecture also distinguishes routes from vehicles and discusses pickup-delivery loads, vehicle assignment, and tactical estimates.

Key takeaways

Chapters

0:00 Infinite Route Costs Enforce Capacity and Other Single-Route Constraints
6:46 Pickup-Delivery Load Mixes Change Which Shipments Can Share a Route
9:47 Time Windows, Vehicle Assignment, and Tactical Route Estimates

Keep these chapters and the full searchable transcript in your own library.

Transcript excerpt

0:00 We will be covering the vehicle routing problem. It is similar to the previous routing problems that we considered before. The only difference is that now the vehicles have different types of limitations or capacity constraints. So as a result of that, to be able to solve a problem, we can end up having to require multiple routes. The key to what is done to enforce these types of constraints is equation one of the lecture. And here what it basically is saying is that the cost of a particular route R is

0:48 whatever the cost would be, which would typically be either distance or travel time, or it could actually be the dollars associated with transporting the product. And that's the cost if the sum of the load, the shipments that are in the load being transported is less than some capacity of the vehicle. In cases where it then exceeds it, we just set the cost equal to infinity. And the reason it works is that things like the minimum insertion procedure or the savings procedure considered in the previous lecture, when we have a cost of infinity, it makes it such that that savings is going to be negative infinity, so

1:34 there's no positive savings. So it would never make sense to actually insert it. Or in terms of minimum cost, having it equal to infinity is never going to be the optimal way to solve things. So as long we basically then just have to encode our capacity constraints by some procedure that when we violate the constraints, we just set the cost of the route to infinity. And then at that point, everything that we've already about in routing carries through to the vehicle routing problem. That is really in essence how we're going to approach these problems.

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Michael G. Kay.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.