Delivery Truck Scheduling

Project date: July 2025

Project link available here (GitHub).

Notes: I made this project during the summer before my sophomore year. In Computational Engineering, one of my majors, we take a scientific computing class taught by the same professor who wrote the textbook below which this project is based out of. I am a very avid textbook reader, and so the fact that this professor wrote four really interesting books on HPC (and free to boot) caught my interest. At the time of writing (halfway through this summer), I’ve read two of the books, including the one below, and plan to read the other two before I take the class in question this fall. To be honest, I would definitely ask for autographs if I had physical copies of the books (and I do own physical copies of a lot of my favorite textbooks, though I do try to restrict them to below $50 most of the time. My favorite so far has been Partial Differential Equations for Scientists and Engineers, which I picked up for $10 (seriously!) and which presents its content in an incredibly intuitive way).

Pointless context aside, I made this project as a way to sharpen my algorithmic design skills, as well as learning how to structure “real” C++ projects past the tiny toy files we made in Intro to Programming. This is probably evident in some of the strange ways I’ve structured some files, but I feel like it definitely accomplished its purpose in that sense.

This project is based on the delivery truck scheduling project from Chapter 52 of Introduction to Scientific Programming in C++17/Fortran2008 by Victor Eijkhout. It constructs a framework for assembling delivery truck routes and then solving the Traveling Salesman Problem (TSP) over them, both with the naive greedy algorithm and with the 2-opt algorithm.

Implementation is done in C++11. Routes may be constructed using the Route class, which contains an ordered sequence of Address objects to deliver to, then various improvements may be made via greedy_route() or opt2_rearrange(). Route preserves the starting and ending locations to simulate depots; the alternative AddressList class may be used to avoid this functionality. All objects support the use of both Euclidean and Manhattan (taxicab) distance.

I may or may not revisit this project in the future; possible next steps for this project include solution of the multiple TSP for multiple delivery trucks, the use of delivery deadlines to create scenarios that evolve over time, implementation of other heuristics such as furthest point insertion or 3-opt tours, or visualization of delivery routes.