Solving Transportation Logistics Problems
Using Advanced Evolutionary Optimization
Transportation logistics problems and many analogous problems are usually too complicated and difficult for
standard Linear or Nonlinear Programming techniques to solve adequately. This is because there are so many possible
routes to consider, once we have more than a few waypoints along the route. For any given number of waypoints, n,
along a route,
there are (n-1)! [i.e., n-1 factorial] possible paths. With more than a few waypoints, this can quickly generate an
astronomically huge number of possible paths, as the following shows:
Number of Waypoints [n]
Number of Unique Paths [(n-1)!]
So a route containing 20 waypoints has more than 121.6 quadrillion possible unique paths.
To solve such problems, we turn to evolutionary optimization. [Follow this link for a brief conceptual overview
of evolutionary optimization.]
The Traveling Salesperson Problem*
The classic traveling salesperson problem involves finding the shortest route that will allow the salesperson to
visit each of a given number of cities just once. Here we will present an example involving 15 cities. As the table
above shows, there are more than 87 billion possible unique paths between these 15 cities.
Here is a statement of the problem. First we have a matrix of distances between 15 cities (labeled zero to 14),
resulting in 14 sequential paths (below the matrix) if we simply move from city 0 to 1, etc., and end by going from
city 14 back to city 0. The numbers in green are the variable values that the optimization model will alter to
design the optimum route. When those numbers change, this will also alter the numbers to their left in the next
The simple route taken in the order that the cities are listed in the matrix gives us a total route length of
817 miles. How short a route can we achieve using evolutionary optimization? Here is the solution to the routing
Beginning at city 0, we move next to city 10, then to city 3 and so on, ending by going from city 12 back to
city 0. The total distance traveled is only 291 miles, a 64% savings in total route length.
This was a simple transportation logistics example using a single vehicle and a single route. Next we will
present a more complicated example.
Back to Top
Multi-Vehicle Transportation Logistics**
Here we present a hypothetical example in which a local company in the western suburbs of Boston, MA, needs to
optimize a delivery schedule using four trucks to make deliveries to 20 customers. Although we could include time
windows in our model, with penalties for early and/or late arrivals, for the sake of simplicity we will omit those
Shown below is the setup of the problem, showing the default situation before optimization. The
truck data are in the top portion of the table, where each truck begins its route at depot location TO-1, TO-2,
TO-3 or TO-4, respectively, and ends its route at the same location, designated TT-1, TT-2, TT-3 or TT-4,
respectively. ("TO" stands for "Truck Origin" point; "TT" stands for "Truck Terminal" point). The latitude
and longitude are shown as well, telling us that, in this particular example, all four trucks actually begin and
end their routes at the same depot location (in this case, the retail store).
The bottom half of the table shows similar data for the customer delivery locations, named D-1 through D-20.
Each delivery location name will subsequently be given a corresponding push-pin location on a satellite-photo map
(see below), where push pins are color-coded according to delivery route.
Here is the initial unoptimized solution, giving us a default baseline solution before we apply
the optimization algorithm to solve the problem:
The default starting scenario has three of the trucks making no deliveries, and the fourth truck making
deliveries until it is empty, in the arbitrary order in which the customers are listed to begin with. This would
obviously be a very inefficient delivery plan, but it serves to set up the problem and give us a baseline.
We won't explain every column in the above table here; but the key columns to note above are the "Depart
(Minute)" column (fifth from the right side); the "Cumulative Capacity" column (second from right); and the
"Capacity Short" column (at the far right).
The "Depart (Minute) column tells us at what time, in relative minutes, the truck departed a point along the
route, beginning with a time of zero at the starting depot and ending, in the bottom row for each truck, with
a final count of minutes. The fourth truck was the only one to make deliveries in the
unoptimized scenario, so we need concentrate only on that portion of the table.
For this hypothetical problem, we assume that each truck has a capacity of five units, and that it delivers one
unit of capacity at each delivery point along the route, thus decreasing its capacity by one unit. The
"Capacity Short" column shows us at which stops there was a capacity shortage, i.e., the truck was empty and could
not make any delivery. Since the fourth truck was the only one to make deliveries, it had no shortages for
the first five stops, and then it had shortages at each stop after the first five on its route, resulting in one
unit of shortage at each of the last 15 stops.
The table below summarizes the result of the unoptimized solution:
The theoretical unoptimized total cost would be excessive (about $6,447). In our hypothetical
example, this total cost is based on a travel cost of $1 per minute, plus a penalty of $100 whenever we are short
of capacity to deliver at a delivery point. In this case, our travel costs are about $4,947, and we were short of
delivery capacity at 15 delivery locations, which adds an additional cost of $1,500 (i.e., 15 x $100). (Note: the
penalty amount of $100 used here is arbitrary, and can be adjusted appropriately for a given real-world situation
to accurately reflect the flexibility of resource constraints--and thus the penalty for violating the
Below we see the result after optimizing the solution:
The first truck completed its route in just over five hours; the second truck finished in about four hours and
thirty-six minutes; the third truck took about 10 hours and 22 minutes; and the fourth truck took about four hours
and thirty-nine minutes. So the total number of travel minutes was about 1,958.
Here is the summary of results, showing that our total travel costs are now only about $1,958. We were not short
of capacity at any delivery point, so we had no penalty fees:
Here is a map of the proposed routes for the four trucks:
And here is the map representation in Google Earth, where each different color of push pin represents a delivery
point for a different truck/route:
The latitudes and longitudes for the delivery points can be imported from the optimized solution's
geographic matrix (not shown here) into a GPS device or an online map-directions provider to
generate a vehicle route the driver can easily follow.
In addition to optimizing transportation logistics, there are other problems that may seem different but are
actually just analogs of transportation. For example, we might have an automated drill press or welding machine,
etc., that has to drill many holes or make many welds in an object. Just as with transportation, we could use
optimization to accomplish these tasks, or many others, with the minimum movement necessary. This could save
substantial time and machine wear over the course of a production run.
Back to Top
Return to Optimization Programming main page
* The raw
input data for the Traveling Salesperson Problem example come from TSPLIB (Traveling Salesman Problem Library), a collection
of traveling salesperson problem datasets maintained by Gerhard Reinelt at:
Those data were furnished under the GNU Lesser Public License, the text
of which may be found here:
** The location data for the four-truck delivery
problem were created by a random-number generator. For real-life problems, these data would be entered either
manually or from a GPS or online map source file.